197 lines
6.6 KiB
C++
197 lines
6.6 KiB
C++
//=======================================================================
|
|
// 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;
|
|
}
|