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 | |
55 | 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 | |
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(x: boost::add_edge(u: 0, v: 1, g_&: iG).first); |
85 | iG_o.push_back(x: boost::add_edge(u: 1, v: 3, g_&: iG).first); |
86 | iG_o.push_back(x: boost::add_edge(u: 3, v: 2, g_&: iG).first); |
87 | iG_o.push_back(x: boost::add_edge(u: 1, v: 5, g_&: iG).first); |
88 | iG_o.push_back(x: boost::add_edge(u: 5, v: 4, g_&: iG).first); |
89 | iG_o.push_back(x: boost::add_edge(u: 5, v: 6, g_&: iG).first); |
90 | iG_o.push_back(x: boost::add_edge(u: 5, v: 3, g_&: iG).first); |
91 | iG_o.push_back(x: boost::add_edge(u: 3, v: 1, g_&: iG).first); |
92 | iG_o.push_back(x: boost::add_edge(u: 1, v: 3, g_&: iG).first); |
93 | |
94 | vG_o.push_back(x: boost::add_edge(u: 0, v: 2, g_&: vG).first); |
95 | vG_o.push_back(x: boost::add_edge(u: 0, v: 4, g_&: vG).first); |
96 | vG_o.push_back(x: boost::add_edge(u: 0, v: 5, g_&: vG).first); |
97 | vG_o.push_back(x: boost::add_edge(u: 5, v: 1, g_&: vG).first); |
98 | vG_o.push_back(x: boost::add_edge(u: 5, v: 3, g_&: vG).first); |
99 | vG_o.push_back(x: boost::add_edge(u: 5, v: 6, g_&: vG).first); |
100 | vG_o.push_back(x: boost::add_edge(u: 5, v: 4, g_&: vG).first); |
101 | vG_o.push_back(x: boost::add_edge(u: 5, v: 2, g_&: vG).first); |
102 | vG_o.push_back(x: boost::add_edge(u: 2, v: 6, g_&: 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_map: iG_o, vG, vG_map: vG_o, func: 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 | |
127 | int main(int argc, char** argv) |
128 | { |
129 | boost::two_graphs_common_spanning_trees_test(); |
130 | return boost::report_errors(); |
131 | } |
132 | |