]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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*/ |