1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
// (C) Copyright 2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
#ifndef TEST_DIRECTION_HPP
#define TEST_DIRECTION_HPP
#include <algorithm>
#include <boost/range.hpp>
#include <boost/concept/assert.hpp>
/** @name Test Out-Directed Graph
* Test all graphs that have directed out edges.
*/
//@{
template < typename Graph, typename VertexSet >
void test_outdirected_graph(
Graph const& g, VertexSet const& verts, boost::mpl::true_)
{
using namespace boost;
BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
std::cout << "...test_outdirected_graph\n";
typedef typename graph_traits< Graph >::out_edge_iterator OutIter;
typedef std::pair< OutIter, OutIter > OutRange;
typedef std::vector< OutRange > OutSet;
// Collect all of the out edge ranges from the graph.
OutSet outs(verts.size());
for (size_t i = 0; i < verts.size(); ++i)
{
outs[i] = out_edges(verts[i], g);
}
BOOST_ASSERT(distance(outs[0]) == 0);
BOOST_ASSERT(distance(outs[1]) == 1);
BOOST_ASSERT(distance(outs[2]) == 1);
BOOST_ASSERT(distance(outs[3]) == 2);
BOOST_ASSERT(distance(outs[4]) == 2);
BOOST_ASSERT(distance(outs[5]) == 1);
// Verify that the edges are actually correct.
// TODO: Find a better way of testing connectivity with multiple edges.
BOOST_ASSERT(has_target(g, *outs[1].first, verts[0]));
BOOST_ASSERT(has_target(g, *outs[2].first, verts[1]));
// BOOST_ASSERT(has_target(g, *outs[3].first++, verts[4]));
// BOOST_ASSERT(has_target(g, *outs[3].first, verts[2]));
// BOOST_ASSERT(has_target(g, *outs[3].first++, verts[4]));
// BOOST_ASSERT(has_target(g, *outs[3].first, verts[2]));
BOOST_ASSERT(has_target(g, *outs[5].first, verts[3]));
}
template < typename Graph, typename VertexSet >
void test_outdirected_graph(Graph const&, VertexSet const&, boost::mpl::false_)
{
}
//@}
/** @name Test In-Directed Graph
* Test all graphs that support in-directed edges.
*/
//@{
template < typename Graph, typename VertexSet >
void test_indirected_graph(
Graph const& g, VertexSet const& verts, boost::mpl::true_)
{
using namespace boost;
BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept< Graph >));
std::cout << "...test_indirected_graph\n";
typedef typename graph_traits< Graph >::in_edge_iterator InIter;
typedef std::pair< InIter, InIter > InRange;
typedef std::vector< InRange > InSet;
// Collect all of the in edges from the graph.
InSet ins(verts.size());
for (size_t i = 0; i < verts.size(); ++i)
{
ins[i] = in_edges(verts[i], g);
}
BOOST_ASSERT(distance(ins[0]) == 2);
BOOST_ASSERT(distance(ins[1]) == 2);
BOOST_ASSERT(distance(ins[2]) == 1);
BOOST_ASSERT(distance(ins[3]) == 1);
BOOST_ASSERT(distance(ins[4]) == 1);
BOOST_ASSERT(distance(ins[5]) == 0);
// Verify that the connected edges are correct.
// TODO: Find a better way of testing connectivity with multiple edges.
BOOST_ASSERT(has_source(g, *ins[2].first, verts[3]));
BOOST_ASSERT(has_source(g, *ins[3].first, verts[5]));
BOOST_ASSERT(has_source(g, *ins[4].first, verts[3]));
}
template < typename Graph, typename VertexSet >
void test_indirected_graph(Graph const&, VertexSet const&, boost::mpl::false_)
{
}
//@}
/** @name Undirected Graphs
* Test all graphs that have undirected edges.
*/
template < typename Graph, typename VertexSet >
void test_undirected_graph(
Graph const& g, VertexSet const& verts, boost::mpl::true_)
{
using namespace boost;
BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
std::cout << "...test_undirected_graph\n";
typedef typename graph_traits< Graph >::out_edge_iterator OutIter;
typedef std::pair< OutIter, OutIter > OutRange;
typedef std::vector< OutRange > OutSet;
// The set of out edges is the same as the set of incident edges.
OutSet outs(verts.size());
for (size_t i = 0; i < verts.size(); ++i)
{
outs[i] = out_edges(verts[i], g);
}
// TODO: Actually test the end connections to ensure that these are
// definitely correct.
BOOST_ASSERT(distance(outs[0]) == 2);
BOOST_ASSERT(distance(outs[1]) == 3);
BOOST_ASSERT(distance(outs[2]) == 2);
BOOST_ASSERT(distance(outs[3]) == 3);
BOOST_ASSERT(distance(outs[4]) == 3);
BOOST_ASSERT(distance(outs[5]) == 1);
}
template < typename Graph, typename VertexSet >
void test_undirected_graph(Graph const&, VertexSet const&, boost::mpl::false_)
{
}
//@}
#endif
|
