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