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
20using namespace boost::assign;
21
22namespace boost
23{
24
25typedef 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
35typedef boost::graph_traits< Graph >::vertex_descriptor vertex_descriptor;
36
37typedef boost::graph_traits< Graph >::edge_descriptor edge_descriptor;
38
39typedef boost::graph_traits< Graph >::vertex_iterator vertex_iterator;
40
41typedef boost::graph_traits< Graph >::edge_iterator edge_iterator;
42
43template < typename Coll, typename Seq > struct check_edge
44{
45public:
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
78void 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
127int main(int argc, char** argv)
128{
129 boost::two_graphs_common_spanning_trees_test();
130 return boost::report_errors();
131}
132

source code of boost/libs/graph/test/two_graphs_common_spanning_trees_test.cpp