Найдите все пути между двумя узлами графика
[___] = 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 в этих случаях.