Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / topological_sort.hpp
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*/