ceph/src/boost/libs/graph/doc/topological_sort.html

   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>
  25 template &lt;typename VertexListGraph, typename OutputIterator,
  26           typename P, typename T, typename R&gt;
  27 void topological_sort(VertexListGraph&amp; g, OutputIterator result,
  28     const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
  29 </PRE>
  30
  31 <P>
  32 The topological sort algorithm creates a linear ordering of the
  33 vertices 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
  35 directed acyclic graph (DAG). The implementation consists mainly of a
  36 call to <a
  37 href="./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
  45 IN: <tt>VertexListGraph&amp; 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
  56 OUT: <tt>OutputIterator result</tt>
  57 <blockquote>
  58 The vertex descriptors of the graph will be output to the
  59 <TT>result</TT> output iterator in <b>reverse</b> topological order.  The
  60 iterator type must model <a
  61 href="http://www.sgi.com/tech/stl/OutputIterator.html">Output
  62 Iterator</a>.<br>
  63
  64 <b>Python</b>: This parameter is not used in Python. Instead, a
  65 Python <tt>list</tt> containing the vertices in topological order is
  66 returned.
  67 </blockquote>
  68
  69 <h3>Named Parameters</h3>
  70
  71 UTIL/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
  90 IN: <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
 114 The time complexity is <i>O(V + E)</i>.
 115
 116
 117 <H3>Example</H3>
 118
 119 <P>
 120 Calculate a topological ordering of the vertices.
 121
 122 <P>
 123 <PRE>
 124   typedef adjacency_list&lt; vecS, vecS, directedS, color_property&lt;&gt; &gt; Graph;
 125   typedef boost::graph_traits&lt;Graph&gt;::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&lt; Vertex &gt; container;
 133   container c;
 134   topological_sort(G, std::back_inserter(c));
 135
 136   cout &lt;&lt; "A topological ordering: ";
 137   for ( container::reverse_iterator ii=c.rbegin(); ii!=c.rend(); ++ii)
 138     cout &lt;&lt; index(*ii) &lt;&lt; " ";
 139   cout &lt;&lt; endl;
 140 </PRE>
 141 The 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 &copy; 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>