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_GRAPH_HPP
8 #define TEST_GRAPH_HPP
9
10 /** @file test_graph.hpp
11 * This file houses the generic graph testing framework, which is essentially
12 * run using the test_graph function. This function is called, passing a
13 * graph object that be constructed and exercised according to the concepts
14 * that the graph models. This test is extensively metaprogrammed in order to
15 * differentiate testable features of graph instances.
16 */
17
18 #include "typestr.hpp"
19
20 #include <utility>
21 #include <vector>
22 #include <boost/assert.hpp>
23 #include <boost/concept/assert.hpp>
24 #include <boost/graph/graph_concepts.hpp>
25 #include <boost/graph/graph_traits.hpp>
26 #include <boost/graph/graph_mutability_traits.hpp>
27 #include <boost/graph/labeled_graph.hpp>
28
29 #define BOOST_META_ASSERT(x) BOOST_ASSERT(x::value)
30
31 typedef std::pair<std::size_t, std::size_t> Pair;
32
33 static const std::size_t N = 6;
34 static const std::size_t M = 7;
35
36 // A helper function that globally defines the graph being constructed. Note
37 // that this graph shown here: http://en.wikipedia.org/wiki/Graph_theory.
edge_pairs()38 std::pair<Pair*, Pair*> edge_pairs() {
39 static Pair pairs[] = {
40 Pair(5, 3), Pair(3, 4), Pair(3, 2), Pair(4, 0), Pair(4, 1),
41 Pair(2, 1), Pair(1, 0)
42 };
43 Pair* f = &pairs[0];
44 Pair* l = f + M;
45 return std::make_pair(f, l);
46 }
47
48 // Return true if the vertex v is the target of the edge e.
49 template <typename Graph, typename Edge, typename Vertex>
has_target(Graph const & g,Edge e,Vertex v)50 bool has_target(Graph const& g, Edge e, Vertex v)
51 { return boost::target(e, g) == v; }
52
53 // Return true if the vertex v is the source of the edge e.
54 template <typename Graph, typename Edge, typename Vertex>
has_source(Graph const & g,Edge e,Vertex v)55 bool has_source(Graph const& g, Edge e, Vertex v)
56 { return boost::source(e, g) == v; }
57
58 /** @name Property Bundles
59 * Support testing with bundled properties. Note that the vertex bundle and
60 * edge bundle MAY NOT be the same if you want to use the property map type
61 * generator to define property maps.
62 */
63 //@{
64 // This is really just a place holder to make sure that bundled graph
65 // properties actually work. There are no semantics to this type.
66 struct GraphBundle {
67 int value;
68 };
69
70 struct VertexBundle {
VertexBundleVertexBundle71 VertexBundle() : value() { }
VertexBundleVertexBundle72 VertexBundle(int n) : value(n) { }
73
operator ==VertexBundle74 bool operator==(VertexBundle const& x) const { return value == x.value; }
operator <VertexBundle75 bool operator<(VertexBundle const& x) const { return value < x.value; }
76
77 int value;
78 };
79
80 struct EdgeBundle {
EdgeBundleEdgeBundle81 EdgeBundle() : value() { }
EdgeBundleEdgeBundle82 EdgeBundle(int n) : value(n) { }
83
operator ==EdgeBundle84 bool operator==(EdgeBundle const& x) const { return value == x.value; }
operator <EdgeBundle85 bool operator<(EdgeBundle const& x) const { return value < x.value; }
86
87 int value;
88 };
89 //@}
90
91 #include "test_construction.hpp"
92 #include "test_destruction.hpp"
93 #include "test_iteration.hpp"
94 #include "test_direction.hpp"
95 #include "test_properties.hpp"
96
97 template <typename Graph>
test_graph(Graph & g)98 void test_graph(Graph& g) {
99 using namespace boost;
100 BOOST_CONCEPT_ASSERT((GraphConcept<Graph>));
101
102 std::cout << typestr(g) << "\n";
103
104 // Define a bunch of tags for the graph.
105 typename graph_has_add_vertex<Graph>::type can_add_vertex;
106 typename graph_has_remove_vertex<Graph>::type can_remove_vertex;
107 typename is_labeled_graph<Graph>::type is_labeled;
108 typename is_directed_unidirectional_graph<Graph>::type is_directed;
109 typename is_directed_bidirectional_graph<Graph>::type is_bidirectional;
110 typename is_undirected_graph<Graph>::type is_undirected;
111
112 // Test constrution and vertex list.
113 build_graph(g, can_add_vertex, is_labeled);
114 build_property_graph(g, can_add_vertex, is_labeled);
115
116 test_vertex_list_graph(g);
117
118 // Collect the vertices for an easy method of "naming" them.
119 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
120 typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
121 std::vector<Vertex> verts;
122 std::pair<VertexIterator, VertexIterator> rng = vertices(g);
123 for( ; rng.first != rng.second; ++rng.first) {
124 verts.push_back(*rng.first);
125 }
126
127 // Test connection and edge list
128 connect_graph(g, verts, is_labeled);
129 // connect_property_graph(g, verts, is_labeld);
130 test_edge_list_graph(g);
131
132 // Test properties
133 test_properties(g, verts);
134
135 // Test directionality.
136 test_outdirected_graph(g, verts, is_directed);
137 test_indirected_graph(g, verts, is_bidirectional);
138 test_undirected_graph(g, verts, is_undirected);
139
140 // Test disconnection
141 disconnect_graph(g, verts, is_labeled);
142 destroy_graph(g, verts, can_remove_vertex, is_labeled);
143 }
144
145
146 #endif
147