Merge lp:~698id/igraph/st-mincut into lp:igraph

[Peter Scott]

Adds Python bindings for the igraph_st_mincut() C function, letting you get a minimum s-t cut. The code is very straightforward, and mostly similar to the other min cut functions, and there are tests.

[Tamás Nepusz (ntamas)]

Thanks a lot, I'll take a look at it soon (probably today).

[Tamás Nepusz (ntamas)]

I took a look at it and it is all right -- one thing I will change before merging is to add "source" and "target" keyword arguments to Graph.mincut as well to make it similar to mincut_value (which calculates the value of an s-t mincut if source and target are given and calculates the global mincut otherwise). Since this is an API change in Graph.mincut, I will make this change in the 0.7 branch only and merge your changes intact into the 0.6 branch. Thanks a lot once again!

review: Approve

=== modified file 'interfaces/python/igraph/__init__.py'
--- interfaces/python/igraph/__init__.py	2012-09-04 22:58:16 +0000
+++ interfaces/python/igraph/__init__.py	2012-10-06 04:05:29 +0000
@@ -651,6 +651,23 @@
         """
         return Cut(self, *GraphBase.mincut(self, capacity))
 
+    def st_mincut(self, source, target, capacity=None):
+        """st_mincut(source, target, capacity=None)
+
+        Calculates the minimum cut between the source and target vertices in a
+        graph.
+
+        @param source: the source vertex ID
+        @param target: the target vertex ID
+        @param capacity: the capacity of the edges. It must be a list or a valid
+          attribute name or C{None}. In the latter case, every edge will have the
+          same capacity.
+        @return: the value of the minimum cut, the IDs of vertices in the
+          first and second partition, and the IDs of edges in the cut,
+          packed in a 4-tuple
+        """
+        return Cut(self, *GraphBase.st_mincut(self, source, target, capacity))
+
     def modularity(self, membership, weights=None):
         """modularity(membership, weights=None)
 

=== modified file 'interfaces/python/igraph/test/flow.py'
--- interfaces/python/igraph/test/flow.py	2010-11-26 13:33:18 +0000
+++ interfaces/python/igraph/test/flow.py	2012-10-06 04:05:29 +0000
@@ -89,6 +89,24 @@
         self.failUnless(mc.value == 4)
         self.assertRaises(KeyError, g.mincut, "unknown")
 
+    def testStMinCut(self):
+        g = self.constructSimpleGraph()
+        mc = g.st_mincut(0, 3, "capacity")
+        self.failUnless(isinstance(mc, Cut))
+        self.failUnless(mc.cut == [3, 4])
+        self.failUnless(mc.value == 4)
+        self.failUnless(set(mc.partition[0]).union(mc.partition[1]) == \
+          set(range(g.vcount())))
+        mc = g.st_mincut(0, 3)
+        self.failUnless(isinstance(mc, Cut))
+        self.failUnless(mc.cut == [3, 4])
+        self.failUnless(mc.value == 2)
+        mc = g.st_mincut(2, 0, "capacity")
+        self.failUnless(isinstance(mc, Cut))
+        self.failUnless(mc.cut == [0, 1])
+        self.failUnless(mc.value == 6)
+
+
     def testAllSTCuts1(self):
         # Simple graph with four vertices
         g = self.constructSimpleGraph(directed=True)

=== modified file 'interfaces/python/src/graphobject.c'
--- interfaces/python/src/graphobject.c	2012-09-25 22:24:23 +0000
+++ interfaces/python/src/graphobject.c	2012-10-06 04:05:29 +0000
@@ -9755,6 +9755,89 @@
   return result;
 }
 
+/** \ingroup python_interface_graph
+ * \brief Calculates a minimum s-t cut in a graph
+ */
+PyObject *igraphmodule_Graph_st_mincut(igraphmodule_GraphObject * self,
+                                       PyObject * args, PyObject * kwds)
+{
+  static char *kwlist[] = { "source", "target", "capacity", NULL };
+  igraph_integer_t source, target;
+  PyObject *cut_o, *part_o, *part2_o, *result;
+  PyObject *source_o, *target_o, *capacity_o = Py_None;
+  igraph_vector_t capacity_vector;
+  igraph_real_t value;
+  igraph_vector_t partition, partition2, cut;
+
+  if (!PyArg_ParseTupleAndKeywords(args, kwds, "OOO", kwlist,
+                                   &source_o, &target_o, &capacity_o))
+    return NULL;
+
+  if (igraphmodule_PyObject_to_vid(source_o, &source, &self->g))
+    return NULL;
+  if (igraphmodule_PyObject_to_vid(target_o, &target, &self->g))
+    return NULL;
+
+  if (igraphmodule_PyObject_to_attribute_values(capacity_o,
+                                                &capacity_vector,
+                                                self, ATTRHASH_IDX_EDGE, 1.0))
+    return igraphmodule_handle_igraph_error();
+
+  if (igraph_vector_init(&partition, 0)) {
+    igraph_vector_destroy(&capacity_vector);
+    return igraphmodule_handle_igraph_error();
+  }
+  if (igraph_vector_init(&partition2, 0)) {
+    igraph_vector_destroy(&partition);
+    igraph_vector_destroy(&capacity_vector);
+    return igraphmodule_handle_igraph_error();
+  }
+  if (igraph_vector_init(&cut, 0)) {
+    igraph_vector_destroy(&partition);
+    igraph_vector_destroy(&partition2);
+    igraph_vector_destroy(&capacity_vector);
+    return igraphmodule_handle_igraph_error();
+  }
+
+  if (igraph_st_mincut(&self->g, &value, &cut, &partition, &partition2,
+        source, target, &capacity_vector)) {
+    igraph_vector_destroy(&cut);
+    igraph_vector_destroy(&partition);
+    igraph_vector_destroy(&partition2);
+    igraph_vector_destroy(&capacity_vector);
+    return igraphmodule_handle_igraph_error();
+  }
+
+  igraph_vector_destroy(&capacity_vector);
+
+  cut_o=igraphmodule_vector_t_to_PyList(&cut, IGRAPHMODULE_TYPE_INT);
+  igraph_vector_destroy(&cut);
+  if (!cut_o) {
+    igraph_vector_destroy(&partition);
+    igraph_vector_destroy(&partition2);
+    return NULL;
+  }
+
+  part_o=igraphmodule_vector_t_to_PyList(&partition, IGRAPHMODULE_TYPE_INT);
+  igraph_vector_destroy(&partition);
+  if (!part_o) {
+    Py_DECREF(cut_o);
+    igraph_vector_destroy(&partition2);
+    return NULL;
+  }
+
+  part2_o=igraphmodule_vector_t_to_PyList(&partition2, IGRAPHMODULE_TYPE_INT);
+  igraph_vector_destroy(&partition2);
+  if (!part2_o) {
+    Py_DECREF(part_o);
+    Py_DECREF(cut_o);
+    return NULL;
+  }
+
+  result = Py_BuildValue("dNNN", (double)value, cut_o, part_o, part2_o);
+  return result;
+}
+
 /**********************************************************************
  * Vertex separators                                                  *
  **********************************************************************/
@@ -14220,6 +14303,24 @@
    "  the ACM 44(4):585-591, 1997.\n"
    },
 
+  {"st_mincut", (PyCFunction) igraphmodule_Graph_st_mincut,
+   METH_VARARGS | METH_KEYWORDS,
+   "st_mincut(source, target, capacity=None)\n\n"
+   "Calculates the minimum cut between the source and target vertices in a\n"
+   "graph.\n\n"
+   "@param source: the source vertex ID\n"
+   "@param target: the target vertex ID\n"
+   "@param capacity: the capacity of the edges. It must be a list or a valid\n"
+   "  attribute name or C{None}. In the latter case, every edge will have the\n"
+   "  same capacity.\n"
+   "@return: the value of the minimum cut, the IDs of vertices in the\n"
+   "  first and second partition, and the IDs of edges in the cut,\n"
+   "  packed in a 4-tuple\n\n"
+   "@attention: this function has a more convenient interface in class\n"
+   "  L{Graph} which wraps the result in a list of L{Cut} objects. It is\n"
+   "  advised to use that.\n"
+  },
+
   /*********************/
   /* VERTEX SEPARATORS */
   /*********************/