Re: [Boost-users] BGL Question/Advice which algorithm to use

7 Jul 2005

      ...
Hi Elisha,
On Jul 6, 2005, at 6:12 PM, Elisha Berns wrote:
...
Ideally I do a topological sort to find the most dependent vertex
(if
that makes sense) which then becomes the root of an n-ary tree, and
then
build the tree from that vertex recursively finding the out-edges of
child vertices.  All that works provided the graph is actually a
DAG.
But sometimes it isn't because there can be small cycles(?) inside
Doug,

Thanks for the reply.  As I am still relatively a novice at graph
algorithms I am still trying to  decipher parts of your response.
Regarding your suggestion to modify the topological sort code, it looks
like only the topological sort visitor needs modification, and seemingly
just removing the exception throwing.  Anyways this is what I came up
with, best_case_topological_sort method that just stores the back edges
should they be needed later.  It looks like this (comments please if
this is what you intended):

Thanks,

#ifndef BOOST_GRAPH_BEST_CASE_TOPOLOGICAL_SORT_HPP
#define BOOST_GRAPH_BEST_CASE_TOPOLOGICAL_SORT_HPP

#include <list>
#include 
#include 
#include 
#include 

namespace boost { 

  // Best case topological sort visitor
  //
  // This visitor merely writes the linear ordering into an
  // OutputIterator. The OutputIterator could be something like an
  // ostream_iterator, or it could be a back/front_insert_iterator.
  // Note that if it is a back_insert_iterator, the recorded order is
  // the reverse topological order. On the other hand, if it is a
  // front_insert_iterator, the recorded order is the topological
  // order.
  //
  template <typename OutputIterator>
  struct best_case_topo_sort_visitor : public dfs_visitor<>
  {
    best_case_topo_sort_visitor(OutputIterator _iter)
      : m_iter(_iter) { }

    template 
    void back_edge(const Edge& u, Graph&) { m_back_edges.push_back(u); }

    template  
    void finish_vertex(const Vertex& u, Graph&) { *m_iter++ = u; }

    OutputIterator m_iter;

	typedef std::list<Edge> EdgeList;
	EdgeList m_back_edges;
  };

  // Topological Sort
  //
  // The topological sort algorithm creates a linear ordering
  // of the vertices such that if edge (u,v) appears in the graph,
  // then u comes before v in the ordering. The graph must
  // be a directed acyclic graph (DAG). The implementation
  // consists mainly of a call to depth-first search.
  //

  template 
  void best_case_topological_sort(VertexListGraph& g, OutputIterator
result,
                        const bgl_named_params& params)
  {
    typedef best_case_topo_sort_visitor<OutputIterator> TopoVisitor;
    depth_first_search(g, params.visitor(TopoVisitor(result)));
  }

  template 
  void best_case_topological_sort(VertexListGraph& g, OutputIterator
result)
  {
    best_case_topological_sort(g, result, 
                     bgl_named_params(0)); // bogus
  }

} // namespace boost

#endif /*BOOST_GRAPH_BEST_CASE_TOPOLOGICAL_SORT_H*/

the
...
...
graph where one vertex refers to its parent's parent's vertex.  So
everything in the graph can be suitable for a DAG except for this
small
set of vertices that becomes self-referential.
One thing I've done in the past was to run the strong_components
algorithm first to detect all of the strongly-connected components
(SCCs). Then, I built another graph with one vertex for each SCC and,
finally, run the topological sort on this new graph.
However, I think my problem was a little different from yours, because
I expected there to be many fewer SCCs than vertices. Since you
mentioned that you have only a few, small cycles, there are other
options. The first option is to copy most of the topological_sort code
but ignore back edges. Another alternative is to use a
filtered_graph<>
to filter out any back edges.
Doug
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users