http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/boost/graph/topological_sort.hpp

// //======================================================================= // 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.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/visitors.hpp> #include <boost/graph/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& u, Graph&) { throw 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*/