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
31typedef std::pair< std::size_t, std::size_t > Pair;
32
33static const std::size_t N = 6;
34static 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.
38std::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.
48template < typename Graph, typename Edge, typename Vertex >
49bool 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.
55template < typename Graph, typename Edge, typename Vertex >
56bool 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.
69struct GraphBundle
70{
71 int value;
72};
73
74struct 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
85struct 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
103template < 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

source code of boost/libs/graph/test/test_graph.hpp