boost/graph/topological_sort.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_TOPOLOGICAL_SORT_HPP
0012 #define BOOST_GRAPH_TOPOLOGICAL_SORT_HPP
0013
0014 #include <boost/config.hpp>
0015 #include <boost/property_map/property_map.hpp>
0016 #include <boost/graph/depth_first_search.hpp>
0017 #include <boost/graph/visitors.hpp>
0018 #include <boost/graph/exception.hpp>
0019 #include <boost/throw_exception.hpp>
0020
0021 namespace boost
0022 {
0023
0024 // Topological sort visitor
0025 //
0026 // This visitor merely writes the linear ordering into an
0027 // OutputIterator. The OutputIterator could be something like an
0028 // ostream_iterator, or it could be a back/front_insert_iterator.
0029 // Note that if it is a back_insert_iterator, the recorded order is
0030 // the reverse topological order. On the other hand, if it is a
0031 // front_insert_iterator, the recorded order is the topological
0032 // order.
0033 //
0034 template < typename OutputIterator >
0035 struct topo_sort_visitor : public dfs_visitor<>
0036 {
0037     topo_sort_visitor(OutputIterator _iter) : m_iter(_iter) {}
0038
0039     template < typename Edge, typename Graph >
0040     void back_edge(const Edge&, Graph&)
0041     {
0042         BOOST_THROW_EXCEPTION(not_a_dag());
0043     }
0044
0045     template < typename Vertex, typename Graph >
0046     void finish_vertex(const Vertex& u, Graph&)
0047     {
0048         *m_iter++ = u;
0049     }
0050
0051     OutputIterator m_iter;
0052 };
0053
0054 // Topological Sort
0055 //
0056 // The topological sort algorithm creates a linear ordering
0057 // of the vertices such that if edge (u,v) appears in the graph,
0058 // then u comes before v in the ordering. The graph must
0059 // be a directed acyclic graph (DAG). The implementation
0060 // consists mainly of a call to depth-first search.
0061 //
0062
0063 template < typename VertexListGraph, typename OutputIterator, typename P,
0064     typename T, typename R >
0065 void topological_sort(VertexListGraph& g, OutputIterator result,
0066     const bgl_named_params< P, T, R >& params)
0067 {
0068     typedef topo_sort_visitor< OutputIterator > TopoVisitor;
0069     depth_first_search(g, params.visitor(TopoVisitor(result)));
0070 }
0071
0072 template < typename VertexListGraph, typename OutputIterator >
0073 void topological_sort(VertexListGraph& g, OutputIterator result)
0074 {
0075     topological_sort(
0076         g, result, bgl_named_params< int, buffer_param_t >(0)); // bogus
0077 }
0078
0079 } // namespace boost
0080
0081 #endif /*BOOST_GRAPH_TOPOLOGICAL_SORT_H*/