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
12 #include <boost/type_traits.hpp>
13 #include <boost/concept/requires.hpp>
14 #include <boost/assign/std/vector.hpp>
15 #include <boost/graph/adjacency_list.hpp>
16 #include <boost/compressed_pair.hpp>
17 #include <boost/test/minimal.hpp>
18 #include <boost/graph/two_graphs_common_spanning_trees.hpp>
19 #include <vector>
20
21 using namespace boost::assign;
22
23
24 namespace boost
25 {
26
27
28 typedef
29 boost::adjacency_list
30 <
31 boost::vecS, // OutEdgeList
32 boost::vecS, // VertexList
33 boost::undirectedS, // Directed
34 boost::no_property, // VertexProperties
35 boost::no_property, // EdgeProperties
36 boost::no_property, // GraphProperties
37 boost::listS // EdgeList
38 >
39 Graph
40 ;
41
42 typedef
43 boost::graph_traits<Graph>::vertex_descriptor
44 vertex_descriptor;
45
46 typedef
47 boost::graph_traits<Graph>::edge_descriptor
48 edge_descriptor;
49
50 typedef
51 boost::graph_traits<Graph>::vertex_iterator
52 vertex_iterator;
53
54 typedef
55 boost::graph_traits<Graph>::edge_iterator
56 edge_iterator;
57
58
59 template < typename Coll, typename Seq >
60 struct check_edge
61 {
62 public:
63 BOOST_CONCEPT_ASSERT((RandomAccessContainer<Coll>));
64 BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>));
65
66 typedef typename Coll::value_type coll_value_type;
67 typedef typename Seq::value_type seq_value_type;
68
69 BOOST_STATIC_ASSERT((is_same<coll_value_type, Seq>::value));
70 BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value));
71
operator ()boost::check_edge72 void operator()(Coll& coll, Seq& seq)
73 {
74 bool found = false;
75
76 for(typename Coll::iterator iterator = coll.begin();
77 !found && iterator != coll.end(); ++iterator)
78 {
79 Seq& coll_seq = *iterator;
80
81 BOOST_REQUIRE(coll_seq.size() == seq.size());
82
83 found = true;
84 for(typename Seq::size_type pos = 0; found && pos < seq.size(); ++pos) {
85 found &= coll_seq[pos] == seq[pos];
86 }
87 }
88
89 BOOST_REQUIRE(found);
90 }
91 };
92
93
two_graphs_common_spanning_trees_test()94 void two_graphs_common_spanning_trees_test()
95 {
96 Graph iG, vG;
97 std::vector< edge_descriptor > iG_o;
98 std::vector< edge_descriptor > vG_o;
99
100 iG_o.push_back(boost::add_edge(0, 1, iG).first);
101 iG_o.push_back(boost::add_edge(1, 3, iG).first);
102 iG_o.push_back(boost::add_edge(3, 2, iG).first);
103 iG_o.push_back(boost::add_edge(1, 5, iG).first);
104 iG_o.push_back(boost::add_edge(5, 4, iG).first);
105 iG_o.push_back(boost::add_edge(5, 6, iG).first);
106 iG_o.push_back(boost::add_edge(5, 3, iG).first);
107 iG_o.push_back(boost::add_edge(3, 1, iG).first);
108 iG_o.push_back(boost::add_edge(1, 3, iG).first);
109
110 vG_o.push_back(boost::add_edge(0, 2, vG).first);
111 vG_o.push_back(boost::add_edge(0, 4, vG).first);
112 vG_o.push_back(boost::add_edge(0, 5, vG).first);
113 vG_o.push_back(boost::add_edge(5, 1, vG).first);
114 vG_o.push_back(boost::add_edge(5, 3, vG).first);
115 vG_o.push_back(boost::add_edge(5, 6, vG).first);
116 vG_o.push_back(boost::add_edge(5, 4, vG).first);
117 vG_o.push_back(boost::add_edge(5, 2, vG).first);
118 vG_o.push_back(boost::add_edge(2, 6, vG).first);
119
120 std::vector< std::vector<bool> > coll;
121 boost::tree_collector<
122 std::vector< std::vector<bool> >, std::vector<bool>
123 > collector(coll);
124 std::vector<bool> inL(iG_o.size(), false);
125
126 boost::two_graphs_common_spanning_trees(iG, iG_o, vG, vG_o, collector, inL);
127
128 check_edge< std::vector< std::vector<bool> >, std::vector<bool> > checker;
129 std::vector<bool> check;
130
131 check.clear();
132 check += true, true, true, true, true, true, false, false, false;
133 checker(coll, check);
134
135 check.clear();
136 check += true, true, true, true, true, true, false, false, false;
137 checker(coll, check);
138 }
139
140
141 }
142
143
test_main(int argc,char ** argv)144 int test_main ( int argc, char** argv )
145 {
146 boost::two_graphs_common_spanning_trees_test();
147 return EXIT_SUCCESS;
148 }
149