BERJAYA

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

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

Re: eff-bot Python book ... revisited
by François Pinard Dec. 23, 1999

Dec. 23, 1999

Ivan Van Laningham <ivanlan(a)callware.com> writes: > (And last time I checked, the PDF viewer for Linux sucked; maybe that's > changed by now, maybe Adobe offers their own 4.0 viewer for Linux. ...) I'm far from PDF, but it happened that Ghostscript helped me at viewing it conveniently on Linux -- through `gv', I rarely use Ghostscript directly. However, sending to the printer from `gv' (a Tkinter introduction, if I remember well?) was less happy, as the inter-letter spacing was all wrong, making the printed result especially difficult to read. Even if it helps me (?!) at reading more slowly, the fatigue grows faster. I have no idea of the cause of this random spacing, far less the solution. -- François Pinard http://www.iro.umontreal.ca/~pinard

3 2

Comparison between Python and "Ruby"
by Ian Clarke Nov. 27, 1999

Nov. 27, 1999

Disclaimer out of the way, I was recently web surfing when I discovered a link to a language called "Ruby" which seems to be similar to Python in that it is a scripting language, and has good support for OO. Ruby's home on the web is at http://www.ruby-lang.org/. The makers of the language have even done a comparison with Python. In it they make the following claims (the strange grammar is their's, not mine): Problems with Python are: * incomplete OOP * Some data (numerical, list, dictionary, string, etc.) are not genuine object. * Extension modules in C don't realize genuine objects. * Tiresome self. are required when each access to instance variable * Functions are first class object (Of cource, we know it is not weak) del, len, etc. are not Object-Oriented. (There are __len__, etc. but ...) * Ugly method calling for superclass * No class method (module functions alternate it) * No way to automatically convert between long integer and small integer. * Because there is no genuine GC, memory leak occur often * Writing extension modules is bothersome (some betterments in 1.5) * Tuple and list has overlap functionally (not serious) * Function objects are accepted as arguments, but iterators are more elegant. * After all, declarations are featured (global) * Slower than Ruby (may be improved?) I am still trying to download a copy of Ruby to look at it myself, however do people think these comments are justified? Ian. -- Ian Clarke Email: I.Clarke(a)strs.co.uk Homepage: http://www.gnu.demon.co.uk/ Also see: http://freenet.on.openprojects.net/ "All we see and all we seem is but a dream within a dream"

34 63

Detect file existance before open?
by Bill Rodgers Nov. 10, 1999

Nov. 10, 1999

I would like to check for the existance of a file before I attempt an open and maybe throw an exception. I don't see a way to do this. I would like to tell the user that the file he specified doesn't exist. Is there a way to do this or do I need to catch the exception and deal with it that way? Thanks, -- Bill Rodgers Enterprise Management Consultant Specialty: BMC/Patrol brodg1(a)ix.netcom.com

8 7

Learning to program
by Jonathan Nov. 9, 1999

Nov. 9, 1999

A friend of mine wants to learn to program. Python seems one of the most suitable languages to start with. I think the Lutz et al book is good at explaining the language to a newcomer, but I'd also like to find an accessible book that explains program design, clarity, debugging, data structures, etc in a Python friendly way. Suggestions? ("Programming Pearls" and "The Practice of Programming" are just too much book for my friend's needs and experience right now.) Jonathan Coupe

3 2

RE: Apply a function to each list member?
by Gaetan Corneau Nov. 8, 1999

Nov. 8, 1999

Thanks Michael (and others who replied privately). I knew I had seen a function to do this somewhere, but I could not find it. "map" is not an intuitive name for me (maybe it would if english was my main language). >>Your ListApply might be a little more space efficient as it works in >>place, but not much, because you allocate a list of length len(l) >>anyway in the range(). I don't know. Efficiency is usually not a concern for me (not when I use Python). Thanks, ______________________________________________________ Gaetan Corneau Software Developer (Quality Assurance Team) BaaN Supply Chain Solutions E-mail: Gaetan_Corneau(a)baan.com Compuserve: Gaetan_Corneau(a)compuserve.com ICQ Number: 7395494 Tel: (418) 266-8252 ______________________________________________________ "Profanity is the one language all programmers know best"

10 11

Control-C on Unix misbehaviour?
by Michael Hudson Nov. 6, 1999

Nov. 6, 1999

Something I noticed but never got around to moaning about around the time of the transition from 1.5.1 to 1.5.2 was that now hitting Ctrl-C at the interpreter prompt tends to dump me out to the shell. I'm fairly sure that's not what {used to,should} happen. I was expecting bash-like behaviour, i.e. abortion of the current command entry. Can anyone confirm this, or am I just talking nonsense again? Regards, Michael

9 9

Module for generic platform information: platform.py
by M.-A. Lemburg Nov. 5, 1999

Nov. 5, 1999

Last week I started to write a small module for more convenient and portable access to information about the platform on which Python is running. Many people have helped and provided lots of information about the various Python compatible platforms out there... thanks everybody :-) Some things where I need some more help are: · support for Linux distributions other than redhat, suse, debian, mandrake · better support for WindowsCE (Jeff Bauer is working on this one) · support for MacOS (not the X Server version; JvR is working on it) · support for Amiga, MS DOS and maybe VMS · a way to find out the true system names and versions on MacOS X Server and Solaris (they both use different names at the OS level, e.g. SunOS 5.5 instead of Solaris 2.5) New features: · system alias support, e.g. SunOS can be reported as Solaris Here is the latest version of that module: http://starship.skyport.net/~lemburg/platform.py To see if it works on your platform, simply run the script. Enjoy, -- Marc-Andre Lemburg ______________________________________________________________________ Y2000: 66 days left Business: http://www.lemburg.com/ Python Pages: http://www.lemburg.com/python/

8 18

Python-list

October 1999