[Boost-commit] svn:boost r50533 - in trunk: boost/graph libs/graph/doc libs/graph/test

Subject: [Boost-commit] svn:boost r50533 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: asutton_at_[hidden]
Date: 2009-01-10 09:22:54

Author: asutton
Date: 2009-01-10 09:22:54 EST (Sat, 10 Jan 2009)
New Revision: 50533
URL: http://svn.boost.org/trac/boost/changeset/50533

Log:
Addressing the problem of subgraphs (not) working with bundled properties.
Added some comments, documentation, and a new test.

Added:
   trunk/libs/graph/test/subgraph_bundled.cpp   (contents, props changed)
Text files modified: 
   trunk/boost/graph/subgraph.hpp     |    15 +++++++++------                         
   trunk/libs/graph/doc/subgraph.html |    20 ++++++++++++++++++++                    
   trunk/libs/graph/test/Jamfile.v2   |    28 +---------------------------            
   3 files changed, 30 insertions(+), 33 deletions(-)

Modified: trunk/boost/graph/subgraph.hpp
==============================================================================
--- trunk/boost/graph/subgraph.hpp	(original)
+++ trunk/boost/graph/subgraph.hpp	2009-01-10 09:22:54 EST (Sat, 10 Jan 2009)
@@ -34,12 +34,15 @@
   //   - If edge e=(u,v) is in the root graph, then edge e
   //     is also in any subgraph that contains both vertex u and v.
 
-  // The Graph template parameter must have a vertex_index
-  // and edge_index internal property. It is assumed that
-  // the vertex indices are assigned automatically by the
-  // graph during a call to add_vertex(). It is not
-  // assumed that the edge vertices are assigned automatically,
-  // they are explicitly assigned here.
+  // The Graph template parameter must have a vertex_index and edge_index
+  // internal property. It is assumed that the vertex indices are assigned
+  // automatically by the graph during a call to add_vertex(). It is not
+  // assumed that the edge vertices are assigned automatically, they are
+  // explicitly assigned here.
+  //
+  // NOTE [asutton]: The requirement of internal indexing causes this to fail
+  // for many, many graphs (i.e., those of non-vecS storage, and using bundled
+  // properties). To work around this - in part - you can do the following:
 
   template <typename Graph>
   class subgraph {

Modified: trunk/libs/graph/doc/subgraph.html
==============================================================================
--- trunk/libs/graph/doc/subgraph.html	(original)
+++ trunk/libs/graph/doc/subgraph.html	2009-01-10 09:22:54 EST (Sat, 10 Jan 2009)
@@ -644,3 +644,23 @@
 traits class is defined in <tt>boost/pending/property.hpp</tt>.
 
 <hr>
+<h2>Notes</h2>
+The subgraph template requires the underlying graph type to supply vertex and
+edge index properties. However, there is no default constructor of any adjacency
+list that satisfies both of these requirements. This is especially true of graphs
+using bundled properties, or any adjacency list whose
+vertex set is selected by anything other that <tt>vecS</tt>.
+
+However, this problem can be overcome by embedding your bundled (or otherwise)
+properties into a <tt>property</tt> that contains an appropriate index. For
+example:
+<pre>
+struct my_vertex { ... };
+typedef property&lt;vertex_index_t, std::size_t, vertex_prop&gt; vertex_prop;
+
+struct my_edge { ... };
+typedef property&lt;edge_index_t, std::size_t, vertex_prop&gt; edge_prop;
+
+typedef adjacency_list&lt;vecS, listS, undirectedS, vertex_prop, edge_prop&gt; Graph;
+typdef subgraph&lt;Graph&gt; Subgraph;
+</pre>

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2009-01-10 09:22:54 EST (Sat, 10 Jan 2009)
@@ -21,7 +21,6 @@
 }
 
 test-suite graph_test :
-
     [ run transitive_closure_test.cpp ]
     [ compile adj_list_cc.cpp ]
 
@@ -59,66 +58,41 @@
       : : : ]
 
     [ compile reverse_graph_cc.cpp ]
-
     [ run sequential_vertex_coloring.cpp ]
-
     [ run subgraph.cpp ../../test/build//boost_test_exec_monitor ]
-
+    [ run subgraph_bundled.cpp ]
     [ run isomorphism.cpp ../../test/build//boost_test_exec_monitor ]
-
     [ run adjacency_matrix_test.cpp ]
-
     [ compile vector_graph_cc.cpp ]
-
     [ compile copy.cpp ]
-
     [ compile property_iter.cpp ]
-
     [ run bundled_properties.cpp ]
-
     [ run floyd_warshall_test.cpp ]
-
     [ run astar_search_test.cpp ]
-
     [ run biconnected_components_test.cpp ]
-
     [ run cuthill_mckee_ordering.cpp ]
-
     [ run king_ordering.cpp ]
-
     [ run matching_test.cpp ]
-
     [ run max_flow_test.cpp ]
-
     [ run kolmogorov_max_flow_test.cpp ]
-
     [ run cycle_ratio_tests.cpp ../build//boost_graph : $(CYCLE_RATIO_INPUT_FILE) ]
-
     [ run basic_planarity_test.cpp ]
-
     [ run make_connected_test.cpp ]
-
     [ run make_bicon_planar_test.cpp ]
-
     [ run make_maximal_planar_test.cpp ]
-
     [ run named_vertices_test.cpp ]
-
     [ run all_planar_input_files_test.cpp
         ../../filesystem/build
         ../../system/build
         : $(PLANAR_INPUT_FILES) ]
-
     [ run parallel_edges_loops_test.cpp
         ../../filesystem/build
         ../../system/build
         : $(PLANAR_INPUT_FILES) ]
-
     [ run r_c_shortest_paths_test.cpp ]
     [ run is_straight_line_draw_test.cpp ]
     [ run metric_tsp_approx.cpp : metric_tsp_approx.txt ]
     [ compile dimacs.cpp ]
-
     $(optional_tests)
     ;
 

Added: trunk/libs/graph/test/subgraph_bundled.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/subgraph_bundled.cpp	2009-01-10 09:22:54 EST (Sat, 10 Jan 2009)
@@ -0,0 +1,130 @@
+// (C) Copyright Jeremy Siek 2004
+// (C) Copyright Andrew Sutton 2009
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <set>
+
+#include <boost/random/mersenne_twister.hpp>
+
+#define BOOST_NO_HASH
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/subgraph.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/graph/graph_test.hpp>
+#include <boost/graph/iteration_macros.hpp>
+
+using namespace boost;
+
+struct node
+{
+    int color;
+};
+
+struct arc
+{
+    int weight;
+};
+typedef property<edge_index_t, std::size_t, arc> arc_prop;
+
+typedef adjacency_list<
+    vecS, vecS, bidirectionalS,
+    node, arc_prop
+> Graph;
+
+typedef subgraph<Graph> Subgraph;
+typedef graph_traits<Subgraph>::vertex_descriptor Vertex;
+typedef graph_traits<Subgraph>::edge_descriptor Edge;
+
+int test_main(int argc, char* argv[])
+{
+  mt19937 gen;
+  for (int t = 0; t < 100; t += 5) {
+    Subgraph g;
+    int N = t + 2;
+    std::vector<Vertex> vertex_set;
+    std::vector< std::pair<Vertex, Vertex> > edge_set;
+
+    generate_random_graph(g, N, N * 2, gen,
+                          std::back_inserter(vertex_set),
+                          std::back_inserter(edge_set));
+    graph_test< Subgraph > gt;
+
+    gt.test_incidence_graph(vertex_set, edge_set, g);
+    gt.test_bidirectional_graph(vertex_set, edge_set, g);
+    gt.test_adjacency_graph(vertex_set, edge_set, g);
+    gt.test_vertex_list_graph(vertex_set, g);
+    gt.test_edge_list_graph(vertex_set, edge_set, g);
+    gt.test_adjacency_matrix(vertex_set, edge_set, g);
+
+    std::vector<Vertex> sub_vertex_set;
+    std::vector<Vertex> sub_global_map;
+    std::vector<Vertex> global_sub_map(num_vertices(g));
+    std::vector< std::pair<Vertex, Vertex> > sub_edge_set;
+
+    Subgraph& g_s = g.create_subgraph();
+
+    const std::set<Vertex>::size_type Nsub = N/2;
+
+    // Collect a set of random vertices to put in the subgraph
+    std::set<Vertex> verts;
+    while (verts.size() < Nsub)
+      verts.insert(random_vertex(g, gen));
+
+    for (std::set<Vertex>::iterator it = verts.begin();
+        it != verts.end(); ++it) {
+      Vertex v_global = *it;
+      Vertex v = add_vertex(v_global, g_s);
+      sub_vertex_set.push_back(v);
+      sub_global_map.push_back(v_global);
+      global_sub_map[v_global] = v;
+    }
+
+    // compute induced edges
+    BGL_FORALL_EDGES(e, g, Subgraph)
+      if (container_contains(sub_global_map, source(e, g))
+          && container_contains(sub_global_map, target(e, g)))
+        sub_edge_set.push_back(std::make_pair(global_sub_map[source(e, g)],
+                                              global_sub_map[target(e, g)]));
+
+    gt.test_incidence_graph(sub_vertex_set, sub_edge_set, g_s);
+    gt.test_bidirectional_graph(sub_vertex_set, sub_edge_set, g_s);
+    gt.test_adjacency_graph(sub_vertex_set, sub_edge_set, g_s);
+    gt.test_vertex_list_graph(sub_vertex_set, g_s);
+    gt.test_edge_list_graph(sub_vertex_set, sub_edge_set, g_s);
+    gt.test_adjacency_matrix(sub_vertex_set, sub_edge_set, g_s);
+
+    if (num_vertices(g_s) == 0)
+      return 0;
+
+    // The testing of properties is completely broken (in graph_test) with
+    // respect to bundled (or even generic) properties.
+    // std::vector<int> weights;
+    // for (unsigned i = 0; i < num_vertices(g_s); ++i)
+        // weights.push_back(i*2);
+    // gt.test_vertex_property_graph(weights, vertex_color_t(), g_s);
+
+    // A regression test: the copy constructor of subgraph did not
+    // copy one of the members, so local_edge->global_edge mapping
+    // was broken.
+    {
+        Subgraph g;
+        graph_traits<Graph>::vertex_descriptor v1, v2;
+        v1 = add_vertex(g);
+        v2 = add_vertex(g);
+        add_edge(v1, v2, g);
+
+        Subgraph sub = g.create_subgraph(vertices(g).first, vertices(g).second);
+
+        graph_traits<Graph>::edge_iterator ei, ee;
+        for (tie(ei, ee) = edges(sub); ei != ee; ++ei) {
+            // This used to segfault.
+            get(edge_weight, sub, *ei);
+        }
+    }
+
+  }
+  return 0;
+}