# Graph algorithm

I'm after an algorithm for organising a graph.  I have a number of points connected by lines, arranged in a 3D structure containing rings of nodes, chains etc.  I need to rearrange this structure into a 2D structure with all lines the same length and all nodes layed out in the clearest form, with minimal overlap.  Any ideas?

Cheers
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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

Regards
0
Author Commented:
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.
0
Commented:
0
Commented:
0
Author Commented:
I'm really after an algorithm, as opposed to a set of tools...
0
EngineerCommented:
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.
0
Author Commented:
I don't understand what you mean.  Can you explain a bit more please.
0
Commented:
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
0
Commented:
Hi
Sorry for delay
My email id is inpras@hotmail.com
U can send me details there
Regards
0
Commented:
You might try simulated annealing to minimize the energy of overlaps
0
Author Commented:
The graph can hav many cycles, and bridges across cycles are also possible.
0
Commented:
look at the link! its a complete c++ lib for handling complex algorithms based on the graph theory ...

nil_dib
0
Author Commented:
nil_dib, I don't want to use another persons library!
0
Commented:
I wonder if this problem is standerd graph-theory...
If it's not you can use a Genetic Search
Luc
0
Author Commented:
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.
0
Commented:
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
0
Commented:
what's the approximate data size (nodes, edges)?
0
Author Commented:
lychee, the data size varies, but probably will be no more than 200 nodes and 300 edges.
0
Commented:
So averaging about 3 neighbors per node?
0
Author Commented:
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)
0
Commented:
I have some (initiate) knowledge in graph theory and I am doing some work in the area (finite State machine induction) and I will be interested in knowing more about this or similar problems. Know good references (books, progs, www links)?

From what I read you want to represent your graph in the form closest to a lattice, right?
You have several "Artificial Inteligence" techniques for that:
(You probably already have background in this, but rembering this cant hurt, OK?)

--> graph-search (maybe the GBF is an approach provided you   choose two good heuristics)
--> genetic approach changes with evaluation changes, has proposed
--> planning (like graph-search but using more knowledge   about specific problem - if you have it). Maybe lattice
knowledge will help, like: a closely connected non-overlapping
subgraph can be determined by..., then you may choose the
remaining hard(overlapping) points and accept some
overlappings.
--> searching but using CSP (constraint Satisfaction Problems)    techniques. You may like to see the ILOG company on net,    they may have some whitepapers that interest you -- uh,    www.ilog.com i think.
--> combining techiques.
0

Experts Exchange Solution brought to you by