|
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.hpp> |
|
16 #include <boost/graph/depth_first_search.hpp> |
|
17 #include <boost/graph/visitors.hpp> |
|
18 #include <boost/graph/exception.hpp> |
|
19 |
|
20 namespace boost { |
|
21 |
|
22 |
|
23 // Topological sort visitor |
|
24 // |
|
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 |
|
31 // order. |
|
32 // |
|
33 template <typename OutputIterator> |
|
34 struct topo_sort_visitor : public dfs_visitor<> |
|
35 { |
|
36 topo_sort_visitor(OutputIterator _iter) |
|
37 : m_iter(_iter) { } |
|
38 |
|
39 template <typename Edge, typename Graph> |
|
40 void back_edge(const Edge& u, Graph&) { throw not_a_dag(); } |
|
41 |
|
42 template <typename Vertex, typename Graph> |
|
43 void finish_vertex(const Vertex& u, Graph&) { *m_iter++ = u; } |
|
44 |
|
45 OutputIterator m_iter; |
|
46 }; |
|
47 |
|
48 |
|
49 // Topological Sort |
|
50 // |
|
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. |
|
56 // |
|
57 |
|
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) |
|
62 { |
|
63 typedef topo_sort_visitor<OutputIterator> TopoVisitor; |
|
64 depth_first_search(g, params.visitor(TopoVisitor(result))); |
|
65 } |
|
66 |
|
67 template <typename VertexListGraph, typename OutputIterator> |
|
68 void topological_sort(VertexListGraph& g, OutputIterator result) |
|
69 { |
|
70 topological_sort(g, result, |
|
71 bgl_named_params<int, buffer_param_t>(0)); // bogus |
|
72 } |
|
73 |
|
74 } // namespace boost |
|
75 |
|
76 #endif /*BOOST_GRAPH_TOPOLOGICAL_SORT_H*/ |