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 {
topo_sort_visitorboost::topo_sort_visitor37 topo_sort_visitor(OutputIterator _iter) : m_iter(_iter) {}
38
39 template < typename Edge, typename Graph >
back_edgeboost::topo_sort_visitor40 void back_edge(const Edge&, Graph&)
41 {
42 BOOST_THROW_EXCEPTION(not_a_dag());
43 }
44
45 template < typename Vertex, typename Graph >
finish_vertexboost::topo_sort_visitor46 void finish_vertex(const Vertex& u, Graph&)
47 {
48 *m_iter++ = u;
49 }
50
51 OutputIterator m_iter;
52 };
53
54 // Topological Sort
55 //
56 // The topological sort algorithm creates a linear ordering
57 // of the vertices such that if edge (u,v) appears in the graph,
58 // then u comes before v in the ordering. The graph must
59 // be a directed acyclic graph (DAG). The implementation
60 // consists mainly of a call to depth-first search.
61 //
62
63 template < typename VertexListGraph, typename OutputIterator, typename P,
64 typename T, typename R >
topological_sort(VertexListGraph & g,OutputIterator result,const bgl_named_params<P,T,R> & params)65 void topological_sort(VertexListGraph& g, OutputIterator result,
66 const bgl_named_params< P, T, R >& params)
67 {
68 typedef topo_sort_visitor< OutputIterator > TopoVisitor;
69 depth_first_search(g, params.visitor(TopoVisitor(result)));
70 }
71
72 template < typename VertexListGraph, typename OutputIterator >
topological_sort(VertexListGraph & g,OutputIterator result)73 void topological_sort(VertexListGraph& g, OutputIterator result)
74 {
75 topological_sort(
76 g, result, bgl_named_params< int, buffer_param_t >(0)); // bogus
77 }
78
79 } // namespace boost
80
81 #endif /*BOOST_GRAPH_TOPOLOGICAL_SORT_H*/
82