Automating Graph Layout

When working with graphs (the nodes and edges kind) on a computer, good arrangement and layout of the nodes is an interesting problem. To us, there is usually an obvious or at least visually appealing way to draw a graph, but a computer has no intuition (yet?) so finding a good layout for the graph can be difficult. It isn't hard to represent a graph as such in a computer, in fact things like adjacency matrices are probably much easier for a computer to read than a human, especially as you add more nodes.

There's also the problem of deciding what sort of layout is the right one for a given graph in the first place: Say you want to plot three things: A mesh network, a tree graph and a import/export relations between countries. Should each be laid out according to the same rules? Probably not - in a mesh network, we do not expect edges that reach far from one side of the graph to the other, so we can generally just place adjecent(in the sense that they are connected) nodes adjacent(location) to each other. A tree graph has a much different structure, in fact as the name implies, we would choose a tree-like layout. Import/export routes would of course be graphed according to actual geographical location, and even if not, the nodes are connected much differently. You might also want to assign a heavier weight or larger size to some nodes (according to GDP, for example).

For all of these, one can create different algorithms that find a good, or even optimal layout. Wikipedia actually has a page about some of them. 

You may remember that I briefly wrote about a project I was considering, namely an interactive Wikipedia (or other webpages, for that matter) grapher. The idea is this: you give the program a starting page, and it then represents this page as a single node. When you then click it, the page is parsed for links to other Wikipedia articles, and each is added as a node on the graph, with an edge to the original article. You can repeat this process for each new node, and edges are added whenever one article links to another one on the graph. 

I've started working on this project recently, and have found a good (but unfortunately somewhat slow - about O(n^3) ) algorithm to draw this graph. Force-based layout creates a layout by treating each edge as a spring that pulls adjacent nodes together, while simultaneously repulsing all nodes from each other using something resembling Coulomb's law, and then iterating until an equilibrium of forces is found. For now, I've only implemented a rough version of this algorithm in Python, but for the final program I'll be using C++, mainly to get better performance for the graphing, but also to gain a bit more experience with it. The drawing will probably be done in SDL, it seems simple enough to use. 

Source code of the above animation's algorithm (graph was generated randomly):

Fun with Kinect Colorization

So I finally got around to figuring out how to use the depth and video feeds from my Kinect using Microsoft's Kinect SDK, and this is what I produced after playing around with some visualization for the depth data. First two images are simply the distance for each pixel multiplied by either 3, 7 or 1 (green, blue, red) and then taken modulo 256, which makes for some pretty cool images. The last one looks a little less spectacular, but is actually more interesting: I wrote a little algorithm to color chunks of pixels of arbitrary size based on the average distance within the block, and then I only apply this coloring to the pixels that are actually a person, while other objects and the background are simply individually colored according to distance.

I'll try and get around to actually producing something useful with this soon, but I thought this stuff was kind of fun.

By the way, this is all written in C# and also uses WPF.

Completed Python Logic Circuit Simulator

Project website

Logic gates are interesting, with a few of them you can create circuits with fairly complex functions. Most of the time, the function of the circuit is anything but obvious from just looking at it. For example, consider this one:
That's an adder. You set the inputs A and B to True or False ( 1 or 0), and the circuit will perform a binary addition where S will give you the sum of the two, and C_out the carry bit. The carry bit can then be fed into another full adder at C_in, and you'll also have two more inputs. This can be expanded to any size one wishes.
All currently functioning computers rely on such gates. Most likely, millions and millions of them are in your cellphone.

If you're at least a little familiar with formal logic, more specifically logical connections such as "and", "or", "nor", "xor" (="exclusive or") and so on, the way these circuits work will probably make sense to you very quickly.

I've written a few posts recently about a logic gate simulator I am writing in Python, pyGates. I won't say I finished it, because there are still a few bugs that come up every now and then, but it's far enough along for others to use. Here's a screenshot of what it currently looks like:


You can create new gates by simply dragging them from the left side of the screen, and destroy them by simply dragging them back there. This is actually the only part where I still get bugs every now and then, sometimes cables don't get destroyed properly, but I'll work on fixing this. For now, you can usually work around that by manually deleting the cable - detaching it from the other gate it is connected to, and clicking into empty space.

The website for the project, a zip file with everything you need and the raw source code is located at my website here: http://home.in.tum.de/~dowling/pyGates/.

More pyGates

I'm making some more progress on pyGates, as you can see above. To my surprise, all the logic in the circuits worked out the first time I tested it, which is unusual for my code... Anyway, the logic for the wires has turned out to be much harder than anything else (connecting, disconnecting, reconnecting, in-sockets vs out-out sockets, etc.) I'm close to having it all work out though. Next, I'll have to add functionality to be able to delete Gates, which should be fairly easy. Finally, I'll make the cables look nicer (right now its just a fairly shitty bezier curve, which it will remain, but hopefully less shitty), and then I'll share the source code either on here or on my webpage, since it's really a bit too long to post here in full.

(By the way, the above circuit will constantly change state when you actually build it)

Project Ideas

Doing is the best way to learn, and since learning is what we're here for, let's do some stuff. I've had a number of different ideas for projects recently and not so recently, so to offer you some inspirations and perhaps for me to see if any of these still make sense when you see them typed out, I've compiled a little list of them. (Some of these are actually projects I've already started working on)

• "Multiplayer" Paint. Basically, this would be like a chat program that lets two (or more?) people draw on the same canvas as one would in mspaint. I would implement this in C++, just because I want to learn more about it (and graphics / network programming) but also because most people don't have Python interpreters with pygame on their machine. It might be time for something different :)
• Javascript multiplayer Paint! Use a JS canvas for client side, and save the changes to canvas stored server side (maybe use php, or node.js for serverside scripting?) Then, everyone who visits the page can draw on it for everyone else to see. Obvious downsides of this however are the fact that this is still the internet, and I suspect sooner or later (sooner) it will meet a similar fate tot that of Chatroulette
  
• A 3-4 DoF Robotic arm. It doesn't have to be a very good one either, just to keep costs down. Forward and inverse kinematics are pretty interesting, and this would be a good way to learn and practice both. Servos can be picked up pretty cheaply as well, and the whole thing could be run from an Arduino - the only real difficulty in this would be the mechanical parts, I have no good way of making them properly. I got this idea from...
  
• .. building a hexapod. 3DoF would be minimum for each leg to be able tog et decently smooth motion, the problem is that this would be a rather costly product (for me, at least)
• A simple webcrawler. I don't know what you would use it for, but my ideas were perhaps a Reddit bot (find/keep track of reposts, produce statistics based on comments, find most used pun of the day, etc.), or a Wikipedia crawler (create a graph of pagelinks, those are always neat)
• On a similar note, implementing a graphing layout algorithm - finding a good layout for graphs (graph meaning a set of nodes connected by edges) automatically. There are different ways to implement this, the spring model seems like the simplest: each edge is like a spring that pulls two connected nodes together, or pushes them apart based on their distance from each other. One could also base the pushing/pulling force on the "weight" of each node (weight could be number of incoming edges, for example)
• implement quantitative stock trading algorithms. This is something I personally find really interesting, though I haven't worked on it much. Wikipedia has a nice page about the different algorithms that are used today. A technical problem that needs to be solved first is getting a decent sample of historical data for a given stock, as this is very often necessary for such algorithms.

Of course these all aren't new ideas, but I've found that I usually have good ideas while working on something else, and these are just inspirations for you anyway. Potentially all of these are good for learning something new!

MaterialMaker tool for TUM informatics

I've been meaning to try out some C# programming, so I collaborated with a friend of mine who is pretty experienced with it on a small but useful project - a tool to automatically download and display our class materials. He had already coded up the interface and execution logic during a particularly boring lecture, but it was all hardcoded to his filesystem and required the materials to already be downloaded and in the right folders. I figured it would be useful to add some functionality and let the program automatically download the latest materials and organize these in a generic directory it creates itself.

To get to the materials, I used RSS links that contained .pdfs and .zips of all the files. I wrote some parsing logic for these, which basically looks for tags and then extracts the direct link to the file. The filename is then checked with the local folders, and if it isn't already there, the file is downloaded.
Screenshot:


If you're a CS student at TUM and would like to use this tool, you can download it from my website: http://home.in.tum.de/~dowling/index.html. It shouldn't be too hard for me to add support for other classes, if you're interested just shoot me a message.

Progress on pyGates

Yesterday I wrote a short paragraph about a project I recently started, a logic gate simulator written in Python (short: pyGates). I spent a night and most of todays classes coding on it, and it's starting to get to a point where it's almost usable. I still need to implement a few more things such as switches and lightbulbs, perhaps I'll add some higher-level logic chips later on, but the basic structure is put together and the wires will also finally behave properly (in terms of connecting to the right sockets and staying there, that is).

Next up is fixing up the graphics, the main thing here is to put in the standardized symbols for the different gates, and making the wires look nice (I'll probably have them hang down as though they were loose cables, similar to logicly). Below is a screenshot of what the program currently looks like (yes, the gates look the same even though they serve different functions).

Basic stock price functions in Python

I've been reading a bit into algorithmic stock trading lately, and thought I'd try and actually simulate a few of the trades strategies. The first thing I needed was a way to get at the stock prices, I figured the easiest way might be scraping either Yahoo or Google Finance. Turns out someone else has done this before, so no need to code it up myself. I think Google Finance has been updated since that module was written, because the regex used doesn't properly fetch the actual price. All I had to do was modify the function in a few places and everything was working as expected.
A neat thing about it is that you don't need to pass the exact ticker symbol you want to get a quote for into the get_quote function, since the stirng gets passed as a query to Google Finance, which autocorrects it.

I also added a stock class, as well as long and shot sell functions. This should be a good enough start to simulate some algorithmic trading.

pyGates

Something I've recently thought about was creating a small logic gate simulator which lets you build simple digital circuits. I've seen this elsewhere before (http://logic.ly/), with a very neat implementation but unfortunately that software now costs money. It shouldn't be too hard to brew something like this together, so I'll give this a shot over the next couple of days and see how it goes. I'll be using python for now just because I like working with it the most, but I might take this as an opportunity to learn JavaScript and host this online. I've already started working on this and have the basic structure together, all it is really is a pygame canvas with gate-objects and a few other things, but it may still take some time until it all comes together in a usable way. I'll keep you posted.