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. |
38 | std::pair< Pair*, Pair* > edge_pairs() |
39 | { |
40 | static Pair pairs[] = { Pair(5, 3), Pair(3, 4), Pair(3, 2), Pair(4, 0), |
41 | Pair(4, 1), Pair(2, 1), Pair(1, 0) }; |
42 | Pair* f = &pairs[0]; |
43 | Pair* l = f + M; |
44 | return std::make_pair(x&: f, y&: l); |
45 | } |
46 | |
47 | // Return true if the vertex v is the target of the edge e. |
48 | template < typename Graph, typename Edge, typename Vertex > |
49 | bool has_target(Graph const& g, Edge e, Vertex v) |
50 | { |
51 | return boost::target(e, g) == v; |
52 | } |
53 | |
54 | // Return true if the vertex v is the source of the edge e. |
55 | template < typename Graph, typename Edge, typename Vertex > |
56 | bool has_source(Graph const& g, Edge e, Vertex v) |
57 | { |
58 | return boost::source(e, g) == v; |
59 | } |
60 | |
61 | /** @name Property Bundles |
62 | * Support testing with bundled properties. Note that the vertex bundle and |
63 | * edge bundle MAY NOT be the same if you want to use the property map type |
64 | * generator to define property maps. |
65 | */ |
66 | //@{ |
67 | // This is really just a place holder to make sure that bundled graph |
68 | // properties actually work. There are no semantics to this type. |
69 | struct GraphBundle |
70 | { |
71 | int value; |
72 | }; |
73 | |
74 | struct VertexBundle |
75 | { |
76 | VertexBundle() : value() {} |
77 | VertexBundle(int n) : value(n) {} |
78 | |
79 | bool operator==(VertexBundle const& x) const { return value == x.value; } |
80 | bool operator<(VertexBundle const& x) const { return value < x.value; } |
81 | |
82 | int value; |
83 | }; |
84 | |
85 | struct EdgeBundle |
86 | { |
87 | EdgeBundle() : value() {} |
88 | EdgeBundle(int n) : value(n) {} |
89 | |
90 | bool operator==(EdgeBundle const& x) const { return value == x.value; } |
91 | bool operator<(EdgeBundle const& x) const { return value < x.value; } |
92 | |
93 | int value; |
94 | }; |
95 | //@} |
96 | |
97 | #include "test_construction.hpp" |
98 | #include "test_destruction.hpp" |
99 | #include "test_iteration.hpp" |
100 | #include "test_direction.hpp" |
101 | #include "test_properties.hpp" |
102 | |
103 | template < typename Graph > void test_graph(Graph& g) |
104 | { |
105 | using namespace boost; |
106 | BOOST_CONCEPT_ASSERT((GraphConcept< Graph >)); |
107 | |
108 | std::cout << typestr(g) << "\n" ; |
109 | |
110 | // Define a bunch of tags for the graph. |
111 | typename graph_has_add_vertex< Graph >::type can_add_vertex; |
112 | typename graph_has_remove_vertex< Graph >::type can_remove_vertex; |
113 | typename is_labeled_graph< Graph >::type is_labeled; |
114 | typename is_directed_unidirectional_graph< Graph >::type is_directed; |
115 | typename is_directed_bidirectional_graph< Graph >::type is_bidirectional; |
116 | typename is_undirected_graph< Graph >::type is_undirected; |
117 | |
118 | // Test constrution and vertex list. |
119 | build_graph(g, can_add_vertex, is_labeled); |
120 | build_property_graph(g, can_add_vertex, is_labeled); |
121 | |
122 | test_vertex_list_graph(g); |
123 | |
124 | // Collect the vertices for an easy method of "naming" them. |
125 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; |
126 | typedef typename graph_traits< Graph >::vertex_iterator VertexIterator; |
127 | std::vector< Vertex > verts; |
128 | std::pair< VertexIterator, VertexIterator > rng = vertices(g); |
129 | for (; rng.first != rng.second; ++rng.first) |
130 | { |
131 | verts.push_back(*rng.first); |
132 | } |
133 | |
134 | // Test connection and edge list |
135 | connect_graph(g, verts, is_labeled); |
136 | // connect_property_graph(g, verts, is_labeld); |
137 | test_edge_list_graph(g); |
138 | |
139 | // Test properties |
140 | test_properties(g, verts); |
141 | |
142 | // Test directionality. |
143 | test_outdirected_graph(g, verts, is_directed); |
144 | test_indirected_graph(g, verts, is_bidirectional); |
145 | test_undirected_graph(g, verts, is_undirected); |
146 | |
147 | // Test disconnection |
148 | disconnect_graph(g, verts, is_labeled); |
149 | destroy_graph(g, verts, can_remove_vertex, is_labeled); |
150 | } |
151 | |
152 | #endif |
153 | |