Older blog entries for pesco (starting at number 4)

Interesting. I'm done with the (graph-theoretical) shortest path algorithm. And by the way, guess what, it's an instance of a breadth-first fold (no shit). That function almost twisted my brain out of my head, though. Fuckin' thing. But judging by how convoluted it started, it turned out pretty nice. 14 siginficant lines of code. OK?

Annotating each node in the graph with its shortest path to a given root node is done in three significant lines of code. Oh, and by the way, of course I ended up using (basically) the same data structure as FGL. Well, at least now I know.

As I was saying... Interesting. My distance to raph is four for both Apprentice and Journeyer level. So the maxflow algorithm is next...

Oh, and thanks Akira, for certifying me. :)

Well, well, well. It turns out the memory leak was not in the graph processing at all. The function to extract the certs from HTML (via regexes) was holding on to stuff, appearently. Forcing evaluation of the extracted certs makes the program run on full CPU power with a maximum residency of eight megabytes. It took around 80 seconds to process all users.

But by the way, my self-made graph module was still very useful. Most importantly, it allows arbitrary node types, as long as they are ordered. Amazingly, this generalization makes the code hugely prettier. I will have to see how the algorithms work out.

Hah! I got a much better idea about the thrashing of my program. I've always thought 512 megabytes were a bit slim for my PowerBook... just kidding.

Dear Diary! I got certificied as Journeyer by my friend shapr. Cool, but my global level is still Observer. I must be too far away from the seeds.

So I've extracted Advogato's certification database. (At least the component reachable from raph, miguel, federico, and alan.) The graph has 4482 nodes (=users), and 45826 edges (=certificates).

Unfortunately, the graph library I used (FGL) feels kind of strange. My "naive" program quickly exhausted my 512 megabytes of memory, throwing the machine into thrash mode. (I've always found it amusing to see people wearing "Thrasher" T-shirts, by the way.) However, because I like "naive" programming, I've just decided to make my own graph library. Finding my distance to the nearest seed will have to wait until it's finished. ;-P

It's funny how quickly I can completely lose interest in practical problems ("What's my distance to the seeds?") in the light of solving something more abstract ("Write a graph library kind of like FGL but cooler, and with which my program works better.").

Anyway, I fully expect the following events to happen next (in any order):

  • The graph library will fail.
  • I will get certified at Journeyer level.
  • Someone will add the seed distance and all other interesting output to mod_virgule.
  • I will abandon my Advogato program.
But hey, it will be an experience. Right.

Wow, I just finished the slides for my Haskell talk (to be held at 21C3). Another Sunday in burst mode.
And strangely, it's fun... I think, I'll do it again.

Oh, and I'm writing an entry into a weblog, for christ's fucking sake! Yeah, there's a swear. I feel much better now. What is everybody's obsession with 'blogging? I don't feel like finding out, actually. But I can hardly resist the urge myself, to unleash on an unsuspecting world, the shocking facts that be. For example: I'm going to start a game of VGA-Planets soon. Nooo!? It's not true! Is it?

I guess the 'blog is giving me a chance to feel special. Thank you, 'blog. ...Blog.

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!