| // |
| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| // |
| #ifndef BOOST_GRAPH_TOPOLOGICAL_SORT_HPP |
| #define BOOST_GRAPH_TOPOLOGICAL_SORT_HPP |
| |
| #include <boost/config.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/graph/depth_first_search.hpp> |
| #include <boost/graph/visitors.hpp> |
| #include <boost/graph/exception.hpp> |
| #include <boost/throw_exception.hpp> |
| |
| namespace boost { |
| |
| |
| // Topological sort visitor |
| // |
| // This visitor merely writes the linear ordering into an |
| // OutputIterator. The OutputIterator could be something like an |
| // ostream_iterator, or it could be a back/front_insert_iterator. |
| // Note that if it is a back_insert_iterator, the recorded order is |
| // the reverse topological order. On the other hand, if it is a |
| // front_insert_iterator, the recorded order is the topological |
| // order. |
| // |
| template <typename OutputIterator> |
| struct topo_sort_visitor : public dfs_visitor<> |
| { |
| topo_sort_visitor(OutputIterator _iter) |
| : m_iter(_iter) { } |
| |
| template <typename Edge, typename Graph> |
| void back_edge(const Edge&, Graph&) { BOOST_THROW_EXCEPTION(not_a_dag()); } |
| |
| template <typename Vertex, typename Graph> |
| void finish_vertex(const Vertex& u, Graph&) { *m_iter++ = u; } |
| |
| OutputIterator m_iter; |
| }; |
| |
| |
| // Topological Sort |
| // |
| // The topological sort algorithm creates a linear ordering |
| // of the vertices such that if edge (u,v) appears in the graph, |
| // then u comes before v in the ordering. The graph must |
| // be a directed acyclic graph (DAG). The implementation |
| // consists mainly of a call to depth-first search. |
| // |
| |
| template <typename VertexListGraph, typename OutputIterator, |
| typename P, typename T, typename R> |
| void topological_sort(VertexListGraph& g, OutputIterator result, |
| const bgl_named_params<P, T, R>& params) |
| { |
| typedef topo_sort_visitor<OutputIterator> TopoVisitor; |
| depth_first_search(g, params.visitor(TopoVisitor(result))); |
| } |
| |
| template <typename VertexListGraph, typename OutputIterator> |
| void topological_sort(VertexListGraph& g, OutputIterator result) |
| { |
| topological_sort(g, result, |
| bgl_named_params<int, buffer_param_t>(0)); // bogus |
| } |
| |
| } // namespace boost |
| |
| #endif /*BOOST_GRAPH_TOPOLOGICAL_SORT_H*/ |