Sunday, February 27, 2005

another blog

Sorry to this to you people, but I split my blog. My current 'technical' hobbies, graph theory/networks and python will be blogged @ The reason is that I wanted to add my blog to some of the composite python feeds such as, but at my current rate of 10% python posts if would not be acceptable. The new blog also has a feedburner link at the bottom of every post, please use that one!

Thursday, February 24, 2005

to throw or or not to throw

Ok, I mean 'to raise', this IS a Python post.
I have recently gotten into graph programming, and been readin' the BGL book .
Not Python, but a great book on writing software libraries in general (with many c++ gems), and has some ideas about graph algorithms that would transfer into Python quite nicely. My favorite (so far) has been the concept of 'algorithm visitor'. As I cannot explain this any better than the BGL authors, I'll just quote:
""" The visitor concepts plays the same role in BGL as functors play in the STL. Functors provide a mechanism for extending an algorithm; for customizing what is done at each step of the algorithm. Visitors allow the user to insert their own operations at various steps within a graph algorithm. Unlike the STL algorithms, graph algorithms typically have multiple event points where one may want to insert a call-back via a functor. Therefore visitors do not have a single operator() method like a functor, but instead have several methods that correspond to the various event points""" More here...
So I hacked up an initial bfs implementation using the visitor concept:

def bfs(graph, start, bfs_visitor=default_bfs_visitor()):
done = {start: True}
queue = [(start, 0)]
while queue:
node, depth = queue.pop(0)
bfs_visitor.discover_vertex(node, depth)
for v in graph.adjacent_vertices(node):
bfs_visitor.discover_edge((node, v))
if(not done.has_key(v)):
done[v] = True
queue.append((v, depth+1))

default_bfs_visitor just implements dummy methods that bfs calls, (discover_vertex and discover_edge). User-defined visitors can selectively override the methods they are interested in.
My next thought was the termination condition. While by default the bfs algorithm would traverse the entire graph there are occasions to terminate early, for example if the node of interest was found or certain depth has been reached. Pygraphlib actually uses an 'end' parameter as a termination condition, which to me seems the 'node of interest' termination condition (their rationale is not well documented). I myself was interested in limiting bfs to a certain depth. First thought was to just add a max_depth paramter to bfs(). But looking at pygraphlib and my case I realized that pygraphlib picking the end vertex as termination and me picking a certain depth is kind of arbitrary. Of course I could provide two termination condition parameters, but this would both complicate and slow down the algorithm. So then I realized that the visitor can already be used for such termination. All I need is to define a special visitor that will, for example, make the bfs function exit when discover_vertex() is calle d with a depth greater than whatever value I initialize the visitor with. But how do I 'exit' bfs? One possibility was to have every visitor funtion return a false if exit is desired at this point. This did not sit right with me, though. I am more inclined to raise an exception in the termination case, which would effectively exit the function. The only problem that I see with this is that the function will now have to be called inside a try-catch block even thoug the exception is pretty much expected in this case. So this also seems wrong. What I finally came up with is the following: a standard traversal_termination_exception should be used by all the visitors that implement a termination condition. This way bfs() can just have a single try-catch for this particular exception, which keeps the code pretty clean. If a special exception really needs to be thrown instead of my traversal_termination_exception I think a Python 2.4 decorator could be useful (I will leave this as a homework exercise due to the hour ;).


Why is this guy the last one to come out of the LIRR train car, right before they they close the door and send the train to the depot? What's he been smoking? Unittesting!
That's right. I have been playing with a small python project that I might eventually release to the open source, if anything comes out of it. I decided to do unittesting from scratch and I was using Dive Into Python for reference - the book has a very nice section on unittesting. So I was sitting till the last minute on the train trying to get the lovely OK to come up, as I broke my first test during refactoring ;(.

what's not working?

My wife just called me up saying 'google is not working' (she meant the Internet - I have periodic need to reset the router). Talk about brand recognition, those lucky bastards! Can you imagine someone saying 'Macy's is not working' 'cause the car won't start?

Wednesday, February 23, 2005

the other Ant

Unofficial Apple Weblog featured ANT under FreewareFebruary . I downloaded it, it rocks! The videoblog space is pretty sparse as of yet (I am going to checkout some feeds tomorrow), but the possibilities!
P.S. I have been following the FreewareMonthX for a while, and Mac really has some unique and cool freeware. In certain categories, such as media/video and maybe some others it kicks other platforms' butts. In general I think the kind of freeware written for a platform indicates somthing about the platform, but for now I will refrain from further generalization.

check out the macros on this guy!

Eric Niebler explains how his FOR_EACH macro proposal for boost works. This is a good example of code that is
- very powerful
- very complicated
- very dangerous
(very brilliant too, IMO)
Economically such code belongs in a good library repository such as boost. The fact that it is peer-reviewed by other very smart and experienced people (assuming FOR_EACH will get accepted) gives me good confidence that it is correct and useful, even though I do not have the skills to develop such code myself. (By 'economically' I mean here the 'economy of scale' and 'labor specialization' that organization like boost exhibits)

Monday, February 21, 2005

kids and programming

Don Box wants to teach his kids programming. I recommended VPython.

Thursday, February 17, 2005

your security health-check

This is really cool, especially since it runs on this!


I joined the rest of the crew in del.i.cious coolness!

sit a little, blog a little

Waiting for the Apprentice, a funny thought comes to mind: Donald Trump Chiapet!

Wednesday, February 16, 2005

coolest python syntax trick

a lotta pythonistas say this is the coolest


Nick Codignotto showed me KonfabulatLinkor a couple of month ago. I forgot about it for a while untill I realized that I have trouble dressing for the weather and it would really pay to see the forecast before I dash of to work. I hate using tv for this and my kid usually watches some show on my desktop before I leave, and I realized that K's weather widget was the ticket. After installing it it did a little more research and found a couple of interesting links:
A nice intro to making your own widgets
A good historical take on the Konfabulator vs. Dashboard contraversy
A Linux alternative (ouch K, this one is python-powered!)

Tuesday, February 15, 2005

google maps

I finally came around to making a comment. IMO the feature and its association with local search is kickass and will earn google quite a few bucks. They are earning a lot of mindshare by staying on the bleeding edge with top-notch GUI (for the web).
In the recent google-map frenzy I found a couple of worthwhile links:
- a nice reverse-engineering of the map tech
- if you ever read Paul Graham (highly recommended, a lot of smart stuff and even more hubris), especially his LISP-related articles, you will laugh your ass of at this parody.

Monday, February 14, 2005

scary freakin' pizza

Check out this demo. The only think its missing is POWERED BY

Sunday, February 06, 2005

why dmoz?

I have been perusing parts of the . The book is very good, although I am very stale on some of the math. (Side note: to judge the book by its color, this is one of the best books I held. The color, paper type, weight, size and font are VERY nice. That is why I posted the full-color link.) It got me to think about a few web-related thoughts.
First, the best explaination of Google's PageRank algorithm I heard to date. Basically if you have a random traveler on the graph structure of the web (choosing a random link available from the current location) the page's rank will be proportional to the number of times this random traveler will stop on this page. Cool. For a somewhat different explaination (and a REALLY COOL animation see Doug Gregor's (of fame) project.
Second, the book mentioned the obvious limitations of human-edited directories such as The real here killer is coverage - there is no way to get enough volunteer-power to cover a significant chunk of the Web to make the directory approach useful. So why is there still some push behind these? I think one of the big benefectors here is the search engines. Why? As the book shows from some studies even the search engines' coverage is not complete (for technical reasons). So let's put the pieces together: search engine graph traversal is not complete, but their ranking depends of the graph traversal. What to do? Why not seed the search with some nice, non-spammed results of volunteer work? That's what I think, anyway, would love to hear other opinions.
Follow-up: I wrote this up without googling it first. Interesing corraboration from jdMorgan here, and a great thread here.

Thursday, February 03, 2005

a new windows ad