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//@{
18template < typename Graph, typename VertexSet >
19void 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
55template < typename Graph, typename VertexSet >
56void 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//@{
65template < typename Graph, typename VertexSet >
66void 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
98template < typename Graph, typename VertexSet >
99void 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 */
107template < typename Graph, typename VertexSet >
108void 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
136template < typename Graph, typename VertexSet >
137void test_undirected_graph(Graph const&, VertexSet const&, boost::mpl::false_)
138{
139}
140//@}
141
142#endif
143

source code of boost/libs/graph/test/test_direction.hpp