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