max.flow {RBGL} | R Documentation

## Compute max flow for a directed graph

### Description

Compute max flow for a directed graph

### Usage

    edmonds.karp.max.flow(g, source, sink)
    push.relabel.max.flow(g, source, sink)
    kolmogorov.max.flow(g, source, sink)

### Arguments

`g` | an instance of the `graph` class with `edgemode` “directed”
`source` | node name (character) or node number (int) for the source of the flow
`sink` | node name (character) or node number (int) for the sink of the flow

### Details

Given a directed graph G=(V, E) of a single connected component with a vertex `source` and a vertex `sink`. Each arc has a positive real valued capacity, currently it's equivalent to the weight of the arc. The flow of the network is the net flow entering the vertex `sink`. The maximum flow problem is to determine the maximum possible value for the flow to the `sink` and the corresponding flow values for each arc.

See documentation on these algorithms in Boost Graph Library for more details.

### Value

A list of

`maxflow` | the max flow from `source` to `sink`
`edges` | the nodes of the arcs with non-zero capacities
`flows` | the flow values of the arcs with non-zero capacities

### Author(s)

Li Long <li.long@isb-sib.ch>

### References

Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )

The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine; (Addison-Wesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0-201-72914-8

### See Also

`minCut`, `edgeConnectivity`

### Examples

    con <- file(system.file("XML/dijkex.gxl",package="RBGL"), open="r")
    g <- fromGXL(con)
    close(con)

    ans1 <- edmonds.karp.max.flow(g, "B", "D")
    ans2 <- edmonds.karp.max.flow(g, 3, 2)     # 3 and 2 equivalent to "C" and "B"

    ans3 <- push.relabel.max.flow(g, 2, 4)     # 2 and 4 equivalent to "B" and "D"
    ans4 <- push.relabel.max.flow(g, "C", "B")

    # error in the following  now, 14 june 2014
    #ans5 <- kolmogorov.max.flow(g, "B", "D")
    #ans6 <- kolmogorov.max.flow(g, 3, 2)

[Package RBGL version 1.63.1 Index]