igraph (version 0.6-1)

graph.maxflow: Maximum flow in a network

Description

In a graph where each edge has a given flow capacity the maximal flow between two vertices is calculated.

Usage

graph.maxflow(graph, source, target, capacity=NULL)
graph.mincut(graph, source=NULL, target=NULL, capacity=NULL,
       value.only = TRUE)

Arguments

graph

The input graph.

source

The id of the source vertex.

target

The id of the target vertex (sometimes also called sink).

capacity

Vector giving the capacity of the edges. If this is NULL (the default) then the capacity edge attribute is used.

value.only

Logical scalar, if TRUE only the minumum cut value is returned, if FALSE the edges in the cut and a the two (or more) partitions are also returned.

Value

• For graph.maxflow a named list with components:
• value
  A numeric scalar, the value of the maximum flow.
• flow
  A numeric vector, the flow itself, one entry for each edge. For undirected graphs this entry is bit trickier, since for these the flow direction is not predetermined by the edge direction. For these graphs the elements of the this vector can be negative, this means that the flow goes from the bigger vertex id to the smaller one. Positive values mean that the flow goes from the smaller vertex id to the bigger one.
• cut
  A numeric vector of edge ids, the minimum cut corresponding to the maximum flow.
• partition1
  A numeric vector of vertex ids, the vertices in the first partition of the minimum cut corresponding to the maximum flow.
• partition2
  A numeric vector of vertex ids, the vertices in the second partition of the minimum cut corresponding to the maximum flow.
• For graph.mincut a numeric constant, the value of the minimum cut, except if value.only=FALSE. In this case a named list with components:
• value
  Numeric scalar, the cut value.
• cut
  Numeric vector, the edges in the cut.
• partition1
  The vertices in the first partition after the cut edges are removed. Note that these vertices might be actually in different components (after the cut edges are removed), as the graph may fall apart into more than two components.
• partition2
  The vertices in the second partition after the cut edges are removed. Note that these vertices might be actually in different components (after the cut edges are removed), as the graph may fall apart into more than two components.

concept

• Maximum flow
• Minimum cut

Details

graph.maxflow calculates the maximum flow between two vertices in a weighted (ie. valued) graph. A flow from source to target is an assignment of non-negative real numbers to the edges of the graph, satisfying two properties: (1) for each edge the flow (ie. the assigned number) is not more than the capacity of the edge (the capacity parameter or edge attribute), (2) for every vertex, except the source and the target the incoming flow is the same as the outgoing flow. The value of the flow is the incoming flow of the target vertex. The maximum flow is the flow of maximum value.

graph.mincut calculates the minimum st-cut between two vertices in a graph (if the source and target arguments are given) or the minimum cut of the graph (if both source and target are NULL).

The minimum st-cut between source and target is the minimum total weight of edges needed to remove to eliminate all paths from source to target.

The minimum cut of a graph is the minimum total weight of the edges needed to remove to separate the graph into (at least) two components. (Which is to make the graph not strongly connected in the directed case.) The maximum flow between two vertices in a graph is the same as the minimum st-cut, so graph.maxflow and graph.mincut essentially calculate the same quantity, the only difference is that graph.mincut can be invoked without giving the source and target arguments and then minimum of all possible minimum cuts is calculated.

For undirected graphs the Stoer-Wagner algorithm (see reference below) is used to calculate the minimum cut.

References

A. V. Goldberg and R. E. Tarjan: A New Approach to the Maximum Flow Problem Journal of the ACM 35:921-940, 1988. M. Stoer and F. Wagner: A simple min-cut algorithm, Journal of the ACM, 44 585-591, 1997.

See Also

shortest.paths, edge.connectivity, vertex.connectivity

Examples

E <- rbind( c(1,3,3), c(3,4,1), c(4,2,2), c(1,5,1), c(5,6,2), c(6,2,10))
colnames(E) <- c("from", "to", "capacity")
g1 <- graph.data.frame(as.data.frame(E))
graph.maxflow(g1, source=V(g1)["1"], target=V(g1)["2"])

g <- graph.ring(100)
graph.mincut(g, capacity=rep(1,vcount(g)))
graph.mincut(g, value.only=FALSE, capacity=rep(1,vcount(g)))

g2 <- graph( c(1,2,2,3,3,4, 1,6,6,5,5,4, 4,1) )
E(g2)$capacity <- c(3,1,2, 10,1,3, 2)
graph.mincut(g2, value.only=FALSE)