toposort

Топологический порядок ориентированного ациклического графика

Свернуть все на странице

Синтаксис

n = toposort(G)
n = toposort(G,'Order',algorithm)
[n,H] = toposort(___)

Описание

пример

n = toposort(G) возвращает топологический порядок узлов в G таким образом i < j для каждого ребра (n(i),n(j)) в G. Ориентированный график G не может иметь никаких циклов.

пример

n = toposort(G,'Order',algorithm) задает алгоритм упорядоченного расположения. Для примера, toposort(G,'Order','stable') использует стабильный алгоритм упорядоченного расположения, основанный на лексикографическом порядке узлов.

пример

[n,H] = toposort(___) дополнительно возвращает ориентированный график H узлы которых находятся в заданном топологическом порядке. Можно использовать любой из комбинаций входных аргументов в предыдущих синтаксисах.

Примеры

свернуть все

Открыть Live Script

Создайте и постройте график, который представляет прогрессию курсов математики университетского уровня. Ребро между двумя курсами означает требование к курсу.

A = [0 1 1 0 0 0 0
     0 0 0 1 0 0 0
     0 1 0 1 0 0 1
     0 0 0 0 1 1 0
     0 0 0 0 0 0 0
     0 0 0 0 1 0 0
     0 0 0 0 1 0 0];
names = {'Calculus I','Linear Algebra','Calculus II', ...
    'Multivariate Calculus','Topology', ...
    'Differential Equations','Real Analysis'};
G = digraph(A,names);
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Найдите топологическую сортировку курсов, чтобы определить, в каком порядке они должны быть завершены.

N = toposort(G)
N = 1×7

     1     3     7     2     4     6     5


G.Nodes.Name(N,:)
ans = 7x1 cell
    {'Calculus I'            }
    {'Calculus II'           }
    {'Real Analysis'         }
    {'Linear Algebra'        }
    {'Multivariate Calculus' }
    {'Differential Equations'}
    {'Topology'              }
Открыть Live Script

Создайте ориентированный граф с помощью логической матрицы смежности, а затем постройте график.

rng default;
A = tril(sprand(10, 10, 0.3), -1)~=0;
G = digraph(A);
[~,G] = toposort(G);
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Найдите топологическую сортировку узлов графика. Хотя G уже находится в топологическом порядке, (1 2 3 4 5 6 7 8 9 10), toposort переупорядочивает узлы.

toposort(G)
ans = 1×10

     2     1     4    10     9     8     5     7     3     6

Задайте Order как 'stable' использовать стабильный алгоритм упорядоченного расположения, чтобы сортировка упорядочивала сначала узлы с меньшими индексами. Устойчивая сортировка не переставляет G если он уже находится в топологическом порядке.

toposort(G,'Order','stable')
ans = 1×10

     1     2     3     4     5     6     7     8     9    10

Входные параметры

свернуть все

Входной график, заданный как digraph объект. G должен быть ориентированным ациклическим графиком. Использовать isdag чтобы подтвердить, что G не содержит циклов.

Использовать digraph для создания ориентированного графа.

Пример: G = digraph([1 2],[2 3])

Алгоритм заказа, заданный как 'fast' или 'stable':

'fast' (по умолчанию)

Основанный на поиске глубины-первый. Узел добавляется в начало списка после рассмотрения всех его потомков.

Если G уже находится в топологическом порядке, этот метод все еще может переупорядочить узлы.

'stable'

На основе лексикографического порядка. n(1) - узел с наименьшим индексом, n(2) следующая наименьшая заданная n(1)и так далее.

Если G находится в топологическом порядке H неизменен и n является 1:numnodes(G).

Пример: [n,H] = toposort(G,'Order','stable')

Выходные аргументы

свернуть все

Индексы узлов, возвращенные как вектор-строка.

Топологически отсортированный графиков, возвращенный как digraph объект. H - тот же график, что и G, но узлы переупорядочены согласно n.

Подробнее о

свернуть все

Топологический порядок

Топологическое упорядоченное расположение ориентированного графа является упорядоченным расположением узлов в графике таким, что каждый узел предстает перед его преемниками (потомками).

Рассмотрим ориентированный граф, узлы которого представляют задачи и ребер которого представляют зависимости, что определенные задачи должны быть выполнены раньше других. Для такого графика топологическая сортировка узлов графика создает допустимую последовательность, в которой можно было бы выполнить задачи.

См. также

| |

Введенный в R2015b

Документация MATLAB

Поддержка

Для просмотра документации необходимо авторизоваться на сайте