1 // Copyright (C) 2012, Michele Caini.
2 // Distributed under the Boost Software License, Version 1.0.
3 // (See accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5
6 // Two Graphs Common Spanning Trees Algorithm
7 // Based on academic article of Mint, Read and Tarjan
8 // Efficient Algorithm for Common Spanning Tree Problem
9 // Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346-347
10
11 #include <boost/type_traits.hpp>
12 #include <boost/concept/requires.hpp>
13 #include <boost/assign/std/vector.hpp>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/compressed_pair.hpp>
16 #include <boost/core/lightweight_test.hpp>
17 #include <boost/graph/two_graphs_common_spanning_trees.hpp>
18 #include <vector>
19
20 using namespace boost::assign;
21
22 namespace boost
23 {
24
25 typedef boost::adjacency_list< boost::vecS, // OutEdgeList
26 boost::vecS, // VertexList
27 boost::undirectedS, // Directed
28 boost::no_property, // VertexProperties
29 boost::no_property, // EdgeProperties
30 boost::no_property, // GraphProperties
31 boost::listS // EdgeList
32 >
33 Graph;
34
35 typedef boost::graph_traits< Graph >::vertex_descriptor vertex_descriptor;
36
37 typedef boost::graph_traits< Graph >::edge_descriptor edge_descriptor;
38
39 typedef boost::graph_traits< Graph >::vertex_iterator vertex_iterator;
40
41 typedef boost::graph_traits< Graph >::edge_iterator edge_iterator;
42
43 template < typename Coll, typename Seq > struct check_edge
44 {
45 public:
46 BOOST_CONCEPT_ASSERT((RandomAccessContainer< Coll >));
47 BOOST_CONCEPT_ASSERT((RandomAccessContainer< Seq >));
48
49 typedef typename Coll::value_type coll_value_type;
50 typedef typename Seq::value_type seq_value_type;
51
52 BOOST_STATIC_ASSERT((is_same< coll_value_type, Seq >::value));
53 BOOST_STATIC_ASSERT((is_same< seq_value_type, bool >::value));
54
operator ()boost::check_edge55 void operator()(Coll& coll, Seq& seq)
56 {
57 bool found = false;
58
59 for (typename Coll::iterator iterator = coll.begin();
60 !found && iterator != coll.end(); ++iterator)
61 {
62 Seq& coll_seq = *iterator;
63
64 BOOST_TEST(coll_seq.size() == seq.size());
65
66 found = true;
67 for (typename Seq::size_type pos = 0; found && pos < seq.size();
68 ++pos)
69 {
70 found &= coll_seq[pos] == seq[pos];
71 }
72 }
73
74 BOOST_TEST(found);
75 }
76 };
77
two_graphs_common_spanning_trees_test()78 void two_graphs_common_spanning_trees_test()
79 {
80 Graph iG, vG;
81 std::vector< edge_descriptor > iG_o;
82 std::vector< edge_descriptor > vG_o;
83
84 iG_o.push_back(boost::add_edge(0, 1, iG).first);
85 iG_o.push_back(boost::add_edge(1, 3, iG).first);
86 iG_o.push_back(boost::add_edge(3, 2, iG).first);
87 iG_o.push_back(boost::add_edge(1, 5, iG).first);
88 iG_o.push_back(boost::add_edge(5, 4, iG).first);
89 iG_o.push_back(boost::add_edge(5, 6, iG).first);
90 iG_o.push_back(boost::add_edge(5, 3, iG).first);
91 iG_o.push_back(boost::add_edge(3, 1, iG).first);
92 iG_o.push_back(boost::add_edge(1, 3, iG).first);
93
94 vG_o.push_back(boost::add_edge(0, 2, vG).first);
95 vG_o.push_back(boost::add_edge(0, 4, vG).first);
96 vG_o.push_back(boost::add_edge(0, 5, vG).first);
97 vG_o.push_back(boost::add_edge(5, 1, vG).first);
98 vG_o.push_back(boost::add_edge(5, 3, vG).first);
99 vG_o.push_back(boost::add_edge(5, 6, vG).first);
100 vG_o.push_back(boost::add_edge(5, 4, vG).first);
101 vG_o.push_back(boost::add_edge(5, 2, vG).first);
102 vG_o.push_back(boost::add_edge(2, 6, vG).first);
103
104 std::vector< std::vector< bool > > coll;
105 boost::tree_collector< std::vector< std::vector< bool > >,
106 std::vector< bool > >
107 collector(coll);
108 std::vector< bool > inL(iG_o.size(), false);
109
110 boost::two_graphs_common_spanning_trees(iG, iG_o, vG, vG_o, collector, inL);
111
112 check_edge< std::vector< std::vector< bool > >, std::vector< bool > >
113 checker;
114 std::vector< bool > check;
115
116 check.clear();
117 check += true, true, true, true, true, true, false, false, false;
118 checker(coll, check);
119
120 check.clear();
121 check += true, true, true, true, true, true, false, false, false;
122 checker(coll, check);
123 }
124
125 }
126
main(int argc,char ** argv)127 int main(int argc, char** argv)
128 {
129 boost::two_graphs_common_spanning_trees_test();
130 return boost::report_errors();
131 }
132