make clean

December 6, 2007

Graph Layout using Genetic Algorithms

Filed under: Uncategorized — harshadrj @ 11:48 pm
Tags: , , ,

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.

GraphDefine

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:

GraphLineShrink

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:

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

GraphPerfect8

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.
Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: