Boost logo

Boost Users :

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


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):



#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
                        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
    best_case_topological_sort(g, result,
                     bgl_named_params<int, buffer_param_t>(0)); // bogus

} // namespace boost

> 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
> > 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
> > But sometimes it isn't because there can be small cycles(?) inside
> > 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
> > 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
> to filter out any back edges.
> Doug
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at