123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196 |
- //=======================================================================
- // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
- //
- // 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)
- //=======================================================================
- /*
- IMPORTANT!!!
- ~~~~~~~~~~~~
- This example uses interfaces that have been deprecated and removed from Boost.Grpah.
- Someone needs to update it, as it does NOT compile.
- */
- #include <boost/config.hpp>
- #include <boost/concept/assert.hpp>
- #include <iostream>
- #include <fstream>
- #include <stack>
- #include <map>
- #include <boost/lexical_cast.hpp>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/depth_first_search.hpp>
- #include <boost/graph/graphviz.hpp>
- #include <boost/graph/copy.hpp>
- #include <boost/graph/reverse_graph.hpp>
- using namespace boost;
- template < typename OutputIterator >
- class back_edge_recorder : public default_dfs_visitor
- {
- public:
- back_edge_recorder(OutputIterator out):m_out(out) { }
- template < typename Edge, typename Graph >
- void back_edge(Edge e, const Graph &)
- {
- *m_out++ = e;
- }
- private:
- OutputIterator m_out;
- };
- // object generator function
- template < typename OutputIterator >
- back_edge_recorder < OutputIterator >
- make_back_edge_recorder(OutputIterator out)
- {
- return back_edge_recorder < OutputIterator > (out);
- }
- template < typename Graph, typename Loops > void
- find_loops(typename graph_traits < Graph >::vertex_descriptor entry,
- const Graph & g,
- Loops & loops) // A container of sets of vertices
- {
- BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));
- typedef typename graph_traits < Graph >::edge_descriptor Edge;
- std::vector < Edge > back_edges;
- std::vector < default_color_type > color_map(num_vertices(g));
- depth_first_visit(g, entry,
- make_back_edge_recorder(std::back_inserter(back_edges)),
- make_iterator_property_map(color_map.begin(),
- get(vertex_index, g), color_map[0]));
- for (typename std::vector < Edge >::size_type i = 0; i < back_edges.size(); ++i) {
- typename Loops::value_type x;
- loops.push_back(x);
- compute_loop_extent(back_edges[i], g, loops.back());
- }
- }
- template < typename Graph, typename Set > void
- compute_loop_extent(typename graph_traits <
- Graph >::edge_descriptor back_edge, const Graph & g,
- Set & loop_set)
- {
- BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));
- typedef typename graph_traits < Graph >::vertex_descriptor Vertex;
- typedef color_traits < default_color_type > Color;
- Vertex loop_head, loop_tail;
- loop_tail = source(back_edge, g);
- loop_head = target(back_edge, g);
- std::vector < default_color_type >
- reachable_from_head(num_vertices(g), Color::white());
- default_color_type c;
- depth_first_visit(g, loop_head, default_dfs_visitor(),
- make_iterator_property_map(reachable_from_head.begin(),
- get(vertex_index, g), c));
- std::vector < default_color_type > reachable_to_tail(num_vertices(g));
- reverse_graph < Graph > reverse_g(g);
- depth_first_visit(reverse_g, loop_tail, default_dfs_visitor(),
- make_iterator_property_map(reachable_to_tail.begin(),
- get(vertex_index, g), c));
- typename graph_traits < Graph >::vertex_iterator vi, vi_end;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- if (reachable_from_head[*vi] != Color::white()
- && reachable_to_tail[*vi] != Color::white())
- loop_set.insert(*vi);
- }
- int
- main(int argc, char *argv[])
- {
- if (argc < 3) {
- std::cerr << "usage: loops_dfs <in-file> <out-file>" << std::endl;
- return -1;
- }
- GraphvizDigraph g_in;
- read_graphviz(argv[1], g_in);
- typedef adjacency_list < vecS, vecS, bidirectionalS,
- GraphvizVertexProperty,
- GraphvizEdgeProperty, GraphvizGraphProperty > Graph;
- typedef graph_traits < Graph >::vertex_descriptor Vertex;
- Graph g;
- #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- // VC++ has trouble with the get_property() function
- get_property(g, graph_name) = "loops";
- #endif
- copy_graph(g_in, g);
- typedef std::set < Vertex > set_t;
- typedef std::list < set_t > list_of_sets_t;
- list_of_sets_t loops;
- Vertex entry = *vertices(g).first;
- find_loops(entry, g, loops);
- property_map<Graph, vertex_attribute_t>::type vattr_map = get(vertex_attribute, g);
- property_map<Graph, edge_attribute_t>::type eattr_map = get(edge_attribute, g);
- graph_traits < Graph >::edge_iterator ei, ei_end;
- for (list_of_sets_t::iterator i = loops.begin(); i != loops.end(); ++i) {
- std::vector < bool > in_loop(num_vertices(g), false);
- for (set_t::iterator j = (*i).begin(); j != (*i).end(); ++j) {
- vattr_map[*j]["color"] = "gray";
- in_loop[*j] = true;
- }
- for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
- if (in_loop[source(*ei, g)] && in_loop[target(*ei, g)])
- eattr_map[*ei]["color"] = "gray";
- }
- std::ofstream loops_out(argv[2]);
- #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- // VC++ has trouble with the get_property() functions
- loops_out << "digraph loops {\n"
- << "size=\"3,3\"\n"
- << "ratio=\"fill\"\n"
- << "shape=\"box\"\n";
- graph_traits<Graph>::vertex_iterator vi, vi_end;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- loops_out << *vi << "[";
- for (std::map<std::string,std::string>::iterator ai = vattr_map[*vi].begin();
- ai != vattr_map[*vi].end(); ++ai) {
- loops_out << ai->first << "=" << ai->second;
- if (next(ai) != vattr_map[*vi].end())
- loops_out << ", ";
- }
- loops_out<< "]";
- }
- for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
- loops_out << source(*ei, g) << " -> " << target(*ei, g) << "[";
- std::map<std::string,std::string>& attr_map = eattr_map[*ei];
- for (std::map<std::string,std::string>::iterator eai = attr_map.begin();
- eai != attr_map.end(); ++eai) {
- loops_out << eai->first << "=" << eai->second;
- if (next(eai) != attr_map.end())
- loops_out << ", ";
- }
- loops_out<< "]";
- }
- loops_out << "}\n";
- #else
- get_property(g, graph_graph_attribute)["size"] = "3,3";
- get_property(g, graph_graph_attribute)["ratio"] = "fill";
- get_property(g, graph_vertex_attribute)["shape"] = "box";
- write_graphviz(loops_out, g,
- make_vertex_attributes_writer(g),
- make_edge_attributes_writer(g),
- make_graph_attributes_writer(g));
- #endif
- return 0;
- }
|