summaryrefslogtreecommitdiff
path: root/libs/graph/test
diff options
context:
space:
mode:
Diffstat (limited to 'libs/graph/test')
-rw-r--r--libs/graph/test/Jamfile.v21
-rw-r--r--libs/graph/test/adj_list_cc.cpp8
-rw-r--r--libs/graph/test/core_numbers_test.cpp1
-rw-r--r--libs/graph/test/csr_graph_test.cpp5
-rw-r--r--libs/graph/test/cycle_ratio_tests.cpp2
-rw-r--r--libs/graph/test/dag_longest_paths.cpp9
-rw-r--r--libs/graph/test/dijkstra_no_color_map_compare.cpp2
-rw-r--r--libs/graph/test/graphviz_test.cpp145
-rw-r--r--libs/graph/test/index_graph.cpp4
-rw-r--r--libs/graph/test/isomorphism.cpp10
-rw-r--r--libs/graph/test/property_iter.cpp2
-rw-r--r--libs/graph/test/stoer_wagner_test.cpp8
-rw-r--r--libs/graph/test/subgraph_bundled.cpp2
-rw-r--r--libs/graph/test/two_graphs_common_spanning_trees_test.cpp148
14 files changed, 285 insertions, 62 deletions
diff --git a/libs/graph/test/Jamfile.v2 b/libs/graph/test/Jamfile.v2
index 8d26b17c49..fd6e967cda 100644
--- a/libs/graph/test/Jamfile.v2
+++ b/libs/graph/test/Jamfile.v2
@@ -119,6 +119,7 @@ test-suite graph_test :
[ compile grid_graph_cc.cpp ]
[ run grid_graph_test.cpp ]
[ run incremental_components_test.cpp ]
+ [ run two_graphs_common_spanning_trees_test.cpp ]
[ run random_spanning_tree_test.cpp ../build//boost_graph ]
[ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ]
[ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
diff --git a/libs/graph/test/adj_list_cc.cpp b/libs/graph/test/adj_list_cc.cpp
index fad293883e..b1e2d544d3 100644
--- a/libs/graph/test/adj_list_cc.cpp
+++ b/libs/graph/test/adj_list_cc.cpp
@@ -76,8 +76,6 @@ int main(int,char*[])
BOOST_CONCEPT_ASSERT(( VertexMutablePropertyGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT(( EdgeMutablePropertyGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT((
- ReadablePropertyGraphConcept<Graph, Vertex, vertex_index_t> ));
- BOOST_CONCEPT_ASSERT((
LvaluePropertyGraphConcept<Graph, Vertex, vertex_color_t> ));
BOOST_CONCEPT_ASSERT((
LvaluePropertyGraphConcept<Graph, Edge, edge_weight_t> ));
@@ -98,8 +96,6 @@ int main(int,char*[])
BOOST_CONCEPT_ASSERT(( VertexMutablePropertyGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT(( EdgeMutablePropertyGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT((
- ReadablePropertyGraphConcept<Graph, Vertex, vertex_index_t> ));
- BOOST_CONCEPT_ASSERT((
LvaluePropertyGraphConcept<Graph, Vertex, vertex_color_t> ));
BOOST_CONCEPT_ASSERT((
LvaluePropertyGraphConcept<Graph, Edge, edge_weight_t> ));
@@ -144,8 +140,6 @@ int main(int,char*[])
BOOST_CONCEPT_ASSERT(( VertexMutablePropertyGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT(( EdgeMutablePropertyGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT((
- ReadablePropertyGraphConcept<Graph, Vertex, vertex_index_t> ));
- BOOST_CONCEPT_ASSERT((
LvaluePropertyGraphConcept<Graph, Vertex, vertex_color_t> ));
BOOST_CONCEPT_ASSERT((
LvaluePropertyGraphConcept<Graph, Edge, edge_weight_t> ));
@@ -166,8 +160,6 @@ int main(int,char*[])
BOOST_CONCEPT_ASSERT(( VertexMutablePropertyGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT(( EdgeMutablePropertyGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT((
- ReadablePropertyGraphConcept<Graph, Vertex, vertex_index_t> ));
- BOOST_CONCEPT_ASSERT((
LvaluePropertyGraphConcept<Graph, Vertex, vertex_color_t> ));
BOOST_CONCEPT_ASSERT((
LvaluePropertyGraphConcept<Graph, Edge, edge_weight_t> ));
diff --git a/libs/graph/test/core_numbers_test.cpp b/libs/graph/test/core_numbers_test.cpp
index 733bf4a6fe..3af0811608 100644
--- a/libs/graph/test/core_numbers_test.cpp
+++ b/libs/graph/test/core_numbers_test.cpp
@@ -78,7 +78,6 @@ int test_2() {
int num_arcs = sizeof(edge_array) / sizeof(Edge);
graph_t G(edge_array, edge_array + num_arcs, weights, num_nodes);
- property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, G);
std::vector<int> core_nums(num_vertices(G));
weighted_core_numbers(G,
diff --git a/libs/graph/test/csr_graph_test.cpp b/libs/graph/test/csr_graph_test.cpp
index 757a8841fe..b6a99603cd 100644
--- a/libs/graph/test/csr_graph_test.cpp
+++ b/libs/graph/test/csr_graph_test.cpp
@@ -280,14 +280,13 @@ void graph_test(const OrigGraph& g)
// Check edge_from_index (and implicitly the edge_index property map) for
// each edge in g2
- std::size_t last_src = 0, last_tgt = 0;
+ std::size_t last_src = 0;
for (boost::tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
BOOST_CHECK(edge_from_index(get(boost::edge_index, g2, *ei), g2) == *ei);
std::size_t src = get(boost::vertex_index, g2, source(*ei, g2));
- std::size_t tgt = get(boost::vertex_index, g2, target(*ei, g2));
+ (void)(std::size_t)get(boost::vertex_index, g2, target(*ei, g2));
BOOST_CHECK(src >= last_src);
last_src = src;
- last_tgt = tgt;
}
// Check out edge iteration and vertex iteration for sortedness
diff --git a/libs/graph/test/cycle_ratio_tests.cpp b/libs/graph/test/cycle_ratio_tests.cpp
index f7ca692181..ac5f208f3b 100644
--- a/libs/graph/test/cycle_ratio_tests.cpp
+++ b/libs/graph/test/cycle_ratio_tests.cpp
@@ -224,7 +224,7 @@ int test_main(int argc, char* argv[])
diGraphInt tg;
property_map<diGraphInt, vertex_index_t>::type vim = get(vertex_index, tg);
property_map<diGraphInt, edge_weight_t>::type ew1m = get(edge_weight, tg);
- property_map<diGraphInt, edge_weight2_t>::type ew2m = ew2m;
+ property_map<diGraphInt, edge_weight2_t>::type ew2m = get(edge_weight2, tg);
diff --git a/libs/graph/test/dag_longest_paths.cpp b/libs/graph/test/dag_longest_paths.cpp
index a3793082d6..4b5151b326 100644
--- a/libs/graph/test/dag_longest_paths.cpp
+++ b/libs/graph/test/dag_longest_paths.cpp
@@ -20,12 +20,11 @@ int test_main(int, char*[])
property<edge_weight_t, int> > Graph;
Graph graph;
- Graph::vertex_descriptor v1, v2, v3, v4;
- v1 = add_vertex(graph);
- v2 = add_vertex(graph);
- v3 = add_vertex(graph);
- v4 = add_vertex(graph);
+ (void)add_vertex(graph);
+ (void)add_vertex(graph);
+ (void)add_vertex(graph);
+ (void)add_vertex(graph);
Graph::edge_descriptor e;
diff --git a/libs/graph/test/dijkstra_no_color_map_compare.cpp b/libs/graph/test/dijkstra_no_color_map_compare.cpp
index a8c140d197..5ff18c1c94 100644
--- a/libs/graph/test/dijkstra_no_color_map_compare.cpp
+++ b/libs/graph/test/dijkstra_no_color_map_compare.cpp
@@ -109,8 +109,6 @@ int test_main(int argc, char* argv[])
put(index_map, current_vertex, vertex_index++);
}
- typedef property_map<graph_t, edge_weight_t>::type weight_map_t;
- weight_map_t weight_map = get(edge_weight, graph);
randomize_property<edge_weight_t>(graph, generator);
// Run comparison test with original dijkstra_shortest_paths
diff --git a/libs/graph/test/graphviz_test.cpp b/libs/graph/test/graphviz_test.cpp
index 765175df1d..adc29034a9 100644
--- a/libs/graph/test/graphviz_test.cpp
+++ b/libs/graph/test/graphviz_test.cpp
@@ -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,46 @@ typedef std::pair<node_t,node_t> edge_t;
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 NameMap, typename MassMap, typename WeightMap>
+bool test_graph(std::istream& dotfile, graph_t& graph,
+ std::size_t correct_num_vertices,
+ mass_map_t const& masses,
+ weight_map_t const& weights,
+ std::string const& node_id,
+ std::string const& g_name,
+ NameMap name,
+ MassMap mass,
+ WeightMap 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()) {
+ graph_t g;
+ return test_graph(dotfile, g, correct_num_vertices, masses, weights, node_id, g_name,
+ get(vertex_name, g), get(vertex_color, g), get(edge_weight, g));
+}
+
+template <typename graph_t, typename NameMap, typename MassMap, typename WeightMap>
+bool test_graph(std::istream& dotfile, graph_t& graph,
+ std::size_t correct_num_vertices,
+ mass_map_t const& masses,
+ weight_map_t const& weights,
+ std::string const& node_id,
+ std::string const& g_name,
+ NameMap name,
+ MassMap mass,
+ WeightMap 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);
dynamic_properties dp(ignore_other_properties);
- typename property_map<graph_t, vertex_name_t>::type name =
- get(vertex_name, graph);
dp.property(node_id,name);
- typename property_map<graph_t, vertex_color_t>::type mass =
- get(vertex_color, graph);
dp.property("mass",mass);
- typename property_map<graph_t, edge_weight_t>::type weight =
- get(edge_weight, graph);
dp.property("weight",weight);
boost::ref_property_map<graph_t*,std::string> gname(
@@ -139,19 +153,31 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +188,9 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +198,10 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +209,9 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +220,9 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
(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 +231,9 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +247,9 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +261,9 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +273,9 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +284,10 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +296,10 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +308,10 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
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 +322,40 @@ bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
"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
+
+ BOOST_AUTO_TEST_CASE (basic_csr_directed_graph_ext_props) {
+ 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, no_property, no_property, graph_p > graph_t;
+ graph_t g;
+ vector_property_map<std::string, property_map<graph_t, vertex_index_t>::const_type> vertex_name(get(vertex_index, g));
+ vector_property_map<float, property_map<graph_t, vertex_index_t>::const_type> vertex_color(get(vertex_index, g));
+ vector_property_map<double, property_map<graph_t, edge_index_t>::const_type> edge_weight(get(edge_index, g));
+ BOOST_CHECK((test_graph(gs,g,6,mass_map_t(),weights,"node_id","",vertex_name,vertex_color,edge_weight)));
+ }
+
// return 0;
// }
diff --git a/libs/graph/test/index_graph.cpp b/libs/graph/test/index_graph.cpp
index b988179f6e..3e757e82e9 100644
--- a/libs/graph/test/index_graph.cpp
+++ b/libs/graph/test/index_graph.cpp
@@ -20,7 +20,7 @@ void test()
static const size_t N = 5;
Graph g;
- IndexMap x = get(vertex_index, g);
+ (void)(IndexMap)get(vertex_index, g);
// build up the graph
Vertex v[N];
@@ -73,7 +73,7 @@ void build()
Graph g(N);
BOOST_ASSERT(max_vertex_index(g) == N);
- IndexMap x = get(vertex_index, g);
+ (void)(IndexMap)get(vertex_index, g);
// Each vertex should be numbered correctly.
Iterator i, end;
diff --git a/libs/graph/test/isomorphism.cpp b/libs/graph/test/isomorphism.cpp
index a151cca1d6..fee22a21d7 100644
--- a/libs/graph/test/isomorphism.cpp
+++ b/libs/graph/test/isomorphism.cpp
@@ -95,6 +95,7 @@ void generate_random_digraph(Graph& g, double edge_probability)
void test_isomorphism2()
{
+ using namespace boost::graph::keywords;
typedef adjacency_list<vecS, vecS, bidirectionalS> graph1;
typedef adjacency_list<listS, listS, bidirectionalS,
property<vertex_index_t, int> > graph2;
@@ -115,8 +116,8 @@ void test_isomorphism2()
bool isomorphism_correct;
clock_t start = clock();
- BOOST_CHECK(isomorphism_correct = isomorphism
- (g1, g2, isomorphism_map(make_assoc_property_map(mapping))));
+ BOOST_CHECK(isomorphism_correct = boost::graph::isomorphism
+ (g1, g2, _isomorphism_map = make_assoc_property_map(mapping)));
clock_t end = clock();
std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
@@ -152,6 +153,7 @@ void test_isomorphism2()
void test_isomorphism(int n, double edge_probability)
{
+ using namespace boost::graph::keywords;
typedef adjacency_list<vecS, vecS, bidirectionalS> graph1;
typedef adjacency_list<listS, listS, bidirectionalS,
property<vertex_index_t, int> > graph2;
@@ -171,8 +173,8 @@ void test_isomorphism(int n, double edge_probability)
bool isomorphism_correct;
clock_t start = clock();
- BOOST_CHECK(isomorphism_correct = isomorphism
- (g1, g2, isomorphism_map(make_assoc_property_map(mapping))));
+ BOOST_CHECK(isomorphism_correct = boost::graph::isomorphism
+ (g1, g2, _isomorphism_map = make_assoc_property_map(mapping)));
clock_t end = clock();
std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
diff --git a/libs/graph/test/property_iter.cpp b/libs/graph/test/property_iter.cpp
index 150061e9f6..d206d2a7a6 100644
--- a/libs/graph/test/property_iter.cpp
+++ b/libs/graph/test/property_iter.cpp
@@ -68,8 +68,10 @@ int main(int, char* [])
std::size_t current_edge_id = 0;
property_map<Graph, vertex_id_t>::type vertex_id_map = get(vertex_id, g);
+ (void)vertex_id_map;
property_map<Graph, edge_id_t>::type edge_id_map = get(edge_id, g);
+ (void)edge_id_map;
for (std::size_t k = 0; k < N; ++k)
add_vertex(current_vertex_id++, g);
diff --git a/libs/graph/test/stoer_wagner_test.cpp b/libs/graph/test/stoer_wagner_test.cpp
index 112bf495c7..034d5498fc 100644
--- a/libs/graph/test/stoer_wagner_test.cpp
+++ b/libs/graph/test/stoer_wagner_test.cpp
@@ -206,10 +206,12 @@ BOOST_AUTO_TEST_CASE(test_prgen_20_70_2)
boost::associative_property_map<std::map<vertex_descriptor, std::size_t> > components(component);
BOOST_CHECK_EQUAL(boost::connected_components(g, components), 1U); // verify the connectedness assumption
- BOOST_AUTO(distances, (boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g))));
+ typedef boost::shared_array_property_map<weight_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> distances_type;
+ distances_type distances = boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g));
typedef std::vector<vertex_descriptor>::size_type index_in_heap_type;
- BOOST_AUTO(indicesInHeap, (boost::make_shared_array_property_map(num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g))));
- boost::d_ary_heap_indirect<vertex_descriptor, 22, BOOST_TYPEOF(indicesInHeap), BOOST_TYPEOF(distances), std::greater<weight_type> > pq(distances, indicesInHeap);
+ typedef boost::shared_array_property_map<index_in_heap_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> indicesInHeap_type;
+ indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
+ boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > pq(distances, indicesInHeap);
int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g), boost::max_priority_queue(pq));
BOOST_CHECK_EQUAL(w, 3407);
diff --git a/libs/graph/test/subgraph_bundled.cpp b/libs/graph/test/subgraph_bundled.cpp
index 81629c95b6..ccfcb42b67 100644
--- a/libs/graph/test/subgraph_bundled.cpp
+++ b/libs/graph/test/subgraph_bundled.cpp
@@ -127,7 +127,7 @@ int test_main(int, char*[])
graph_traits<Graph>::edge_iterator ei, ee;
for (boost::tie(ei, ee) = edges(sub); ei != ee; ++ei) {
// This used to segfault.
- get(edge_weight, sub, *ei);
+ get(&arc::weight, sub, *ei);
}
}
diff --git a/libs/graph/test/two_graphs_common_spanning_trees_test.cpp b/libs/graph/test/two_graphs_common_spanning_trees_test.cpp
new file mode 100644
index 0000000000..741845a397
--- /dev/null
+++ b/libs/graph/test/two_graphs_common_spanning_trees_test.cpp
@@ -0,0 +1,148 @@
+// Copyright (C) 2012, Michele Caini.
+// 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)
+
+// Two Graphs Common Spanning Trees Algorithm
+// Based on academic article of Mint, Read and Tarjan
+// Efficient Algorithm for Common Spanning Tree Problem
+// Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346-347
+
+
+#include <boost/type_traits.hpp>
+#include <boost/concept/requires.hpp>
+#include <boost/assign/std/vector.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/compressed_pair.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/two_graphs_common_spanning_trees.hpp>
+#include <vector>
+
+using namespace boost::assign;
+
+
+namespace boost
+{
+
+
+typedef
+boost::adjacency_list
+ <
+ boost::vecS, // OutEdgeList
+ boost::vecS, // VertexList
+ boost::undirectedS, // Directed
+ boost::no_property, // VertexProperties
+ boost::no_property, // EdgeProperties
+ boost::no_property, // GraphProperties
+ boost::listS // EdgeList
+ >
+Graph
+;
+
+typedef
+boost::graph_traits<Graph>::vertex_descriptor
+vertex_descriptor;
+
+typedef
+boost::graph_traits<Graph>::edge_descriptor
+edge_descriptor;
+
+typedef
+boost::graph_traits<Graph>::vertex_iterator
+vertex_iterator;
+
+typedef
+boost::graph_traits<Graph>::edge_iterator
+edge_iterator;
+
+
+template < typename Coll, typename Seq >
+struct check_edge
+{
+public:
+ BOOST_CONCEPT_ASSERT((RandomAccessContainer<Coll>));
+ BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>));
+
+ typedef typename Coll::value_type coll_value_type;
+ typedef typename Seq::value_type seq_value_type;
+
+ BOOST_STATIC_ASSERT((is_same<coll_value_type, Seq>::value));
+ BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value));
+
+ void operator()(Coll& coll, Seq& seq)
+ {
+ bool found = false;
+
+ for(typename Coll::iterator iterator = coll.begin();
+ !found && iterator != coll.end(); ++iterator)
+ {
+ Seq& coll_seq = *iterator;
+
+ BOOST_REQUIRE(coll_seq.size() == seq.size());
+
+ found = true;
+ for(typename Seq::size_type pos = 0; found && pos < seq.size(); ++pos) {
+ found &= coll_seq[pos] == seq[pos];
+ }
+ }
+
+ BOOST_REQUIRE(found);
+ }
+};
+
+
+void two_graphs_common_spanning_trees_test()
+{
+ Graph iG, vG;
+ std::vector< edge_descriptor > iG_o;
+ std::vector< edge_descriptor > vG_o;
+
+ iG_o.push_back(boost::add_edge(0, 1, iG).first);
+ iG_o.push_back(boost::add_edge(1, 3, iG).first);
+ iG_o.push_back(boost::add_edge(3, 2, iG).first);
+ iG_o.push_back(boost::add_edge(1, 5, iG).first);
+ iG_o.push_back(boost::add_edge(5, 4, iG).first);
+ iG_o.push_back(boost::add_edge(5, 6, iG).first);
+ iG_o.push_back(boost::add_edge(5, 3, iG).first);
+ iG_o.push_back(boost::add_edge(3, 1, iG).first);
+ iG_o.push_back(boost::add_edge(1, 3, iG).first);
+
+ vG_o.push_back(boost::add_edge(0, 2, vG).first);
+ vG_o.push_back(boost::add_edge(0, 4, vG).first);
+ vG_o.push_back(boost::add_edge(0, 5, vG).first);
+ vG_o.push_back(boost::add_edge(5, 1, vG).first);
+ vG_o.push_back(boost::add_edge(5, 3, vG).first);
+ vG_o.push_back(boost::add_edge(5, 6, vG).first);
+ vG_o.push_back(boost::add_edge(5, 4, vG).first);
+ vG_o.push_back(boost::add_edge(5, 2, vG).first);
+ vG_o.push_back(boost::add_edge(2, 6, vG).first);
+
+ std::vector< std::vector<bool> > coll;
+ boost::tree_collector<
+ std::vector< std::vector<bool> >, std::vector<bool>
+ > collector(coll);
+ std::vector<bool> inL(iG_o.size(), false);
+
+ boost::two_graphs_common_spanning_trees(iG, iG_o, vG, vG_o, collector, inL);
+
+ check_edge< std::vector< std::vector<bool> >, std::vector<bool> > checker;
+ std::vector<bool> check;
+
+ check.clear();
+ check += true, true, true, true, true, true, false, false, false;
+ checker(coll, check);
+
+ check.clear();
+ check += true, true, true, true, true, true, false, false, false;
+ checker(coll, check);
+}
+
+
+}
+
+
+int test_main ( int argc, char** argv )
+{
+ boost::two_graphs_common_spanning_trees_test();
+ return EXIT_SUCCESS;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-24 18:40:52 +0000