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
26 // This matches MutableGraph, so just add some vertices.
27 template < typename Graph >
build_graph(Graph & g,boost::mpl::true_,boost::mpl::false_)28 void build_graph(Graph& g, boost::mpl::true_, boost::mpl::false_)
29 {
30 using namespace boost;
31 BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
32 BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept< Graph >));
33
34 std::cout << "...build_normal\n";
35 for (std::size_t i = 0; i < N; ++i)
36 {
37 add_vertex(g);
38 }
39 BOOST_ASSERT(num_vertices(g) == N);
40 }
41
42 // This will match labeled graphs.
43 template < typename Graph >
build_graph(Graph & g,boost::mpl::false_,boost::mpl::true_)44 void build_graph(Graph& g, boost::mpl::false_, boost::mpl::true_)
45 {
46 using namespace boost;
47 BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
48 // BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept<Graph>));
49
50 std::cout << "...build_labeled\n";
51 // Add each vertex labeled with the number i.
52 for (std::size_t i = 0; i < N; ++i)
53 {
54 add_vertex(i, g);
55 }
56 BOOST_ASSERT(num_vertices(g) == N);
57 }
58 //@}
59
60 /** @name Build Mutable
61 * For mutable property graphs, try to add a vertex with a property. This test
62 * actually builds a new graph - or at least tries to. We're not testing for
63 * labeled graphs since that's actually done in build_graph above.
64 */
65 //@{
66 template < typename Graph, typename Add, typename Label >
build_property_graph(Graph const & g,Add,Label)67 void build_property_graph(Graph const& g, Add, Label)
68 {
69 }
70
71 template < typename Graph >
build_property_graph(Graph const &,boost::mpl::true_,boost::mpl::false_)72 void build_property_graph(Graph const&, boost::mpl::true_, boost::mpl::false_)
73 {
74 using namespace boost;
75 BOOST_CONCEPT_ASSERT((VertexMutablePropertyGraphConcept< Graph >));
76 typedef typename vertex_property_type< Graph >::type VertexProp;
77
78 std::cout << "...build mutable\n";
79
80 // Start with clean graph. Nothing really to assert. Just make sure it
81 // copmpiles.
82 Graph h;
83 add_vertex(VertexProp(), h);
84 }
85 //@}
86
87 /** @name Connect Graph
88 * Given a constructed graph, connect the edges to create a the standard
89 * testing graph. To facilitate ease of use, we pass a vector of vertices
90 * along with the graph such that v[0] -> *vertices(g).first, etc. The
91 * Labeled type parameter is used to dispatch connection techniques for
92 * normal or labled graphs.
93 */
94 //@{
95 template < typename Graph, typename VertexSet >
connect_graph(Graph & g,VertexSet const & verts,boost::mpl::false_)96 void connect_graph(Graph& g, VertexSet const& verts, boost::mpl::false_)
97 {
98 using namespace boost;
99 BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< Graph >));
100 BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< Graph >));
101
102 std::cout << "...connect_normal\n";
103 Pair *f, *l;
104 for (boost::tie(f, l) = edge_pairs(); f != l; ++f)
105 {
106 Pair const& e = *f;
107 add_edge(verts[e.first], verts[e.second], g);
108 }
109
110 // Is the lollipop connected? Is the lollipop not connected to the roof?
111 BOOST_ASSERT(edge(verts[5], verts[3], g).second == true);
112 BOOST_ASSERT(edge(verts[5], verts[0], g).second == false);
113 }
114
115 template < typename Graph, typename VertexSet >
connect_graph(Graph & g,VertexSet const & verts,boost::mpl::true_)116 void connect_graph(Graph& g, VertexSet const& verts, boost::mpl::true_)
117 {
118 using namespace boost;
119 BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< Graph >));
120 // BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept<Graph>));
121
122 std::cout << "...connect_labeled\n";
123 // With labeled graphs, we want to operate directly on the edge numbers
124 // rather than looking up the correct vertex index. This is because the
125 // vertices are already mapped to indices.
126 Pair* p = edge_pairs().first;
127 for (std::size_t i = 0; i < M; ++i)
128 {
129 Pair const& e = p[i];
130 add_edge_by_label(e.first, e.second, g);
131 }
132
133 // Is the lollipop connected?
134 BOOST_ASSERT(edge_by_label(5, 3, g).second == true);
135 BOOST_ASSERT(edge_by_label(5, 0, g).second == false);
136 }
137 //@}
138
139 #endif
140