1 files changed, 130 insertions, 0 deletions
diff --git a/src/boost/libs/graph/test/test_direction.hpp b/src/boost/libs/graph/test/test_direction.hpp
new file mode 100644
index 00000000..1084c06b
--- /dev/null
+++ b/src/boost/libs/graph/test/test_direction.hpp
@@ -0,0 +1,130 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef TEST_DIRECTION_HPP
+#define TEST_DIRECTION_HPP
+
+#include <algorithm>
+#include <boost/range.hpp>
+#include <boost/concept/assert.hpp>
+
+/** @name Test Out-Directed Graph
+ * Test all graphs that have directed out edges.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_outdirected_graph(Graph const& g, VertexSet const& verts, boost::mpl::true_) {
+    using namespace boost;
+    BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<Graph>));
+
+    std::cout << "...test_outdirected_graph\n";
+    typedef typename graph_traits<Graph>::out_edge_iterator OutIter;
+    typedef std::pair<OutIter, OutIter> OutRange;
+    typedef std::vector<OutRange> OutSet;
+
+    // Collect all of the out edge ranges from the graph.
+    OutSet outs(verts.size());
+    for(size_t i = 0; i < verts.size(); ++i) {
+        outs[i] = out_edges(verts[i], g);
+    }
+
+    BOOST_ASSERT(distance(outs[0]) == 0);
+    BOOST_ASSERT(distance(outs[1]) == 1);
+    BOOST_ASSERT(distance(outs[2]) == 1);
+    BOOST_ASSERT(distance(outs[3]) == 2);
+    BOOST_ASSERT(distance(outs[4]) == 2);
+    BOOST_ASSERT(distance(outs[5]) == 1);
+
+    // Verify that the edges are actually correct.
+    // TODO: Find a better way of testing connectivity with multiple edges.
+    BOOST_ASSERT(has_target(g, *outs[1].first, verts[0]));
+    BOOST_ASSERT(has_target(g, *outs[2].first, verts[1]));
+    // BOOST_ASSERT(has_target(g, *outs[3].first++, verts[4]));
+    // BOOST_ASSERT(has_target(g, *outs[3].first, verts[2]));
+    // BOOST_ASSERT(has_target(g, *outs[3].first++, verts[4]));
+    // BOOST_ASSERT(has_target(g, *outs[3].first, verts[2]));
+    BOOST_ASSERT(has_target(g, *outs[5].first, verts[3]));
+}
+
+template <typename Graph, typename VertexSet>
+void test_outdirected_graph(Graph const&, VertexSet const&, boost::mpl::false_)
+{ }
+//@}
+
+/** @name Test In-Directed Graph
+ * Test all graphs that support in-directed edges.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_indirected_graph(Graph const& g, VertexSet const& verts, boost::mpl::true_) {
+    using namespace boost;
+    BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept<Graph>));
+
+    std::cout << "...test_indirected_graph\n";
+    typedef typename graph_traits<Graph>::in_edge_iterator InIter;
+    typedef std::pair<InIter, InIter> InRange;
+    typedef std::vector<InRange> InSet;
+
+    // Collect all of the in edges from the graph.
+    InSet ins(verts.size());
+    for(size_t i = 0; i < verts.size(); ++i) {
+        ins[i] = in_edges(verts[i], g);
+    }
+
+    BOOST_ASSERT(distance(ins[0]) == 2);
+    BOOST_ASSERT(distance(ins[1]) == 2);
+    BOOST_ASSERT(distance(ins[2]) == 1);
+    BOOST_ASSERT(distance(ins[3]) == 1);
+    BOOST_ASSERT(distance(ins[4]) == 1);
+    BOOST_ASSERT(distance(ins[5]) == 0);
+
+    // Verify that the connected edges are correct.
+    // TODO: Find a better way of testing connectivity with multiple edges.
+    BOOST_ASSERT(has_source(g, *ins[2].first, verts[3]));
+    BOOST_ASSERT(has_source(g, *ins[3].first, verts[5]));
+    BOOST_ASSERT(has_source(g, *ins[4].first, verts[3]));
+}
+
+template <typename Graph, typename VertexSet>
+void test_indirected_graph(Graph const&, VertexSet const&, boost::mpl::false_)
+{ }
+//@}
+
+/** @name Undirected Graphs
+ * Test all graphs that have undirected edges.
+ */
+template <typename Graph, typename VertexSet>
+void test_undirected_graph(Graph const& g, VertexSet const& verts, boost::mpl::true_) {
+    using namespace boost;
+    BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<Graph>));
+
+    std::cout << "...test_undirected_graph\n";
+    typedef typename graph_traits<Graph>::out_edge_iterator OutIter;
+    typedef std::pair<OutIter, OutIter> OutRange;
+    typedef std::vector<OutRange> OutSet;
+
+    // The set of out edges is the same as the set of incident edges.
+    OutSet outs(verts.size());
+    for(size_t i = 0; i < verts.size(); ++i) {
+        outs[i] = out_edges(verts[i], g);
+    }
+
+    // TODO: Actually test the end connections to ensure that these are
+    // definitely correct.
+    BOOST_ASSERT(distance(outs[0]) == 2);
+    BOOST_ASSERT(distance(outs[1]) == 3);
+    BOOST_ASSERT(distance(outs[2]) == 2);
+    BOOST_ASSERT(distance(outs[3]) == 3);
+    BOOST_ASSERT(distance(outs[4]) == 3);
+    BOOST_ASSERT(distance(outs[5]) == 1);
+}
+
+template <typename Graph, typename VertexSet>
+void test_undirected_graph(Graph const&, VertexSet const&, boost::mpl::false_)
+{ }
+//@}
+
+#endif