Changeset fa8ca4

Timestamp:

06/04/12 17:36:59 (12 months ago)

Author:

Tiago de Paula Peixoto <tiago@…>

Branches:

master

Children:

2ca0c3

Parents:

e43e4e

git-author:

Tiago de Paula Peixoto <tiago@…> (06/04/12 16:27:03)

git-committer:

Tiago de Paula Peixoto <tiago@…> (06/04/12 17:36:59)

Message:

Implement topology.is_bipartite()

Location:

src

Files:

• graph/topology/Makefile.am (modified) (1 diff)
• graph/topology/graph_bipartite.cc (added)
• graph/topology/graph_topology.cc (modified) (2 diffs)
• graph_tool/topology/__init__.py (modified) (3 diffs)

src/graph/topology/Makefile.am

@@ -17 +17 @@
 libgraph_tool_topology_la_SOURCES = \
     graph_all_distances.cc \
+    graph_bipartite.cc \
     graph_components.cc \
     graph_distance.cc \

src/graph/topology/graph_topology.cc

@@ -39 +39 @@
                           size_t n_max, size_t seed);
 double reciprocity(GraphInterface& gi);
+bool is_bipartite(GraphInterface& gi, boost::any part_map);
 
 void export_components();
@@ -60 +61 @@
     def("is_planar", &is_planar);
     def("reciprocity", &reciprocity);
+    def("is_bipartite", &is_bipartite);
     export_components();
     export_similarity();

src/graph_tool/topology/__init__.py

@@ -45 +45 @@
    label_biconnected_components
    label_largest_component
+   is_bipartite
    is_planar
    edge_reciprocity
@@ -67 +68 @@
            "transitive_closure", "label_components", "label_largest_component",
            "label_biconnected_components", "shortest_distance", "shortest_path",
-           "pseudo_diameter", "is_planar", "similarity", "edge_reciprocity"]
+           "pseudo_diameter", "is_bipartite", "is_planar", "similarity", "edge_reciprocity"]
 
 
@@ -1007 +1008 @@
 
 
+def is_bipartite(g, partition=False):
+    """
+    Test if the graph is bipartite.
+
+    Parameters
+    ----------
+    g : :class:`~graph_tool.Graph`
+        Graph to be used.
+    partition : bool (optional, default: ``False``)
+        If ``True``, return the two partitions in case the graph is bipartite.
+
+    Returns
+    -------
+    is_bipartite : bool
+        Whether or not the graph is bipartite.
+    partition : :class:`~graph_tool.PropertyMap` (only if `partition=True`)
+        A vertex property map with the graph partitioning (or `None`) if the
+        graph is not bipartite.
+
+    Notes
+    -----
+
+    An undirected graph is bipartite if one can partition its set of vertices
+    into two sets, such that all edges go from one set to the other.
+
+    This algorithm runs in :math:`O(V + E)` time.
+
+    Examples
+    --------
+    >>> g = gt.lattice([10, 10])
+    >>> is_bi, part = gt.is_bipartite(g, partition=True)
+    >>> print(is_bi)
+    True
+    >>> gt.graph_draw(g, vertex_color=part, output_size=(300, 300), output="bipartite.pdf")
+    <...>
+
+    .. figure:: bipartite.*
+        :align: center
+
+        Bipartition of a 2D lattice.
+
+    References
+    ----------
+    .. [boost-bipartite] http://www.boost.org/libs/graph/doc/is_bipartite.html
+    """
+
+    if partition:
+        part = g.new_vertex_property("bool")
+    else:
+        part = None
+    g = GraphView(g, directed=False)
+    is_bi = libgraph_tool_topology.is_bipartite(g._Graph__graph,
+                                                _prop("v", g, part))
+    if partition:
+        return is_bi, part
+    else:
+        return is_bi
+
+
 def is_planar(g, embedding=False, kuratowski=False):
     """