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;
// }