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

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

Jan. 20, 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

Dealing with faults matters (was: Is Python dying?)
by claird＠Starbase.NeoSoft.COM Aug. 28, 2003

Aug. 28, 2003

In article <3706f449.12085377(a)news.cybercity.dk>, Morten Christensen <mmc(a)vip.cybercity.dk> wrote: >On 31 Mar 1999 06:01:03 -0600, claird(a)Starbase.NeoSoft.COM (Cameron >Laird) wrote: >>*I* certainly discuss it. Anyone who understands >>that exception-handling is important I invite to >>realize that exception-handling on the sociologi- >>cal-organizational dimension has an even bigger >>multiplier. >> >>This is a plank of my "Visual C considered profes- >>sional malpractice" campaign. > >??? > >...I understand exception handling and regard it as very important, >although the (Visual) C++ implementation is really awful (as everyone >who have experienced "unexplainable" Visual C++ exceptions of unknown >origin and type knows ).... I also know a lot about how exception >handling is actually implemented in modern OO languages such as C++ >(this was the subject I wrote my master thesis on).... > >HOWEVER, I have NO clue about what you mean by exception-handling as a >multiplier on the sociological-organization dimension :-) I would like >to find out. Can you explain? . . . Happily. Excuse my giddiness, please; I see that that last message *did* wander too far into the land of obscurity. Here's what I was saying: exception-handling is important. Programs that intelligently use exception-handling mechanisms are better programs. Exception-handling is even more important to people. People and organizations that deal with exceptions intelligently, and don't pre- tend that everything should be without fault, are better people and organizations. In fact, a correct computer program often has over half its lines devoted to accomo- dating error. A wise person will have good ways to respond to criticism/problems/diffi- culties/...; dealing with success is relatively easier. -- Cameron Laird http://starbase.neosoft.com/~claird/home.html claird(a)NeoSoft.com +1 281 996 8546 FAX

3 2

Bug in v1.5.2 Websucker GUI?
by dhfx＠realtime.net June 13, 2003

June 13, 2003

I'm running v1.5.2 on a Win95 box. I tried wsgui.py and got the following error message: ... File "C:\ ... \WSGUI.PY", line 165, in go self.sucker.rootdir = os.path.dirname( [ websucker.Sucker.savefilename(self.url)) ] TypeError: unbound method must be called with class instance 1st arg (the part in [ ] didn't appear in the message - I added it from the code) The object-instance self.sucker is an instantiation of class SuckerThread, which is derived from class Sucker of the websucker code module. The SuckerThread class includes a method savefilename() which overwrites the method in websucker.Sucker of the same name. Whoever coded wsgui evidently wanted to use the method of the parent class, rather than the method of the derived class. What seems to be giving trouble is that the arg of dirname() is a class method, rather than a method of an instance of the class. Here's what I did: I defined a new method savefilename1() in SuckerThread which just calls the savefilename() of the parent class: def savefilename1(self, url): return websucker.Sucker.savefilename(self, url) Then I changed the code at "line 165" to the following: self.sucker.rootdir = os.path.dirname( self.sucker.savefilename1(url)) and now it works. Note that the arg "self" of savefilename1() in the line above is not needed, it's implicit. In fact, when I had it in, I got an error message that I had too many args! David Friedman

5 8

Getting to know Python
by Arnaldo Sept. 29, 1999

Sept. 29, 1999

I just downloaded and compiled python in a sunos4.1 OS. I'm starting to have fun with it but I'm really new to the language. I'm planning to buy a book this weekend so I can learn more about python's syntax and posibly implement some of my c-shell/perl scripts in python. In the mean-time I'm eager to have with the interactive interpreter. How do I access the shell from the interpreter to enter commands like ,clear, ls, cp, etc. Is it posible, how do I do that? thanks guys ajr

4 3

Python Performance
by sreekant kodela Aug. 25, 1999

Aug. 25, 1999

Dear all I finally completed my website. It is fully functional and I used PostgreSQL, Python and Apache for that. Before I actually put the thing on the net, - Is there anyway I can improve the performance of python code. It is vital because almost all of the website is dynamically generated except intial welcome / logon screens etc and images. PostgreSQL being slow doesn't make things easier either. I know there is Pyapache. I am looking for it's binary. Is there any other way of doing it faster ? Help is much appreciated Thanks sreekant

18 37

syntax
by Xavier Bec Aug. 23, 1999

Aug. 23, 1999

Hello, Why are the double dots ":" necessary after a if, for or while instruction ? All the others instructions are terminated with a cariage return but not condition or loop ones. I know that a semi-column is facultative and only used if you have to put a second instruction on the same line. Why is not the same for if, etc. if i == 10 print i print "test" or if i == 10 : print i; print "test" Any suggestion ? -- Xavier Bec mailto:xav@buf.fr BUF Compagnie http://www.buf.fr 3, rue Roquepine tel: (33) 1 42 68 18 28 75008 Paris - FRANCE fax: (33) 1 42 68 18 29

5 4

Python GUI
by Brad Aug. 14, 1999

Aug. 14, 1999

Is there a Python GUI builder out there anywhere? Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.

10 24

designing question
by pserrand Aug. 13, 1999

Aug. 13, 1999

I have the mission to develop a rather big database front-end application. Since the application must be multi-platform LINUX -WIN it will be developed in Python. For infomatiion, this is what will be used : Python of course Tk Pmw Gadfly I have two questions: 1. The database will hold abouth 50.000 lines in its biggest table, can gadfly handle this without problems, what abouth acces time ?? 2. The application will have abouth 50 different inputscreens wich acces all to different tables. I will create a class for every window wich inheret from a general 'input-screen'-class. I wonder if a should place the db-access code (insert-update-delete) in every specific window or if i should create a big db class wich has all possible db-acces in it ? Ex : Possibility 1 : class window : def __init__ .. def createwidget: ... def handlevents : ... def insertrecord : ... def deleterecord: .... def update record : .... Possibility 2: class window def __init__ .. def createwidget: ... def handlevents : call here db().inserttable1() db().updatetable1() db().deletetable1() class db def __init__: connect to db def inserttable1 .. def updatetable1 ... def deletetable1 ... Hope my question is clear and sorry for the bad english, i'm french :) Pierrette

4 4

Printing from python on Windows platform
by Johann Spies Aug. 10, 1999

Aug. 10, 1999

I am a Linux user writing a program for somebody that will use it on a Windows platform. In Linux I use the following to redirect printing to the printer: drukker = sys.stdout drukker = os.popen('lpr','w') drukker.write(drukstuk) sys.stdout.write(drukstuk) What would the windows equivalent be? Johann -------------------------------------------------------------------------- | Johann Spies Windsorlaan 19 | | jhspies(a)futurenet.co.za 3201 Pietermaritzburg | | Tel/Faks Nr. +27 331-46-1310 Suid-Afrika (South Africa) | -------------------------------------------------------------------------- "Have not I commanded thee? Be strong and of a good courage; be not afraid, neither be thou dismayed; for the LORD thy God is with thee whithersoever thou goest." Joshua 1:9

2 1

ANN: Gadfly bugfix test release
by aaron_watters＠my-deja.com Aug. 8, 1999

Aug. 8, 1999

Gadfly users and others: Please try one of the following files http://www.chordate.com/kwParsing/kwPtest.tgz (tar/gz version) or http://www.chordate.com/kwParsing/kwPtest.zip (zip version) I believe this replacement fixes the following longstanding bugs: -- multiline strings should be supported by sql parser. -- table creates should not require a commit before inserts work. -- unique indices should raise exception on non-unique insert. -- table create followed by a recreate shouldn't require a commit to work. -- an obscure recovery error which is hard to describe -- a server bug having to do with not handling poorly formed requests correctly. Also, the *.zip file has the correct version of gfclient.py unlike the current one. Also http://www.chordate.com/gfcontrib.html has the correct gfplus.py link now. Pleasy anyone try these replacements. The test suite http://www.chordate.com/kwParsing/indexbug.py demos that some of these bugs have been fixed (it will fail in several ways with the current version). If I don't hear complaints I will make this gadfly 1.01 in a week or so. The changes are mainly very small ones. The big ones aren't ready for prime time yet. -- Aaron Watters === Kramer: Do you yearn? George: Do I yearn? Kramer: Yes, do you yearn? George: No. I crave. I crave constantly, but I never yearn. Kramer: Well, I yearn. Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.

2 2