...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

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 =all defaults)

The topological sort algorithm creates a linear ordering of the
vertices such that if edge *(u,v)* appears in the graph, then
*v* comes before *u* in the ordering. The graph must be a
directed acyclic graph (DAG). The implementation consists mainly of a
call to `depth_first_search()`.

A directed acylic graph (DAG). The graph type must be a model of Vertex List Graph and Incidence Graph. If the graph is not a DAG then aOUT:not_a_dagexception will be thrown and the user should discard the contents ofresultrange.

Python: The parameter is namedgraph.

The vertex descriptors of the graph will be output to theresultoutput iterator inreversetopological order. The iterator type must model Output Iterator.

Python: This parameter is not used in Python. Instead, a Pythonlistcontaining the vertices in topological order is returned.

This is used by the algorithm to keep track of its progress through the graph. The typeIN:ColorMapmust be a model of Read/Write Property Map and its key type must be the graph's vertex descriptor type and the value type of the color map must model ColorValue.

Default:an iterator_property_map created from astd::vectorofdefault_color_typeof sizenum_vertices(g)and using thei_mapfor the index map.

Python: The color map must be avertex_color_mapfor the graph.

This maps each vertex to an integer in the range[0, num_vertices(g)). This parameter is only necessary when the default color property map is used. The typeVertexIndexMapmust be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default:get(vertex_index, g)Note: if you use this default, make sure your graph has an internalvertex_indexproperty. For example,adjacency_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

Python: Unsupported parameter.

Calculate a topological ordering of the vertices.

typedef adjacency_list< vecS, vecS, directedS, color_property<> > Graph; typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; Pair edges[6] = { Pair(0,1), Pair(2,4), Pair(2,5), Pair(0,3), Pair(1,4), Pair(4,3) }; Graph G(6, edges, edges + 6); typedef std::vector< Vertex > container; container c; topological_sort(G, std::back_inserter(c)); cout << "A topological ordering: "; for ( container::reverse_iterator ii=c.rbegin(); ii!=c.rend(); ++ii) cout << index(*ii) << " "; cout << endl;The output is:

A topological ordering: 2 5 0 1 4 3

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |