[857] | 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*/
|
---|