Changeset 2ca0c3

Timestamp:

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

Author:

Tiago de Paula Peixoto <tiago@…>

Branches:

master

Children:

ebc00a

Parents:

fa8ca4

git-author:

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

git-committer:

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

Message:

Implement random_spanning_tree() and label_out_component()

Location:

src

Files:

• graph/topology/Makefile.am (modified) (1 diff)
• graph/topology/graph_components.cc (modified) (2 diffs)
• graph/topology/graph_components.hh (modified) (2 diffs)
• graph/topology/graph_random_spanning_tree.cc (added)
• graph/topology/graph_topology.cc (modified) (2 diffs)
• graph_tool/topology/__init__.py (modified) (6 diffs)

src/graph/topology/Makefile.am

@@ -27 +27 @@
     graph_planar.cc \
     graph_random_matching.cc \
+    graph_random_spanning_tree.cc \
     graph_reciprocity.cc \
     graph_similarity.cc \

src/graph/topology/graph_components.cc

@@ -51 +51 @@
 }
 
+void do_label_out_component(GraphInterface& gi, size_t root, boost::any prop)
+{
+    run_action<>()(gi, bind<void>(label_out_component(), _1, _2, root),
+                   writable_vertex_scalar_properties())(prop);
+}
+
 void export_components()
 {
@@ -56 +62 @@
     python::def("label_biconnected_components",
                 &do_label_biconnected_components);
+    python::def("label_out_component", &do_label_out_component);
 };

src/graph/topology/graph_components.hh

@@ -64 +64 @@
 
         vector<size_t>& h = _hist;
-        size_t bin = v;        
+        size_t bin = v;
         if (bin > _max)
             return;
@@ -161 +161 @@
 
 
+struct label_out_component
+{
+    template <class CompMap>
+    class marker_visitor: public bfs_visitor<>
+    {
+    public:
+        marker_visitor() { }
+        marker_visitor(CompMap comp) : _comp(comp) { }
+
+        template <class Vertex, class Graph>
+        void discover_vertex(Vertex u, const Graph& g)
+        {
+            _comp[u] = true;
+        }
+    private:
+        CompMap _comp;
+    };
+
+    template <class Graph, class CompMap>
+    void operator()(const Graph& g, CompMap comp_map, size_t root) const
+    {
+        marker_visitor<CompMap> marker(comp_map);
+        breadth_first_search(g, vertex(root, g), visitor(marker));
+    }
+};
+
+
 } // graph_tool namespace
 

src/graph/topology/graph_topology.cc

@@ -40 +40 @@
 double reciprocity(GraphInterface& gi);
 bool is_bipartite(GraphInterface& gi, boost::any part_map);
+void get_random_spanning_tree(GraphInterface& gi, size_t root,
+                              boost::any weight_map, boost::any tree_map,
+                              size_t seed);
 
 void export_components();
@@ -62 +65 @@
     def("reciprocity", &reciprocity);
     def("is_bipartite", &is_bipartite);
+    def("random_spanning_tree", &get_random_spanning_tree);
     export_components();
     export_similarity();

src/graph_tool/topology/__init__.py

@@ -39 +39 @@
    max_independent_vertex_set
    min_spanning_tree
+   random_spanning_tree
    dominator_tree
    topological_sort
@@ -45 +46 @@
    label_biconnected_components
    label_largest_component
+   label_out_component
    is_bipartite
    is_planar
@@ -65 +67 @@
 __all__ = ["isomorphism", "subgraph_isomorphism", "mark_subgraph",
            "max_cardinality_matching", "max_independent_vertex_set",
-           "min_spanning_tree", "dominator_tree", "topological_sort",
-           "transitive_closure", "label_components", "label_largest_component",
-           "label_biconnected_components", "shortest_distance", "shortest_path",
-           "pseudo_diameter", "is_bipartite", "is_planar", "similarity", "edge_reciprocity"]
+           "min_spanning_tree", "random_spanning_tree", "dominator_tree",
+           "topological_sort", "transitive_closure", "label_components",
+           "label_largest_component", "label_biconnected_components",
+           "label_out_component", "shortest_distance", "shortest_path",
+           "pseudo_diameter", "is_bipartite", "is_planar", "similarity",
+           "edge_reciprocity"]
 
 
@@ -285 +289 @@
     g : :class:`~graph_tool.Graph`
         Graph to be used.
-    weights : :class:`~graph_tool.PropertyMap` (optional, default: None)
+    weights : :class:`~graph_tool.PropertyMap` (optional, default: `None`)
         The edge weights. If provided, the minimum spanning tree will minimize
         the edge weights.
-    root : :class:`~graph_tool.Vertex` (optional, default: None)
+    root : :class:`~graph_tool.Vertex` (optional, default: `None`)
         Root of the minimum spanning tree. If this is provided, Prim's algorithm
         is used. Otherwise, Kruskal's algorithm is used.
-    tree_map : :class:`~graph_tool.PropertyMap` (optional, default: None)
+    tree_map : :class:`~graph_tool.PropertyMap` (optional, default: `None`)
         If provided, the edge tree map will be written in this property map.
 
@@ -362 +366 @@
 
 
+def random_spanning_tree(g, weights=None, root=None, tree_map=None):
+    """
+    Return a random spanning tree of a given graph, which can be directed or
+    undirected.
+
+    Parameters
+    ----------
+    g : :class:`~graph_tool.Graph`
+        Graph to be used.
+    weights : :class:`~graph_tool.PropertyMap` (optional, default: `None`)
+        The edge weights. If provided, the probability of a particular spanning
+        tree being selected is the product of its edge weights.
+    root : :class:`~graph_tool.Vertex` (optional, default: `None`)
+        Root of the spanning tree. If not provided, it will be selected randomly.
+    tree_map : :class:`~graph_tool.PropertyMap` (optional, default: `None`)
+        If provided, the edge tree map will be written in this property map.
+
+    Returns
+    -------
+    tree_map : :class:`~graph_tool.PropertyMap`
+        Edge property map with mark the tree edges: 1 for tree edge, 0
+        otherwise.
+
+    Notes
+    -----
+    The typical running time for random graphs is :math:`O(N\log N)`.
+
+    Examples
+    --------
+    >>> from numpy.random import seed, random
+    >>> seed(42)
+    >>> g, pos = gt.triangulation(random((400, 2)) * 10, type="delaunay")
+    >>> weight = g.new_edge_property("double")
+    >>> for e in g.edges():
+    ...    weight[e] = linalg.norm(pos[e.target()].a - pos[e.source()].a)
+    >>> tree = gt.random_spanning_tree(g, weights=weight)
+    >>> gt.graph_draw(g, pos=pos, output="rtriang_orig.pdf")
+    <...>
+    >>> g.set_edge_filter(tree)
+    >>> gt.graph_draw(g, pos=pos, output="triang_min_span_tree.pdf")
+    <...>
+
+
+    .. image:: rtriang_orig.*
+        :width: 400px
+    .. image:: triang_random_span_tree.*
+        :width: 400px
+
+    *Left:* Original graph, *Right:* A random spanning tree.
+
+    References
+    ----------
+
+    .. [wilson-generating-1996] David Bruce Wilson, "Generating random spanning
+       trees more quickly than the cover time", Proceedings of the twenty-eighth
+       annual ACM symposium on Theory of computing, Pages 296-303, ACM New York,
+       1996, :doi:`10.1145/237814.237880`
+    .. [boost-rst] http://www.boost.org/libs/graph/doc/random_spanning_tree.html
+    """
+    if tree_map is None:
+        tree_map = g.new_edge_property("bool")
+    if tree_map.value_type() != "bool":
+        raise ValueError("edge property 'tree_map' must be of value type bool.")
+
+    if root is None:
+        root = g.vertex(numpy.random.randint(0, g.num_vertices()),
+                        use_index=False)
+
+    # we need to restrict ourselves to the in-component of root
+    l = label_out_component(GraphView(g, reversed=True), root)
+    g = GraphView(g, vfilt=l)
+
+    seed = numpy.random.randint(0, sys.maxsize)
+    libgraph_tool_topology.\
+        random_spanning_tree(g._Graph__graph, int(root),
+                             _prop("e", g, weights),
+                             _prop("e", g, tree_map), seed)
+    return tree_map
+
+
 def dominator_tree(g, root, dom_map=None):
     """Return a vertex property map the dominator vertices for each vertex.
@@ -598 +682 @@
     else:
         label.a = (c.a == h.argmax()) & (vfilt.a ^ inv)
+    return label
+
+
+def label_out_component(g, root):
+    """
+    Label the out-component (or simply the component for undirected graphs) of a
+    root vertex.
+
+    Parameters
+    ----------
+    g : :class:`~graph_tool.Graph`
+        Graph to be used.
+    root : :class:`~graph_tool.Vertex`
+        The root vertex.
+
+    Returns
+    -------
+    comp : :class:`~graph_tool.PropertyMap`
+         Boolean vertex property map which labels the out-component.
+
+    Notes
+    -----
+    The algorithm runs in :math:`O(V + E)` time.
+
+    Examples
+    --------
+    >>> from numpy.random import seed, poisson
+    >>> seed(43)
+    >>> g = gt.random_graph(100, lambda: poisson(1), directed=False)
+    >>> l = gt.label_out_component(g, g.vertex(0))
+    >>> print(l.a)
+    [1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1
+     1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0
+     0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0]
+
+    The in-component can be obtained by reversing the graph.
+
+    >>> l = gt.label_out_component(GraphView(g, reversed=True), g.vertex(0))
+    >>> print(l.a)
+    [1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1
+     1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0
+     0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0]
+    """
+
+    label = g.new_vertex_property("bool")
+    libgraph_tool_topology.\
+             label_out_component(g._Graph__graph, int(root),
+                                 _prop("v", g, label))
     return label