ceph/src/boost/libs/graph/example/two_graphs_common_spanning_trees.cpp

   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/graph/adjacency_list.hpp>
  13 #include <boost/graph/two_graphs_common_spanning_trees.hpp>
  14 #include <exception>
  15 #include <vector>
  16
  17
  18 using namespace std;
  19
  20 typedef
  21 boost::adjacency_list
  22   <
  23     boost::vecS,         // OutEdgeList
  24     boost::vecS,         // VertexList
  25     boost::undirectedS,  // Directed
  26     boost::no_property,  // VertexProperties
  27     boost::no_property,  // EdgeProperties
  28     boost::no_property,  // GraphProperties
  29     boost::listS         // EdgeList
  30   >
  31 Graph
  32 ;
  33
  34 typedef
  35 boost::graph_traits<Graph>::vertex_descriptor
  36 vertex_descriptor;
  37
  38 typedef
  39 boost::graph_traits<Graph>::edge_descriptor
  40 edge_descriptor;
  41
  42 typedef
  43 boost::graph_traits<Graph>::vertex_iterator
  44 vertex_iterator;
  45
  46 typedef
  47 boost::graph_traits<Graph>::edge_iterator
  48 edge_iterator;
  49
  50
  51 int main(int argc, char **argv)
  52 {
  53   Graph iG, vG;
  54   vector< edge_descriptor > iG_o;
  55   vector< edge_descriptor > vG_o;
  56
  57   iG_o.push_back(boost::add_edge(0, 1, iG).first);
  58   iG_o.push_back(boost::add_edge(0, 2, iG).first);
  59   iG_o.push_back(boost::add_edge(0, 3, iG).first);
  60   iG_o.push_back(boost::add_edge(0, 4, iG).first);
  61   iG_o.push_back(boost::add_edge(1, 2, iG).first);
  62   iG_o.push_back(boost::add_edge(3, 4, iG).first);
  63
  64   vG_o.push_back(boost::add_edge(1, 2, vG).first);
  65   vG_o.push_back(boost::add_edge(2, 0, vG).first);
  66   vG_o.push_back(boost::add_edge(2, 3, vG).first);
  67   vG_o.push_back(boost::add_edge(4, 3, vG).first);
  68   vG_o.push_back(boost::add_edge(0, 3, vG).first);
  69   vG_o.push_back(boost::add_edge(0, 4, vG).first);
  70
  71   vector<bool> inL(iG_o.size(), false);
  72
  73   std::vector< std::vector<bool> > coll;
  74   boost::tree_collector<
  75       std::vector< std::vector<bool> >,
  76       std::vector<bool>
  77     > tree_collector(coll);
  78   boost::two_graphs_common_spanning_trees
  79     (
  80       iG,
  81       iG_o,
  82       vG,
  83       vG_o,
  84       tree_collector,
  85       inL
  86     );
  87
  88   std::vector< std::vector<bool> >::iterator it;
  89   for(it = coll.begin(); it != coll.end(); ++it) {
  90     // Here you can play with the trees that the algorithm has found.
  91   }
  92
  93   return 0;
  94 }