2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
11 #ifndef BOOST_GRAPH_TOPOLOGICAL_SORT_HPP
12 #define BOOST_GRAPH_TOPOLOGICAL_SORT_HPP
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>
23 // Topological sort visitor
25 // This visitor merely writes the linear ordering into an
26 // OutputIterator. The OutputIterator could be something like an
27 // ostream_iterator, or it could be a back/front_insert_iterator.
28 // Note that if it is a back_insert_iterator, the recorded order is
29 // the reverse topological order. On the other hand, if it is a
30 // front_insert_iterator, the recorded order is the topological
33 template <typename OutputIterator
>
34 struct topo_sort_visitor
: public dfs_visitor
<>
36 topo_sort_visitor(OutputIterator _iter
)
39 template <typename Edge
, typename Graph
>
40 void back_edge(const Edge
&, Graph
&) { throw not_a_dag(); }
42 template <typename Vertex
, typename Graph
>
43 void finish_vertex(const Vertex
& u
, Graph
&) { *m_iter
++ = u
; }
45 OutputIterator m_iter
;
51 // The topological sort algorithm creates a linear ordering
52 // of the vertices such that if edge (u,v) appears in the graph,
53 // then u comes before v in the ordering. The graph must
54 // be a directed acyclic graph (DAG). The implementation
55 // consists mainly of a call to depth-first search.
58 template <typename VertexListGraph
, typename OutputIterator
,
59 typename P
, typename T
, typename R
>
60 void topological_sort(VertexListGraph
& g
, OutputIterator result
,
61 const bgl_named_params
<P
, T
, R
>& params
)
63 typedef topo_sort_visitor
<OutputIterator
> TopoVisitor
;
64 depth_first_search(g
, params
.visitor(TopoVisitor(result
)));
67 template <typename VertexListGraph
, typename OutputIterator
>
68 void topological_sort(VertexListGraph
& g
, OutputIterator result
)
70 topological_sort(g
, result
,
71 bgl_named_params
<int, buffer_param_t
>(0)); // bogus
76 #endif /*BOOST_GRAPH_TOPOLOGICAL_SORT_H*/