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 | topo_sort_visitor(OutputIterator _iter) |
38 | : 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 | 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 | 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 | depth_first_search(g, params.visitor(TopoVisitor(result))); |
66 | } |
67 | |
68 | template <typename VertexListGraph, typename OutputIterator> |
69 | void topological_sort(VertexListGraph& g, OutputIterator result) |
70 | { |
71 | 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*/ |
78 | |