allpaths
Найдите все пути между двумя узлами графика
Синтаксис
Описание
[___] = allpaths( задает дополнительные опции, используя один или несколько аргументов имя-значение. Можно использовать любой выходной аргумент, комбинации в предыдущих синтаксисах. Для примера можно задать G,s,t,Name,Value)MaxNumPaths и скаляром, чтобы ограничить количество возвращенных путей.
Примеры
Все пути в неориентированном графе
Создайте матрицу смежности для полного графика с четырьмя узлами, а затем создайте неориентированный граф из матрицы смежности. Постройте график.
A = ones(4); G = graph(A); plot(G)
Вычислите все пути в графике, которые начинаются в узле 1 и заканчиваются в узле 3.
paths = allpaths(G,1,3)
paths=5×1 cell array
{[ 1 2 3]}
{[1 2 4 3]}
{[ 1 3]}
{[1 4 2 3]}
{[ 1 4 3]}
Ребра вдоль путей
Второй выходной аргумент allpaths возвращает ребра, расположенные вдоль каждого пути. Это особенно полезно для мультиграфиков, где индекс края требуется для однозначной идентификации ребер на пути.
Создайте ориентированный мультиграфик с восемью узлами и 18 ребрами. Задайте имена для узлов. Постройте график с маркированными узлами и ребрами.
s = [1 1 2 2 3 3 2 2 4 6 8 6 6 7 3 3 5 3];
t = [2 3 1 3 2 1 4 4 6 2 6 7 8 8 5 5 7 7];
names = {'A','B','C','D','E','F','G','H'};
G = digraph(s,t,[],names);
p = plot(G,'EdgeLabel',1:numedges(G));
Вычислите все пути между узлом A и узлом H. Задайте два выходных аргументов, чтобы также вернуть индексы кромок для ребер вдоль каждого пути.
[paths,edgepaths] = allpaths(G,'A','H');
Просмотрите узлы и ребра вдоль первого пути.
paths{1}ans = 1x6 cell
{'A'} {'B'} {'C'} {'E'} {'G'} {'H'}
edgepaths{1}ans = 1×5
1 4 9 13 17
Выделите узлы и ребра вдоль первого пути.
highlight(p,'Edges',edgepaths{1},'EdgeColor','r','LineWidth',1.5,'NodeColor','r','MarkerSize',6)
Предельное количество возвращенных путей
Используйте 'MaxNumPaths', 'MaxPathLength', и 'MinPathLength' опции ограничения количества путей, возвращаемых allpaths.
Создайте матрицу смежности для полного графика с 20 узлами. Создайте неориентированный граф из матрицы смежности, опуская самоциклы.
A = ones(20);
G = graph(A,'omitselfloops');Поскольку все узлы в графике связаны со всеми другими узлами, в графике существует большое количество путей между любыми двумя узлами (больше 1.7e16). Поэтому невозможно вычислить все пути между двумя узлами, поскольку результаты не помещаются в памяти. Вместо этого вычислите первые 10 путей от узла 2 до узла 5.
paths1 = allpaths(G,2,5,'MaxNumPaths',10)paths1=10×1 cell array
{[ 2 1 3 4 5]}
{[ 2 1 3 4 6 5]}
{[ 2 1 3 4 6 7 5]}
{[ 2 1 3 4 6 7 8 5]}
{[ 2 1 3 4 6 7 8 9 5]}
{[ 2 1 3 4 6 7 8 9 10 5]}
{[ 2 1 3 4 6 7 8 9 10 11 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 13 5]}
{[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}
Теперь вычислите первые 10 путей между узлом 2 и узлом 5, которые имеют длину пути, меньшую или равную 2.
paths2 = allpaths(G,2,5,'MaxNumPaths',10,'MaxPathLength',2)
paths2=10×1 cell array
{[ 2 1 5]}
{[ 2 3 5]}
{[ 2 4 5]}
{[ 2 5]}
{[ 2 6 5]}
{[ 2 7 5]}
{[ 2 8 5]}
{[ 2 9 5]}
{[2 10 5]}
{[2 11 5]}
Наконец, вычислите первые 10 путей между узлом 2 и узлом 5, которые имеют длину пути, большую или равную 3.
paths3 = allpaths(G,2,5,'MaxNumPaths',10,'MinPathLength',3)
paths3=10×1 cell array
{[ 2 1 3 4 5]}
{[ 2 1 3 4 6 5]}
{[ 2 1 3 4 6 7 5]}
{[ 2 1 3 4 6 7 8 5]}
{[ 2 1 3 4 6 7 8 9 5]}
{[ 2 1 3 4 6 7 8 9 10 5]}
{[ 2 1 3 4 6 7 8 9 10 11 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 13 5]}
{[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}
Входные параметры
Выходные аргументы
Совет
Количество путей в графике в большой степени зависит от структуры графика. Для некоторых графовых структур количество путей может расти экспоненциально с числом узлов. Для примера - полный график с 12 узлами, заданная
G = graph(ones(12))содержит почти 10 миллионов путей между любыми двумя узлами. ИспользуйтеMaxNumPaths,MaxPathLength, иMinPathLengthПары "имя-значение" для управления выходаallpathsв этих случаях.