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