Previous Page Next Page Contents

Network::maxFlow -- computes a maximal flow through a network

Introduction

Network::maxFlow(G, q, s) computes a maximal flow through network G from node q to node s.

Call(s)

Network::maxFlow(G, q, s)

Parameters

G - network
q,s - expressions (nodes in G)

Returns

a list, containing a number and a table

Details

Example 1

In the complete network with four vertices and default capacities of 1, the maximum flow from one vertex to another one consists of sending one unit through each of the remaining vertices and one directly, which makes three units altogether.

>> N1 := Network::complete(4):
   Network::maxFlow(N1,1,4)
                                table(
                                  [4, 3] = 0,
                                  [4, 2] = 0,
                                  [4, 1] = 0,
                                  [3, 4] = 1,
                                  [3, 2] = 0,
                             3,   [3, 1] = 0,
                                  [2, 4] = 1,
                                  [2, 3] = 0,
                                  [2, 1] = 0,
                                  [1, 4] = 1,
                                  [1, 3] = 1,
                                  [1, 2] = 1
                                )

Example 2

A more complex example, the following network shows that this function also finds flows through multiple edges, unlike Network::admissibleFlow, which only works on completely described flows.

>> V := [1,2,3,q,s]:
   Edge := [[q,1], [q,2], [1,2], [1,3], [2,3], [3,s]]:
   up := [5, 5, 2, 6, 6, 1]:
   N2 := Network(V, Edge, Capacity=up):
   Network::maxFlow(N2, q, s)
                                table(
                                  [3, s] = 1,
                                  [2, 3] = 1,
                             1,   [1, 3] = 0,
                                  [1, 2] = 0,
                                  [q, 2] = 1,
                                  [q, 1] = 0
                                )

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000