diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/sorting.py --- a/thirdparty/python-graph/graph/sorting.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,49 +0,0 @@ -# Copyright (c) 2007-2008 Pedro Matiello -# -# Permission is hereby granted, free of charge, to any person -# obtaining a copy of this software and associated documentation -# files (the "Software"), to deal in the Software without -# restriction, including without limitation the rights to use, -# copy, modify, merge, publish, distribute, sublicense, and/or sell -# copies of the Software, and to permit persons to whom the -# Software is furnished to do so, subject to the following -# conditions: - -# The above copyright notice and this permission notice shall be -# included in all copies or substantial portions of the Software. - -# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, -# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES -# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT -# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, -# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING -# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR -# OTHER DEALINGS IN THE SOFTWARE. - - -""" -Sorting algorithms for python-graph. - -@sort: topological_sorting -""" - - -# Topological sorting - -def topological_sorting(graph): - """ - Topological sorting. - - @attention: Topological sorting is meaningful only for directed acyclic graphs. - - @type graph: graph - @param graph: Graph. - - @rtype: list - @return: Topological sorting for the graph. - """ - # The topological sorting of a DAG is equivalent to its reverse postordering. - tmp, tmp, post = graph.depth_first_search() - post.reverse() - return post