graph.maxflow {igraph} R Documentation

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. This currently only works for undirected graphs.

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.

Starting from version 0.5 igraph can return the edges in the minimum cut for undirected graphs.

Value

A numeric constant, the maximum flow, or the minimum cut, except if `value.only=FALSE` for `graph.mincut`. 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.

normal-bracket56bracket-normal

Author(s)

Gabor Csardi csardi@rmki.kfki.hu

References

A. V. Goldberg and R. E. Tarjan: ``A New Approach to the Maximum Flow Problem'' Journal of the ACM 35:921-940, 1988.

`shortest.paths`, `edge.connectivity`, `vertex.connectivity`
```g <- graph.ring(100)