Re: [igraph] minimum cut; undirected graph

[gregory benison]

> If you check the paper and have some ideas on how to add the min-cut
> calculation, that would help.

Since the algorithm is based on merging nodes, and then finding the
minimum cut by cutting off just one of these (composite) nodes, I
think the minimum cut can be found by arranging to remember which
nodes have been merged.  The attached file is the example from the
Stoer and Wagner paper.

Greg

=== modified file 'src/flow.c'
--- src/flow.c  2007-03-31 00:27:55 +0000
+++ src/flow.c  2007-03-31 00:29:27 +0000
@@ -366,7 +366,7 @@

  IGRAPH_CHECK(igraph_maxflow_value(graph, value, source, target, capacity));
  return 0;
-}
+}

/* This is a flow-based version, but there is a better one
   for undirected graphs */
@@ -546,6 +546,171 @@
  return 0;
}

+
+int igraph_mincut_undirected(const igraph_t *graph,
+                            igraph_integer_t *res,
+                            igraph_vector_t* cut,
+                            const igraph_vector_t *capacity) {
+
+  long int no_of_nodes=igraph_vcount(graph);
+  long int no_of_edges=igraph_ecount(graph);
+
+  igraph_i_cutheap_t heap;
+  igraph_real_t mincut=1.0/0.0;        /* infinity */
+  long int i;
+
+  igraph_i_adjlist_t adjlist;
+  igraph_i_adjedgelist_t adjedgelist;
+
+  /*
+   * The algorithm is based on merging nodes at each phase, so
+   * for each node we maintain a vector containing the indices
+   * of all nodes that have been merged into that one.
+   */
+  igraph_vector_t cut_phase[no_of_nodes];
+
+  /* initially each node set contains only itself */
+  for (i = 0; i < no_of_nodes; ++i)
+    {
+      igraph_vector_init(&(cut_phase[i]), 1);
+      igraph_vector_set(&(cut_phase[i]), 0, i);
+    }
+
+  if (igraph_vector_size(capacity) != no_of_edges) {
+    IGRAPH_ERROR("Invalid capacity vector size", IGRAPH_EINVAL);
+  }
+
+  IGRAPH_CHECK(igraph_i_cutheap_init(&heap, no_of_nodes));
+  IGRAPH_FINALLY(igraph_i_cutheap_destroy, &heap);
+
+  IGRAPH_CHECK(igraph_i_adjedgelist_init(graph, &adjedgelist, IGRAPH_OUT));
+  IGRAPH_FINALLY(igraph_i_adjedgelist_destroy, &adjedgelist);
+
+  IGRAPH_CHECK(igraph_i_adjlist_init(graph, &adjlist, IGRAPH_OUT));
+  IGRAPH_FINALLY(igraph_i_adjlist_destroy, &adjlist);
+
+  while (igraph_i_cutheap_size(&heap) >= 2) {
+
+    long int last;
+    igraph_real_t acut;
+    long int a, n;
+
+    igraph_vector_t *edges, *neis, *edges2, *neis2;
+
+    do {
+      a=igraph_i_cutheap_popmax(&heap);
+
+      /* update the weights of the active vertices connected to a */
+      edges=igraph_i_adjedgelist_get(&adjedgelist, a);
+      neis=igraph_i_adjlist_get(&adjlist, a);
+      n=igraph_vector_size(edges);
+      for (i=0; i<n; i++) {
+       igraph_integer_t edge=VECTOR(*edges)[i];
+       igraph_integer_t to=VECTOR(*neis)[i];
+       igraph_real_t weight=VECTOR(*capacity)[(long int)edge];
+       igraph_i_cutheap_update(&heap, to, weight);
+      }
+
+    } while (igraph_i_cutheap_active_size(&heap) > 1);
+
+    /* Now, there is only one active vertex left,
+       calculate the cut of the phase */
+    acut=igraph_i_cutheap_maxvalue(&heap);
+    last=igraph_i_cutheap_popmax(&heap);
+
+    /*
+     * Test if this is a minimum cut (so far)...
+     * if so, store both the value and the partition,
+     * which is just the set of nodes that have been merged into
+     * the last node
+     */
+    if (acut < mincut) {
+      mincut=acut;
+      igraph_vector_copy(cut, &(cut_phase[last]));
+    }
+
+    /* merge the node sets a <- last */
+    while (igraph_vector_size(&(cut_phase[last])) > 0)
+      igraph_vector_push_back(&(cut_phase[a]),
+                             igraph_vector_pop_back(&cut_phase[last]));
+
+
+    if (mincut == 0) {
+      break;
+    }
+
+    /* And contract the last and the remaining vertex (a and last) */
+    /* First remove the a--last edge if there is one, a is still the
+       last deactivated vertex */
+    edges=igraph_i_adjedgelist_get(&adjedgelist, a);
+    neis=igraph_i_adjlist_get(&adjlist, a);
+    n=igraph_vector_size(edges);
+    for (i=0; i<n; ) {
+      if (VECTOR(*neis)[i]==last) {
+       VECTOR(*neis)[i] = VECTOR(*neis)[n-1];
+       VECTOR(*edges)[i] = VECTOR(*edges)[n-1];
+       igraph_vector_pop_back(neis);
+       igraph_vector_pop_back(edges);
+       n--;
+      } else {
+       i++;
+      }
+    }
+
+    edges=igraph_i_adjedgelist_get(&adjedgelist, last);
+    neis=igraph_i_adjlist_get(&adjlist, last);
+    n=igraph_vector_size(edges);
+    for (i=0; i<n; ) {
+      if (VECTOR(*neis)[i] == a) {
+       VECTOR(*neis)[i] = VECTOR(*neis)[n-1];
+       VECTOR(*edges)[i] = VECTOR(*edges)[n-1];
+       igraph_vector_pop_back(neis);
+       igraph_vector_pop_back(edges);
+       n--;
+      } else {
+       i++;
+      }
+    }
+
+    /* Now rewrite the edge lists of last's neighbors */
+    neis=igraph_i_adjlist_get(&adjlist, last);
+    n=igraph_vector_size(neis);
+    for (i=0; i<n; i++) {
+      igraph_integer_t nei=VECTOR(*neis)[i];
+      long int n2, j;
+      neis2=igraph_i_adjlist_get(&adjlist, nei);
+      n2=igraph_vector_size(neis2);
+      for (j=0; j<n2; j++) {
+       if (VECTOR(*neis2)[j] == last) {
+         VECTOR(*neis2)[j] = a;
+       }
+      }
+    }
+
+    /* And append the lists of last to the lists of a */
+    edges=igraph_i_adjedgelist_get(&adjedgelist, a);
+    neis=igraph_i_adjlist_get(&adjlist, a);
+    edges2=igraph_i_adjedgelist_get(&adjedgelist, last);
+    neis2=igraph_i_adjlist_get(&adjlist, last);
+    IGRAPH_CHECK(igraph_vector_append(edges, edges2));
+    IGRAPH_CHECK(igraph_vector_append(neis, neis2));
+    igraph_vector_clear(edges2); /* TODO: free it */
+    igraph_vector_clear(neis2);         /* TODO: free it */
+
+    /* Remove the deleted vertex from the heap entirely */
+    igraph_i_cutheap_reset_undefine(&heap, last);
+  }
+
+  *res=mincut;
+
+  igraph_i_adjedgelist_destroy(&adjedgelist);
+  igraph_i_adjlist_destroy(&adjlist);
+  igraph_i_cutheap_destroy(&heap);
+  IGRAPH_FINALLY_CLEAN(3);
+  return 0;
+}
+
+
/**
 * \function igraph_mincut_value
 * \brief The minimum edge cut in a graph

=== modified file 'src/igraph.h'
--- src/igraph.h        2007-03-31 00:27:55 +0000
+++ src/igraph.h        2007-03-31 00:29:27 +0000
@@ -989,6 +989,9 @@
                        const igraph_vector_t *capacity);
int igraph_mincut_value(const igraph_t *graph, igraph_real_t *res,
                       const igraph_vector_t *capacity);
+int igraph_mincut_undirected(const igraph_t *graph, igraph_real_t *res,
+                       igraph_vector_t* cut,
+                       const igraph_vector_t *capacity);
int igraph_st_mincut_value(const igraph_t *graph, igraph_real_t *res,
                           igraph_integer_t source, igraph_integer_t target,
                          const igraph_vector_t *capacity);



======================
Gregory Benison
Oregon State University
(541)-737-1876
gbenison at gmail dot com
======================

stoer.c
Description: Text Data