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
ch52jbAsked:
Who is Participating?
 
yodanConnect With a Mentor 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
 
inprasCommented:
Hi
Can U tell more specifically or can elaborate with an example Pl?

Regards
0
 
ch52jbAuthor 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
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

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

nil_dib
0
 
ch52jbAuthor Commented:
nil_dib, I don't want to use another persons library!
0
 
LucHoltkampCommented:
I wonder if this problem is standerd graph-theory...
If it's not you can use a Genetic Search
Luc
0
 
ch52jbAuthor 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
 
LucHoltkampCommented:
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
 
_lychee_Commented:
what's the approximate data size (nodes, edges)?
0
 
ch52jbAuthor Commented:
lychee, the data size varies, but probably will be no more than 200 nodes and 300 edges.
0
 
ozoCommented:
So averaging about 3 neighbors per node?
0
 
ch52jbAuthor 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
 
yodanCommented:
OOPS! I didn't meant to give answer! please reject it ok?
0
All Courses

From novice to tech pro — start learning today.