Line data    Source code

       1             : //
       2             : //=======================================================================
       3             : // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
       4             : // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
       5             : //
       6             : // Distributed under the Boost Software License, Version 1.0. (See
       7             : // accompanying file LICENSE_1_0.txt or copy at
       8             : // http://www.boost.org/LICENSE_1_0.txt)
       9             : //=======================================================================
      10             : //
      11             : #ifndef BOOST_GRAPH_TOPOLOGICAL_SORT_HPP
      12             : #define BOOST_GRAPH_TOPOLOGICAL_SORT_HPP
      13             : 
      14             : #include <boost/config.hpp>
      15             : #include <boost/property_map/property_map.hpp>
      16             : #include <boost/graph/depth_first_search.hpp>
      17             : #include <boost/graph/visitors.hpp>
      18             : #include <boost/graph/exception.hpp>
      19             : #include <boost/throw_exception.hpp>
      20             : 
      21             : namespace boost { 
      22             : 
      23             : 
      24             :   // Topological sort visitor
      25             :   //
      26             :   // This visitor merely writes the linear ordering into an
      27             :   // OutputIterator. The OutputIterator could be something like an
      28             :   // ostream_iterator, or it could be a back/front_insert_iterator.
      29             :   // Note that if it is a back_insert_iterator, the recorded order is
      30             :   // the reverse topological order. On the other hand, if it is a
      31             :   // front_insert_iterator, the recorded order is the topological
      32             :   // order.
      33             :   //
      34             :   template <typename OutputIterator>
      35             :   struct topo_sort_visitor : public dfs_visitor<>
      36             :   {
      37           0 :     topo_sort_visitor(OutputIterator _iter)
      38           0 :       : m_iter(_iter) { }
      39             :     
      40             :     template <typename Edge, typename Graph>
      41             :     void back_edge(const Edge&, Graph&) { BOOST_THROW_EXCEPTION(not_a_dag()); }
      42             :     
      43             :     template <typename Vertex, typename Graph> 
      44           0 :     void finish_vertex(const Vertex& u, Graph&) { *m_iter++ = u; }
      45             :     
      46             :     OutputIterator m_iter;
      47             :   };
      48             : 
      49             : 
      50             :   // Topological Sort
      51             :   //
      52             :   // The topological sort algorithm creates a linear ordering
      53             :   // of the vertices such that if edge (u,v) appears in the graph,
      54             :   // then u comes before v in the ordering. The graph must
      55             :   // be a directed acyclic graph (DAG). The implementation
      56             :   // consists mainly of a call to depth-first search.
      57             :   //
      58             : 
      59             :   template <typename VertexListGraph, typename OutputIterator,
      60             :     typename P, typename T, typename R>
      61           0 :   void topological_sort(VertexListGraph& g, OutputIterator result,
      62             :                         const bgl_named_params<P, T, R>& params)
      63             :   {
      64             :     typedef topo_sort_visitor<OutputIterator> TopoVisitor;
      65           0 :     depth_first_search(g, params.visitor(TopoVisitor(result)));
      66             :   }
      67             : 
      68             :   template <typename VertexListGraph, typename OutputIterator>
      69           0 :   void topological_sort(VertexListGraph& g, OutputIterator result)
      70             :   {
      71           0 :     topological_sort(g, result, 
      72             :                      bgl_named_params<int, buffer_param_t>(0)); // bogus
      73             :   }
      74             : 
      75             : } // namespace boost
      76             : 
      77             : #endif /*BOOST_GRAPH_TOPOLOGICAL_SORT_H*/