]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | //@{ | |
f67539c2 TL |
18 | template < typename Graph, typename VertexSet > |
19 | void test_outdirected_graph( | |
20 | Graph const& g, VertexSet const& verts, boost::mpl::true_) | |
21 | { | |
7c673cae | 22 | using namespace boost; |
f67539c2 | 23 | BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >)); |
7c673cae FG |
24 | |
25 | std::cout << "...test_outdirected_graph\n"; | |
f67539c2 TL |
26 | typedef typename graph_traits< Graph >::out_edge_iterator OutIter; |
27 | typedef std::pair< OutIter, OutIter > OutRange; | |
28 | typedef std::vector< OutRange > OutSet; | |
7c673cae FG |
29 | |
30 | // Collect all of the out edge ranges from the graph. | |
31 | OutSet outs(verts.size()); | |
f67539c2 TL |
32 | for (size_t i = 0; i < verts.size(); ++i) |
33 | { | |
7c673cae FG |
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 | ||
f67539c2 | 55 | template < typename Graph, typename VertexSet > |
7c673cae | 56 | void test_outdirected_graph(Graph const&, VertexSet const&, boost::mpl::false_) |
f67539c2 TL |
57 | { |
58 | } | |
7c673cae FG |
59 | //@} |
60 | ||
61 | /** @name Test In-Directed Graph | |
62 | * Test all graphs that support in-directed edges. | |
63 | */ | |
64 | //@{ | |
f67539c2 TL |
65 | template < typename Graph, typename VertexSet > |
66 | void test_indirected_graph( | |
67 | Graph const& g, VertexSet const& verts, boost::mpl::true_) | |
68 | { | |
7c673cae | 69 | using namespace boost; |
f67539c2 | 70 | BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept< Graph >)); |
7c673cae FG |
71 | |
72 | std::cout << "...test_indirected_graph\n"; | |
f67539c2 TL |
73 | typedef typename graph_traits< Graph >::in_edge_iterator InIter; |
74 | typedef std::pair< InIter, InIter > InRange; | |
75 | typedef std::vector< InRange > InSet; | |
7c673cae FG |
76 | |
77 | // Collect all of the in edges from the graph. | |
78 | InSet ins(verts.size()); | |
f67539c2 TL |
79 | for (size_t i = 0; i < verts.size(); ++i) |
80 | { | |
7c673cae FG |
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 | ||
f67539c2 | 98 | template < typename Graph, typename VertexSet > |
7c673cae | 99 | void test_indirected_graph(Graph const&, VertexSet const&, boost::mpl::false_) |
f67539c2 TL |
100 | { |
101 | } | |
7c673cae FG |
102 | //@} |
103 | ||
104 | /** @name Undirected Graphs | |
105 | * Test all graphs that have undirected edges. | |
106 | */ | |
f67539c2 TL |
107 | template < typename Graph, typename VertexSet > |
108 | void test_undirected_graph( | |
109 | Graph const& g, VertexSet const& verts, boost::mpl::true_) | |
110 | { | |
7c673cae | 111 | using namespace boost; |
f67539c2 | 112 | BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >)); |
7c673cae FG |
113 | |
114 | std::cout << "...test_undirected_graph\n"; | |
f67539c2 TL |
115 | typedef typename graph_traits< Graph >::out_edge_iterator OutIter; |
116 | typedef std::pair< OutIter, OutIter > OutRange; | |
117 | typedef std::vector< OutRange > OutSet; | |
7c673cae FG |
118 | |
119 | // The set of out edges is the same as the set of incident edges. | |
120 | OutSet outs(verts.size()); | |
f67539c2 TL |
121 | for (size_t i = 0; i < verts.size(); ++i) |
122 | { | |
7c673cae FG |
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 | ||
f67539c2 | 136 | template < typename Graph, typename VertexSet > |
7c673cae | 137 | void test_undirected_graph(Graph const&, VertexSet const&, boost::mpl::false_) |
f67539c2 TL |
138 | { |
139 | } | |
7c673cae FG |
140 | //@} |
141 | ||
142 | #endif |