131 lines
4.5 KiB
C++
131 lines
4.5 KiB
C++
// (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
|