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

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-07-07 15:41:15

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 <boost/config.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>

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 <typename Edge, typename Graph>
    void back_edge(const Edge& u, Graph&) { m_back_edges.push_back(u); }
    
    template <typename Vertex, typename Graph> 
    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 <typename VertexListGraph, typename OutputIterator,
    typename P, typename T, typename R>
  void best_case_topological_sort(VertexListGraph& g, OutputIterator
result,
                        const bgl_named_params<P, T, R>& params)
  {
    typedef best_case_topo_sort_visitor<OutputIterator> TopoVisitor;
    depth_first_search(g, params.visitor(TopoVisitor(result)));
  }

  template <typename VertexListGraph, typename OutputIterator>
  void best_case_topological_sort(VertexListGraph& g, OutputIterator
result)
  {
    best_case_topological_sort(g, result, 
                     bgl_named_params<int, buffer_param_t>(0)); // bogus
  }

} // namespace boost

#endif /*BOOST_GRAPH_BEST_CASE_TOPOLOGICAL_SORT_H*/
 
> 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
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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users