Compacting mathematical graph

Question

I want to draw a graph that will be something like this: alt text http://img25.imageshack.us/img25/9786/problemo.png

You can see 3 pathes: a, b & c. How can I change position of elements (1,2,3...,9) to make long of the path as short as possible? I mean this lines should be as short as possible.

Im very interested in it becouse I am drawing a graph with question, some kind of infographic like 'follow the lines to know the answer'. I know that its a bit about graph theory... so if its too hard, do you know if Is there any program for linux to compact stuff like this?

For example program should work like this: In input it should get 3 pathes

a='1,5,7,8,4,2,6'
b='4,2,3,6,9,8,5'
c='7,9'

And in output in should be coordinates of this elements.

Answer 1

Whenever I have an optimization problem that is difficult to solve, I think of genetic algorithms. My solution below assumes that you are familiar with GA (not very difficult to implement it yourself)

Looking at the example graph you gave, let us suppose that the nodes will be placed on a NxN grid (integer positions), then to codify the genomes, consider the following scheme:

00101 00100 11010 11110 11000     
  A     B     C     D     E

where each part encodes the position in the grid (in binary) of the nodes (in that order). The length of each part depends on the size of the grid ( length=ceil(log2(N*N)) ).
The grid is numbered row by row, left to right.

So as an example, for a complete graph with 4 nodes (A,B,C,D) and a 3x3 grid, the string:

0011 0001 0101 1000    =   3  1  5  8 
 A    B    C    D          A  B  C  D

represents the following layout:

. B .       00  01  02
A . C       03  04  05
. . D       06  07  08

Next we design the crossover operator as usual (one- or two-points crossover), and mutation as well (flip one bit at random). We just have to make sure that at any time, we only have valid positions inside the grid.
Finally the fitness function will be some function of the distances between the nodes on the path (sum for multiple paths), which will penalizes long paths (as a minimization problem). An example is to take the city-block distance between the nodes.
The rest of the method is the standard genetic algorithm (initialization, evaluation, selection, reproduction, termination).

Example To illustrate, consider the previous layout with the city-block distance, given the following two paths: A D C B and C B D A

A -> D -> C -> B
  3  + 1  + 2    = 6        therefore
C -> B -> D -> A              fitness(0011 0001 0101 1000) = 6 + 8 = 14
  2  + 3  + 3    = 8

Obviously the goal is to find the layout that minimizes the fitness function.