Subject: [Boost-commit] svn:boost r77893 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2012-04-10 15:52:01
Author: jewillco
Date: 2012-04-10 15:51:59 EDT (Tue, 10 Apr 2012)
New Revision: 77893
URL: http://svn.boost.org/trac/boost/changeset/77893
Log:
Added algorithm from Michele Caini for common spanning trees of two graphs; fixes #6401
Added:
trunk/boost/graph/two_graphs_common_spanning_trees.hpp (contents, props changed)
trunk/libs/graph/doc/two_graphs_common_spanning_trees.html (contents, props changed)
trunk/libs/graph/example/two_graphs_common_spanning_trees.cpp (contents, props changed)
trunk/libs/graph/test/two_graphs_common_spanning_trees_test.cpp (contents, props changed)
Text files modified:
trunk/libs/graph/doc/table_of_contents.html | 5 +++++
trunk/libs/graph/example/Jamfile.v2 | 1 +
trunk/libs/graph/test/Jamfile.v2 | 1 +
3 files changed, 7 insertions(+), 0 deletions(-)
Added: trunk/boost/graph/two_graphs_common_spanning_trees.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/two_graphs_common_spanning_trees.hpp 2012-04-10 15:51:59 EDT (Tue, 10 Apr 2012)
@@ -0,0 +1,870 @@
+// 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
+
+
+#ifndef BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
+#define BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
+
+
+#include <boost/config.hpp>
+
+#include <boost/bimap.hpp>
+#include <boost/type_traits.hpp>
+#include <boost/concept/requires.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/undirected_dfs.hpp>
+#include <boost/graph/connected_components.hpp>
+#include <boost/graph/filtered_graph.hpp>
+#include <vector>
+#include <stack>
+#include <map>
+
+
+namespace boost
+{
+
+
+namespace detail {
+
+
+ template
+ <
+ typename TreeMap,
+ typename PredMap,
+ typename DistMap,
+ typename LowMap,
+ typename Buffer
+ >
+ struct bridges_visitor: public default_dfs_visitor
+ {
+ bridges_visitor(
+ TreeMap tree,
+ PredMap pred,
+ DistMap dist,
+ LowMap low,
+ Buffer& buffer
+ ): mTree(tree), mPred(pred), mDist(dist), mLow(low), mBuffer(buffer)
+ { mNum = -1; }
+
+ template <typename Vertex, typename Graph>
+ void initialize_vertex(const Vertex& u, const Graph& g)
+ {
+ put(mPred, u, u);
+ put(mDist, u, -1);
+ }
+
+ template <typename Vertex, typename Graph>
+ void discover_vertex(const Vertex& u, const Graph& g)
+ {
+ put(mDist, u, ++mNum);
+ put(mLow, u, get(mDist, u));
+ }
+
+ template <typename Edge, typename Graph>
+ void tree_edge(const Edge& e, const Graph& g)
+ {
+ put(mPred, target(e, g), source(e, g));
+ put(mTree, target(e, g), e);
+ }
+
+ template <typename Edge, typename Graph>
+ void back_edge(const Edge& e, const Graph& g)
+ {
+ put(mLow, source(e, g),
+ std::min(get(mLow, source(e, g)), get(mDist, target(e, g))));
+ }
+
+ template <typename Vertex, typename Graph>
+ void finish_vertex(const Vertex& u, const Graph& g)
+ {
+ Vertex parent = get(mPred, u);
+ if(get(mLow, u) > get(mDist, parent))
+ mBuffer.push(get(mTree, u));
+ put(mLow, parent,
+ std::min(get(mLow, parent), get(mLow, u)));
+ }
+
+ TreeMap mTree;
+ PredMap mPred;
+ DistMap mDist;
+ LowMap mLow;
+ Buffer& mBuffer;
+ int mNum;
+ };
+
+
+ template <typename Buffer>
+ struct cycle_finder: public base_visitor< cycle_finder<Buffer> >
+ {
+ typedef on_back_edge event_filter;
+ cycle_finder(): mBuffer(0) { }
+ cycle_finder(Buffer* buffer)
+ : mBuffer(buffer) { }
+ template <typename Edge, typename Graph>
+ void operator()(const Edge& e, const Graph& g)
+ {
+ if(mBuffer)
+ mBuffer->push(e);
+ }
+ Buffer* mBuffer;
+ };
+
+
+ template <typename DeletedMap>
+ struct deleted_edge_status
+ {
+ deleted_edge_status() { }
+ deleted_edge_status(DeletedMap map): mMap(map) { }
+ template <typename Edge>
+ bool operator()(const Edge& e) const
+ { return (!get(mMap, e)); }
+ DeletedMap mMap;
+ };
+
+
+ template <typename InLMap>
+ struct inL_edge_status
+ {
+ inL_edge_status() { }
+ inL_edge_status(InLMap map): mMap(map) { }
+ template <typename Edge>
+ bool operator()(const Edge& e) const
+ { return get(mMap, e); }
+ InLMap mMap;
+ };
+
+
+ template <
+ typename Graph,
+ typename Func,
+ typename Seq,
+ typename Map
+ >
+ void rec_two_graphs_common_spanning_trees
+ (
+ const Graph& iG,
+ bimap<
+ bimaps::set_of<int>,
+ bimaps::set_of< typename graph_traits<Graph>::edge_descriptor >
+ > iG_bimap,
+ Map aiG_inL,
+ Map diG,
+ const Graph& vG,
+ bimap<
+ bimaps::set_of<int>,
+ bimaps::set_of< typename graph_traits<Graph>::edge_descriptor >
+ > vG_bimap,
+ Map avG_inL,
+ Map dvG,
+ Func func,
+ Seq inL
+ )
+ {
+ typedef graph_traits<Graph> GraphTraits;
+
+ typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
+ typedef typename GraphTraits::edge_descriptor edge_descriptor;
+
+ typedef typename Seq::size_type seq_size_type;
+
+ int edges = num_vertices(iG) - 1;
+//
+// [ Michele Caini ]
+//
+// Using the condition (edges != 0) leads to the accidental submission of
+// sub-graphs ((V-1+1)-fake-tree, named here fat-tree).
+// Remove this condition is a workaround for the problem of fat-trees.
+// Please do not add that condition, even if it improves performance.
+//
+// Here is proposed the previous guard (that was wrong):
+// for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i)
+//
+ {
+ for(seq_size_type i = 0; i < inL.size(); ++i)
+ if(inL[i])
+ --edges;
+
+ if(edges < 0)
+ return;
+ }
+
+ bool is_tree = (edges == 0);
+ if(is_tree) {
+ func(inL);
+ } else {
+ std::map<vertex_descriptor, default_color_type> vertex_color;
+ std::map<edge_descriptor, default_color_type> edge_color;
+
+ std::stack<edge_descriptor> iG_buf, vG_buf;
+ bool found = false;
+
+ seq_size_type m;
+ for(seq_size_type j = 0; j < inL.size() && !found; ++j) {
+ if(!inL[j]
+ && !get(diG, iG_bimap.left.at(j))
+ && !get(dvG, vG_bimap.left.at(j)))
+ {
+ put(aiG_inL, iG_bimap.left.at(j), true);
+ put(avG_inL, vG_bimap.left.at(j), true);
+
+ undirected_dfs(
+ make_filtered_graph(iG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(aiG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)),
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+ undirected_dfs(
+ make_filtered_graph(vG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(avG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)),
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+
+ if(iG_buf.empty() && vG_buf.empty()) {
+ inL[j] = true;
+ found = true;
+ m = j;
+ } else {
+ while(!iG_buf.empty()) iG_buf.pop();
+ while(!vG_buf.empty()) vG_buf.pop();
+ put(aiG_inL, iG_bimap.left.at(j), false);
+ put(avG_inL, vG_bimap.left.at(j), false);
+ }
+ }
+ }
+
+ if(found) {
+
+ std::stack<edge_descriptor> iG_buf_copy, vG_buf_copy;
+ for(seq_size_type j = 0; j < inL.size(); ++j) {
+ if(!inL[j]
+ && !get(diG, iG_bimap.left.at(j))
+ && !get(dvG, vG_bimap.left.at(j)))
+ {
+
+ put(aiG_inL, iG_bimap.left.at(j), true);
+ put(avG_inL, vG_bimap.left.at(j), true);
+
+ undirected_dfs(
+ make_filtered_graph(iG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(aiG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder<
+ std::stack<edge_descriptor> > (&iG_buf)),
+ associative_property_map< std::map<
+ vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+ undirected_dfs(
+ make_filtered_graph(vG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(avG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder<
+ std::stack<edge_descriptor> > (&vG_buf)),
+ associative_property_map< std::map<
+ vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+
+ if(!iG_buf.empty() || !vG_buf.empty()) {
+ while(!iG_buf.empty()) iG_buf.pop();
+ while(!vG_buf.empty()) vG_buf.pop();
+ put(diG, iG_bimap.left.at(j), true);
+ put(dvG, vG_bimap.left.at(j), true);
+ iG_buf_copy.push(iG_bimap.left.at(j));
+ vG_buf_copy.push(vG_bimap.left.at(j));
+ }
+
+ put(aiG_inL, iG_bimap.left.at(j), false);
+ put(avG_inL, vG_bimap.left.at(j), false);
+ }
+ }
+
+ // REC
+ detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq, Map>
+ (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL);
+
+ while(!iG_buf_copy.empty()) {
+ put(diG, iG_buf_copy.top(), false);
+ put(dvG, vG_bimap.left.at(
+ iG_bimap.right.at(iG_buf_copy.top())), false);
+ iG_buf_copy.pop();
+ }
+ while(!vG_buf_copy.empty()) {
+ put(dvG, vG_buf_copy.top(), false);
+ put(diG, iG_bimap.left.at(
+ vG_bimap.right.at(vG_buf_copy.top())), false);
+ vG_buf_copy.pop();
+ }
+
+ inL[m] = false;
+ put(aiG_inL, iG_bimap.left.at(m), false);
+ put(avG_inL, vG_bimap.left.at(m), false);
+
+ put(diG, iG_bimap.left.at(m), true);
+ put(dvG, vG_bimap.left.at(m), true);
+
+ std::map<vertex_descriptor, edge_descriptor> tree_map;
+ std::map<vertex_descriptor, vertex_descriptor> pred_map;
+ std::map<vertex_descriptor, int> dist_map, low_map;
+
+ detail::bridges_visitor<
+ associative_property_map<
+ std::map<vertex_descriptor, edge_descriptor>
+ >,
+ associative_property_map<
+ std::map<vertex_descriptor, vertex_descriptor>
+ >,
+ associative_property_map< std::map<vertex_descriptor, int> >,
+ associative_property_map< std::map<vertex_descriptor, int> >,
+ std::stack<edge_descriptor>
+ >
+ iG_vis(
+ associative_property_map<
+ std::map< vertex_descriptor, edge_descriptor> >(tree_map),
+ associative_property_map<
+ std::map< vertex_descriptor, vertex_descriptor> >(pred_map),
+ associative_property_map<
+ std::map< vertex_descriptor, int> >(dist_map),
+ associative_property_map<
+ std::map< vertex_descriptor, int> >(low_map),
+ iG_buf
+ ),
+ vG_vis(
+ associative_property_map<
+ std::map< vertex_descriptor, edge_descriptor> >(tree_map),
+ associative_property_map<
+ std::map< vertex_descriptor, vertex_descriptor> >(pred_map),
+ associative_property_map<
+ std::map< vertex_descriptor, int> >(dist_map),
+ associative_property_map<
+ std::map< vertex_descriptor, int> >(low_map),
+ vG_buf
+ );
+
+ undirected_dfs(make_filtered_graph(iG,
+ detail::deleted_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(diG)),
+ iG_vis,
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+ undirected_dfs(make_filtered_graph(vG,
+ detail::deleted_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(dvG)),
+ vG_vis,
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+
+ found = false;
+ std::stack<edge_descriptor> iG_buf_tmp, vG_buf_tmp;
+ while(!iG_buf.empty() && !found) {
+ if(!inL[iG_bimap.right.at(iG_buf.top())]) {
+ put(aiG_inL, iG_buf.top(), true);
+ put(avG_inL, vG_bimap.left.at(
+ iG_bimap.right.at(iG_buf.top())), true);
+
+ undirected_dfs(
+ make_filtered_graph(iG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(aiG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder<
+ std::stack<edge_descriptor> > (&iG_buf_tmp)),
+ associative_property_map<
+ std::map<
+ vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+ undirected_dfs(
+ make_filtered_graph(vG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(avG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder<
+ std::stack<edge_descriptor> > (&vG_buf_tmp)),
+ associative_property_map<
+ std::map<
+ vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+
+ if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) {
+ found = true;
+ } else {
+ while(!iG_buf_tmp.empty()) iG_buf_tmp.pop();
+ while(!vG_buf_tmp.empty()) vG_buf_tmp.pop();
+ iG_buf_copy.push(iG_buf.top());
+ }
+
+ put(aiG_inL, iG_buf.top(), false);
+ put(avG_inL, vG_bimap.left.at(
+ iG_bimap.right.at(iG_buf.top())), false);
+ }
+ iG_buf.pop();
+ }
+ while(!vG_buf.empty() && !found) {
+ if(!inL[vG_bimap.right.at(vG_buf.top())]) {
+ put(avG_inL, vG_buf.top(), true);
+ put(aiG_inL, iG_bimap.left.at(
+ vG_bimap.right.at(vG_buf.top())), true);
+
+ undirected_dfs(
+ make_filtered_graph(iG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(aiG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder<
+ std::stack<edge_descriptor> > (&iG_buf_tmp)),
+ associative_property_map<
+ std::map<
+ vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+ undirected_dfs(
+ make_filtered_graph(vG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(avG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder<
+ std::stack<edge_descriptor> > (&vG_buf_tmp)),
+ associative_property_map<
+ std::map<
+ vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+
+ if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) {
+ found = true;
+ } else {
+ while(!iG_buf_tmp.empty()) iG_buf_tmp.pop();
+ while(!vG_buf_tmp.empty()) vG_buf_tmp.pop();
+ vG_buf_copy.push(vG_buf.top());
+ }
+
+ put(avG_inL, vG_buf.top(), false);
+ put(aiG_inL, iG_bimap.left.at(
+ vG_bimap.right.at(vG_buf.top())), false);
+ }
+ vG_buf.pop();
+ }
+
+ if(!found) {
+
+ while(!iG_buf_copy.empty()) {
+ inL[iG_bimap.right.at(iG_buf_copy.top())] = true;
+ put(aiG_inL, iG_buf_copy.top(), true);
+ put(avG_inL, vG_bimap.left.at(
+ iG_bimap.right.at(iG_buf_copy.top())), true);
+ iG_buf.push(iG_buf_copy.top());
+ iG_buf_copy.pop();
+ }
+ while(!vG_buf_copy.empty()) {
+ inL[vG_bimap.right.at(vG_buf_copy.top())] = true;
+ put(avG_inL, vG_buf_copy.top(), true);
+ put(aiG_inL, iG_bimap.left.at(
+ vG_bimap.right.at(vG_buf_copy.top())), true);
+ vG_buf.push(vG_buf_copy.top());
+ vG_buf_copy.pop();
+ }
+
+ // REC
+ detail::rec_two_graphs_common_spanning_trees<
+ Graph, Func, Seq, Map>
+ (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL);
+
+ while(!iG_buf.empty()) {
+ inL[iG_bimap.right.at(iG_buf.top())] = false;
+ put(aiG_inL, iG_buf.top(), false);
+ put(avG_inL, vG_bimap.left.at(
+ iG_bimap.right.at(iG_buf.top())), false);
+ iG_buf.pop();
+ }
+ while(!vG_buf.empty()) {
+ inL[vG_bimap.right.at(vG_buf.top())] = false;
+ put(avG_inL, vG_buf.top(), false);
+ put(aiG_inL, iG_bimap.left.at(
+ vG_bimap.right.at(vG_buf.top())), false);
+ vG_buf.pop();
+ }
+
+ }
+
+ put(diG, iG_bimap.left.at(m), false);
+ put(dvG, vG_bimap.left.at(m), false);
+
+ }
+ }
+ }
+
+} // namespace detail
+
+
+
+template <typename Coll, typename Seq>
+struct tree_collector
+{
+
+public:
+ BOOST_CONCEPT_ASSERT((BackInsertionSequence<Coll>));
+ BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>));
+ BOOST_CONCEPT_ASSERT((CopyConstructible<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));
+
+ tree_collector(Coll& seqs): mSeqs(seqs) { }
+
+ inline void operator()(Seq seq)
+ { mSeqs.push_back(seq); }
+
+private:
+ Coll& mSeqs;
+
+};
+
+
+
+template <
+ typename Graph,
+ typename Order,
+ typename Func,
+ typename Seq
+>
+BOOST_CONCEPT_REQUIRES(
+ ((RandomAccessContainer<Order>))
+ ((IncidenceGraphConcept<Graph>))
+ ((UnaryFunction<Func, void, Seq>))
+ ((Mutable_RandomAccessContainer<Seq>))
+ ((VertexAndEdgeListGraphConcept<Graph>)),
+ (void)
+)
+two_graphs_common_spanning_trees
+ (
+ const Graph& iG,
+ Order iG_map,
+ const Graph& vG,
+ Order vG_map,
+ Func func,
+ Seq inL
+ )
+{
+ typedef graph_traits<Graph> GraphTraits;
+
+ typedef typename GraphTraits::directed_category directed_category;
+ typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
+ typedef typename GraphTraits::edge_descriptor edge_descriptor;
+
+ typedef typename GraphTraits::edges_size_type edges_size_type;
+ typedef typename GraphTraits::edge_iterator edge_iterator;
+
+ typedef typename Seq::const_iterator seq_const_iterator;
+ typedef typename Seq::difference_type seq_diff_type;
+ typedef typename Seq::value_type seq_value_type;
+ typedef typename Seq::size_type seq_size_type;
+ typedef typename Seq::iterator seq_iterator;
+
+ typedef typename Order::const_iterator order_const_iterator;
+ typedef typename Order::difference_type order_diff_type;
+ typedef typename Order::value_type order_value_type;
+ typedef typename Order::size_type order_size_type;
+ typedef typename Order::iterator order_iterator;
+
+ BOOST_STATIC_ASSERT((is_same<order_value_type, edge_descriptor>::value));
+ BOOST_CONCEPT_ASSERT((Convertible<order_size_type, edges_size_type>));
+
+ BOOST_CONCEPT_ASSERT((Convertible<seq_size_type, edges_size_type>));
+ BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value));
+
+ BOOST_STATIC_ASSERT((is_same<directed_category, undirected_tag>::value));
+
+ if(num_vertices(iG) != num_vertices(vG))
+ return;
+
+ if(inL.size() != num_edges(iG)
+ || inL.size() != num_edges(vG))
+ return;
+
+ if(iG_map.size() != num_edges(iG)
+ || vG_map.size() != num_edges(vG))
+ return;
+
+ typedef bimaps::bimap<
+ bimaps::set_of< int >,
+ bimaps::set_of< order_value_type >
+ > bimap_type;
+ typedef typename bimap_type::value_type bimap_value;
+
+ bimap_type iG_bimap, vG_bimap;
+ for(order_size_type i = 0; i < iG_map.size(); ++i)
+ iG_bimap.insert(bimap_value(i, iG_map[i]));
+ for(order_size_type i = 0; i < vG_map.size(); ++i)
+ vG_bimap.insert(bimap_value(i, vG_map[i]));
+
+ edge_iterator current, last;
+ tie(current, last) = edges(iG);
+ for(; current != last; ++current)
+ if(iG_bimap.right.find(*current) == iG_bimap.right.end())
+ return;
+ tie(current, last) = edges(vG);
+ for(; current != last; ++current)
+ if(vG_bimap.right.find(*current) == vG_bimap.right.end())
+ return;
+
+ std::stack<edge_descriptor> iG_buf, vG_buf;
+
+ std::map<vertex_descriptor, edge_descriptor> tree_map;
+ std::map<vertex_descriptor, vertex_descriptor> pred_map;
+ std::map<vertex_descriptor, int> dist_map, low_map;
+
+ detail::bridges_visitor<
+ associative_property_map<
+ std::map<vertex_descriptor, edge_descriptor>
+ >,
+ associative_property_map<
+ std::map<vertex_descriptor, vertex_descriptor>
+ >,
+ associative_property_map< std::map<vertex_descriptor, int> >,
+ associative_property_map< std::map<vertex_descriptor, int> >,
+ std::stack<edge_descriptor>
+ >
+ iG_vis(
+ associative_property_map<
+ std::map< vertex_descriptor, edge_descriptor> >(tree_map),
+ associative_property_map<
+ std::map< vertex_descriptor, vertex_descriptor> >(pred_map),
+ associative_property_map<std::map< vertex_descriptor, int> >(dist_map),
+ associative_property_map<std::map< vertex_descriptor, int> >(low_map),
+ iG_buf
+ ),
+ vG_vis(
+ associative_property_map<
+ std::map< vertex_descriptor, edge_descriptor> >(tree_map),
+ associative_property_map<
+ std::map< vertex_descriptor, vertex_descriptor> >(pred_map),
+ associative_property_map<std::map< vertex_descriptor, int> >(dist_map),
+ associative_property_map<std::map< vertex_descriptor, int> >(low_map),
+ vG_buf
+ );
+
+ std::map<vertex_descriptor, default_color_type> vertex_color;
+ std::map<edge_descriptor, default_color_type> edge_color;
+
+ undirected_dfs(iG, iG_vis,
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+ undirected_dfs(vG, vG_vis,
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+
+ while(!iG_buf.empty()) {
+ inL[iG_bimap.right.at(iG_buf.top())] = true;
+ iG_buf.pop();
+ }
+ while(!vG_buf.empty()) {
+ inL[vG_bimap.right.at(vG_buf.top())] = true;
+ vG_buf.pop();
+ }
+
+ std::map<edge_descriptor, bool> iG_inL, vG_inL;
+ associative_property_map< std::map<edge_descriptor, bool> >
+ aiG_inL(iG_inL), avG_inL(vG_inL);
+
+ for(seq_size_type i = 0; i < inL.size(); ++i)
+ {
+ if(inL[i]) {
+ put(aiG_inL, iG_bimap.left.at(i), true);
+ put(avG_inL, vG_bimap.left.at(i), true);
+ } else {
+ put(aiG_inL, iG_bimap.left.at(i), false);
+ put(avG_inL, vG_bimap.left.at(i), false);
+ }
+ }
+
+ undirected_dfs(
+ make_filtered_graph(iG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(aiG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)),
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+ undirected_dfs(
+ make_filtered_graph(vG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(avG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)),
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+
+ if(iG_buf.empty() && vG_buf.empty()) {
+
+ std::map<edge_descriptor, bool> iG_deleted, vG_deleted;
+ associative_property_map< std::map<edge_descriptor, bool> > diG(iG_deleted);
+ associative_property_map< std::map<edge_descriptor, bool> > dvG(vG_deleted);
+
+ tie(current, last) = edges(iG);
+ for(; current != last; ++current)
+ put(diG, *current, false);
+ tie(current, last) = edges(vG);
+ for(; current != last; ++current)
+ put(dvG, *current, false);
+
+ for(seq_size_type j = 0; j < inL.size(); ++j) {
+ if(!inL[j]) {
+ put(aiG_inL, iG_bimap.left.at(j), true);
+ put(avG_inL, vG_bimap.left.at(j), true);
+
+ undirected_dfs(
+ make_filtered_graph(iG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(aiG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)),
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+ undirected_dfs(
+ make_filtered_graph(vG,
+ detail::inL_edge_status< associative_property_map<
+ std::map<edge_descriptor, bool> > >(avG_inL)),
+ make_dfs_visitor(
+ detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)),
+ associative_property_map<
+ std::map<vertex_descriptor, default_color_type> >(vertex_color),
+ associative_property_map<
+ std::map<edge_descriptor, default_color_type> >(edge_color)
+ );
+
+ if(!iG_buf.empty() || !vG_buf.empty()) {
+ while(!iG_buf.empty()) iG_buf.pop();
+ while(!vG_buf.empty()) vG_buf.pop();
+ put(diG, iG_bimap.left.at(j), true);
+ put(dvG, vG_bimap.left.at(j), true);
+ }
+
+ put(aiG_inL, iG_bimap.left.at(j), false);
+ put(avG_inL, vG_bimap.left.at(j), false);
+ }
+ }
+
+ int cc = 0;
+
+ std::map<vertex_descriptor, int> com_map;
+ cc += connected_components(
+ make_filtered_graph(iG,
+ detail::deleted_edge_status<associative_property_map<
+ std::map<edge_descriptor, bool> > >(diG)),
+ associative_property_map<std::map<vertex_descriptor, int> >(com_map)
+ );
+ cc += connected_components(
+ make_filtered_graph(vG,
+ detail::deleted_edge_status<associative_property_map<
+ std::map<edge_descriptor, bool> > >(dvG)),
+ associative_property_map< std::map<vertex_descriptor, int> >(com_map)
+ );
+
+ if(cc != 2)
+ return;
+
+ // REC
+ detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq,
+ associative_property_map< std::map<edge_descriptor, bool> > >
+ (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL);
+
+ }
+
+}
+
+
+template <
+ typename Graph,
+ typename Func,
+ typename Seq
+>
+BOOST_CONCEPT_REQUIRES(
+ ((IncidenceGraphConcept<Graph>))
+ ((EdgeListGraphConcept<Graph>)),
+ (void)
+)
+two_graphs_common_spanning_trees
+ (
+ const Graph& iG,
+ const Graph& vG,
+ Func func,
+ Seq inL
+ )
+{
+ typedef graph_traits<Graph> GraphTraits;
+
+ typedef typename GraphTraits::edge_descriptor edge_descriptor;
+ typedef typename GraphTraits::edges_size_type edges_size_type;
+ typedef typename GraphTraits::edge_iterator edge_iterator;
+
+ std::vector<edge_descriptor> iGO, vGO;
+ edge_iterator curr, last;
+
+ tie(curr, last) = edges(iG);
+ for(; curr != last; ++curr)
+ iGO.push_back(*curr);
+
+ tie(curr, last) = edges(vG);
+ for(; curr != last; ++curr)
+ vGO.push_back(*curr);
+
+ two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL);
+}
+
+
+} // namespace boost
+
+
+#endif // BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html 2012-04-10 15:51:59 EDT (Tue, 10 Apr 2012)
@@ -186,6 +186,11 @@
<LI><A
href="./random_spanning_tree.html"><tt>random_spanning_tree</tt></A>
</OL>
+ <LI>Algorithm for Common Spanning Trees of Two Graphs
+ <OL>
+ <LI><A
+ href="./two_graphs_common_spanning_trees.html"><tt>two_graphs_common_spanning_trees</tt></A>
+ </OL>
<LI>Connected Components Algorithms
<OL>
<LI>connected_components
Added: trunk/libs/graph/doc/two_graphs_common_spanning_trees.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/two_graphs_common_spanning_trees.html 2012-04-10 15:51:59 EDT (Tue, 10 Apr 2012)
@@ -0,0 +1,143 @@
+<html>
+<!--
+ 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
+-->
+<head>
+<title>Boost Graph Library: Two-Graphs Common Spanning Trees</title>
+<body bgcolo="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" alink="#ff0000">
+<img src="../../../boost.png" alt="C++ Boost" width="277" height="86">
+
+<br clear>
+
+<h1><tt><a name="sec:two-graphs-common-spanning-trees">Two-Graphs Common Spanning Trees (MRT Algorithm)</a></tt></h1>
+
+<p>
+The <b>MRT</b> algorithm, based on an academic article of <b>Mint</b>, <b>Read</b> and
+<b>Tarjan</b>, is an efficient algorithm for the common spanning tree problem.<br/>
+This kind of algorithm is widely used in electronics, being the basis of the
+analysis of electrical circuits. Another area of interest may be that of the
+networking.
+</p>
+
+<p>
+The proposed algorithm receives several arguments and works with callbacks.<br/>
+The prototypes are:
+</p>
+
+<p>
+<i>// Ordered Edges List</i>
+<pre>
+template < typename Graph, typename Order, typename Func, typename Seq >
+void two_graphs_common_spanning_trees
+ (
+ const Graph& iG,
+ Order iG_map,
+ const Graph& vG,
+ Order vG_map,
+ Func func,
+ Seq inL
+ )
+</pre>
+
+<i>// Unordered Edges List</i>
+<pre>
+template < typename Graph, typename Func, typename Seq >
+void two_graphs_common_spanning_trees
+ (
+ const Graph& iG,
+ const Graph& vG,
+ Func func,
+ Seq inL
+ )
+</pre>
+</p>
+
+<p>
+The problem of common spanning tree is easily described.<br/>
+Imagine we have two graphs that are represented as lists of edges. A common
+spanning tree is a set of indices that identifies a spanning tree for both
+the first and for the second of the two graphs. Despite it is easily accomplished
+with edge list representation for graphs, it is intuitively difficult to achieve
+with adjacency list representation. This is due to the fact that it is necessary
+to represent an edge with an absolute index.
+</p>
+<p>
+Note that the set of common spanning trees of the two graphs is a subset of
+the set of spanning trees of the first graph, as well as those of the second
+graph.
+</p>
+
+<h3>Where Defined</h3>
+
+<p>
+boost/graph/two_graphs_common_spanning_trees.hpp
+
+<h3>Parameters</h3>
+
+<tt>const Graph& iG, const Graph& vG</tt>
+<blockquote>
+These are the graphs to be analyzed.<br/>
+They must comply with the concepts VertexAndEdgeListGraphConcept and IncidenceGraphConcept.<br/>
+In addition, the directed_category should be of type undirected_tag.
+</blockquote>
+
+<tt>Order iG_map, Order vG_map</tt>
+<blockquote>
+These are lists of references to edges, that define the preferred order for access to the lists of edges.<br/>
+They must comply with the concept RandomAccessContainer.
+</blockquote>
+
+<tt>Func func</tt>
+<blockquote>
+This is a callback that is invoked by the algorithm for each common spanning tree found.<br/>
+It must comply with the concept UnaryFunction with void as return value, and an object of type <i>typeof(inL)</i> as argument.
+</blockquote>
+
+<tt>Seq inL[1]</tt>
+<blockquote>
+This is the way in which the edges are marked as belonging to the common spanning tree.<br/>
+It must comply with the concept Mutable_RandomAccessContainer. In addition, the value_type should be of type bool.
+If the i-th edge or <i>inL[i]</i> is true, then it belongs to the common spanning tree, otherwise it does not belong.
+</blockquote>
+
+<h3>Example</h3>
+
+<p>
+The file
+examples/two_graphs_common_spanning_trees.cpp
+contains an example of finding common spanning trees of two undirected graphs.
+</p>
+
+<h3>Notes</h3>
+
+<p>
+<a name="1">[1]</a><br/>
+ The presence of <i>inL</i> may seem senseless. The algorithm can use a vector of
+ placeholders internally generated. However, doing so has more flexibility on
+ the callback function. Moreover, being largely involved in the electronics
+ world, there are cases where some edges have to be forced in every tree (ie
+ you want to search all the trees that have the same root): With this
+ solution, the problem is easily solved.<br/>
+ Intuitively from the above, <i>inL</i> must be of a size equal to <i>(V-1)</i>, where
+ <i>V</i> is the number of vertices of the graph.
+</p>
+
+<br/>
+<hr>
+<table>
+<tr valign=top>
+<td nowrap>Copyright © 2012</td>
+<td>Michele Caini, (<a href="mailto:michele.caini_at_[hidden]">michele.caini_at_[hidden]</a>)</td>
+</tr>
+</table>
+
+</body>
+</html>
Modified: trunk/libs/graph/example/Jamfile.v2
==============================================================================
--- trunk/libs/graph/example/Jamfile.v2 (original)
+++ trunk/libs/graph/example/Jamfile.v2 2012-04-10 15:51:59 EDT (Tue, 10 Apr 2012)
@@ -38,3 +38,4 @@
exe undirected_adjacency_list : undirected_adjacency_list.cpp ;
exe directed_graph : directed_graph.cpp ;
exe undirected_graph : undirected_graph.cpp ;
+exe two_graphs_common_spanning_trees : two_graphs_common_spanning_trees.cpp ;
Added: trunk/libs/graph/example/two_graphs_common_spanning_trees.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/two_graphs_common_spanning_trees.cpp 2012-04-10 15:51:59 EDT (Tue, 10 Apr 2012)
@@ -0,0 +1,94 @@
+// 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/graph/adjacency_list.hpp>
+#include <boost/graph/two_graphs_common_spanning_trees.hpp>
+#include <exception>
+#include <vector>
+
+
+using namespace std;
+
+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;
+
+
+int main(int argc, char **argv)
+{
+ Graph iG, vG;
+ vector< edge_descriptor > iG_o;
+ vector< edge_descriptor > vG_o;
+
+ iG_o.push_back(boost::add_edge(0, 1, iG).first);
+ iG_o.push_back(boost::add_edge(0, 2, iG).first);
+ iG_o.push_back(boost::add_edge(0, 3, iG).first);
+ iG_o.push_back(boost::add_edge(0, 4, iG).first);
+ iG_o.push_back(boost::add_edge(1, 2, iG).first);
+ iG_o.push_back(boost::add_edge(3, 4, iG).first);
+
+ vG_o.push_back(boost::add_edge(1, 2, vG).first);
+ vG_o.push_back(boost::add_edge(2, 0, vG).first);
+ vG_o.push_back(boost::add_edge(2, 3, vG).first);
+ vG_o.push_back(boost::add_edge(4, 3, vG).first);
+ vG_o.push_back(boost::add_edge(0, 3, vG).first);
+ vG_o.push_back(boost::add_edge(0, 4, vG).first);
+
+ vector<bool> inL(iG_o.size(), false);
+
+ std::vector< std::vector<bool> > coll;
+ boost::tree_collector<
+ std::vector< std::vector<bool> >,
+ std::vector<bool>
+ > tree_collector(coll);
+ boost::two_graphs_common_spanning_trees
+ (
+ iG,
+ iG_o,
+ vG,
+ vG_o,
+ tree_collector,
+ inL
+ );
+
+ std::vector< std::vector<bool> >::iterator it;
+ for(it = coll.begin(); it != coll.end(); ++it) {
+ // Here you can play with the trees that the algorithm has found.
+ }
+
+ return 0;
+}
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2012-04-10 15:51:59 EDT (Tue, 10 Apr 2012)
@@ -119,6 +119,7 @@
[ compile grid_graph_cc.cpp ]
[ run grid_graph_test.cpp ]
[ run incremental_components_test.cpp ]
+ [ run two_graphs_common_spanning_trees_test.cpp ]
[ run random_spanning_tree_test.cpp ../build//boost_graph ]
[ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ]
[ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
Added: trunk/libs/graph/test/two_graphs_common_spanning_trees_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/two_graphs_common_spanning_trees_test.cpp 2012-04-10 15:51:59 EDT (Tue, 10 Apr 2012)
@@ -0,0 +1,148 @@
+// 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;
+}