maxflow (биограф)

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

Синтаксис

[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-by-N. Он должен иметь одну запись для каждого ненулевого значения (края) в матрице смежности N-на-N. Порядок пользовательских мощностей в векторе должен соответствовать порядку ненулевых значений в матрице смежности N-на-N, когда она проходит по столбцам. По умолчанию `maxflow` получает информацию о емкости из ненулевых записей в матрице смежности N-на-N.
`MethodValue`	Символьный вектор или строка, указывающая алгоритм, используемый для поиска минимального покрывающего дерева (MST). Возможны следующие варианты: `'Edmonds'` - использует алгоритм Эдмондса и Карпа, реализация которого основана на вариации, называемой алгоритмом маркировки. Сложность времени `O(NE^2)`, где `N` и `E` - количество узлов и рёбер соответственно. `'Goldberg'` - Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует общий метод, известный как prelow-push. Сложность времени `O(N^2sqrt(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' - Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует общий метод, известный как prelow-push. Сложность времени O(N^2*sqrt(E)), где N и E - количество узлов и рёбер соответственно.

Ссылки

[1] Эдмондс, Дж. и Карп, Р.М. (1972). Теоретические улучшения алгоритмической эффективности для проблем сетевого потока. Журнал ACM 19, 248-264.

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

[3] Сиек, Дж. Г., Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).

См. также

Темы

объект-биограф

Представлен в R2006b

Документация