allpaths

Найдите все пути между двумя вершинами графика

Описание

пример

paths = allpaths(G,s,t) возвращает все пути в графике G тот запуск в исходном узле s и закончите в целевом узле t. Выход paths массив ячеек где содержимое каждой ячейки paths{k} узлы списков, которые лежат на пути.

пример

[paths,edgepaths] = allpaths(G,s,t) также возвращает ребра на каждом пути от s к t. Выход edgepaths массив ячеек где edgepaths{k} дает ребра вдоль соответствующего пути, paths{k}.

пример

[___] = allpaths(G,s,t,Name,Value) задает дополнительные опции с помощью одного или нескольких аргументов значения имени. Можно использовать любую из комбинаций выходного аргумента в предыдущих синтаксисах. Например, можно задать MaxNumPaths и скаляр, чтобы ограничить количество возвращенных путей.

Примеры

свернуть все

Создайте матрицу смежности для полного графика с четырьмя узлами, и затем создайте неориентированного графа из матрицы смежности. Постройте график.

A = ones(4);
G = graph(A);
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Вычислите все пути в графике, которые начинаются в узле 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));

Figure contains an axes. The axes contains an object of type graphplot.

Вычислите все пути между узлом 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)

Figure contains an axes. The axes contains an object of type graphplot.

Используйте '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]}

Входные параметры

свернуть все

Введите график в виде любого graph или digraph объект. Используйте graph создать неориентированного графа или digraph создать ориентированного графа.

Пример: G = graph(1,2)

Пример: G = digraph([1 2],[2 3])

Входные и выходные идентификаторы узла в виде отдельных аргументов индексов узла или имен узла.

ЗначениеПример
Скалярный индекс узла1
Имя узла вектора символов'A'
Имя узла строкового скаляра"A"

Пример: allpaths(G,2,5) вычисляет все пути между узлом 2 и узлом 5.

Пример: allpaths(G,'node1','node2') вычисляет все пути между именованными узлами node1 и node2.

Аргументы в виде пар имя-значение

Задайте дополнительные разделенные запятой пары Name,Value аргументы. Name имя аргумента и Value соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: allpaths(G,s,t,'MaxNumPaths',100) возвращает только первые 100 результатов в лексикографическое упорядоченное расположение путей.

Максимальное количество путей в виде разделенной запятой пары, состоящей из 'MaxNumPaths' и неотрицательный целочисленный скаляр. Эта опция полезна, когда количество путей между двумя узлами становится достаточно большим, чтобы поразить пределы памяти. Можно задать MaxNumPaths ограничить количество путей, возвращенных allpaths так, чтобы результаты соответствовали в доступной памяти.

Пример: allpaths(G,s,t,'MaxNumPaths',100)

Максимальная длина пути в виде разделенной запятой пары, состоящей из 'MaxPathLength' и неотрицательный целочисленный скаляр. Эта опция фильтрует результаты, возвращенные allpaths так, чтобы никакие пути с длиной, больше, чем заданный предел, не были возвращены. Длина пути измеряется количеством ребер в нем, игнорируя вес ребра.

Чтобы найти пути с областью значений длин, задайте оба 'MaxPathLength' и 'MinPathLength'. Чтобы найти пути с точной заданной длиной, задайте то же значение для обоих 'MaxPathLength' и 'MinPathLength'.

Пример: allpaths(G,s,t,'MaxPathLength',4) возвращает пути, которые имеют длину, меньше чем или равную 4.

Пример: allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5) возвращает пути, которые имеют длину 3, 4, или 5.

Минимальная длина пути в виде разделенной запятой пары, состоящей из 'MinPathLength' и неотрицательный целочисленный скаляр. Эта опция фильтрует результаты, возвращенные allpaths так, чтобы никакие пути с длиной, меньшей, чем заданный предел, не были возвращены. Длина пути измеряется количеством ребер в нем, игнорируя вес ребра.

Чтобы найти пути с областью значений длин, задайте оба 'MaxPathLength' и 'MinPathLength'. Чтобы найти пути с точной заданной длиной, задайте то же значение для обоих 'MaxPathLength' и 'MinPathLength'.

Пример: allpaths(G,s,t,'MinPathLength',2) возвращает пути, которые имеют длину, больше, чем или равный 2.

Пример: allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5) возвращает пути, которые имеют длину 3, 4, или 5.

Выходные аргументы

свернуть все

Пути между заданными узлами, возвращенными как массив ячеек. Каждый элемент paths{k} содержит узлы, которые простираются вдоль одного из путей между заданными входными и выходными узлами. Пути возвращены в лексикографическом порядке. Если входные и выходные узлы s и t задайте тот же узел, затем условно allpaths возвращает один путь, содержащий тот узел. Если узел t недостижимо от узла s, затем paths isempty.

Тип данных записей в paths зависит от пути s и t заданы:

  • Если s и t заданы как числовые индексы узла, затем каждый элемент paths{k} числовой вектор из индексов узла.

  • Если s и t заданы как имена узла строки, затем каждый элемент paths{k} массив строк имен узла.

  • Если s и t заданы как имена узла вектора символов, затем каждый элемент paths{k} массив ячеек имен узла вектора символов.

Ребра вдоль каждого пути, возвращенного как массив ячеек. Каждый элемент edgepaths{k} содержит индексы ребра для ребер, которые простираются вдоль соответствующего пути, paths{k}. Если узел t недостижимо от узла s, затем edgepaths isempty.

Советы

  • Количество путей в графике зависит в большой степени от структуры графика. Для некоторых структур графика количество путей может вырасти экспоненциально с количеством узлов. Например, полный график с 12 узлами, данными G = graph(ones(12)) содержит почти 10 миллионов путей между любыми двумя из его узлов. Используйте MaxNumPaths, MaxPathLength, и MinPathLength пары "имя-значение", чтобы управлять выходом allpaths в этих случаях.

Смотрите также

| | |

Введенный в R2021a
Для просмотра документации необходимо авторизоваться на сайте