🌐 Mailman 3 September 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

Python compilers?
by Nolan Darilek Oct. 17, 1999

Oct. 17, 1999

I've been programming with C++ for nearly a year, and after seeing how other languages are structured, and their benefits, I'm becoming disenchanted with it. So, I've been searching for another language. One item which I would like to have, though, is the ability to compile to native code. While I completely agree with open source philosophies, I'd like to have the option to not release source if, for example, I was working on a game and wanted to dissuade the lazy from peeking at the script source for the solution. :) I know about freeze, but the created binaries are extremely large, which makes sense considering how they are made. :) So, are there any native Python compilers? Someone on IRC mentioned a project called Viper, and my searches seem to indicate that it is under development, but is there any information on the web about its status? Also, What is swallow? I tried doing a websearch for swallow and Python, and ended up with tons of Holy Grail references, but nothing to answer my question. :) I ask because I've seen swallow coupled with viper in a few messages; is swallow another python/pseudopython interpreter/compiler? One final question. How compatible/cross-platform are Python bytecodes? If I wanted to distribute applications in Python while hiding the sources from the user, would it be possible to distribute .pyc files, or the bytecodes specific to a specific version/platform?

7 7

newbee
by Eric Holmes Oct. 14, 1999

Oct. 14, 1999

hi i want to know how to get started with python the language. regards eric

5 4

French pun on Python! :-)
by François Pinard Oct. 13, 1999

Oct. 13, 1999

Hi, people. While introducing Python to a few friends, I noticed they tend to naturally use `je Pythonne', `nous Pythonnons', etc. as an easy pun on the word Python. I think that English people pronounce `pie-ton', while French people say `pea-to[n]' (said faster, with the `n' silent). This has the same sounds as for the word `piton'. A `piton' is a familiar word to design any mechanical device on which someone pushes, like an electrical button, or often, one of the keys of a computer keyboard. So, `je pitonne', `nous pitonnons', etc. already became a familiar way to express any soft computer hacking. I thought this might amuse some of you. -- François Pinard http://www.iro.umontreal.ca/~pinard

4 4

Re: Marking translatable strings
by François Pinard Oct. 10, 1999

Oct. 10, 1999

Greg Ewing <greg.ewing(a)compaq.com> writes: > Tim Peters wrote: > > > > > Experience shows that horizontal space is often a valuable resource while > > > writing code, so we should try to be economical there for overall > > > legibility, much more than typability. > How about hacking the unary "+" operator on strings to > do translation? It would be hard to get any more horizontally > economical than that, and it wouldn't require any change to > the scanner or parser. It would need a change to Python, as currently: TypeError: bad operand type(s) for unary + but indeed, if such a change was accepted, it would be especially neat. For example: "printing %s" % +"hello" +"printing %s" % "hello" +"printing %s" % +"hello" would allow precise, yet unobtrusive control over exactly what gets translated. I'm presuming, here, that unary `+' binds very tightly. Would you foresee any difficulty while writing a _simple_ tool, to be integrated in `xgettext' (or `xpot':-) that would properly identify unary `+' operators before strings, I mean, never mistaking a binary `+' as unary? -- François Pinard http://www.iro.umontreal.ca/~pinard

5 5

Nolan's question of the day: distributed servers?
by Nolan Darilek Oct. 7, 1999

Oct. 7, 1999

I've kept up a good tradition (Maybe not, depending on your point of view :) of asking one question per day. Here's today's. :) My current big project is a MUD server in Python. I have some interesting ideas, only one of which I'll bore you all with. :) I honestly don't know how Python will perform in this area. I'm not aiming my code at lower-end processors though, so I'm not terribly worried, but in order to alleviate some of this, I'm trying to either use an existing object distribution scheme such as CORBA/ILU, or *shudder* write my own. :) Let me start by saying that I am not intimately familiar with CORBA or ILU. I know what they were meant to accomplish, and I could probably write a simpler program using them, but my needs are slightly different, and I don't know if these schemes will handle them. Basically, persistent objects are loaded into Namespaces. A Namespace is a class which stores all objects in a specified location (Location meaning a database) as local variables. So, if you had an object called Ball in a database which is stored in a file called "objects.db", you could do: # Open the database and load all objects. root = Namespace("objects.db") # Access our Ball. ball = root.Ball # And then bounce it. ball.bounce() Since a namespace itself is a persistent object, databases can store other namespaces. However, namespaces don't just access databases; they can also access servers. So, you could do: root.server1 = Namespace("thematrix.mud.org", "4000) and then all objects which are available to the server thematrix.mud.org 8000 would be available. Initially this scheme will require a trusted environment, and security should be implemented later. So, a network of namespaces will exist, each accessing either a database or a server. My current concern, though, is that the server shouldn't have to know how every single object on every single server works before it starts. From what I've seen of CORBA (And correct me if I'm wrong.) class interfaces need to be specified before hand and compiled to skeletons. This wouldn't work for me, since if someone on server x decides to code, say, a flying car, making a skeleton wouldn't be practical. So my current questions are, is it possible to somehow export a dynamic interface in realtime, as opposed to carefully specifying an interface beforehand and loading it into the server? Another idea which I have been considering is breaking the object into two components, an exportable version and a server-resident version. So, if someone gets a ball from another server, the user's server is only sent a ball with its description and a list of commands/methods. If the user chooses to bounce the ball, the user's server passes the bounce request to the server which originated the ball, the ball processes the method and returns its results to the user. This method seems somewhat unclean though, since the person's ball wouldn't bounce if the server which originated it was down. If, instead, the user's server knew how to bounce the ball, the server would be able to work independently. Another option would be to pickle requested objects and dump them over the network to the originating server, possibly using zlib for speed. So, if someone requests a copy of root.server1.ball, the ball object would be pickled at the destination and sent across the network. Perhaps this would be the best solution, since both sides of the connection would have a copy of the object, though changes in one would still need to effect the other, which may prove difficult. Has anyone done something like this? If so, do you have any recommendations? Thanks for listening/reading the somewhat confusing and confused rants of a newbie. :)

10 9

Help! Adding methods to Zope
by sjoshi＠ingr.com Oct. 6, 1999

Oct. 6, 1999

Hello I'm trying to use the simple example in the Zope doc where it talks about using the feedback.py script. I have saved the script to cgi-bin directory and I'm trying to add the method in it as an external method through the manage screen in Zope. However I keep getting an error saying Error Value: The file name, E:\cgi-bin\feedback, should be a simple file name. Can someone please point out what I'm missing thanks Sunit Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.

3 2

Checking for 'new' POP3 mail
by Python Addict Oct. 5, 1999

Oct. 5, 1999

I'm writing a program that will try to intelligently examine the contents of a user's POP3 mail spool and then forward certain matched mesages to one of those groovy alpha pagers. After stripping out all the MIME bits and graphics of course. The program will be long running (for days at a time if a user is on a trip). The poplib works brilliantly but there doesn't seem to be an obvious built-in way to see what's 'new' between sweeps of the POP3 spool. Before I attempt to write the next bit, I just wanted to see if I'm on the right track with my thoughts. Messages come and go so just purely checking on the number of messages in the spool isn't going to work. Our POP server supports the optional UIDL command which returns the message number, a space, and then a unique identifier for each message. I thought I'd take this list, chop off the message number and put the unique message values into a list on the very first pass. On all other sweeps of the POP3 spool, I could create a second list and then check against the first to see if there were any new, unique message id's (and if so, do some checking on them for further action). Then the original list would be tossed away and replaced with the last list as it would be more up to date. Am I making things complex for no reason or is there some built in functionality I'm missing from the POP spec? Is there a Python-ish way of comparing two lists that I might not be aware of? I was going to start at the beginning of the second list, waddle through it, and search for each element in the first list. Thanks very much for any thoughts.

4 3