Exponenta Banner

graphconncomp

Найдите строго или слабо соединенные компоненты в графике

Синтаксис

[S, C] = graphconncomp(G)
[S, C] = graphconncomp(G, ...'Directed', DirectedValue, ...)
[S, C] = graphconncomp(G, ...'Weak', WeakValue, ...)

Аргументы

G N на n разреженная матрица, которая представляет график. Ненулевые записи в матричном G указывают на присутствие ребра.
DirectedValueСвойство, которое указывает, направлен ли график или неориентированный. Введите false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true.

Основанный на DFS алгоритм вычисляет связанные компоненты. Временной сложностью является O(N+E), где N и E являются количеством узлов и ребер соответственно.

WeakValueСвойство, которое указывает, найти ли слабо соединенные компоненты или строго соединенные компоненты. Слабо связанный компонент является максимальной группой узлов, которые взаимно достижимы путем нарушения направлений ребра. Установите WeakValue на true находить слабо соединенные компоненты. Значением по умолчанию является false, который находит строго соединенные компоненты. Состояние этого параметра не имеет никакого эффекта на неориентированных графов, потому что слабо и строго связанные компоненты то же самое в неориентированных графах. Временной сложностью является O(N+E), где N и E являются количеством узлов и ребер соответственно.

Описание

Совет

Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.

[S, C] = graphconncomp(G) находит строго связанные компоненты графика представленными матричным G с помощью алгоритма Тарьяна. Строго связанный компонент является максимальной группой узлов, которые взаимно достижимы, не нарушая направления ребра. Вход G является N на n разреженной матрицей, которая представляет график. Ненулевые записи в матричном G указывают на присутствие ребра.

Количество найденных компонентов возвращено в S, и C является указанием вектора, которому компоненту принадлежит каждый узел.

Алгоритм Тарьяна имеет временную сложность O(N+E), где N и E являются количеством узлов и ребер соответственно.

[S, C] = graphconncomp(G, ...'PropertyName', PropertyValue, ...)  вызывает graphconncomp с дополнительными свойствами, которые используют имя свойства / пары значения свойства. Можно задать одно или несколько свойств в любом порядке. Каждый PropertyName должен быть заключен в одинарные кавычки и нечувствительный к регистру. Это имя свойства / пары значения свойства следующие:

[S, C] = graphconncomp(G, ...'Directed', DirectedValue, ...) указывает, направлен ли график или неориентированный. Установите directedValue на false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true. Основанный на DFS алгоритм вычисляет связанные компоненты. Временной сложностью является O(N+E), где N и E являются количеством узлов и ребер соответственно.

[S, C] = graphconncomp(G, ...'Weak', WeakValue, ...) указывает, найти ли слабо соединенные компоненты или строго соединенные компоненты. Слабо связанный компонент является максимальной группой узлов, которые взаимно достижимы путем нарушения направлений ребра. Установите WeakValue на true находить слабо соединенные компоненты. Значением по умолчанию является false, который находит строго соединенные компоненты. Состояние этого параметра не имеет никакого эффекта на неориентированных графов, потому что слабо и строго связанные компоненты то же самое в неориентированных графах. Временной сложностью является O(N+E), где N и E являются количеством узлов и ребер соответственно.

Примечание

По определению один узел может быть строго связанным компонентом.

Примечание

Направленный граф без петель (DAG) не может иметь никаких строго связанных компонентов, больше, чем один.

Примеры

  1. Создайте и просмотрите ориентированного графа с 10 узлами и 17 ребрами.

    DG = sparse([1 1 1 2 2 3 3 4 5 6 7 7 8 9 9  9 9], ...
           [2 6 8 3 1 4 2 5 4 7 6 4 9 8 10 5 3],true,10,10)

DG =

   (2,1)        1
   (1,2)        1
   (3,2)        1
   (2,3)        1
   (9,3)        1
   (3,4)        1
   (5,4)        1
   (7,4)        1
   (4,5)        1
   (9,5)        1
   (1,6)        1
   (7,6)        1
   (6,7)        1
   (1,8)        1
   (9,8)        1
   (8,9)        1
   (9,10)       1

h = view(biograph(DG));

  2. Найдите количество строго связанных компонентов в ориентированном графе и определите, которому компоненту принадлежит каждый из этих 10 узлов.

    [S,C] = graphconncomp(DG)

S =

     4


C =

     4     4     4     1     1     2     2     4     4     3

  3. Окрасьте узлы для каждого компонента с различным цветом.

    colors = jet(S);
for i = 1:numel(h.nodes)
  h.Nodes(i).Color = colors(C(i),:);
end

Ссылки

[1] Тарьян, R.E., (1972). Поиск в глубину и линейные алгоритмы графика. SIAM Journal при Вычислении 1 (2), 146–160.

[2] Sedgewick, R., (2002). Алгоритмы на C++, алгоритмы графика части 5 (Аддисон-Уэсли).

[3] Siek, J.G., Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

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

| | | | | | | | | |

Документация Bioinformatics Toolbox
Поддержка