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