The field of Genetic Programming (GP) has always fascinated me, due to my interest in AI. But GP is a tough nut to crack. Genetic Algorithms (GA) is an easier stepping stone, that I wanted to try first. So, my interest was kindled when I saw jiva-ng, a scala based framework for GA.

After trying out some of the stock examples in the jiva-ng wiki, I was itching to try something a bit more involved, and I decided to try Graph Layout-ing.

Laying out a graph in 2D can be defined as the act of organizing the nodes of a graph (directed or otherwise) in a 2D space, adhering to some constraints. The constraints could be loosely defined for purely visual applications such as viewing a family tree, or a filesystem hierarchy. For more serious applications, such as VLSI design, the constraints may be stricter (and more specific). For now, let’s try something simple.

### Defining the problem

The given graph is described by N, the set of nodes, and E, the set of edges. Each edge is a tuple (N1, N2) where N1, N2 belong to N. We have to layout this graph in a visually pleasing manner.

Since the graph has to be plotted in 2D, each node has to be a co-ordinate pair (x,y). Let the number of nodes in N be n. Then x and y can be any integer [0 to n-1]. However, I couldn’t find an easy way to deal with co-ordinate pairs in jiva-ng, and hence I mapped the co-ordinates to an integer range [0 to (n*n – 1)], by arranging the co-ordinates row-wise.

In the above example, the above edge can be described as ((1, 0), (3, 3)) using co-ordinate pairs, or simply as (1, 18) when the nodes are mapped to the integer range.

With this, we are set to define the problem in jiva-ng as follows:

val problem = ProbBuilder.buildIntegerProb { buildr =>

val numNodes = GraphDescr.nodeList.length

buildr name “Graph Layout”

buildr popSize 6

buildr chrSize (numNodes, (numNodes * numNodes) – 1)

buildr numEvolutions 10

buildr fitnessFunction new NqFitness()

buildr defaultEvolver (0.5, 0.9)

}

With this definition, the jiva-ng evolver will create chromosomes that represent the position of our graph. Next, we need to define a suitable fitness function to choose the right chromosomes. As a first step, I decided to define fitness by the number of intersections in the graph (the one with the least intersections would have the highest fitness). To compute the number of intersections I implemented the Bentley-Ottmann Algorithm which is the most efficient in its class. A simpler O(n^2) algorithm would have worked too, but that wouldn’t have been fun 🙂

Now, the Bentley-Ottmann Algorithm as described in that link, isn’t as simple to implement if all corner cases are considered. To avoid these complications, I had to get rid of overlapping nodes. I used this simple trick:

Each line segment is shrunk by a small amount, to avoid intersections near end-points. To ensure that this solution works well, I first scale up the graph a thousand times, and then shrink the line segments by a few pixels.

With all this setup correctly, let’s see how our little genetic algorithm performs. I tried first with a simple graph with 4 nodes and 5 edges:

Well! Not bad! The layouts with less intersections indeed have higher scores! Next I tried, an 8 edged graph:

Works mostly correctly. There are two layouts with score 64.0 (the highest) and they appear correct. But there is one bad layout with a score of 64.0 too. See if you can spot it.

Next, I want to try these out..

- Refine the fitness function to so that layouts with roughly equal edge lengths are preferred. This can be done easily by finding the standard deviation of the edge lengths.
- Try this algorithm on a larger graph.
- Try genetic programming instead of GA.

## Leave a Reply