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