1 // (C) Copyright 2009 Andrew Sutton
2 //
3 // Use, modification and distribution are subject to the
4 // Boost Software License, Version 1.0 (See accompanying file
5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
6
7 #ifndef TEST_CONSTRUCTION_HPP
8 #define TEST_CONSTRUCTION_HPP
9
10 #include <boost/concept/assert.hpp>
11 #include <utility>
12
13 /** @name Build Graph
14 * Build the standard graph structure used in the remaining tests. Depending
15 * on the mutability traits of the graph G, this may or may not add N vertices
16 * to graph. The Add and Label type parameters are used to dispatch a build
17 * method for normal or labeled graphs.
18 */
19 //@{
20 // This will basically catch adjacency matrices, which don't get built.
21 template <typename Graph, typename Add, typename Label>
build_graph(Graph & g,Add,Label)22 void build_graph(Graph& g, Add, Label)
23 { }
24
25 // This matches MutableGraph, so just add some vertices.
26 template <typename Graph>
build_graph(Graph & g,boost::mpl::true_,boost::mpl::false_)27 void build_graph(Graph& g, boost::mpl::true_, boost::mpl::false_) {
28 using namespace boost;
29 BOOST_CONCEPT_ASSERT((VertexListGraphConcept<Graph>));
30 BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept<Graph>));
31
32 std::cout << "...build_normal\n";
33 for(std::size_t i = 0; i < N; ++i) {
34 add_vertex(g);
35 }
36 BOOST_ASSERT(num_vertices(g) == N);
37 }
38
39 // This will match labeled graphs.
40 template <typename Graph>
build_graph(Graph & g,boost::mpl::false_,boost::mpl::true_)41 void build_graph(Graph& g, boost::mpl::false_, boost::mpl::true_) {
42 using namespace boost;
43 BOOST_CONCEPT_ASSERT((VertexListGraphConcept<Graph>));
44 // BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept<Graph>));
45
46 std::cout << "...build_labeled\n";
47 // Add each vertex labeled with the number i.
48 for(std::size_t i = 0; i < N; ++i) {
49 add_vertex(i, g);
50 }
51 BOOST_ASSERT(num_vertices(g) == N);
52 }
53 //@}
54
55 /** @name Build Mutable
56 * For mutable property graphs, try to add a vertex with a property. This test
57 * actually builds a new graph - or at least tries to. We're not testing for
58 * labeled graphs since that's actually done in build_graph above.
59 */
60 //@{
61 template <typename Graph, typename Add, typename Label>
build_property_graph(Graph const & g,Add,Label)62 void build_property_graph(Graph const& g, Add, Label)
63 { }
64
65 template <typename Graph>
build_property_graph(Graph const &,boost::mpl::true_,boost::mpl::false_)66 void build_property_graph(Graph const&, boost::mpl::true_, boost::mpl::false_) {
67 using namespace boost;
68 BOOST_CONCEPT_ASSERT((VertexMutablePropertyGraphConcept<Graph>));
69 typedef typename vertex_property_type<Graph>::type VertexProp;
70
71 std::cout << "...build mutable\n";
72
73 // Start with clean graph. Nothing really to assert. Just make sure it
74 // copmpiles.
75 Graph h;
76 add_vertex(VertexProp(), h);
77 }
78 //@}
79
80
81 /** @name Connect Graph
82 * Given a constructed graph, connect the edges to create a the standard
83 * testing graph. To facilitate ease of use, we pass a vector of vertices
84 * along with the graph such that v[0] -> *vertices(g).first, etc. The
85 * Labeled type parameter is used to dispatch connection techniques for
86 * normal or labled graphs.
87 */
88 //@{
89 template <typename Graph, typename VertexSet>
connect_graph(Graph & g,VertexSet const & verts,boost::mpl::false_)90 void connect_graph(Graph& g, VertexSet const& verts, boost::mpl::false_) {
91 using namespace boost;
92 BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept<Graph>));
93 BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept<Graph>));
94
95 std::cout << "...connect_normal\n";
96 Pair *f, *l;
97 for(boost::tie(f, l) = edge_pairs(); f != l; ++f) {
98 Pair const& e = *f;
99 add_edge(verts[e.first], verts[e.second], g);
100 }
101
102 // Is the lollipop connected? Is the lollipop not connected to the roof?
103 BOOST_ASSERT(edge(verts[5], verts[3], g).second == true);
104 BOOST_ASSERT(edge(verts[5], verts[0], g).second == false);
105 }
106
107 template <typename Graph, typename VertexSet>
connect_graph(Graph & g,VertexSet const & verts,boost::mpl::true_)108 void connect_graph(Graph& g, VertexSet const& verts, boost::mpl::true_) {
109 using namespace boost;
110 BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept<Graph>));
111 // BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept<Graph>));
112
113 std::cout << "...connect_labeled\n";
114 // With labeled graphs, we want to operate directly on the edge numbers
115 // rather than looking up the correct vertex index. This is because the
116 // vertices are already mapped to indices.
117 Pair* p = edge_pairs().first;
118 for(std::size_t i = 0; i < M; ++i) {
119 Pair const& e = p[i];
120 add_edge_by_label(e.first, e.second, g);
121 }
122
123 // Is the lollipop connected?
124 BOOST_ASSERT(edge_by_label(5, 3, g).second == true);
125 BOOST_ASSERT(edge_by_label(5, 0, g).second == false);
126 }
127 //@}
128
129 #endif
130