1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 2000 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<Head> 10<Title>Boost Graph Library: Topological Sort</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18 19<H1><A NAME="sec:topological-sort"> 20<img src="figs/python.gif" alt="(Python)"/> 21<TT>topological_sort</TT> 22</H1> 23 24<PRE> 25template <typename VertexListGraph, typename OutputIterator, 26 typename P, typename T, typename R> 27void topological_sort(VertexListGraph& g, OutputIterator result, 28 const bgl_named_params<P, T, R>& params = <i>all defaults</i>) 29</PRE> 30 31<P> 32The topological sort algorithm creates a linear ordering of the 33vertices such that if edge <i>(u,v)</i> appears in the graph, then 34<i>v</i> comes before <i>u</i> in the ordering. The graph must be a 35directed acyclic graph (DAG). The implementation consists mainly of a 36call to <a 37href="./depth_first_search.html"><tt>depth_first_search()</tt></a>. 38</p> 39 40<h3>Where Defined:</h3> 41<a href="../../../boost/graph/topological_sort.hpp"><TT>boost/graph/topological_sort.hpp</TT></a> 42 43<h3>Parameters</h3> 44 45IN: <tt>VertexListGraph& g</tt> 46<blockquote> 47 A directed acylic graph (DAG). The graph type must 48 be a model of <a href="./VertexListGraph.html">Vertex List Graph</a> 49 and <a href="./IncidenceGraph.html">Incidence Graph</a>. 50 If the graph is not a DAG then a <a href="./exception.html#not_a_dag"><tt>not_a_dag</tt></a> 51 exception will be thrown and the 52 user should discard the contents of <tt>result</tt> range.<br> 53 <b>Python</b>: The parameter is named <tt>graph</tt>. 54</blockquote> 55 56OUT: <tt>OutputIterator result</tt> 57<blockquote> 58The vertex descriptors of the graph will be output to the 59<TT>result</TT> output iterator in <b>reverse</b> topological order. The 60iterator type must model <a 61href="http://www.boost.org/sgi/stl/OutputIterator.html">Output 62Iterator</a>.<br> 63 64<b>Python</b>: This parameter is not used in Python. Instead, a 65Python <tt>list</tt> containing the vertices in topological order is 66returned. 67</blockquote> 68 69<h3>Named Parameters</h3> 70 71UTIL/OUT: <tt>color_map(ColorMap color)</tt> 72<blockquote> 73 This is used by the algorithm to keep track of its progress through 74 the graph. The type <tt>ColorMap</tt> must be a model of <a 75 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 76 Property Map</a> and its key type must be the graph's vertex 77 descriptor type and the value type of the color map must model 78 <a href="./ColorValue.html">ColorValue</a>.<br> 79 <b>Default:</b> an <a 80 href="../../property_map/doc/iterator_property_map.html"> 81 </tt>iterator_property_map</tt></a> created from a 82 <tt>std::vector</tt> of <tt>default_color_type</tt> of size 83 <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index 84 map.<br> 85 86 <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for 87 the graph. 88</blockquote> 89 90IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> 91<blockquote> 92 This maps each vertex to an integer in the range <tt>[0, 93 num_vertices(g))</tt>. This parameter is only necessary when the 94 default color property map is used. The type <tt>VertexIndexMap</tt> 95 must be a model of <a 96 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 97 Map</a>. The value type of the map must be an integer type. The 98 vertex descriptor type of the graph needs to be usable as the key 99 type of the map.<br> 100 101 <b>Default:</b> <tt>get(vertex_index, g)</tt> 102 Note: if you use this default, make sure your graph has 103 an internal <tt>vertex_index</tt> property. For example, 104 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 105 not have an internal <tt>vertex_index</tt> property. 106 <br> 107 108 <b>Python</b>: Unsupported parameter. 109</blockquote> 110 111 112<H3>Complexity</H3> 113 114The time complexity is <i>O(V + E)</i>. 115 116 117<H3>Example</H3> 118 119<P> 120Calculate a topological ordering of the vertices. 121 122<P> 123<PRE> 124 typedef adjacency_list< vecS, vecS, directedS, color_property<> > Graph; 125 typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; 126 Pair edges[6] = { Pair(0,1), Pair(2,4), 127 Pair(2,5), 128 Pair(0,3), Pair(1,4), 129 Pair(4,3) }; 130 Graph G(6, edges, edges + 6); 131 132 typedef std::vector< Vertex > container; 133 container c; 134 topological_sort(G, std::back_inserter(c)); 135 136 cout << "A topological ordering: "; 137 for ( container::reverse_iterator ii=c.rbegin(); ii!=c.rend(); ++ii) 138 cout << index(*ii) << " "; 139 cout << endl; 140</PRE> 141The output is: 142<PRE> 143 A topological ordering: 2 5 0 1 4 3 144</PRE> 145 146 147<br> 148<HR> 149<TABLE> 150<TR valign=top> 151<TD nowrap>Copyright © 2000-2001</TD><TD> 152<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) 153</TD></TR></TABLE> 154 155</BODY> 156</HTML> 157
