conncomp (biograph)

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

Синтаксис

[S, C] = conncomp(BGObj)
[S, C] = conncomp(BGObj, ...'Directed', DirectedValue, ...)
[S, C] = conncomp(BGObj, ...'Weak', WeakValue, ...)

Аргументы

BGObj Биообъект диаграмм, созданный biograph Конструктор Object.
DirectedValueСвойство, которое указывает, направлен ли график или неориентированный. Введите false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true.

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

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

Описание

Совет

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

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

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

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

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

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

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

Примечание

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

Примечание

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

Ссылки

[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). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

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