TopSort in Python?
Dinu C. Gherman
implementation of topsort, the topological sorting algorithm?
Or maybe *any* topsort? I remember only one such algorithm...
python.org/search doesn't reveal any...
Thanks,
Dinu
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Tim Peters
> Does anybody have a simple-minded-but-working full-Python
> implementation of topsort, the topological sorting algorithm?
> Or maybe *any* topsort? I remember only one such algorithm...
> python.org/search doesn't reveal any...
Searching for "topological" instead turns up two hits there, a few more on
DejaNews. Apparently "the std" algorithm I posted years ago predates
DejaNews, though. So here's a fancier version ...
check-out-aaron's-kjbuckets-too-ly y'rs - tim
# topsort takes a list of pairs, where each pair (x, y) is taken to
# mean that x <= y wrt some abstract partial ordering. The return
# value is a list, representing a total ordering that respects all
# the input constraints.
# E.g.,
# topsort( [(1,2), (3,3)] )
# may return any of (but nothing other than)
# [3, 1, 2]
# [1, 3, 2]
# [1, 2, 3]
# because those are the permutations of the input elements that
# respect the "1 precedes 2" and "3 precedes 3" input constraints.
# Note that a constraint of the form (x, x) is really just a trick
# to make sure x appears *somewhere* in the output list.
#
# If there's a cycle in the constraints, say
# topsort( [(1,2), (2,1)] )
# then CycleError is raised, and the exception object supports
# many methods to help analyze and break the cycles. This requires
# a good deal more code than topsort itself!
from exceptions import Exception
class CycleError(Exception):
def __init__(self, sofar, numpreds, succs):
Exception.__init__(self, "cycle in constraints",
sofar, numpreds, succs)
self.preds = None
# return as much of the total ordering as topsort was able to
# find before it hit a cycle
def get_partial(self):
return self[1]
# return remaining elt -> count of predecessors map
def get_pred_counts(self):
return self[2]
# return remaining elt -> list of successors map
def get_succs(self):
return self[3]
# return remaining elements (== those that don't appear in
# get_partial())
def get_elements(self):
return self.get_pred_counts().keys()
# Return a list of pairs representing the full state of what's
# remaining (if you pass this list back to topsort, it will raise
# CycleError again, and if you invoke get_pairlist on *that*
# exception object, the result will be isomorphic to *this*
# invocation of get_pairlist).
# The idea is that you can use pick_a_cycle to find a cycle,
# through some means or another pick an (x,y) pair in the cycle
# you no longer want to respect, then remove that pair from the
# output of get_pairlist and try topsort again.
def get_pairlist(self):
succs = self.get_succs()
answer = []
for x in self.get_elements():
if succs.has_key(x):
for y in succs[x]:
answer.append( (x, y) )
else:
# make sure x appears in topsort's output!
answer.append( (x, x) )
return answer
# return remaining elt -> list of predecessors map
def get_preds(self):
if self.preds is not None:
return self.preds
self.preds = preds = {}
remaining_elts = self.get_elements()
for x in remaining_elts:
preds[x] = []
succs = self.get_succs()
for x in remaining_elts:
if succs.has_key(x):
for y in succs[x]:
preds[y].append(x)
if __debug__:
for x in remaining_elts:
assert len(preds[x]) > 0
return preds
# return a cycle [x, ..., x] at random
def pick_a_cycle(self):
remaining_elts = self.get_elements()
# We know that everything in remaining_elts has a predecessor,
# but don't know that everything in it has a successor. So
# crawling forward over succs may hit a dead end. Instead we
# crawl backward over the preds until we hit a duplicate, then
# reverse the path.
preds = self.get_preds()
from random import choice
x = choice(remaining_elts)
answer = []
index = {}
in_answer = index.has_key
while not in_answer(x):
index[x] = len(answer) # index of x in answer
answer.append(x)
x = choice(preds[x])
answer.append(x)
answer = answer[index[x]:]
answer.reverse()
return answer
def topsort(pairlist):
numpreds = {} # elt -> # of predecessors
successors = {} # elt -> list of successors
for first, second in pairlist:
# make sure every elt is a key in numpreds
if not numpreds.has_key(first):
numpreds[first] = 0
if not numpreds.has_key(second):
numpreds[second] = 0
# if they're the same, there's no real dependence
if first == second:
continue
# since first < second, second gains a pred ...
numpreds[second] = numpreds[second] + 1
# ... and first gains a succ
if successors.has_key(first):
successors[first].append(second)
else:
successors[first] = [second]
# suck up everything without a predecessor
answer = filter(lambda x, numpreds=numpreds: numpreds[x] == 0,
numpreds.keys())
# for everything in answer, knock down the pred count on
# its successors; note that answer grows *in* the loop
for x in answer:
assert numpreds[x] == 0
del numpreds[x]
if successors.has_key(x):
for y in successors[x]:
numpreds[y] = numpreds[y] - 1
if numpreds[y] == 0:
answer.append(y)
# following "del" isn't needed; just makes
# CycleError details easier to grasp
del successors[x]
if numpreds:
# everything in numpreds has at least one predecessor ->
# there's a cycle
if __debug__:
for x in numpreds.keys():
assert numpreds[x] > 0
raise CycleError(answer, numpreds, successors)
return answer
Dinu C. Gherman
Does anybody have a simple-minded-but-working full-Python
implementation of topsort, the topological sorting algorithm?
Or maybe *any* topsort? I remember only one such algorithm...
python.org/search doesn't reveal any...
Thanks,
Tim Peters
[Dinu C. Gherman]
> Does anybody have a simple-minded-but-working full-Python
> implementation of topsort, the topological sorting algorithm?
> Or maybe *any* topsort? I remember only one such algorithm...
> python.org/search doesn't reveal any...
Searching for "topological" instead turns up two hits there, a few more on
Dinu C. Gherman
although MCF's has the strange feature of adding (1,) here
or there. TP's has a great Exception class, it seems...
Ok, last week-end I typed in the algorithm sitting on my
own shelf at home (just to add one more). I haven't made any
timings, but I like that this one below is pretty short and
easy to understand. The top-level function parameters are
a bit different, but I wrote a wrapper function for using
the "more regular" one, too...
Anyway,-not-really-that-important-now'ly,
Dinu
"""A simple and short topological sorting algorithm in Python.
Input
The input is a set of unique elements (vertices), V, and a di-
rected graph of edges between them, E, where V is a list of
any Python objects and E a list of (v, w) tuples, with v and
w representing indices in V.
Output
The output is L = TS(V, E), a sorted list of all elements in
V, given E. Elements x in V without any (v, w) in E for with
v == x or w == x are prepended to L. Moreover, for all v, w
in V, v != w: (v, w) in E => index(L, v) < index(L, w).
Algorithm
In the directed graph we progressively pick one leaf node,
remove all adges to it and add it at the head of the (ini-
tially empty) result list. If there is no more such leaf
node, we have either a cycle (if there are still edges/
nodes left) or we're done. Isolated nodes (with neither in-
nor outcoming edges) are inserted at the head of the result
list.
Notes
Much of the algorithm can be changed to adapt to different
needs (while still calling it topsort), like the order of
isolated nodes, throwing a real exception when a cycle is
detected, a more efficient implementation of allEdgesFrom(),
or a randomized order of elements where multiple solutions
do exist, the omission of the vertices list parameter in the
top-level function (meaning using edges (v, v) in E), the
use of a class to remove some of the parameter passing, etc.
Dinu Gherman,
July 1999
"""
import sys
def allEdgesFrom(v0, E):
"Return a list of all edges (v0, w) in E starting at v0."
resEdges = []
for v, w in E:
if v0 == v:
resEdges.append((v, w))
return resEdges
def _topSort(v, E, visited, sorted, sortedIndices):
"Recursive topsort function."
# print "trying", v, visited, sorted, sortedIndices
visited[v] = 1
for v, w in allEdgesFrom(v, E):
# print "edge found", (v, w)
if not visited[w]:
_topSort(w, E, visited, sorted, sortedIndices)
else:
if not sorted[w]:
print "No sorting possible!"
sys.exit(0)
sorted[v] = 1
sortedIndices.insert(0, v)
def topSort(V, E):
"Top-level sorting function."
n = len(V)
visited = [0] * n # Flags for (un-)visited elements.
sorted = [0] * n # Flags for (un-)sorted elements.
sortedIndices = [] # The list of sorted element indices.
for v in range(n):
if not visited[v]:
_topSort(v, E, visited, sorted, sortedIndices)
# Build and return a list of elements from the sort indices.
sortedElements = []
for i in sortedIndices:
sortedElements.append(V[i])
return sortedElements
def wrap(pairs):
"""Convert an element pairs list into (verticesList, edgeIndexList).
This might be useful for those who prefer topsort(edgeList)
instead of topsort(verticesList, edgeIndexList)...
E.g. wrap( [('a','b'), ('b','c'), ('c','a')] )
-> (['a','b','c'], [(0,1), (1,2), (2,0)])
"""
e = []
v = []
# Make a list of unique vertices.
for x, y in pairs:
if x not in v:
v.append(x)
if y not in v:
v.append(y)
# Convert original element pairs into index pairs.
for x, y in pairs:
e.append((v.index(x), v.index(y)))
return v, e
def testCase(V, E):
print V
print E
print topSort(V, E)
print
def test():
# Test wrapper.
# E = [('a','b'), ('b','c'), ('c','a')]
# print E
# print wrap(E)
# print
# No error to be expected.
V = ['a', 'b', 'c', 'd', 'e', 'f']
E = [(0,1), (1,2), (1,3), (3,4), (4,5), (3,2)]
testCase(V, E)
# Still no error, but an isolated element 'g' should appear.
V = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
E = [(0,1), (1,2), (1,3), (3,4), (4,5), (3,2)]
testCase(V, E)
# Error because of cycle in graph.
V = ['a', 'b', 'c']
E = [(0,1), (1,2), (2,0)]
testCase(V, E)
if __name__ == '__main__':
test()
start...@gmail.com
Thanks for the topsort code. It would be useful in a project I'm
working on. Can I use the code for free under public domain? Thanks!
On Jun 30 1999, 11:00 pm, "Tim Peters"
<Tim.Pet...@p98.f112.n480.z2.fidonet.org> wrote:
> From: "Tim Peters" <tim_...@email.msn.com>
Paddy
> Tim,
>
> Thanks for the topsort code. It would be useful in a project I'm
> working on. Can I use the code for free under public domain? Thanks!
>
know to look for the topological sort algorithm by name?
(http://paddy3118.blogspot.com/2007/10/whats-in-name.html)
- Paddy.
Paul Rubin
> When I needed one I didn't know the name. I'm curious, how did you
> know to look for the topological sort algorithm by name?
It's a well known algorithm in computer science, described in any
number of textbooks, for example probably
http://projects.csail.mit.edu/clrs/
There is also a wikipedia article:
Carl Banks
> On Jan 18, 9:47 pm, startec...@gmail.com wrote:> Tim,
>
> > Thanks for the topsort code. It would be useful in a project I'm
> > working on. Can I use the code for free under public domain? Thanks!
>
> When I needed one I didn't know the name. I'm curious, how did you
> know to look for the topological sort algorithm by name?
I spent quite a bit of time looking for this one myself. It was quite
a stumper. Sometimes Google gets us in the habit of just firing
random search terms when we ought to be thinking it out.
After quite of bit of dead end searching--like a week--I stepped back,
thought about what I was looking for. I wanted a sort of dependency
system: A must happen before B. What other programs do that? make,
of course. I looked at the documents for make and found the term
"directed acyclic graph", and pretty much instantly knew I had it.
(It seems silly in retrospect that I didn't think of graphs before
that, but then it also seems silly no one invented movable type before
1436.)
Once I had that term, a quick Google search led me to the Wikipedia
article, which led me to the topsort algorithm. I did a dance of joy.
Ten minutes later I saw it mentioned it on comp.lang.python.
Carl Banks
Paddy
>
> Ten minutes later I saw it mentioned it on comp.lang.python.
It's almost as if you looking for it made it popular :-)
- Paddy.
duncan smith
> On Jan 18, 7:01 pm, Paddy <paddy3...@googlemail.com> wrote:
>> On Jan 18, 9:47 pm, startec...@gmail.com wrote:> Tim,
>>
>>> Thanks for the topsort code. It would be useful in a project I'm
>>> working on. Can I use the code for free under public domain? Thanks!
>> When I needed one I didn't know the name. I'm curious, how did you
>> know to look for the topological sort algorithm by name?
>
> I spent quite a bit of time looking for this one myself. It was quite
> a stumper. Sometimes Google gets us in the habit of just firing
> random search terms when we ought to be thinking it out.
>
> After quite of bit of dead end searching--like a week--I stepped back,
> thought about what I was looking for. I wanted a sort of dependency
> system: A must happen before B. What other programs do that? make,
> of course. I looked at the documents for make and found the term
> "directed acyclic graph", and pretty much instantly knew I had it.
Searching for "precedence diagram" might throw up some relevant results;
but you've probably already discovered that. I have some basic
precedence diagram code (no warranty etc.) somewhere if anyone is
interested.
Duncan
Paddy
wrote:
I searched for dependancy sort, and later dependency sort (cos I
couldn't spell). I had convinced that I was using the right term and
was flummoxed by the lack of hits. Even today the term topological
sort means far less than what it describes: sorting items based on
their interdependencies.
Is this a case of something being named after its mathematical/
technical description and so obscuring its wider practical use cases?
- Paddy.
P.S. we have revived a thread started in 1999!
Mike C. Fletcher
...
> I searched for dependancy sort, and later dependency sort (cos I
> couldn't spell). I had convinced that I was using the right term and
> was flummoxed by the lack of hits. Even today the term topological
> sort means far less than what it describes: sorting items based on
> their interdependencies.
>
to http://www.vrplumber.com/programming/ (which has Tim and my
algorithms (toposort.py)) as the second link... vagaries of Google I
suppose.
> Is this a case of something being named after its mathematical/
> technical description and so obscuring its wider practical use cases?
>
description on the download page (since I had the same problem starting
out (I implemented the algorithm before I knew the name IIRC)).
> P.S. we have revived a thread started in 1999!
>
Have fun,
Mike
--
________________________________________________
Mike C. Fletcher
Designer, VR Plumber, Coder
http://www.vrplumber.com
http://blog.vrplumber.com
Tim Peters
> Thanks for the topsort code. It would be useful in a project I'm
> working on. Can I use the code for free under public domain? Thanks!
If I ran the world, everything I posted to a public place would be
public domain. Alas, the last lawyer who typed at me about this
insisted that an individual in the USA cannot meaningfully disclaim
copyright, so perhaps you're required to pay me millions of dollars
instead ;-)
To keep him happy and you solvent, I hereby license the code under the
MIT license:
http://www.opensource.org/licenses/mit-license.php
Copyright (c) 1999-2008 Tim Peters
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.