igraph Reference Manual

For using the igraph C library

Chapter 20. Maximum Flows, Minimum Cuts and related measures

1. Maximum Flows

1.1. igraph_maxflow — Maximum network flow between a pair of vertices

int igraph_maxflow(const igraph_t *graph, igraph_real_t *value,
		   igraph_vector_t *flow, igraph_vector_t *cut,
		   igraph_vector_t *partition, igraph_vector_t *partition2,
		   igraph_integer_t source, igraph_integer_t target,
		   const igraph_vector_t *capacity,
		   igraph_maxflow_stats_t *stats);

This function implements the Goldberg-Tarjan algorithm for calculating value of the maximum flow in a directed or undirected graph. The algorithm was given in Andrew V. Goldberg, Robert E. Tarjan: A New Approach to the Maximum-Flow Problem, Journal of the ACM, 35(4), 921-940, 1988.

The input of the function is a graph, a vector of real numbers giving the capacity of the edges and two vertices of the graph, the source and the target. A flow is a function assigning positive real numbers to the edges and satisfying two requirements: (1) the flow value is less than the capacity of the edge and (2) at each vertex except the source and the target, the incoming flow (ie. the sum of the flow on the incoming edges) is the same as the outgoing flow (ie. the sum of the flow on the outgoing edges). The value of the flow is the incoming flow at the target vertex. The maximum flow is the flow with the maximum value.

Arguments: 

graph:

The input graph, either directed or undirected.

value:

Pointer to a real number, the value of the maximum will be placed here, unless it is a null pointer.

flow:

If not a null pointer, then it must be a pointer to an initialized vector. The vector will be resized, and the flow on each edge will be placed in it, in the order of the edge ids. For undirected graphs this argument is bit trickier, since for these the flow direction is not predetermined by the edge direction. For these graphs the elements of the flow 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 null pointer or a pointer to an initialized vector. If not a null pointer, then the minimum cut corresponding to the maximum flow is stored here, i.e. all edge ids that are part of the minimum cut are stored in the vector.

partition:

A null pointer or a pointer to an initialized vector. If not a null pointer, then the first partition of the minimum cut that corresponds to the maximum flow will be placed here. The first partition is always the one that contains the source vertex.

partition2:

A null pointer or a pointer to an initialized vector. If not a null pointer, then the second partition of the minimum cut that corresponds to the maximum flow will be placed here. The second partition is always the one that contains the target vertex.

source:

The id of the source vertex.

target:

The id of the target vertex.

capacity:

Vector containing the capacity of the edges. If NULL, then every edge is considered to have capacity 1.0.

stats:

Counts of the number of different operations preformed by the algorithm are stored here.

Returns: 

Error code.

Time complexity: O(|V|^3). In practice it is much faster, but i cannot prove a better lower bound for the data structure i've used. In fact, this implementation runs much faster than the hi_pr implementation discussed in B. V. Cherkassky and A. V. Goldberg: On implementing the push-relabel method for the maximum flow problem, (Algorithmica, 19:390--410, 1997) on all the graph classes i've tried.

See also: 

Example 20.1.  File examples/simple/flow.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

#include <sys/time.h>
#include <sys/resource.h>

float timer ()
{
  struct rusage r;

  getrusage(0, &r);
  return (float)(r.ru_utime.tv_sec+r.ru_utime.tv_usec/(float)1000000);
}

int main() {
  
  igraph_t g;
  igraph_real_t flow;
  igraph_vector_t capacity;
  igraph_integer_t source, target;
  FILE *infile;
  float t;
  igraph_maxflow_stats_t stats;

  igraph_vector_init(&capacity, 0);

  /***************/
  infile=fopen("ak-4102.max", "r");
  igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity,
			   IGRAPH_DIRECTED);
  fclose(infile);

  t=timer();
  igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats);
  t=timer()-t;
/*   printf("4102: %g (time %.10f)\n", flow, t); */
  if (flow != 8207) {
    return 1;
  }
  igraph_destroy(&g);  
  /***************/

/*   /\***************\/ */
/*   infile=fopen("ak-8198.max", "r"); */
/*   igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, */
/* 			   IGRAPH_DIRECTED); */
/*   fclose(infile); */

/*   t=timer(); */
/*   igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */
/*   t=timer()-t; */
/*   printf("8198: %g (time %.10f)\n", flow, t); */
/*   igraph_destroy(&g); */
/*   /\***************\/ */

/*   /\***************\/ */
/*   infile=fopen("ak-16390.max", "r"); */
/*   igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, */
/* 			   IGRAPH_DIRECTED); */
/*   fclose(infile); */

/*   t=timer(); */
/*   igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */
/*   t=timer()-t; */
/*   printf("16390: %g (time %.10f)\n", flow, t); */
/*   igraph_destroy(&g); */
/*   /\***************\/ */

/*   /\***************\/ */
/*   infile=fopen("ak-32774.max", "r"); */
/*   igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, */
/* 			   IGRAPH_DIRECTED); */
/*   fclose(infile); */

/*   t=timer(); */
/*   igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */
/*   t=timer()-t; */
/*   printf("32774: %g (time %.10f)\n", flow, t); */
/*   igraph_destroy(&g); */
/*   /\***************\/ */

/*   /\***************\/ */
/*   infile=fopen("ak-65542.max", "r"); */
/*   igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, */
/* 			   IGRAPH_DIRECTED); */
/*   fclose(infile); */

/*   t=timer(); */
/*   igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */
/*   t=timer()-t; */
/*   printf("65542: %g (time %.10f)\n", flow, t); */
/*   igraph_destroy(&g); */
/*   /\***************\/ */

  igraph_vector_destroy(&capacity);
  
  return 0;
}


Example 20.2.  File examples/simple/flow2.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int check_flow(int errorinc,
	       const igraph_t *graph, igraph_real_t flow_value, 
	       const igraph_vector_t *flow, const igraph_vector_t *cut, 
	       const igraph_vector_t *partition,
	       const igraph_vector_t *partition2, 
	       long int source, long int target, 
	       const igraph_vector_t *capacity, 
	       igraph_bool_t print) {

  long int i, n=igraph_vcount(graph), m=igraph_ecount(graph);
  long int nc=igraph_vector_size(cut);
  igraph_vector_t inedges, outedges;
  igraph_bool_t directed=igraph_is_directed(graph);
  igraph_real_t cutsize;
  igraph_t graph_copy;
  igraph_matrix_t sp;

  if (print) {
    printf("flow value: %g\n", (double) flow_value);
    printf("flow: "); igraph_vector_print(flow);
    printf("first partition:  "); igraph_vector_print(partition);
    printf("second partition: "); igraph_vector_print(partition2);
    printf("edges in the cut: ");
    for (i=0; i<nc; i++) {
      long int edge=VECTOR(*cut)[i];
      long int from=IGRAPH_FROM(graph, edge);
      long int to  =IGRAPH_TO  (graph, edge);
      if (!directed && from > to) {
	igraph_integer_t tmp=from;
	from=to;
	to=tmp;
      }
      printf("%li-%li (%g), ", from, to, VECTOR(*capacity)[edge]);
    }
    printf("\n");
  }
  fflush(stdout);
        
  /* Always less than the capacity */
  for (i=0; i<m; i++) {
    if (VECTOR(*flow)[i] > VECTOR(*capacity)[i]) {
      return errorinc+3;
    }
  }
  
  /* What comes in goes out, but only in directed graphs, 
     there is no in and out in undirected ones...
   */
  if (igraph_is_directed(graph)) {
    igraph_vector_init(&inedges, 0);
    igraph_vector_init(&outedges, 0);

    for (i=0; i<n; i++) {
      long int n1, n2, j;
      igraph_real_t in_flow=0.0, out_flow=0.0;
      igraph_incident(graph, &inedges,  i, IGRAPH_IN);
      igraph_incident(graph, &outedges, i, IGRAPH_OUT);
      n1=igraph_vector_size(&inedges);
      n2=igraph_vector_size(&outedges);
      for (j=0; j<n1; j++) {
	long int e=VECTOR(inedges)[j];
	in_flow += VECTOR(*flow)[e];
      }
      for (j=0; j<n2; j++) {
	long int e=VECTOR(outedges)[j];
	out_flow += VECTOR(*flow)[e];
      }
      if (i == source) {
	if (in_flow > 0) { return errorinc+4; }
	if (out_flow != flow_value) { return errorinc+5; }
      } else if (i == target) {
	if (out_flow > 0) { return errorinc+6; }
	if (in_flow != flow_value) { return errorinc+7; }
	
      } else {
	if (in_flow != out_flow) { return errorinc+8; }
      }
    }
    
    igraph_vector_destroy(&inedges);
    igraph_vector_destroy(&outedges);
  }

  /* Check the minimum cut size*/
  for (i=0, cutsize=0.0; i<nc; i++) {
    long int edge=VECTOR(*cut)[i];
    cutsize += VECTOR(*capacity)[edge];
  }
  if (fabs(cutsize-flow_value) > 1e-14) { return errorinc+9; }

  /* Check that the cut indeed cuts */
  igraph_copy(&graph_copy, graph);
  igraph_delete_edges(&graph_copy, igraph_ess_vector(cut));
  igraph_matrix_init(&sp, 1, 1);
  igraph_shortest_paths(&graph_copy, &sp, /*from=*/ igraph_vss_1(source),
			/*to=*/ igraph_vss_1(target), IGRAPH_OUT);
  if (MATRIX(sp, 0, 0) != IGRAPH_INFINITY) { return errorinc+10; }
  igraph_matrix_destroy(&sp);
  igraph_destroy(&graph_copy);

  return 0;
}

int main() {
  
  igraph_t g;
  igraph_real_t flow_value;
  igraph_vector_t cut;
  igraph_vector_t capacity;
  igraph_vector_t partition, partition2;
  igraph_vector_t flow;
  long int i, n;
  igraph_integer_t source, target;
  FILE *infile;
  igraph_real_t flow_value2=0.0;
  int check;
  igraph_maxflow_stats_t stats;
  
  igraph_vector_init(&capacity, 0);

  /***************/
  infile=fopen("ak-4102.max", "r");
  igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity,
  			   IGRAPH_DIRECTED);
  fclose(infile);

  igraph_vector_init(&cut, 0);
  igraph_vector_init(&partition, 0);
  igraph_vector_init(&partition2, 0);
  igraph_vector_init(&flow, 0);

  igraph_maxflow(&g, &flow_value, &flow, &cut, &partition,
		 &partition2, source, target, &capacity, &stats);

  if (flow_value != 8207) {
    return 1;
  }

  n=igraph_vector_size(&cut);
  for (i=0; i<n; i++) {
    long int e=VECTOR(cut)[i];
    flow_value2 += VECTOR(capacity)[e];
  }
  if (flow_value != flow_value2) {
    return 2;
  }

  /* Check the flow */
  if ( (check=check_flow(0, &g, flow_value, &flow, &cut, &partition,
			 &partition2, source, target, &capacity, 
			 /*print=*/ 0))) {
    return check;
  }

  igraph_destroy(&g);
  igraph_vector_destroy(&capacity);
  igraph_vector_destroy(&cut);
  igraph_vector_destroy(&partition);
  igraph_vector_destroy(&partition2);
  igraph_vector_destroy(&flow);

  /* ------------------------------------- */

  igraph_small(&g, 4, IGRAPH_UNDIRECTED,
	       0,1,0,2,1,2,1,3,2,3, -1);
  igraph_vector_init_int_end(&capacity, -1, 4,2,10,2,2, -1);
  igraph_vector_init(&cut, 0);
  igraph_vector_init(&partition, 0);
  igraph_vector_init(&partition2, 0);
  igraph_vector_init(&flow, 0);

  igraph_maxflow(&g, &flow_value, &flow, &cut, &partition, &partition2, 
		 /*source=*/ 0, /*target=*/ 3, &capacity, &stats);

  if ( (check=check_flow(20, &g, flow_value, &flow, &cut, &partition,
			 &partition2, 0, 3, &capacity, 
			 /*print=*/ 1))) {
    return check;
  }

  igraph_vector_destroy(&cut);
  igraph_vector_destroy(&partition2);
  igraph_vector_destroy(&partition);
  igraph_vector_destroy(&capacity);
  igraph_vector_destroy(&flow);
  igraph_destroy(&g);

  /* ------------------------------------- */

  igraph_small(&g, 6, IGRAPH_DIRECTED,
	       0,1,1,2,2,3, 0,5,5,4,4,3, 3,0, -1);
  igraph_vector_init_int_end(&capacity, -1, 3,1,2, 10,1,3, 2, -1);
  igraph_vector_init(&cut, 0);
  igraph_vector_init(&partition, 0);
  igraph_vector_init(&partition2, 0);
  igraph_vector_init(&flow, 0);

  igraph_maxflow(&g, &flow_value, &flow, &cut, &partition, &partition2, 
		 /*source=*/ 0, /*target=*/ 2, &capacity, &stats);

  if ( (check=check_flow(40, &g, flow_value, &flow, &cut, &partition,
			 &partition2, 0, 2, &capacity, 
			 /*print=*/ 1))) {
    return check;
  }

  igraph_vector_destroy(&cut);
  igraph_vector_destroy(&partition2);
  igraph_vector_destroy(&partition);
  igraph_vector_destroy(&capacity);
  igraph_vector_destroy(&flow);
  igraph_destroy(&g);

  return 0;
}


1.2. igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm

int igraph_maxflow_value(const igraph_t *graph, igraph_real_t *value,
			 igraph_integer_t source, igraph_integer_t target,
			 const igraph_vector_t *capacity,
			 igraph_maxflow_stats_t *stats);

This function implements the Goldberg-Tarjan algorithm for calculating value of the maximum flow in a directed or undirected graph. The algorithm was given in Andrew V. Goldberg, Robert E. Tarjan: A New Approach to the Maximum-Flow Problem, Journal of the ACM, 35(4), 921-940, 1988.

The input of the function is a graph, a vector of real numbers giving the capacity of the edges and two vertices of the graph, the source and the target. A flow is a function assigning positive real numbers to the edges and satisfying two requirements: (1) the flow value is less than the capacity of the edge and (2) at each vertex except the source and the target, the incoming flow (ie. the sum of the flow on the incoming edges) is the same as the outgoing flow (ie. the sum of the flow on the outgoing edges). The value of the flow is the incoming flow at the target vertex. The maximum flow is the flow with the maximum value.

According to a theorem by Ford and Fulkerson (L. R. Ford Jr. and D. R. Fulkerson. Maximal flow through a network. Canadian J. Math., 8:399-404, 1956.) the maximum flow between two vertices is the same as the minimum cut between them (also called the minimum s-t cut). So igraph_st_mincut_value() gives the same result in all cases as igraph_maxflow_value().

Note that the value of the maximum flow is the same as the minimum cut in the graph.

Arguments: 

graph:

The input graph, either directed or undirected.

value:

Pointer to a real number, the result will be placed here.

source:

The id of the source vertex.

target:

The id of the target vertex.

capacity:

Vector containing the capacity of the edges. If NULL, then every edge is considered to have capacity 1.0.

stats:

Counts of the number of different operations preformed by the algorithm are stored here.

Returns: 

Error code.

Time complexity: O(|V|^3).

See also: 

igraph_maxflow() to calculate the actual flow. igraph_mincut_value(), igraph_edge_connectivity(), igraph_vertex_connectivity() for properties based on the maximum flow.

1.3. igraph_dominator_tree — Calculates the dominator tree of a flowgraph

int igraph_dominator_tree(const igraph_t *graph,
			  igraph_integer_t root,
			  igraph_vector_t *dom,
			  igraph_t *domtree,
			  igraph_vector_t *leftout,
			  igraph_neimode_t mode);

A flowgraph is a directed graph with a distinguished start (or root) vertex r, such that for any vertex v, there is a path from r to v. A vertex v dominates another vertex w (not equal to v), if every path from r to w contains v. Vertex v is the immediate dominator or w, v=idom(w), if v dominates w and every other dominator of w dominates v. The edges {(idom(w), w)| w is not r} form a directed tree, rooted at r, called the dominator tree of the graph. Vertex v dominates vertex w if and only if v is an ancestor of w in the dominator tree.

This function implements the Lengauer-Tarjan algorithm to construct the dominator tree of a directed graph. For details please see Thomas Lengauer, Robert Endre Tarjan: A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS) I/1, 121--141, 1979.

Arguments: 

graph:

A directed graph. If it is not a flowgraph, and it contains some vertices not reachable from the root vertex, then these vertices will be collected in the leftout vector.

root:

The id of the root (or source) vertex, this will be the root of the tree.

dom:

Pointer to an initialized vector or a null pointer. If not a null pointer, then the immediate dominator of each vertex will be stored here. For vertices that are not reachable from the root, IGRAPH_NAN is stored here. For the root vertex itself, -1 is added.

domtree:

Pointer to an uninitialized igraph_t, or NULL. If not a null pointer, then the dominator tree is returned here. The graph contains the vertices that are unreachable from the root (if any), these will be isolates.

leftout:

Pointer to an initialized vector object, or NULL. If not NULL, then the ids of the vertices that are unreachable from the root vertex (and thus not part of the dominator tree) are stored here.

mode:

Constant, must be IGRAPH_IN or IGRAPH_OUT. If it is IGRAPH_IN, then all directions are considered as opposite to the original one in the input graph.

Returns: 

Error code.

Time complexity: very close to O(|E|+|V|), linear in the number of edges and vertices. More precisely, it is O(|V|+|E|alpha(|E|,|V|)), where alpha(|E|,|V|) is a functional inverse of Ackermann's function.

Example 20.3.  File examples/simple/dominator_tree.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>
#include <stdio.h>

int main() {

  igraph_t g, domtree;
  igraph_vector_t dom, leftout;

  igraph_vector_init(&dom, 0);
  igraph_small(&g, 13, IGRAPH_DIRECTED,
	       0,1, 0,7, 0,10,
	       1,2, 1,5,
	       2,3,
	       3,4,
	       4,3, 4,0,
	       5,3, 5,6,
	       6,3,
	       7,8, 7,10, 7,11,
	       8,9,
	       9,4, 9,8,
	       10,11,
	       11,12,
	       12,9,
	       -1);

  /* Check NULL vector arguments */
  igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ 0,
			/*leftout=*/ 0, /*mode=*/ IGRAPH_OUT);

  /* Proper calculation */
  igraph_dominator_tree(&g, /*root=*/ 0, &dom, /*domtree=*/ 0,
			/*leftout=*/ 0, /*mode=*/ IGRAPH_OUT);
  igraph_vector_print(&dom);

  /* Tree calculation */
  igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ &domtree,
			/*leftout=*/ 0, /*mode=*/ IGRAPH_OUT);
  igraph_write_graph_edgelist(&domtree, stdout);
  
  igraph_vector_destroy(&dom);
  igraph_destroy(&domtree);
  igraph_destroy(&g);

  /* -------------------------------------------------------------------*/
  
  igraph_vector_init(&dom, 0);
  igraph_small(&g, 13, IGRAPH_DIRECTED,
	       1,0, 2,0, 3,0,
	       4,1,
	       1,2, 4,2, 5,2,
	       6,3, 7,3,
	       12,4,
	       8,5, 
	       9,6,
	       9,7, 10,7,
	       5,8, 11,8,
	       11,9,
	       9,10,
	       9,11, 0,11,
	       8,12,
	       -1);

  /* Check NULL vector arguments */
  igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ 0,
			/*leftout=*/ 0, /*mode=*/ IGRAPH_IN);

  /* Proper calculation */
  igraph_dominator_tree(&g, /*root=*/ 0, &dom, /*domtree=*/ 0,
			/*leftout=*/ 0, /*mode=*/ IGRAPH_IN);
  igraph_vector_print(&dom);

  /* Tree calculation */
  igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ &domtree,
			/*leftout=*/ 0, /*mode=*/ IGRAPH_IN);
  igraph_write_graph_edgelist(&domtree, stdout);
  
  igraph_vector_destroy(&dom);
  igraph_destroy(&domtree);
  igraph_destroy(&g);

  /* -------------------------------------------------------------------*/

  igraph_vector_init(&dom, 0);
  igraph_vector_init(&leftout, 0);

  /* Check a graph with more components */
  igraph_small(&g, 20, IGRAPH_DIRECTED,
	       0,1, 0,2, 0,3,
	       1,4,
	       2,1, 2,4, 2,8,
	       3,9, 3,10,
	       4,15,
	       8,11, 
	       9,12,
	       10,12, 10,13,
	       11,8, 11,14,
	       12,14,
	       13,12,
	       14,12, 14,0,
	       15,11,
	       -1);

  igraph_dominator_tree(&g, /*root=*/ 0, &dom, &domtree,
			&leftout, /*mode=*/ IGRAPH_OUT);
  igraph_vector_print(&dom);
  igraph_vector_print(&leftout);
  igraph_write_graph_edgelist(&domtree, stdout);

  igraph_vector_destroy(&dom);
  igraph_vector_destroy(&leftout);
  igraph_destroy(&domtree);
  igraph_destroy(&g);

  /* -------------------------------------------------------------------*/

  igraph_vector_init(&dom, 0);
  igraph_vector_init(&leftout, 0);
  
  igraph_small(&g, 10, IGRAPH_DIRECTED, 
	       0,9,
	       1,0, 1,2,
	       2,3, 2,7,
	       3,1,
	       4,1, 4,3,
	       5,2, 5,3, 5,4, 5,8,
	       6,5, 6,9,
	       8,7,
	       -1);
  
  igraph_dominator_tree(&g, /*root=*/ 9, &dom, &domtree,
			&leftout, /*mode=*/ IGRAPH_IN);
  igraph_vector_print(&dom);
  igraph_vector_print(&leftout);
  igraph_write_graph_edgelist(&domtree, stdout);
   
  igraph_vector_destroy(&dom);
  igraph_vector_destroy(&leftout);
  igraph_destroy(&domtree);
  igraph_destroy(&g);
 
  return 0;
}


1.4. igraph_maxflow_stats_t — A simple data type to return some statistics from the

typedef struct {
  int nopush, norelabel, nogap, nogapnodes, nobfs;

push-relabel maximum flow solver.

Arguments: 

nopush:

The number of push operations performed.

norelabel:

The number of relabel operarions performed.

nogap:

The number of times the gap heuristics was used.

nogapnodes:

The total number of vertices that were omitted form further calculations because of the gap heuristics.

nobfs:

The number of times the reverse BFS was run to assign good values to the height function. This includes an initial run before the whole algorithm, so it is always at least one.

2. Cuts and minimum cuts

2.1. igraph_st_mincut — Minimum cut between a source and a target vertex

int igraph_st_mincut(const igraph_t *graph, igraph_real_t *value,
		     igraph_vector_t *cut, igraph_vector_t *partition,
		     igraph_vector_t *partition2,
		     igraph_integer_t source, igraph_integer_t target,
		     const igraph_vector_t *capacity);

Finds the edge set that has the smallest total capacity among all edge sets that disconnect the source and target vertices.

The calculation is performed using maximum flow techniques, by calling igraph_maxflow().

Arguments: 

graph:

The input graph.

value:

Pointer to a real variable, the value of the cut is stored here.

cut:

Pointer to a real vector, the edge ids that are included in the cut are stored here. This argument is ignored if it is a null pointer.

partition:

Pointer to a real vector, the vertex ids of the vertices in the first partition of the cut are stored here. The first partition is always the one that contains the source vertex. This argument is ignored if it is a null pointer.

partition2:

Pointer to a real vector, the vertex ids of the vertices in the second partition of the cut are stored here. The second partition is always the one that contains the target vertex. This argument is ignored if it is a null pointer.

source:

Integer, the id of the source vertex.

target:

Integer, the id of the target vertex.

capacity:

Vector containing the capacity of the edges. If a null pointer, then every edge is considered to have capacity 1.0.

Returns: 

Error code.

See also: 

Time complexity: see igraph_maxflow().

2.2. igraph_st_mincut_value — The minimum s-t cut in a graph

int igraph_st_mincut_value(const igraph_t *graph, igraph_real_t *value,
			   igraph_integer_t source, igraph_integer_t target,
			   const igraph_vector_t *capacity);

The minimum s-t cut in a weighted (=valued) graph is the total minimum edge weight needed to remove from the graph to eliminate all paths from a given vertex (source) to another vertex (target). Directed paths are considered in directed graphs, and undirected paths in undirected graphs.

The minimum s-t cut between two vertices is known to be same as the maximum flow between these two vertices. So this function calls igraph_maxflow_value() to do the calculation.

Arguments: 

graph:

The input graph.

value:

Pointer to a real variable, the result will be stored here.

source:

The id of the source vertex.

target:

The id of the target vertex.

capacity:

Pointer to the capacity vector, it should contain non-negative numbers and its length should be the same the the number of edges in the graph. It can be a null pointer, then every edge has unit capacity.

Returns: 

Error code.

Time complexity: O(|V|^3), see also the discussion for igraph_maxflow_value(), |V| is the number of vertices.

2.3. igraph_all_st_cuts — List all edge-cuts between two vertices in a directed graph

int igraph_all_st_cuts(const igraph_t *graph,
		       igraph_vector_ptr_t *cuts,
		       igraph_vector_ptr_t *partition1s,
		       igraph_integer_t source,
		       igraph_integer_t target);

This function lists all edge-cuts between a source and a target vertex. Every cut is listed exactly once. The implemented algorithm is described in JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351--372, 1996.

Arguments: 

graph:

The input graph, is must be directed.

cuts:

An initialized pointer vector, the cuts are stored here. It is a list of pointers to igraph_vector_t objects. Each vector will contain the ids of the edges in the cut. This argument is ignored if it is a null pointer. To free all memory allocated for cuts, you need call igraph_vector_destroy() and then igraph_free() on each element, before destroying the pointer vector itself.

partition1s:

An initialized pointer vector, the list of vertex sets, generating the actual edge cuts, are stored here. Each vector contains a set of vertex ids. If X is such a set, then all edges going from X to the complement of X form an (s,t) edge-cut in the graph. This argument is ignored if it is a null pointer. To free all memory allocated for partition1s, you need call igraph_vector_destroy() and then igraph_free() on each element, before destroying the pointer vector itself.

source:

The id of the source vertex.

target:

The id of the target vertex.

Returns: 

Error code.

Time complexity: O(n(|V|+|E|)), where |V| is the number of vertices, |E| is the number of edges, and n is the number of cuts.

Example 20.4.  File examples/simple/igraph_all_st_cuts.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>
#include <igraph_marked_queue.h>
#include <igraph_estack.h>

int igraph_i_all_st_cuts_pivot(const igraph_t *graph,
			       const igraph_marked_queue_t *S,
			       const igraph_estack_t *T,
			       long int source,
			       long int target,
			       long int *v,
			       igraph_vector_t *Isv);

int main() {
  igraph_t g;
  igraph_vector_ptr_t cuts, partition1s;
  long int i, n;

  igraph_marked_queue_t S;
  igraph_estack_t T;
  long int v;
  igraph_vector_t Isv;

  /* ----------------------------------------------------------- */
  /* This is the example from the Provan-Shier paper, 
     for calculating the dominator tree and finding the right pivot 
     element */
  
  igraph_small(&g, 12, IGRAPH_DIRECTED,
  	       /* a->b */ 0,1,
  	       /* b->t */ 1,11,
  	       /* c->b */ 2,1,  /* c->d */ 2,3,
  	       /* d->e */ 3,4,  /* d->i */ 3,8,
  	       /* e->c */ 4,2,
  	       /* f->c */ 5,2,  /* f->e */ 5,4,
  	       /* g->d */ 6,3,  /* g->e */ 6,4,  /* g->f */ 6,5,
  	                        /* g->j */ 6,9,
  	       /* h->g */ 7,6,  /* h->t */ 7,11,
  	       /* i->a */ 8,0,
  	       /* j->i */ 9,8,
  	       /* s->a */ 10,0, /* s->c */ 10,2, /* s->h */ 10,7,
  	       -1);
  
  /* S={s,a} */
  igraph_marked_queue_init(&S, igraph_vcount(&g));
  igraph_marked_queue_start_batch(&S);
  igraph_marked_queue_push(&S, 10);
  igraph_marked_queue_push(&S, 0);
  
  /* T={t} */
  igraph_estack_init(&T, igraph_vcount(&g), 1);
  igraph_estack_push(&T, 11);

  igraph_vector_init(&Isv, 0);
  igraph_i_all_st_cuts_pivot(&g, &S, &T,
  				/*source=*/ 10, /*target=*/ 11,
  				&v, &Isv);

  /* Expected result: v=c, Isv={c,d,e,i} */
  printf("%li; ", v);
  igraph_vector_print(&Isv);
  
  igraph_vector_destroy(&Isv);
  igraph_estack_destroy(&T);
  igraph_marked_queue_destroy(&S);
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 3, IGRAPH_DIRECTED,
  	       0,1, 1,2,
  	       -1);
  
  /* S={}, T={} */
  igraph_marked_queue_init(&S, igraph_vcount(&g));
  igraph_estack_init(&T, igraph_vcount(&g), 3);

  igraph_vector_init(&Isv, 0);
  igraph_i_all_st_cuts_pivot(&g, &S, &T,
  				/*source=*/ 0, /*target=*/ 2,
  				&v, &Isv);
  printf("%li; ", v);
  igraph_vector_print(&Isv);

  igraph_vector_destroy(&Isv);
  igraph_estack_destroy(&T);
  igraph_marked_queue_destroy(&S);
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 3, IGRAPH_DIRECTED,
  	       0,1, 1,2,
  	       -1);
  
  /* S={}, T={0} */
  igraph_marked_queue_init(&S, igraph_vcount(&g));

  igraph_estack_init(&T, igraph_vcount(&g), 3);
  igraph_estack_push(&T, 0);

  igraph_vector_init(&Isv, 0);
  igraph_i_all_st_cuts_pivot(&g, &S, &T,
  				/*source=*/ 0, /*target=*/ 2,
  				&v, &Isv);
  printf("%li; ", v);
  igraph_vector_print(&Isv);

  igraph_vector_destroy(&Isv);
  igraph_estack_destroy(&T);
  igraph_marked_queue_destroy(&S);
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 3, IGRAPH_DIRECTED,
  	       0,1, 1,2,
  	       -1);
  
  /* S={0}, T={} */
  igraph_marked_queue_init(&S, igraph_vcount(&g));
  igraph_marked_queue_push(&S, 0);

  igraph_estack_init(&T, igraph_vcount(&g), 3);

  igraph_vector_init(&Isv, 0);
  igraph_i_all_st_cuts_pivot(&g, &S, &T,
  				/*source=*/ 0, /*target=*/ 2,
  				&v, &Isv);
  printf("%li; ", v);
  igraph_vector_print(&Isv);

  igraph_vector_destroy(&Isv);
  igraph_estack_destroy(&T);
  igraph_marked_queue_destroy(&S);
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 3, IGRAPH_DIRECTED,
  	       0,1, 1,2,
  	       -1);
  
  /* S={0}, T={1} */
  igraph_marked_queue_init(&S, igraph_vcount(&g));
  igraph_marked_queue_push(&S, 0);

  igraph_estack_init(&T, igraph_vcount(&g), 3);
  igraph_estack_push(&T, 1);

  igraph_vector_init(&Isv, 0);
  igraph_i_all_st_cuts_pivot(&g, &S, &T,
  				/*source=*/ 0, /*target=*/ 2,
  				&v, &Isv);
  printf("%li; ", v);
  igraph_vector_print(&Isv);

  igraph_vector_destroy(&Isv);
  igraph_estack_destroy(&T);
  igraph_marked_queue_destroy(&S);
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 3, IGRAPH_DIRECTED,
  	       0,1, 1,2,
  	       -1);
  
  /* S={0,1}, T={} */
  igraph_marked_queue_init(&S, igraph_vcount(&g));
  igraph_marked_queue_push(&S, 0);
  igraph_marked_queue_push(&S, 1);

  igraph_estack_init(&T, igraph_vcount(&g), 3);

  igraph_vector_init(&Isv, 0);
  igraph_i_all_st_cuts_pivot(&g, &S, &T,
  				/*source=*/ 0, /*target=*/ 2,
  				&v, &Isv);
  printf("%li; ", v);
  igraph_vector_print(&Isv);

  igraph_vector_destroy(&Isv);
  igraph_estack_destroy(&T);
  igraph_marked_queue_destroy(&S);
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 3, IGRAPH_DIRECTED,
  	       0,1, 1,2,
  	       -1);

  igraph_vector_ptr_init(&partition1s, 0);
  igraph_all_st_cuts(&g, /*cuts=*/ 0, &partition1s,
		     /*source=*/ 0, /*target=*/ 2);

  n=igraph_vector_ptr_size(&partition1s);
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(partition1s)[i];
    igraph_vector_print(v);
    igraph_vector_destroy(v);
    igraph_free(v);
  }
  igraph_vector_ptr_destroy(&partition1s);
  
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 5, IGRAPH_DIRECTED,
  	       0,1, 1,2, 1,3, 2,4, 3,4,
  	       -1);

  igraph_vector_ptr_init(&partition1s, 0);
  igraph_all_st_cuts(&g, /*cuts=*/ 0, &partition1s,
		     /*source=*/ 0, /*target=*/ 4);

  n=igraph_vector_ptr_size(&partition1s);
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(partition1s)[i];
    igraph_vector_print(v);
    igraph_vector_destroy(v);
    igraph_free(v);
  }
  igraph_vector_ptr_destroy(&partition1s);
  
  igraph_destroy(&g);  

  /* ----------------------------------------------------------- */

  igraph_small(&g, 6, IGRAPH_DIRECTED,
  	       0,1, 1,2, 1,3, 2,4, 3,4, 1,5, 5,4,
  	       -1);

  igraph_vector_ptr_init(&cuts, 0);
  igraph_vector_ptr_init(&partition1s, 0);
  igraph_all_st_cuts(&g, &cuts, &partition1s,
		     /*source=*/ 0, /*target=*/ 4);

  n=igraph_vector_ptr_size(&partition1s);
  printf("Partitions and cuts:\n");
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(partition1s)[i];
    igraph_vector_t *v2=VECTOR(cuts)[i];
    printf("P: ");
    igraph_vector_print(v);
    igraph_vector_destroy(v);
    igraph_free(v);
    printf("C: ");
    igraph_vector_print(v2);
    igraph_vector_destroy(v2);
    igraph_free(v2);
  }
  igraph_vector_ptr_destroy(&partition1s);
  igraph_vector_ptr_destroy(&cuts);
  
  igraph_destroy(&g);  

  /* ----------------------------------------------------------- */
  
  igraph_small(&g, 3, IGRAPH_DIRECTED,
  	       0,2, 1,2,
  	       -1);

  igraph_vector_ptr_init(&cuts, 0);
  igraph_vector_ptr_init(&partition1s, 0);
  igraph_all_st_cuts(&g, &cuts, &partition1s,
		     /*source=*/ 1, /*target=*/ 2);

  n=igraph_vector_ptr_size(&partition1s);
  printf("Partitions and cuts:\n");
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(partition1s)[i];
    igraph_vector_t *v2=VECTOR(cuts)[i];
    printf("P: ");
    igraph_vector_print(v);
    igraph_vector_destroy(v);
    igraph_free(v);
    printf("C: ");
    igraph_vector_print(v2);
    igraph_vector_destroy(v2);
    igraph_free(v2);
  }
  igraph_vector_ptr_destroy(&partition1s);
  igraph_vector_ptr_destroy(&cuts);
  
  igraph_destroy(&g);  

  /* ----------------------------------------------------------- */
  
  igraph_small(&g, 5, IGRAPH_DIRECTED,
	       0,1, 1,2, 2,3, 3,4, 3,1,
	       -1);

  igraph_vector_ptr_init(&cuts, 0);
  igraph_vector_ptr_init(&partition1s, 0);
  igraph_all_st_cuts(&g, &cuts, &partition1s,
		     /*source=*/ 0, /*target=*/ 4);

  n=igraph_vector_ptr_size(&partition1s);
  printf("Partitions and cuts:\n");
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(partition1s)[i];
    igraph_vector_t *v2=VECTOR(cuts)[i];
    printf("P: ");
    igraph_vector_print(v);
    igraph_vector_destroy(v);
    igraph_free(v);
    printf("C: ");
    igraph_vector_print(v2);
    igraph_vector_destroy(v2);
    igraph_free(v2);
  }
  igraph_vector_ptr_destroy(&partition1s);
  igraph_vector_ptr_destroy(&cuts);
  
  igraph_destroy(&g);  

  /* ----------------------------------------------------------- */
  
  igraph_small(&g, 7, IGRAPH_DIRECTED,
	       0,1,0,2, 1,3,2,3,
	       1,4,1,5,1,6, 
	       4,2,5,2,6,2,
	       -1);

  igraph_vector_ptr_init(&cuts, 0);
  igraph_vector_ptr_init(&partition1s, 0);
  igraph_all_st_cuts(&g, &cuts, &partition1s,
		     /*source=*/ 0, /*target=*/ 3);

  n=igraph_vector_ptr_size(&partition1s);
  printf("Partitions and cuts:\n");
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(partition1s)[i];
    igraph_vector_t *v2=VECTOR(cuts)[i];
    printf("P: ");
    igraph_vector_print(v);
    igraph_vector_destroy(v);
    igraph_free(v);
    printf("C: ");
    igraph_vector_print(v2);
    igraph_vector_destroy(v2);
    igraph_free(v2);
  }
  igraph_vector_ptr_destroy(&partition1s);
  igraph_vector_ptr_destroy(&cuts);
  
  igraph_destroy(&g);  

  return 0;
}


2.4. igraph_all_st_mincuts — All minimum s-t cuts of a directed graph

int igraph_all_st_mincuts(const igraph_t *graph, igraph_real_t *value,
			  igraph_vector_ptr_t *cuts,
			  igraph_vector_ptr_t *partition1s,
			  igraph_integer_t source,
			  igraph_integer_t target,
			  const igraph_vector_t *capacity);

This function lists all minimum edge cuts between two vertices, in a directed graph. The implemented algorithm is described in JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351--372, 1996.

Arguments: 

graph:

The input graph, it must be directed.

value:

Pointer to a real number, the value of the minimum cut is stored here, unless it is a null pointer.

cuts:

An initialized pointer vector, the cuts are stored here. It is a list of pointers to igraph_vector_t objects. Each vector will contain the ids of the edges in the cut. This argument is ignored if it is a null pointer. To free all memory allocated for cuts, you need call igraph_vector_destroy() and then igraph_free() on each element, before destroying the pointer vector itself.

partition1s:

An initialized pointer vector, the list of vertex sets, generating the actual edge cuts, are stored here. Each vector contains a set of vertex ids. If X is such a set, then all edges going from X to the complement of X form an (s,t) edge-cut in the graph. This argument is ignored if it is a null pointer.

source:

The id of the source vertex.

target:

The id of the target vertex.

capacity:

Vector of edge capacities. If this is a null pointer, then all edges are assumed to have capacity one.

Returns: 

Error code.

Time complexity: O(n(|V|+|E|))+O(F), where |V| is the number of vertices, |E| is the number of edges, and n is the number of cuts; O(F) is the time complexity of the maximum flow algorithm, see igraph_maxflow().

Example 20.5.  File examples/simple/igraph_all_st_mincuts.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int print_and_destroy(igraph_real_t value, 
		      igraph_vector_ptr_t *partitions, 
		      igraph_vector_ptr_t *cuts) {
  long int i, n=igraph_vector_ptr_size(partitions);
  printf("Value: %g\n", value);
  for (i=0; i<n; i++) {
    igraph_vector_t *vec=VECTOR(*partitions)[i];
    igraph_vector_t *vec2=cuts ? VECTOR(*cuts)[i] : 0;
    printf("Partition: "); igraph_vector_print(vec);
    if (vec2) { printf("Cut: "); igraph_vector_print(vec2); }
    igraph_vector_destroy(vec);
    if (vec2) { igraph_vector_destroy(vec2); }
    igraph_free(vec);
    if (vec2) { igraph_free(vec2); }
  }  
  igraph_vector_ptr_destroy(partitions);
  if (cuts) { igraph_vector_ptr_destroy(cuts); }
  
  return 0;
}

int main() {

  igraph_t g;
  igraph_vector_ptr_t partitions;
  igraph_vector_ptr_t cuts;
  igraph_real_t value;
  
  igraph_small(&g, 5, IGRAPH_DIRECTED,
  	       0,1, 1,2, 2,3, 3,4,
  	       -1);
  
  igraph_vector_ptr_init(&partitions, 0);
  igraph_vector_ptr_init(&cuts, 0);
  igraph_all_st_mincuts(&g, &value, &cuts, &partitions,
  			/*source=*/ 0, /*target=*/ 4,
  			/*capacity=*/ 0);
  
  print_and_destroy(value, &partitions, &cuts);
  igraph_destroy(&g);

  /* ---------------------------------------------------------------- */
  
  igraph_small(&g, 6, IGRAPH_DIRECTED, 0,1, 1,2, 1,3, 2,4, 3,4, 4,5, -1);
  igraph_vector_ptr_init(&partitions, 0);
  igraph_vector_ptr_init(&cuts, 0);
  igraph_all_st_mincuts(&g, &value, &cuts, &partitions,
  			/*source=*/ 0, /*target=*/ 5, /*capacity=*/ 0);

  print_and_destroy(value, &partitions, &cuts);
  igraph_destroy(&g);

  /* ---------------------------------------------------------------- */
  
  igraph_small(&g, 6, IGRAPH_DIRECTED, 0,1, 1,2, 1,3, 2,4, 3,4, 4,5, -1);
  igraph_vector_ptr_init(&partitions, 0);
  igraph_vector_ptr_init(&cuts, 0);
  igraph_all_st_mincuts(&g, &value, &cuts, &partitions,
  			/*source=*/ 0, /*target=*/ 4, /*capacity=*/ 0);

  print_and_destroy(value, &partitions, &cuts);
  igraph_destroy(&g);

  /* ---------------------------------------------------------------- */
  
  igraph_small(&g, 9, IGRAPH_DIRECTED, 0,1, 0,2, 1,3, 2,3,
	       1,4,4,2, 1,5,5,2, 1,6,6,2, 1,7,7,2, 1,8,8,2,
	       -1);
  igraph_vector_ptr_init(&partitions, 0);
  igraph_vector_ptr_init(&cuts, 0);
  igraph_all_st_mincuts(&g, &value, &cuts, &partitions,
  			/*source=*/ 0, /*target=*/ 3, /*capacity=*/ 0);

  print_and_destroy(value, &partitions, &cuts);
  igraph_destroy(&g);

 
  return 0;
}


2.5. igraph_mincut — Calculates the minimum cut in a graph.

int igraph_mincut(const igraph_t *graph,
		  igraph_real_t *value,
		  igraph_vector_t *partition,
		  igraph_vector_t *partition2,
		  igraph_vector_t *cut,
		  const igraph_vector_t *capacity);

This function calculates the minimum cut in a graph. The minimum cut is the minimum set of edges which needs to be removed to disconnect the graph. The minimum is calculated using the weights (capacity) of the edges, so the cut with the minimum total capacity is calculated.

For directed graphs an implementation based on calculating 2|V|-2 maximum flows is used. For undirected graphs we use the Stoer-Wagner algorithm, as described in M. Stoer and F. Wagner: A simple min-cut algorithm, Journal of the ACM, 44 585-591, 1997.

The first implementation of the actual cut calculation for undirected graphs was made by Gregory Benison, thanks Greg.

Arguments: 

graph:

The input graph.

value:

Pointer to a float, the value of the cut will be stored here.

partition:

Pointer to an initialized vector, the ids of the vertices in the first partition after separating the graph will be stored here. The vector will be resized as needed. This argument is ignored if it is a NULL pointer.

partition2:

Pointer to an initialized vector the ids of the vertices in the second partition will be stored here. The vector will be resized as needed. This argument is ignored if it is a NULL pointer.

cut:

Pointer to an initialized vector, the ids of the edges in the cut will be stored here. This argument is ignored if it is a NULL pointer.

capacity:

A numeric vector giving the capacities of the edges. If a null pointer then all edges have unit capacity.

Returns: 

Error code.

See also: 

igraph_mincut_value(), a simpler interface for calculating the value of the cut only.

Time complexity: for directed graphs it is O(|V|^4), but see the remarks at igraph_maxflow(). For undirected graphs it is O(|V||E|+|V|^2 log|V|). |V| and |E| are the number of vertices and edges respectively.

Example 20.6.  File examples/simple/igraph_mincut.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2007-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int print_mincut(const igraph_t *graph, igraph_real_t value, 
		 const igraph_vector_t *partition, 
		 const igraph_vector_t *partition2, 
		 const igraph_vector_t *cut, 
		 const igraph_vector_t *capacity) {
  
  long int i, nc=igraph_vector_size(cut);
  igraph_bool_t directed=igraph_is_directed(graph);

  printf("mincut value: %g\n", (double) value);
  printf("first partition:  ");  igraph_vector_print(partition);
  printf("second partition: ");  igraph_vector_print(partition2);
  printf("edges in the cut: ");
  for (i=0; i<nc; i++) {
    long int edge=VECTOR(*cut)[i];
    long int from=IGRAPH_FROM(graph, edge);
    long int to  =IGRAPH_TO  (graph, edge);
    if (!directed && from > to) {
      igraph_integer_t tmp=from;
      from=to;
      to=tmp;
    }
    printf("%li-%li (%g), ", from, to, VECTOR(*capacity)[edge]);
  }
  printf("\n");
  
  return 0;
}

int main() {
  
  igraph_t g;
  igraph_vector_t weights, partition, partition2, cut;
  igraph_real_t value;

  igraph_vector_init(&partition, 0);
  igraph_vector_init(&partition2, 0);
  igraph_vector_init(&cut, 0);

  /* -------------------------------------------- */
  
  igraph_small(&g, 0, IGRAPH_UNDIRECTED, 
	       0,1, 0,4, 1,2, 1,4, 1,5, 2,3, 2,6, 3,6, 3,7, 4,5, 5,6, 6,7,
	       -1);
  igraph_vector_init_int_end(&weights, -1, 2,3,3,2,2, 4,2,2,2,3, 1,3, -1);
  
  igraph_mincut(&g, &value, &partition, &partition2, &cut, &weights);
  print_mincut(&g, value, &partition, &partition2, &cut, &weights);
  
  igraph_vector_destroy(&weights);
  igraph_destroy(&g);

  /* -------------------------------------------- */

  igraph_small(&g, 6, IGRAPH_DIRECTED,
	       0,1,1,2,2,3, 0,5,5,4,4,3, 3,0, -1);
  igraph_vector_init_int_end(&weights, -1, 3,1,2, 10,1,3, 2, -1);

  igraph_mincut(&g, &value, &partition, &partition2, &cut, &weights);
  print_mincut(&g, value, &partition, &partition2, &cut, &weights);

  igraph_vector_destroy(&weights);
  igraph_destroy(&g);

  /* -------------------------------------------- */

  igraph_small(&g, 5, IGRAPH_DIRECTED,
	       4,3, 3,2, 2,1, 1,0, 
	       -1);
  igraph_vector_init_int_end(&weights, -1, 1,1,1,1, -1);
  igraph_mincut(&g, &value, &partition, &partition2, &cut, &weights);
  print_mincut(&g, value, &partition, &partition2, &cut, &weights);

  igraph_vector_destroy(&weights);
  igraph_destroy(&g);

  /* -------------------------------------------- */

  igraph_vector_destroy(&cut);
  igraph_vector_destroy(&partition2);
  igraph_vector_destroy(&partition);
 
  return 0;
}


2.6. igraph_mincut_value — The minimum edge cut in a graph

int igraph_mincut_value(const igraph_t *graph, igraph_real_t *res, 
			const igraph_vector_t *capacity);

The minimum edge cut in a graph is the total minimum weight of the edges needed to remove from the graph to make the graph not strongly connected. (If the original graph is not strongly connected then this is zero.) Note that in undirected graphs strong connectedness is the same as weak connectedness.

The minimum cut can be calculated with maximum flow techniques, although the current implementation does this only for directed graphs and a separate non-flow based implementation is used for undirected graphs. See Mechthild Stoer and Frank Wagner: A simple min-cut algorithm, Journal of the ACM 44 585--591, 1997. For directed graphs the maximum flow is calculated between a fixed vertex and all the other vertices in the graph and this is done in both directions. Then the minimum is taken to get the minimum cut.

Arguments: 

graph:

The input graph.

res:

Pointer to a real variable, the result will be stored here.

capacity:

Pointer to the capacity vector, it should contain the same number of non-negative numbers as the number of edges in the graph. If a null pointer then all edges will have unit capacity.

Returns: 

Error code.

See also: 

Time complexity: O(log(|V|)*|V|^2) for undirected graphs and O(|V|^4) for directed graphs, but see also the discussion at the documentation of igraph_maxflow_value().

3. Connectivity

3.1. igraph_st_edge_connectivity — Edge connectivity of a pair of vertices

int igraph_st_edge_connectivity(const igraph_t *graph, igraph_integer_t *res,
				igraph_integer_t source, 
				igraph_integer_t target);

The edge connectivity of two vertices (source and target) in a graph is the minimum number of edges that have to be deleted from the graph to eliminate all paths from source to target.

This function uses the maximum flow algorithm to calculate the edge connectivity.

Arguments: 

graph:

The input graph, it has to be directed.

res:

Pointer to an integer, the result will be stored here.

source:

The id of the source vertex.

target:

The id of the target vertex.

Returns: 

Error code.

Time complexity: O(|V|^3).

See also: 

3.2. igraph_edge_connectivity — The minimum edge connectivity in a graph.

int igraph_edge_connectivity(const igraph_t *graph, igraph_integer_t *res,
			     igraph_bool_t checks);

This is the minimum of the edge connectivity over all pairs of vertices in the graph.

The edge connectivity of a graph is the same as group adhesion as defined in Douglas R. White and Frank Harary: The cohesiveness of blocks in social networks: node connectivity and conditional density, Sociological Methodology 31:305--359, 2001.

Arguments: 

graph:

The input graph.

res:

Pointer to an integer, the result will be stored here.

checks:

Logical constant. Whether to check that the graph is connected and also the degree of the vertices. If the graph is not (strongly) connected then the connectivity is obviously zero. Otherwise if the minimum degree is one then the edge connectivity is also one. It is a good idea to perform these checks, as they can be done quickly compared to the connectivity calculation itself. They were suggested by Peter McMahan, thanks Peter.

Returns: 

Error code.

Time complexity: O(log(|V|)*|V|^2) for undirected graphs and O(|V|^4) for directed graphs, but see also the discussion at the documentation of igraph_maxflow_value().

See also: 

3.3. igraph_st_vertex_connectivity — The vertex connectivity of a pair of vertices

int igraph_st_vertex_connectivity(const igraph_t *graph, 
				  igraph_integer_t *res,
				  igraph_integer_t source,
				  igraph_integer_t target,
				  igraph_vconn_nei_t neighbors);

The vertex connectivity of two vertices (source and target) is the minimum number of vertices that have to be deleted to eliminate all paths from source to target. Directed paths are considered in directed graphs.

The vertex connectivity of a pair is the same as the number of different (ie. node-independent) paths from source to target.

The current implementation uses maximum flow calculations to obtain the result.

Arguments: 

graph:

The input graph.

res:

Pointer to an integer, the result will be stored here.

source:

The id of the source vertex.

target:

The id of the target vertex.

neighbors:

A constant giving what to do if the two vertices are connected. Possible values: IGRAPH_VCONN_NEI_ERROR, stop with an error message, IGRAPH_VCONN_NEGATIVE, return -1. IGRAPH_VCONN_NUMBER_OF_NODES, return the number of nodes. IGRAPH_VCONN_IGNORE, ignore the fact that the two vertices are connected and calculated the number of vertices needed to eliminate all paths except for the trivial (direct) paths between source and vertex. TOOD: what about neighbors?

Returns: 

Error code.

Time complexity: O(|V|^3), but see the discussion at igraph_maxflow_value().

See also: 

3.4. igraph_vertex_connectivity — The vertex connectivity of a graph

int igraph_vertex_connectivity(const igraph_t *graph, igraph_integer_t *res, 
			       igraph_bool_t checks);

The vertex connectivity of a graph is the minimum vertex connectivity along each pairs of vertices in the graph.

The vertex connectivity of a graph is the same as group cohesion as defined in Douglas R. White and Frank Harary: The cohesiveness of blocks in social networks: node connectivity and conditional density, Sociological Methodology 31:305--359, 2001.

Arguments: 

graph:

The input graph.

res:

Pointer to an integer, the result will be stored here.

checks:

Logical constant. Whether to check that the graph is connected and also the degree of the vertices. If the graph is not (strongly) connected then the connectivity is obviously zero. Otherwise if the minimum degree is one then the vertex connectivity is also one. It is a good idea to perform these checks, as they can be done quickly compared to the connectivity calculation itself. They were suggested by Peter McMahan, thanks Peter.

Returns: 

Error code.

Time complexity: O(|V|^5).

See also: 

4. Edge- and Vertex-Disjoint Paths

4.1. igraph_edge_disjoint_paths — The maximum number of edge-disjoint paths between two vertices.

int igraph_edge_disjoint_paths(const igraph_t *graph, igraph_integer_t *res,
			       igraph_integer_t source, 
			       igraph_integer_t target);

A set of paths between two vertices is called edge-disjoint if they do not share any edges. The maximum number of edge-disjoint paths are calculated by this function using maximum flow techniques. Directed paths are considered in directed graphs.

Note that the number of disjoint paths is the same as the edge connectivity of the two vertices using uniform edge weights.

Arguments: 

graph:

The input graph, can be directed or undirected.

res:

Pointer to an integer variable, the result will be stored here.

source:

The id of the source vertex.

target:

The id of the target vertex.

Returns: 

Error code.

Time complexity: O(|V|^3), but see the discussion at igraph_maxflow_value().

See also: 

4.2. igraph_vertex_disjoint_paths — Maximum number of vertex-disjoint paths between two vertices.

int igraph_vertex_disjoint_paths(const igraph_t *graph, igraph_integer_t *res,
				 igraph_integer_t source,
				 igraph_integer_t target);

A set of paths between two vertices is called vertex-disjoint if they share no vertices. The calculation is performed by using maximum flow techniques.

Note that the number of vertex-disjoint paths is the same as the vertex connectivity of the two vertices in most cases (if the two vertices are not connected by an edge).

Arguments: 

graph:

The input graph.

res:

Pointer to an integer variable, the result will be stored here.

source:

The id of the source vertex.

target:

The id of the target vertex.

Returns: 

Error code.

Time complexity: O(|V|^3).

See also: 

5. Graph Adhesion and Cohesion

5.1. igraph_adhesion — Graph adhesion, this is (almost) the same as edge connectivity.

int igraph_adhesion(const igraph_t *graph, igraph_integer_t *res,
		    igraph_bool_t checks);

This quantity is defined by White and Harary in The cohesiveness of blocks in social networks: node connectivity and conditional density, (Sociological Methodology 31:305--359, 2001) and basically it is the edge connectivity of the graph with uniform edge weights.

Arguments: 

graph:

The input graph, either directed or undirected.

res:

Pointer to an integer, the result will be stored here.

checks:

Logical constant. Whether to check that the graph is connected and also the degree of the vertices. If the graph is not (strongly) connected then the adhesion is obviously zero. Otherwise if the minimum degree is one then the adhesion is also one. It is a good idea to perform these checks, as they can be done quickly compared to the edge connectivity calculation itself. They were suggested by Peter McMahan, thanks Peter. *

Returns: 

Error code.

Time complexity: O(log(|V|)*|V|^2) for undirected graphs and O(|V|^4) for directed graphs, but see also the discussion at the documentation of igraph_maxflow_value().

See also: 

5.2. igraph_cohesion — Graph cohesion, this is the same as vertex connectivity.

int igraph_cohesion(const igraph_t *graph, igraph_integer_t *res,
		    igraph_bool_t checks);

This quantity was defined by White and Harary in The cohesiveness of blocks in social networks: node connectivity and conditional density, (Sociological Methodology 31:305--359, 2001) and it is the same as the vertex connectivity of a graph.

Arguments: 

graph:

The input graph.

res:

Pointer to an integer variable, the result will be stored here.

checks:

Logical constant. Whether to check that the graph is connected and also the degree of the vertices. If the graph is not (strongly) connected then the cohesion is obviously zero. Otherwise if the minimum degree is one then the cohesion is also one. It is a good idea to perform these checks, as they can be done quickly compared to the vertex connectivity calculation itself. They were suggested by Peter McMahan, thanks Peter.

Returns: 

Error code.

Time complexity: O(|V|^4), |V| is the number of vertices. In practice it is more like O(|V|^2), see igraph_maxflow_value().

See also: 

6. Cohesive Blocks

6.1. igraph_cohesive_blocks — Identifies the hierarchical cohesive block structure of a graph

int igraph_cohesive_blocks(const igraph_t *graph,
			   igraph_vector_ptr_t *blocks,
			   igraph_vector_t *cohesion,
			   igraph_vector_t *parent,
			   igraph_t *block_tree);

Cohesive blocking is a method of determining hierarchical subsets of graph vertices based on their structural cohesion (or vertex connectivity). For a given graph G, a subset of its vertices S is said to be maximally k-cohesive if there is no superset of S with vertex connectivity greater than or equal to k. Cohesive blocking is a process through which, given a k-cohesive set of vertices, maximally l-cohesive subsets are recursively identified with l>k. Thus a hiearchy of vertex subsets is found, whith the entire graph G at its root. See the following reference for details: J. Moody and D. R. White. Structural cohesion and embeddedness: A hierarchical concept of social groups. American Sociological Review, 68(1):103--127, Feb 2003.

This function implements cohesive blocking and calculates the complete cohesive block hierarchy of a graph.

Arguments: 

graph:

The input graph. It must be undirected and simple. See igraph_is_simple().

blocks:

If not a null pointer, then it must be an initialized vector of pointers and the cohesive blocks are stored here. Each block is encoded with a numeric vector, that contains the vertex ids of the block.

cohesion:

If not a null pointer, then it must be an initialized vector and the cohesion of the blocks is stored here, in the same order as the blocks in the blocks pointer vector.

parent:

If not a null pointer, then it must be an initialized vector and the block hierarchy is stored here. For each block, the id (i.e. the position in the blocks pointer vector) of its parent block is stored. For the top block in the hierarchy, -1 is stored.

block_tree:

If not a null pointer, then it must be a pointer to an uninitialized graph, and the block hierarchy is stored here as an igraph graph. The vertex ids correspond to the order of the blocks in the blocks vector.

Returns: 

Error code.

Time complexity: TODO.

Example 20.7.  File examples/simple/cohesive_blocks.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int doit(igraph_t *g) {

  igraph_vector_ptr_t blocks;
  igraph_vector_t cohesion;
  igraph_vector_t parent;
  igraph_t block_tree;
  long int i;

  igraph_vector_ptr_init(&blocks, 0);
  igraph_vector_init(&cohesion, 0);
  igraph_vector_init(&parent, 0);

  igraph_cohesive_blocks(g, &blocks, &cohesion, &parent, 
			 &block_tree);
  
  printf("Blocks:\n");
  for (i=0; i<igraph_vector_ptr_size(&blocks); i++) {
    igraph_vector_t *sg=VECTOR(blocks)[i];
    printf("  "); igraph_vector_print(sg);
    igraph_vector_destroy(sg);
    igraph_free(sg);
  }
  printf("Cohesion:\n  ");  igraph_vector_print(&cohesion);
  printf("Parents:\n  ");   igraph_vector_print(&parent);
  printf("Block graph:\n"); igraph_write_graph_edgelist(&block_tree, stdout);

  igraph_vector_ptr_destroy(&blocks);
  igraph_vector_destroy(&cohesion);
  igraph_vector_destroy(&parent);
  igraph_destroy(&block_tree);

  return 0;
}

int main() {
  
  igraph_t g;
  int ret;

  /* --------------------------------------------------------*/
  /* The graph from the Moody-White paper                    */

  igraph_small(&g, 23, IGRAPH_UNDIRECTED,
	       0,1, 0,2, 0,3, 0,4, 0,5,
	       1,2, 1,3, 1,4, 1,6,
	       2,3, 2,5, 2,6,
	       3,4, 3,5, 3,6,
	       4,5, 4,6, 4,20,
	       5,6, 
	       6,7, 6,10, 6,13, 6,18,
	       7,8, 7,10, 7,13,
	       8,9,
	       9,11, 9,12,
	       10,11, 10,13,
	       11,15,
	       12,15,
	       13,14,
	       14,15,
	       16,17, 16,18, 16,19,
	       17,19, 17,20,
	       18,19, 18,21, 18,22,
	       19,20,
	       20,21, 20,22,
	       21,22,
	       -1);
  
  if ( (ret=doit(&g)) ) { return ret; }
  igraph_destroy(&g);
  printf("--\n");

  /* --------------------------------------------------------*/
  /* A tricky graph, where the separators themselves         */
  /* form a block. But recently we don't include this        */
  /* block in the results.                                   */

  igraph_small(&g, 8, IGRAPH_UNDIRECTED,
	       0,1,0,4,0,5, 1,2,1,4,1,5,1,6, 2,3,2,5,2,6,2,7,
	       3,6,3,7, 4,5, 5,6, 6,7, 
	       -1);
  
  if ( (ret=doit(&g)) ) { return ret; }
  igraph_destroy(&g);
  printf("--\n");  

  /* --------------------------------------------------------*/
  /* The science camp graph from http://intersci.ss.uci.edu/ */
  /* wiki/index.php/Cohesive_blocking                        */

  igraph_small(&g, 18, IGRAPH_UNDIRECTED, 
	       0,1,0,2,0,3, 
	       1,2,1,3,1,16,1,17, 
	       2,3, 
	       3,17, 
	       4,5,4,6,4,7,4,8,
	       5,6,5,7, 
	       6,7,6,8,
	       7,8,7,16,
	       8,9,8,10,
	       9,11,9,12,9,13,9,14,
	       10,11,10,12,10,13,
	       11,14,
	       12,13,12,14,12,15,
	       15,16,15,17,
	       16,17,
	       -1);
	       
  if ( (ret=doit(&g)) ) { return ret; }
  igraph_destroy(&g);
  printf("--\n");  

  /* --------------------------------------------------------*/
  /* Zachary karate-club                                     */
  
  igraph_small(&g, 34, IGRAPH_UNDIRECTED,
	       0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,10,0,11,0,12,0,13,
	       0,17,0,19,0,21,0,31,
	       1,2,1,3,1,7,1,13,1,17,1,19,1,21,1,30,
	       2,3,2,7,2,27,2,28,2,32,2,9,2,8,2,13,
	       3,7,3,12,3,13,
	       4,6,4,10,
	       5,6,5,10,5,16,
	       6,16,
	       8,30,8,32,8,33,
	       9,33,
	       13,33,
	       14,32,14,33,
	       15,32,15,33,
	       18,32,18,33,
	       19,33,
	       20,32,20,33,
	       22,32,22,33,
	       23,25,23,27,23,32,23,33,23,29,
	       24,25,24,27,24,31,
	       25,31,
	       26,29,26,33,
	       27,33,
	       28,31,28,33,
	       29,32,29,33,
	       30,32,30,33,
	       31,32,31,33,
	       32,33,
	       -1);

  if ( (ret=doit(&g)) ) { return ret; }
  igraph_destroy(&g);
  printf("--\n");  
  
  return 0;
}