maxflow (biograph)

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

Синтаксис

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

Аргументы

BGObj Объект биографика, созданный biograph (конструктор объектов).
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' - Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует родовой метод, известный как preflow-push. Сложность во времени O(N^2*sqrt(E)), где N и E являются числом узлов и кромками соответственно.

Описание

Совет

Для получения вводной информации о функциях теории графиков, см. «Функции теории графиков».

[MaxFlow, FlowMatrix, Cut] = maxflow(BGObj, SNode, TNode) вычисляет максимальное течение ориентированного графа, представленного матрицей смежности N на N, извлеченной из объекта биографика, BGObj, из узла SNode к узлу TNode. Ненулевые значения в матрице определяют емкость ребер. Выходные MaxFlow является максимальным потоком и FlowMatrix является разреженной матрицей со всеми значениями потока для каждого ребра. FlowMatrix(X, Y) - поток из узла 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' - Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует родовой метод, известный как preflow-push. Сложность во времени O(N^2*sqrt(E)), где N и E являются числом узлов и кромками соответственно.

Ссылки

[1] Edmonds, J. and Karp, R.M. (1972). Теоретические улучшения алгоритмической эффективности для задач сетевого потока. Журнал ACM 19, 248-264.

[2] Голдберг, А. В. (1985). Новый алгоритм максимального расхода. MIT Technical Report MIT/LCS/TM-291, Лаборатория компьютерных наук, MIT.

[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).

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