Найдите все пути между двумя вершинами графика
[___] = allpaths( задает дополнительные опции с помощью одних или нескольких аргументов name-value. Можно использовать любую из комбинаций выходного аргумента в предыдущих синтаксисах. Например, можно задать 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 в этих случаях.