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

   1 //=======================================================================
   2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
   3 //
   4 // Distributed under the Boost Software License, Version 1.0. (See
   5 // accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //=======================================================================
   8 #include <boost/config.hpp>
   9 #include <boost/concept/assert.hpp>
  10 #include <iostream>
  11 #include <fstream>
  12 #include <stack>
  13 #include <map>
  14 #include <boost/lexical_cast.hpp>
  15 #include <boost/graph/adjacency_list.hpp>
  16 #include <boost/graph/depth_first_search.hpp>
  17 #include <boost/graph/graphviz.hpp>
  18 #include <boost/graph/copy.hpp>
  19 #include <boost/graph/reverse_graph.hpp>
  20
  21 using namespace boost;
  22
  23 template < typename OutputIterator >
  24 class back_edge_recorder : public default_dfs_visitor
  25 {
  26 public:
  27   back_edge_recorder(OutputIterator out):m_out(out) { }
  28
  29   template < typename Edge, typename Graph >
  30   void back_edge(Edge e, const Graph &)
  31   {
  32     *m_out++ = e;
  33   }
  34 private:
  35   OutputIterator m_out;
  36 };
  37
  38 // object generator function
  39 template < typename OutputIterator >
  40 back_edge_recorder < OutputIterator >
  41 make_back_edge_recorder(OutputIterator out)
  42 {
  43   return back_edge_recorder < OutputIterator > (out);
  44 }
  45
  46 template < typename Graph, typename Loops > void
  47 find_loops(typename graph_traits < Graph >::vertex_descriptor entry,
  48            const Graph & g,
  49            Loops & loops)    // A container of sets of vertices
  50 {
  51   BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));
  52   typedef typename graph_traits < Graph >::edge_descriptor Edge;
  53   std::vector < Edge > back_edges;
  54   std::vector < default_color_type > color_map(num_vertices(g));
  55   depth_first_visit(g, entry,
  56                     make_back_edge_recorder(std::back_inserter(back_edges)),
  57                     make_iterator_property_map(color_map.begin(),
  58                                                get(vertex_index, g), color_map[0]));
  59
  60   for (typename std::vector < Edge >::size_type i = 0; i < back_edges.size(); ++i) {
  61     typename Loops::value_type x;
  62     loops.push_back(x);
  63     compute_loop_extent(back_edges[i], g, loops.back());
  64   }
  65 }
  66
  67 template < typename Graph, typename Set > void
  68 compute_loop_extent(typename graph_traits <
  69                     Graph >::edge_descriptor back_edge, const Graph & g,
  70                     Set & loop_set)
  71 {
  72   BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));
  73   typedef typename graph_traits < Graph >::vertex_descriptor Vertex;
  74   typedef color_traits < default_color_type > Color;
  75
  76   Vertex loop_head, loop_tail;
  77   loop_tail = source(back_edge, g);
  78   loop_head = target(back_edge, g);
  79
  80   std::vector < default_color_type >
  81     reachable_from_head(num_vertices(g), Color::white());
  82   default_color_type c;
  83   depth_first_visit(g, loop_head, default_dfs_visitor(),
  84                     make_iterator_property_map(reachable_from_head.begin(),
  85                                                get(vertex_index, g), c));
  86
  87   std::vector < default_color_type > reachable_to_tail(num_vertices(g));
  88   reverse_graph < Graph > reverse_g(g);
  89   depth_first_visit(reverse_g, loop_tail, default_dfs_visitor(),
  90                     make_iterator_property_map(reachable_to_tail.begin(),
  91                                                get(vertex_index, g), c));
  92
  93   typename graph_traits < Graph >::vertex_iterator vi, vi_end;
  94   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
  95     if (reachable_from_head[*vi] != Color::white()
  96         && reachable_to_tail[*vi] != Color::white())
  97       loop_set.insert(*vi);
  98 }
  99
 100
 101 int
 102 main(int argc, char *argv[])
 103 {
 104   if (argc < 3) {
 105     std::cerr << "usage: loops_dfs <in-file> <out-file>" << std::endl;
 106     return -1;
 107   }
 108   GraphvizDigraph g_in;
 109   read_graphviz(argv[1], g_in);
 110
 111   typedef adjacency_list < vecS, vecS, bidirectionalS,
 112     GraphvizVertexProperty,
 113     GraphvizEdgeProperty, GraphvizGraphProperty > Graph;
 114   typedef graph_traits < Graph >::vertex_descriptor Vertex;
 115
 116   Graph g;
 117 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
 118   // VC++ has trouble with the get_property() function
 119   get_property(g, graph_name) = "loops";
 120 #endif
 121
 122   copy_graph(g_in, g);
 123
 124   typedef std::set < Vertex > set_t;
 125   typedef std::list < set_t > list_of_sets_t;
 126   list_of_sets_t loops;
 127   Vertex entry = *vertices(g).first;
 128
 129   find_loops(entry, g, loops);
 130
 131   property_map<Graph, vertex_attribute_t>::type vattr_map = get(vertex_attribute, g);
 132   property_map<Graph, edge_attribute_t>::type eattr_map = get(edge_attribute, g);
 133   graph_traits < Graph >::edge_iterator ei, ei_end;
 134
 135   for (list_of_sets_t::iterator i = loops.begin(); i != loops.end(); ++i) {
 136     std::vector < bool > in_loop(num_vertices(g), false);
 137     for (set_t::iterator j = (*i).begin(); j != (*i).end(); ++j) {
 138       vattr_map[*j]["color"] = "gray";
 139       in_loop[*j] = true;
 140     }
 141     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
 142       if (in_loop[source(*ei, g)] && in_loop[target(*ei, g)])
 143         eattr_map[*ei]["color"] = "gray";
 144   }
 145
 146   std::ofstream loops_out(argv[2]);
 147 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
 148   // VC++ has trouble with the get_property() functions
 149   loops_out << "digraph loops {\n"
 150             << "size=\"3,3\"\n"
 151             << "ratio=\"fill\"\n"
 152             << "shape=\"box\"\n";
 153   graph_traits<Graph>::vertex_iterator vi, vi_end;
 154   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
 155     loops_out << *vi << "[";
 156     for (std::map<std::string,std::string>::iterator ai = vattr_map[*vi].begin();
 157          ai != vattr_map[*vi].end(); ++ai) {
 158       loops_out << ai->first << "=" << ai->second;
 159       if (next(ai) != vattr_map[*vi].end())
 160         loops_out << ", ";
 161     }
 162     loops_out<< "]";
 163   }
 164
 165   for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
 166     loops_out << source(*ei, g) << " -> " << target(*ei, g) << "[";
 167     std::map<std::string,std::string>& attr_map = eattr_map[*ei];
 168     for (std::map<std::string,std::string>::iterator eai = attr_map.begin();
 169          eai != attr_map.end(); ++eai) {
 170       loops_out << eai->first << "=" << eai->second;
 171       if (next(eai) != attr_map.end())
 172         loops_out << ", ";
 173     }
 174     loops_out<< "]";
 175   }
 176   loops_out << "}\n";
 177 #else
 178   get_property(g, graph_graph_attribute)["size"] = "3,3";
 179   get_property(g, graph_graph_attribute)["ratio"] = "fill";
 180   get_property(g, graph_vertex_attribute)["shape"] = "box";
 181
 182   write_graphviz(loops_out, g,
 183                  make_vertex_attributes_writer(g),
 184                  make_edge_attributes_writer(g),
 185                  make_graph_attributes_writer(g));
 186 #endif
 187   return 0;
 188 }