123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130 |
- // (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
|