Graph algorithm

Hi
Can U tell more specifically or can elaborate with an example Pl?

Regards

Imagine a layout of nodes and interconnecting lines in 3D, with rings and chains.  When viewed in 2D, there will be overlap of nodes, and the interconnecting lines will be of differing length.  I need a means of rearranging the 2D layout of nodes so that the resultant layout has minimal line overlap, no node overlap, and is laid out in the clearest means possible.  If you've got an email address, I can send you some pictures showing the before and after states.

http://www.cs.uni-sb.de/RW/users/sander/html/gstools.html
http://i44www.info.uni-karlsruhe.de/~frick/gd/index.html

http://www.mpi-sb.mpg.de/LEDA/leda.html

nil_dib

I'm really after an algorithm, as opposed to a set of tools...

One possible algorithm would be to sort the nodes on the number of connection it has. Then take the one with the largest and put it on the 2D layer. Then put any connecting nodes onto the layer without any overlap. Repeat until no more nodes are left.

I don't understand what you mean.  Can you explain a bit more please.

the algo's wrong if u can have cycles within the graph cos it doesn't specify how to lay out the connecting nodes... so suppose it is ?random?

        C
             F
      B A D
             G
        E

A connected to BCDE; D connected to FG; G connected to B

since the algo is a step by step one (starting with most nodes) u lay out BCDE first... then D has most -- so u lay out FG, then when G is connected to B u have a intersection that is not necessary

Hi
Sorry for delay
My email id is inpras@hotmail.com
U can send me details there
Regards

You might try simulated annealing to minimize the energy of overlaps

The graph can hav many cycles, and bridges across cycles are also possible.

look at the link! its a complete c++ lib for handling complex algorithms based on the graph theory ...

nil_dib

nil_dib, I don't want to use another persons library!

I wonder if this problem is standerd graph-theory...
If it's not you can use a Genetic Search
Luc

Luc, what is a genetic search.  Is it similar to a genetic algorithm, i.e. try different layouts, compare tham against a fitness function (e.g. no of crosovers etc) and reproduce, cos I thought about using genetic algorithms, but I'm not to sure how fast they are, speed is important.

Yes, it's the same, and no, it will not be fast, however it is a relatively simple problem, so you will probably be able to test several thousand cases a second... I don't know how important speed is here? But you must think of a (few) second(s) solving time if you use a GA.
Graphs algorithms are not my speciality, but as far as I know, there is no ready to use algorithm for this case? But a GA is easy to implement, and (almost) garanteed to find a good solution. So that's why a GA might be a good choice.
Luc

what's the approximate data size (nodes, edges)?

lychee, the data size varies, but probably will be no more than 200 nodes and 300 edges.

So averaging about 3 neighbors per node?

Normally, averaging one edge per node, but it a worst case, 3 per node (the 200 nodes/300 edges is a worst case, normal usage will be around 20 nodes and 20 edges)

OOPS! I didn't meant to give answer! please reject it ok?