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

Subject: [Boost-commit] svn:boost r77189 - in trunk: boost/graph libs/graph/test
From: jewillco_at_[hidden]
Date: 2012-03-03 16:19:39

Author: jewillco
Date: 2012-03-03 16:19:38 EST (Sat, 03 Mar 2012)
New Revision: 77189
URL: http://svn.boost.org/trac/boost/changeset/77189

Log:
Tried to do read_graphviz for CSR; does not work but some infrastructure changed so it is being committed
Text files modified: 
   trunk/boost/graph/graphviz.hpp          |   102 ++++++++++++++++++++++++++++++          
   trunk/libs/graph/test/graphviz_test.cpp |   132 ++++++++++++++++++++++++++++++--------- 
   2 files changed, 202 insertions(+), 32 deletions(-)

Modified: trunk/boost/graph/graphviz.hpp
==============================================================================
--- trunk/boost/graph/graphviz.hpp	(original)
+++ trunk/boost/graph/graphviz.hpp	2012-03-03 16:19:38 EST (Sat, 03 Mar 2012)
@@ -25,10 +25,14 @@
 #include <boost/property_map/dynamic_property_map.hpp>
 #include <boost/graph/overloading.hpp>
 #include <boost/graph/dll_import_export.hpp>
+#include <boost/graph/compressed_sparse_row_graph.hpp>
 #include <boost/spirit/include/classic_multi_pass.hpp>
 #include <boost/lexical_cast.hpp>
+#include <boost/static_assert.hpp>
 #include <boost/algorithm/string/replace.hpp>
 #include <boost/xpressive/xpressive_static.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <boost/foreach.hpp>
 
 namespace boost {
 
@@ -713,6 +717,9 @@
 
   virtual void  // RG: need new second parameter to support BGL subgraphs
   set_graph_property(const id_t& key, const id_t& value) = 0;
+
+  virtual void
+  finish_building_graph() = 0;
 };
 
 template<typename MutableGraph>
@@ -781,6 +788,8 @@
     put(key, dp_, &graph_, value);
   }
 
+  void finish_building_graph() {}
+
 
  protected:
   MutableGraph& graph_;
@@ -790,6 +799,99 @@
   std::map<edge_t, bgl_edge_t> bgl_edges;
 };
 
+template<typename Directed,
+         typename VertexProperty,
+         typename EdgeProperty,
+         typename GraphProperty,
+         typename Vertex,
+         typename EdgeIndex>
+class mutate_graph_impl<compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> >
+  : public mutate_graph
+{
+  // The first part of this is to make the code dependent on a template parameter.
+  BOOST_STATIC_ASSERT_MSG(sizeof(Directed) == 0,
+                          "Graphviz loading for CSR graphs is broken");
+
+  typedef compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> CSRGraph;
+  typedef typename graph_traits<CSRGraph>::vertices_size_type bgl_vertex_t;
+  typedef typename graph_traits<CSRGraph>::edges_size_type    bgl_edge_t;
+
+ public:
+  mutate_graph_impl(CSRGraph& graph, dynamic_properties& dp,
+                    std::string node_id_prop)
+    : graph_(graph), dp_(dp), vertex_count(0), node_id_prop_(node_id_prop) { }
+
+  ~mutate_graph_impl() {}
+
+  void finish_building_graph() {
+    CSRGraph temp(edges_are_unsorted, edges.begin(), edges.end(), vertex_count);
+    set_property(temp, graph_all, get_property(graph_, graph_all));
+    graph_ = temp;
+    typedef tuple<id_t, bgl_edge_t, id_t> ve_prop;
+    BOOST_FOREACH(const ve_prop& t, vertex_and_edge_props) {
+      put(get<0>(t), dp_, get<1>(t), get<2>(t));
+    }
+  }
+
+  bool is_directed() const
+  {
+    return
+      boost::is_convertible<
+        typename boost::graph_traits<CSRGraph>::directed_category,
+        boost::directed_tag>::value;
+  }
+
+  virtual void do_add_vertex(const node_t& node)
+  {
+    // Add the node to the graph.
+    bgl_vertex_t v = vertex_count++;
+
+    // Set up a mapping from name to BGL vertex.
+    bgl_nodes.insert(std::make_pair(node, v));
+
+    // node_id_prop_ allows the caller to see the real id names for nodes.
+    vertex_and_edge_props.push_back(make_tuple(node_id_prop_, v, node));
+  }
+
+  void
+  do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
+  {
+    bgl_edge_t result = edges.size();
+    edges.push_back(std::make_pair(bgl_nodes[source], bgl_nodes[target]));
+    bgl_edges.insert(std::make_pair(edge, result));
+  }
+
+  void
+  set_node_property(const id_t& key, const node_t& node, const id_t& value)
+  {
+    vertex_and_edge_props.push_back(make_tuple(key, bgl_nodes[node], value));
+  }
+
+  void
+  set_edge_property(const id_t& key, const edge_t& edge, const id_t& value)
+  {
+    vertex_and_edge_props.push_back(make_tuple(key, bgl_edges[edge], value));
+  }
+
+  void
+  set_graph_property(const id_t& key, const id_t& value)
+  {
+    /* RG: pointer to graph prevents copying */
+    put(key, dp_, &graph_, value);
+  }
+
+
+ protected:
+  CSRGraph& graph_;
+  dynamic_properties& dp_;
+  bgl_vertex_t vertex_count;
+  std::string node_id_prop_;
+  std::vector<tuple<id_t, bgl_edge_t, id_t> > vertex_and_edge_props;
+  std::vector<std::pair<bgl_vertex_t, bgl_vertex_t> > edges;
+  std::map<node_t, bgl_vertex_t> bgl_nodes;
+  std::map<edge_t, bgl_edge_t> bgl_edges;
+};
+
 } } } // end namespace boost::detail::graph
 
 #ifdef BOOST_GRAPH_USE_SPIRIT_PARSER

Modified: trunk/libs/graph/test/graphviz_test.cpp
==============================================================================
--- trunk/libs/graph/test/graphviz_test.cpp	(original)
+++ trunk/libs/graph/test/graphviz_test.cpp	2012-03-03 16:19:38 EST (Sat, 03 Mar 2012)
@@ -17,6 +17,7 @@
 #include <boost/graph/graphviz.hpp>
 #include <boost/assign/std/map.hpp>
 #include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/compressed_sparse_row_graph.hpp>
 #include <boost/graph/graph_traits.hpp>
 #include <boost/tuple/tuple.hpp>
 #include <boost/property_map/dynamic_property_map.hpp>
@@ -41,33 +42,49 @@
 typedef std::map<node_t,float> mass_map_t;
 typedef std::map<edge_t,double> weight_map_t;
 
-template <typename Directedness, typename OutEdgeList>
+template <typename graph_t, typename NameMapKey, typename MassMapKey, typename WeightMapKey>
+bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
+                mass_map_t const& masses,
+                weight_map_t const& weights,
+                std::string const& node_id = "node_id",
+                std::string const& g_name = std::string(),
+                NameMapKey name_map_key = boost::vertex_name,
+                MassMapKey mass_map_key = boost::vertex_color,
+                WeightMapKey weight_map_key = boost::edge_weight);
+
+template <typename graph_t>
 bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
                 mass_map_t const& masses,
                 weight_map_t const& weights,
                 std::string const& node_id = "node_id",
                 std::string const& g_name = std::string()) {
+  return test_graph<graph_t, boost::vertex_name_t, boost::vertex_color_t, boost::edge_weight_t>(dotfile, correct_num_vertices, masses, weights, node_id);
+}
+
+template <typename graph_t, typename NameMapKey, typename MassMapKey, typename WeightMapKey>
+bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
+                mass_map_t const& masses,
+                weight_map_t const& weights,
+                std::string const& node_id = "node_id",
+                std::string const& g_name = std::string(),
+                NameMapKey name_map_key = boost::vertex_name,
+                MassMapKey mass_map_key = boost::vertex_color,
+                WeightMapKey weight_map_key = boost::edge_weight) {
 
-  typedef property < vertex_name_t, std::string,
-            property < vertex_color_t, float > > vertex_p;  
-  typedef property < edge_weight_t, double > edge_p;
-  typedef property < graph_name_t, std::string > graph_p;
-  typedef adjacency_list < OutEdgeList, vecS, Directedness,
-    vertex_p, edge_p, graph_p > graph_t;
   typedef typename graph_traits < graph_t >::edge_descriptor edge_t;
   typedef typename graph_traits < graph_t >::vertex_descriptor vertex_t;
 
   // Construct a graph and set up the dynamic_property_maps.
-  graph_t graph(0);
+  graph_t graph;
   dynamic_properties dp(ignore_other_properties);
-  typename property_map<graph_t, vertex_name_t>::type name =
-    get(vertex_name, graph);
+  typename property_map<graph_t, NameMapKey>::type name =
+    get(name_map_key, graph);
   dp.property(node_id,name);
-  typename property_map<graph_t, vertex_color_t>::type mass =
-    get(vertex_color, graph);
+  typename property_map<graph_t, MassMapKey>::type mass =
+    get(mass_map_key, graph);
   dp.property("mass",mass);
-  typename property_map<graph_t, edge_weight_t>::type weight =
-    get(edge_weight, graph);
+  typename property_map<graph_t, WeightMapKey>::type weight =
+    get(weight_map_key, graph);
   dp.property("weight",weight);
 
   boost::ref_property_map<graph_t*,std::string> gname(
@@ -139,19 +156,31 @@
 
   typedef istringstream gs_t;
 
+  typedef property < vertex_name_t, std::string,
+            property < vertex_color_t, float > > vertex_p;  
+  typedef property < edge_weight_t, double > edge_p;
+  typedef property < graph_name_t, std::string > graph_p;
+
+  struct vertex_p_bundled {std::string name; float color;};
+  struct edge_p_bundled {double weight;};
+
   // Basic directed graph tests
   BOOST_AUTO_TEST_CASE (basic_directed_graph_1) {
     mass_map_t masses;
     insert ( masses )  ("a",0.0f) ("c",7.7f) ("e", 6.66f);
     gs_t gs("digraph { a  node [mass = 7.7] c e [mass = 6.66] }");
-    BOOST_CHECK((test_graph<directedS,vecS>(gs,3,masses,weight_map_t())));
+    typedef adjacency_list < vecS, vecS, directedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,3,masses,weight_map_t())));
   }
 
   BOOST_AUTO_TEST_CASE (basic_directed_graph_2) {
     mass_map_t masses;
     insert ( masses )  ("a",0.0f) ("e", 6.66f);
     gs_t gs("digraph { a  node [mass = 7.7] \"a\" e [mass = 6.66] }");
-    BOOST_CHECK((test_graph<directedS,vecS>(gs,2,masses,weight_map_t())));
+    typedef adjacency_list < vecS, vecS, directedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,2,masses,weight_map_t())));
   }
 
   BOOST_AUTO_TEST_CASE (basic_directed_graph_3) {
@@ -162,7 +191,9 @@
     gs_t gs("digraph { a -> b eDge [weight = 7.7] "
             "c -> d e-> f [weight = 6.66] "
             "d ->e->a [weight=.5]}");
-    BOOST_CHECK((test_graph<directedS,vecS>(gs,6,mass_map_t(),weights)));
+    typedef adjacency_list < vecS, vecS, directedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,6,mass_map_t(),weights)));
   }
 
   // undirected graph with alternate node_id property name
@@ -170,8 +201,10 @@
     mass_map_t masses;
     insert ( masses )  ("a",0.0f) ("c",7.7f) ("e", 6.66f);
     gs_t gs("graph { a  node [mass = 7.7] c e [mass = 6.66] }");
-    BOOST_CHECK((test_graph<undirectedS,vecS>(gs,3,masses,weight_map_t(),
-                                             "nodenames")));
+    typedef adjacency_list < vecS, vecS, undirectedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,3,masses,weight_map_t(),
+                                     "nodenames")));
   }
 
   // Basic undirected graph tests
@@ -179,7 +212,9 @@
     mass_map_t masses;
     insert ( masses )  ("a",0.0f) ("c",7.7f) ("e", 6.66f);
     gs_t gs("graph { a  node [mass = 7.7] c e [mass =\\\n6.66] }");
-    BOOST_CHECK((test_graph<undirectedS,vecS>(gs,3,masses,weight_map_t())));
+    typedef adjacency_list < vecS, vecS, undirectedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,3,masses,weight_map_t())));
   }
 
   BOOST_AUTO_TEST_CASE (basic_undirected_graph_2) {
@@ -188,7 +223,9 @@
       (make_pair("c","d"),7.7)(make_pair("e","f"),6.66);
     gs_t gs("graph { a -- b eDge [weight = 7.7] "
             "c -- d e -- f [weight = 6.66] }");
-    BOOST_CHECK((test_graph<undirectedS,vecS>(gs,6,mass_map_t(),weights)));
+    typedef adjacency_list < vecS, vecS, undirectedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,6,mass_map_t(),weights)));
   }
 
   // Mismatch directed graph test
@@ -197,7 +234,9 @@
     insert ( masses )  ("a",0.0f) ("c",7.7f) ("e", 6.66f);
     gs_t gs("graph { a  nodE [mass = 7.7] c e [mass = 6.66] }");
     try {
-      test_graph<directedS,vecS>(gs,3,masses,weight_map_t());
+      typedef adjacency_list < vecS, vecS, directedS,
+        vertex_p, edge_p, graph_p > graph_t;
+      test_graph<graph_t>(gs,3,masses,weight_map_t());
       BOOST_ERROR("Failed to throw boost::undirected_graph_error.");
     } catch (boost::undirected_graph_error&) {
     } catch (boost::directed_graph_error&) {
@@ -211,7 +250,9 @@
     insert ( masses )  ("a",0.0f) ("c",7.7f) ("e", 6.66f);
     gs_t gs("digraph { a  node [mass = 7.7] c e [mass = 6.66] }");
     try {
-      test_graph<undirectedS,vecS>(gs,3,masses,weight_map_t());
+      typedef adjacency_list < vecS, vecS, undirectedS,
+        vertex_p, edge_p, graph_p > graph_t;
+      test_graph<graph_t>(gs,3,masses,weight_map_t());
       BOOST_ERROR("Failed to throw boost::directed_graph_error.");
     } catch (boost::directed_graph_error&) {}
   }
@@ -223,7 +264,9 @@
     insert( weights )(make_pair("a","b"),7.7);
     gs_t gs("diGraph { a -> b [weight = 7.7]  a -> b [weight = 7.7] }");
     try {
-      test_graph<directedS,setS>(gs,2,mass_map_t(),weights);
+      typedef adjacency_list < setS, vecS, directedS,
+        vertex_p, edge_p, graph_p > graph_t;
+      test_graph<graph_t>(gs,2,mass_map_t(),weights);
       BOOST_ERROR("Failed to throw boost::bad_parallel_edge.");
     } catch (boost::bad_parallel_edge&) {}
   }
@@ -233,7 +276,9 @@
     weight_map_t weights;
     insert( weights )(make_pair("a","b"),7.7);
     gs_t gs("digraph { a -> b [weight = 7.7]  a -> b [weight = 7.7] }");
-    BOOST_CHECK((test_graph<directedS,vecS>(gs,2,mass_map_t(),weights)));
+    typedef adjacency_list < vecS, vecS, directedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,2,mass_map_t(),weights)));
   }
 
   // Graph Property Test 1
@@ -242,8 +287,10 @@
     insert ( masses )  ("a",0.0f) ("c",0.0f) ("e", 6.66f);
     gs_t gs("digraph { graph [name=\"foo \\\"escaped\\\"\"]  a  c e [mass = 6.66] }");
     std::string graph_name("foo \"escaped\"");
-    BOOST_CHECK((test_graph<directedS,vecS>(gs,3,masses,weight_map_t(),"",
-                                            graph_name)));
+    typedef adjacency_list < vecS, vecS, directedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,3,masses,weight_map_t(),"",
+                                     graph_name)));
   }
 
   // Graph Property Test 2
@@ -252,8 +299,10 @@
     insert ( masses )  ("a",0.0f) ("c",0.0f) ("e", 6.66f);
     gs_t gs("digraph { name=\"fo\"+ \"\\\no\"  a  c e [mass = 6.66] }");
     std::string graph_name("foo");
-    BOOST_CHECK((test_graph<directedS,vecS>(gs,3,masses,weight_map_t(),"",
-                                            graph_name)));
+    typedef adjacency_list < vecS, vecS, directedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,3,masses,weight_map_t(),"",
+                                     graph_name)));
   }
 
   // Graph Property Test 3 (HTML)
@@ -262,8 +311,10 @@
     insert ( masses )  ("a",0.0f) ("c",0.0f) ("e", 6.66f);
     std::string graph_name = "<html title=\"x'\" title2='y\"'>foo<b><![CDATA[><bad tag&>]]>bar</b>\n<br/>\nbaz</html>";
     gs_t gs("digraph { name=" + graph_name + "  a  c e [mass = 6.66] }");
-    BOOST_CHECK((test_graph<directedS,vecS>(gs,3,masses,weight_map_t(),"",
-                                            graph_name)));
+    typedef adjacency_list < vecS, vecS, directedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,3,masses,weight_map_t(),"",
+                                     graph_name)));
   }
 
   // Comments embedded in strings
@@ -274,7 +325,24 @@
       "a1 [ label = \"//depot/path/to/file_29#9\" ];"
       "a0 -> a1 [ color=gray ];"
       "}");
-    BOOST_CHECK((test_graph<directedS,vecS>(gs,2,mass_map_t(),weight_map_t())));
+    typedef adjacency_list < vecS, vecS, directedS,
+      vertex_p, edge_p, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,2,mass_map_t(),weight_map_t())));
   }
+
+#if 0 // Currently broken
+  BOOST_AUTO_TEST_CASE (basic_csr_directed_graph) {
+    weight_map_t weights;
+    insert( weights )(make_pair("a","b"),0.0)
+      (make_pair("c","d"),7.7)(make_pair("e","f"),6.66)
+      (make_pair("d","e"),0.5)(make_pair("e","a"),0.5);
+    gs_t gs("digraph { a -> b eDge [weight = 7.7] "
+            "c -> d e-> f [weight = 6.66] "
+            "d ->e->a [weight=.5]}");
+    typedef compressed_sparse_row_graph<directedS, vertex_p_bundled, edge_p_bundled, graph_p > graph_t;
+    BOOST_CHECK((test_graph<graph_t>(gs,6,mass_map_t(),weights,"node_id","",&vertex_p_bundled::name,&vertex_p_bundled::color,&edge_p_bundled::weight)));
+  }
+#endif
+
 // return 0;
 // }