graph.maxflow             package:igraph             R Documentation

_M_a_x_i_m_u_m _f_l_o_w _i_n _a _n_e_t_w_o_r_k

_D_e_s_c_r_i_p_t_i_o_n:

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

_U_s_a_g_e:

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

_A_r_g_u_m_e_n_t_s:

   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. 

_D_e_t_a_i_l_s:

     '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.

_V_a_l_u_e:

     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.

_A_u_t_h_o_r(_s):

     Gabor Csardi csardi@rmki.kfki.hu

_R_e_f_e_r_e_n_c_e_s:

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

_S_e_e _A_l_s_o:

     'shortest.paths', 'edge.connectivity', 'vertex.connectivity'

_E_x_a_m_p_l_e_s:

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

