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 >
test_outdirected_graph(Graph const & g,VertexSet const & verts,boost::mpl::true_)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 >
test_outdirected_graph(Graph const &,VertexSet const &,boost::mpl::false_)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 >
test_indirected_graph(Graph const & g,VertexSet const & verts,boost::mpl::true_)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 >
test_indirected_graph(Graph const &,VertexSet const &,boost::mpl::false_)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 >
test_undirected_graph(Graph const & g,VertexSet const & verts,boost::mpl::true_)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 >
test_undirected_graph(Graph const &,VertexSet const &,boost::mpl::false_)137 void test_undirected_graph(Graph const&, VertexSet const&, boost::mpl::false_)
138 {
139 }
140 //@}
141
142 #endif
143