🌐 Mailman 3 July 2003 - Python-list - python.org

TopSort in Python?
by Tim Peters Jan. 21, 2008

Jan. 21, 2008

From: "Tim Peters" <tim_one(a)email.msn.com> [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 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

8 9

problem using py2exe
by Ho-Kyeong Aug. 1, 2005

Aug. 1, 2005

Can anybody give me a detailed explanation of using extension modules in py2exe? My python code imports 'tkSnack', a extension module, and my setup.py is like this: #setup.py from distutils.core import setup import py2exe setup(name="pitch", scripts=["pitch.py"] ) (that is, pitch.py imports tkSnack.) In cmd, I type 'python setup.py py2exe'. It works well, but I execute the pitch.exe, then error happens. Traceback (most recent call last): File "<string>", line 14, in ? File "<string>", line 7, in pitch File "tkSnack.pyc", line 21, in initializeSnack TclError: can't find package snack I look up in python.org, but I have no idea.

4 3

help with warning formatting
by Mike Brown March 11, 2005

March 11, 2005

I'm trying to get the hang of warnings. % cat t.py import warnings warnings.warn('foo') % python t.py t.py:2: UserWarning: foo warnings.warn('foo') Is there a way to just issue the warning message itself, or to at least suppress printing the line where the warning occurred (" warnings.warn('foo')" in the example)? See, I want to warn the user of my application that they're doing something risky or improper, so I just want to emit the 'foo', subject to the usual determination of whether the warning needs to be printed at all. For my purposes, the user doesn't need to know where the warning occurred, and they certainly don't need to see pieces of the call stack. The way it works now, it seems to be intended to warn the application programmer that they're doing something risky in the code (?). Thanks in advance for any advice.

4 4

Win32 drive mapping... aka "net use"
by lshuler＠my-deja.com March 5, 2005

March 5, 2005

Is there an API using Win32 extensions to map a drive share? I have not found one yet and have tried searching "Win32 map drive". I am looking for the equivalent of: net use <share path> If not, is there an alternative other than making a call to system("net use <path>"). Thanks in advance, Lance Sent via Deja.com http://www.deja.com/ Before you buy.

11 15

Gate Oxide thickness of CMOS
by hasi＠rediffmail.com Jan. 2, 2005

Jan. 2, 2005

Hi, I would like to know the following details for a CMOS 1.gate oxide thickness 2.The Number of masks 3.Number of transistors per chip Thanks, Hasi!

3 2

Parsing apache log files
by Fernando Rodr�guez Dec. 21, 2004

Dec. 21, 2004

Is there any module for parsing apache log files? O:-) I guess it could be done with regular expressions, but I'm not very gifted with them... :-) ----------------------- Fernando Rodriguez

2 1

Blank ASP pages
by python Dec. 10, 2004

Dec. 10, 2004

My server is spitting out blank .asp pages which use python. If Python is not declared, the asp pages work fine. I just yesterday stepped up to Python 1.52 and the new win32all After the install, the blanks started appearing. All the paths look fine in registry. Any clues? ( Intel dual PIII 550 Xeon, 1G RAM, NT 4.0 SP 6a, IIS 4) ************************************************** Jason S. Nadler Lead Programmer Channel21 Productions, Inc. ... What are you doing right now? **************************************************

3 2

any good, free web hosts supporting python cgi scripts?
by chimera4＠fastmail.fm Dec. 6, 2004

Dec. 6, 2004

Hi, I want to try out using python for cgi scripts, but most free hosts do not support python. Any of you know any free web hosts that do? Thanks a lot.

3 2

ImageWin Dib draw usage?
by Ilariu Raducan Sept. 30, 2004

Sept. 30, 2004

Hi All, Does anybody has experience working with ImageWin.Dib.draw? I tried to use it to draw in a window in the rectangle return from GetClipBox(). I use the same rectangle for source and destination and the result is a bit strange: a different region from the one expected is displayed. I have looked at the PIL source code. The windows API function used there in StretchBlt. Should that be StretchDIBits? Regards, Lale

3 2

Is it possible to write a Audio CD Player by using python only?
by MiLF Sept. 29, 2004

Sept. 29, 2004

Is it possible to write a Audio CD Player by using python only?

6 9