maxflow (biograph)

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

Синтаксис

[MaxFlow, FlowMatrix, Cut] = maxflow(BGObj, SNode, TNode)
[...] = maxflow(BGObj, SNode, TNode, ...'Capacity', CapacityValue, ...)
[...] = maxflow(BGObj, SNode, TNode, ...'Method', MethodValue, ...)

Аргументы

BGObj Биообъект диаграмм, созданный biograph Конструктор Object.
SNodeУзел в ориентированном графе, представленном N на n матрицей смежности, извлеченной из биообъекта диаграмм, BGObj.
TNodeУзел в ориентированном графе, представленном N на n матрицей смежности, извлеченной из биообъекта диаграмм, BGObj.
CapacityValueВектор-столбец, который задает пользовательские мощности к ребрам в N на n матрице смежности. Это должно иметь одну запись для каждого ненулевого значения (ребро) в N на n матрице смежности. Порядок пользовательских мощностей в векторе должен совпадать с порядком ненулевых значений в N на n матрице смежности, когда это пересечено по столбцам. По умолчанию, maxflow получает полную информацию от ненулевых записей в N на n матрице смежности.
MethodValueВектор символов или строка, которая задает алгоритм, раньше находили минимальное дерево охвата (MST). Выбор:
  • 'Edmonds' — Использует алгоритм Эдмондса и Карпа, реализация которого основана на изменении, названном алгоритмом маркировки. Временной сложностью является O(N*E^2), где N и E количество узлов и ребер соответственно.

  • 'Goldberg' — Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует общий метод, известный как нажатие перед потоком. Временной сложностью является O(N^2*sqrt(E)), где N и E количество узлов и ребер соответственно.

Описание

Совет

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

[MaxFlow, FlowMatrix, Cut] = maxflow(BGObj, SNode, TNode) вычисляет максимальный поток ориентированного графа, представленного N на n матрицей смежности, извлеченной из биообъекта диаграмм, BGObj, от узла SNode к узлу TNode. Ненулевые записи в матрице определяют способность ребер. Выведите MaxFlow максимальный поток и FlowMatrix разреженная матрица со всеми значениями потока для каждого ребра. FlowMatrixXY) поток от узла X к узлу Y. Выведите Cut логический вектор-строка, указывающий на узлы, соединенные с SNode после вычисления минимального сокращения между SNode и TNode. Если несколько решений минимальной проблемы сокращения существуют, то Cut матрица.

Совет

Алгоритм, который определяет Cut, все минимальные сокращения, имеет временную сложность O (2^N), где N является количеством узлов. Если эта информация не нужна, используйте maxflow метод без третьего выхода.

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

[...] = maxflow(BGObj, SNode, TNode, ...'Capacity', CapacityValue, ...) позволяет вам задать пользовательские мощности к ребрам. CapacityValue вектор-столбец, имеющий одну запись для каждого ненулевого значения (ребро) в N на n матрице смежности. Порядок пользовательских мощностей в векторе должен совпадать с порядком ненулевых значений в матрице, когда это пересечено по столбцам. По умолчанию, graphmaxflow получает полную информацию от ненулевых записей в матрице.

[...] = maxflow(BGObj, SNode, TNode, ...'Method', MethodValue, ...) позволяет вам указать, что алгоритм раньше находил минимальное дерево охвата (MST). Выбор:

  • 'Edmonds' — Использует алгоритм Эдмондса и Карпа, реализация которого основана на изменении, названном алгоритмом маркировки. Временной сложностью является O(N*E^2), где N и E количество узлов и ребер соответственно.

  • 'Goldberg' — Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует общий метод, известный как нажатие перед потоком. Временной сложностью является O(N^2*sqrt(E)), где N и E количество узлов и ребер соответственно.

Ссылки

[1] Эдмондс, J. и Карп, R.M. (1972). Теоретические улучшения алгоритмического КПД для сетевых проблем потока. Журнал ACM 19, 248-264.

[2] Голдберг, A.V. (1985). Новый Алгоритм Потока Max. Технический отчет MIT MIT/LCS/TM-291, Лаборатория для Информатики, MIT.

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

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