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