Balancing Graphs in O(n*log(n))

The Barnes-Hut algorithm is used to model N-body systems more efficiently, at the expense of precision. However, the improvement in performance is tremendous: from O( n² ) to O( n*log(n) ). For reference, this is what that looks like:

Since our force-based approach to computing graph layout is essentially nothing other than an N-body simulation, and we don't require great precision anyway, this algorithm seems perfect for us to use. The way it works is basically this:

• The set of nodes is sorted into a quadtree, which is essentially a binary tree, but with an added dimension
• Each of the quadtree sectors keeps track of its mass and center of mass
• To compute the forces, the tree is traversed and for points that are "far" from a certain center of mass, only the force from the node to that center of mass is calculated, as opposed to each force between all nodes

This leads to a significant decrease in overall calculations that needs to be done, since distant nodes no longer need to interact directly. There is some overhead on creating the quadtree every frame, but the growth of this is also O(n*log(n)). If you want to learn more, here is a very good explanation of the algorithm complete with pseudocode (in German, but the code is understandable anyway). 

I haven't had time to implement this algorithm in our Qt application to graph Wikipedia, however I managed to code up the basic algorithm in Python. The improvement is tremendous, before I was never able to reasonably run a simulation with more than 80 or so nodes in Python, now even systems up to 350 nodes run at a reasonable framerate.

Illustration of the quadtree (unbalanced)

The same graph after balancing

The algorithm can also be parallelized very well, so the potential of this is tremendous, with good implementation and appropriate hardware we could realistically graph all of the German Wikipedia (~1.3 million articles), maybe more. 

The full Python code is here.

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):

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)

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.

Simulating birds

TL;DR: I wrote a simulation of swarming birds in Python using Pygame. The code can be found here.

So a while ago I caught a a bit of a documentary about swarming behavior in birds and fish, and I was interested to see if I could manage to write a little program to simulate such behavior. It's pretty interesting how the behavior of each bird is pretty simple and easy to model, yet on the macroscopic side, complex patterns emerge in such a system.

It's not too difficult to think about the behavior of each bird in a swarm:

1. Primarily, it will try to stay with the rest of the swarm, which on one hand means that it will stay relatively close to the groups "center" (i.e. their average position), and on the other that it will roughly match the velocity of its neighbors (especially in terms of direction).
   
2. Each bird also has it's own free will. On average of the whole group, this will determine the swarms tendency of movement.
3. Finally, the swarm as a whole may be drawn to some type of goal (e.g. food), which means that when simulating a swarm, each bird will sooner or later move towards this goal, though it will likely be more influenced by where the rest of the group is going.
   

I won't tediously take you through every line of the program I ended up with, but I think for anyone interested in this type of program, there's two major things about my model that are worth noting.

View

It should be taken into account that birds will only be drawn to the birds that they actually see, so for my program I implemented a view angle that is used to determine what other birds each bird uses to orient itself.
In an earlier version of this program, each birds navigation was based on all birds within a certain radius, which ended up having the swarm group together much more closely, but ultimately didn't look natural.

So how can it be determined if one bird can see another? The simplest (and really the only practical) way to do it involves the scalar product of the "seeing" birds' (B1) velocity vector and the vector from that bird to the one the whose visibility we are trying to determine (B2).








If theta is smaller than the defined viewing angle of the birds, then B1 can indeed see B2.

In Python, we can write the following function:

def isinview(x, y):                      
 if x==y:                              
     return False

 b1b2v = [birds[y][1][0]-birds[x][1][0],
     birds[y][1][1]-birds[x][1][1]]

 if (b1b2v[0]*birds[x][2][0] + b1b2v[1]*birds[x][2][1])/(vmag(b1b2v)*vmag(birds[x][2])) <= viewangle:
     return True
 else:
     return False

Note: The viewangle variable is stored as the cosine of the desired view angle, so that acos() doesn't need to be called hundreds of times in every frame.)

To clarify, in the program, the birds variable is a list containing the data for each bird:

• birds[n] is the nth bird
• birds[n][0] is the nth bird's "name" (for debugging, highlighting certain birds, etc.)
• birds[n][1] refers to the nth birds' position
• birds[n][2] is the velocity
• birds[n][3] and [4] are the last two velocity vectors, these are used as a component for the velocity calculation in every frame to simulate inertia, so that individual birds don't change direction so suddenly, leading to a more natural looking flight path.

Weighting

The other thing that needs to be considered is the weighting of the individual velocity components. Each birds' velocity in every frame is based on a number of factors: their free will (in the program, this is a random vector), the visible birds' positions, their velocities, a goal point, the birds past velocity vectors (inertia), and if so desired, the positions and velocities of all birds within a certain radius.
It needs to be decided how strongly each of these components should influence the birds flight. For instance, the random vector should probably be a weaker component than the inertia component, or the component that points towards the average position of the other birds should be fairly weak, otherwise the swarm will almost certainly never spread apart much.

The velocity vectors are therefore calculated this way: each component is assigned a "weight" in the beginning of the program. Each component vector is multiplied by its corresponding weight, and then all components are added together. Finally, the two numbers making up this sum vector are then each divided by the sum of the weights. This effectively creates sort of a weighted average. Perhaps this is not the most mathematically valid way to do it, but it enables us to alter the swarms behavior by playing with the weights of the individual components. For example, we can make the swarm more likely to spread apart by lowering the weight of the visible birds' positions to velocity.

If you would like to try out or play with the simulation yourself, the full code can be found here.

If you found this interesting, you may also be interested in Craig Reynolds' website on boids, he created and continues to work on sophisticated model of this phenomenon since 1986, there's tons of reading material on related subjects there, too.