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
21namespace 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

source code of boost/boost/graph/topological_sort.hpp