123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148 |
- // Copyright (C) 2012, Michele Caini.
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- // Two Graphs Common Spanning Trees Algorithm
- // Based on academic article of Mint, Read and Tarjan
- // Efficient Algorithm for Common Spanning Tree Problem
- // Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346-347
- #include <boost/type_traits.hpp>
- #include <boost/concept/requires.hpp>
- #include <boost/assign/std/vector.hpp>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/compressed_pair.hpp>
- #include <boost/test/minimal.hpp>
- #include <boost/graph/two_graphs_common_spanning_trees.hpp>
- #include <vector>
- using namespace boost::assign;
- namespace boost
- {
- typedef
- boost::adjacency_list
- <
- boost::vecS, // OutEdgeList
- boost::vecS, // VertexList
- boost::undirectedS, // Directed
- boost::no_property, // VertexProperties
- boost::no_property, // EdgeProperties
- boost::no_property, // GraphProperties
- boost::listS // EdgeList
- >
- Graph
- ;
- typedef
- boost::graph_traits<Graph>::vertex_descriptor
- vertex_descriptor;
- typedef
- boost::graph_traits<Graph>::edge_descriptor
- edge_descriptor;
- typedef
- boost::graph_traits<Graph>::vertex_iterator
- vertex_iterator;
- typedef
- boost::graph_traits<Graph>::edge_iterator
- edge_iterator;
- template < typename Coll, typename Seq >
- struct check_edge
- {
- public:
- BOOST_CONCEPT_ASSERT((RandomAccessContainer<Coll>));
- BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>));
- typedef typename Coll::value_type coll_value_type;
- typedef typename Seq::value_type seq_value_type;
- BOOST_STATIC_ASSERT((is_same<coll_value_type, Seq>::value));
- BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value));
- void operator()(Coll& coll, Seq& seq)
- {
- bool found = false;
- for(typename Coll::iterator iterator = coll.begin();
- !found && iterator != coll.end(); ++iterator)
- {
- Seq& coll_seq = *iterator;
- BOOST_REQUIRE(coll_seq.size() == seq.size());
- found = true;
- for(typename Seq::size_type pos = 0; found && pos < seq.size(); ++pos) {
- found &= coll_seq[pos] == seq[pos];
- }
- }
- BOOST_REQUIRE(found);
- }
- };
- void two_graphs_common_spanning_trees_test()
- {
- Graph iG, vG;
- std::vector< edge_descriptor > iG_o;
- std::vector< edge_descriptor > vG_o;
- iG_o.push_back(boost::add_edge(0, 1, iG).first);
- iG_o.push_back(boost::add_edge(1, 3, iG).first);
- iG_o.push_back(boost::add_edge(3, 2, iG).first);
- iG_o.push_back(boost::add_edge(1, 5, iG).first);
- iG_o.push_back(boost::add_edge(5, 4, iG).first);
- iG_o.push_back(boost::add_edge(5, 6, iG).first);
- iG_o.push_back(boost::add_edge(5, 3, iG).first);
- iG_o.push_back(boost::add_edge(3, 1, iG).first);
- iG_o.push_back(boost::add_edge(1, 3, iG).first);
- vG_o.push_back(boost::add_edge(0, 2, vG).first);
- vG_o.push_back(boost::add_edge(0, 4, vG).first);
- vG_o.push_back(boost::add_edge(0, 5, vG).first);
- vG_o.push_back(boost::add_edge(5, 1, vG).first);
- vG_o.push_back(boost::add_edge(5, 3, vG).first);
- vG_o.push_back(boost::add_edge(5, 6, vG).first);
- vG_o.push_back(boost::add_edge(5, 4, vG).first);
- vG_o.push_back(boost::add_edge(5, 2, vG).first);
- vG_o.push_back(boost::add_edge(2, 6, vG).first);
- std::vector< std::vector<bool> > coll;
- boost::tree_collector<
- std::vector< std::vector<bool> >, std::vector<bool>
- > collector(coll);
- std::vector<bool> inL(iG_o.size(), false);
- boost::two_graphs_common_spanning_trees(iG, iG_o, vG, vG_o, collector, inL);
- check_edge< std::vector< std::vector<bool> >, std::vector<bool> > checker;
- std::vector<bool> check;
- check.clear();
- check += true, true, true, true, true, true, false, false, false;
- checker(coll, check);
- check.clear();
- check += true, true, true, true, true, true, false, false, false;
- checker(coll, check);
- }
- }
- int test_main ( int argc, char** argv )
- {
- boost::two_graphs_common_spanning_trees_test();
- return EXIT_SUCCESS;
- }
|