|
1 # Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com> |
|
2 # |
|
3 # Permission is hereby granted, free of charge, to any person |
|
4 # obtaining a copy of this software and associated documentation |
|
5 # files (the "Software"), to deal in the Software without |
|
6 # restriction, including without limitation the rights to use, |
|
7 # copy, modify, merge, publish, distribute, sublicense, and/or sell |
|
8 # copies of the Software, and to permit persons to whom the |
|
9 # Software is furnished to do so, subject to the following |
|
10 # conditions: |
|
11 |
|
12 # The above copyright notice and this permission notice shall be |
|
13 # included in all copies or substantial portions of the Software. |
|
14 |
|
15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
|
16 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
|
17 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
|
18 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
|
19 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
|
20 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
|
21 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
|
22 # OTHER DEALINGS IN THE SOFTWARE. |
|
23 |
|
24 |
|
25 """ |
|
26 Sorting algorithms for python-graph. |
|
27 |
|
28 @sort: topological_sorting |
|
29 """ |
|
30 |
|
31 |
|
32 # Topological sorting |
|
33 |
|
34 def topological_sorting(graph): |
|
35 """ |
|
36 Topological sorting. |
|
37 |
|
38 @attention: Topological sorting is meaningful only for directed acyclic graphs. |
|
39 |
|
40 @type graph: graph |
|
41 @param graph: Graph. |
|
42 |
|
43 @rtype: list |
|
44 @return: Topological sorting for the graph. |
|
45 """ |
|
46 # The topological sorting of a DAG is equivalent to its reverse postordering. |
|
47 tmp, tmp, post = graph.depth_first_search() |
|
48 post.reverse() |
|
49 return post |