Graph Layout Algorithms
Hi, I'm trying to research Graph Layout to find some algorithms. I basically have to assign geometric data to some lines and nodes as part of an electrical system.
I'm not necessarily looking for code, but perhaps pseudo code or algorithms which would help me generate a graph which could be analyzed.
I've done several searches on the web, but I just get programs which implement these algorithms but do not necesarily show or teach you how.
Does anyone have any suggestions for me?
Thanks!
[525 byte] By [
joel24a] at [2007-9-29 23:42:45]
The name for this field is Graph Drawing. The first Google hit for "Graph Drawing" turns up a resource which has links to various subscription online papers, a basic tutorial, etc.
Hi,
Are you looking for code that generates a graph structure (possibly random) or code that calculates a layout for a given graph structure?
If the former is the case, take a look at the demo source code for a random graph generating algorithm of the yFiles library:
http://www.yworks.com/products/yfiles/doc/demo/demo/base/RandomGraphGenerator.java.html
(yes, the link is correct)
Greetings, Sebastian
I'm most likely looking for some type of hierarchichal (sp?) layout.
I would prefer not to have edges cross, although that may be impossible in some circumstances.
I have a series of nodes and lines with no geometrical data. My project is to assign these appropriate geometrical data which will generate a graph that would be suitable for analytical purposes.
try citeseerfor example http://citeseer.nj.nec.com/cs?q=graph+layout&cs=1matfud
> I'm most likely looking for some type of hierarchichal
> (sp?) layout.
One of the most famous implementations for hierarchic layouts is by Sugiyama (use this in your google search).
> I would prefer not to have edges cross, although that
> may be impossible in some circumstances.
Not only may this be impossible (very often), the problem of finding a solution even if one exists is NP-complete, i.e. it might well take "forever" finding such a solution for non-trivial graph structures.
In our graph layout library yFiles, we are using clever heuristics for finding 'good' solutions, but they may not be optimal. You may give our free graph editor yEd a shot: among other layout styles it demonstrates the hierarchic layout style nicely:
http://www.yworks.com/products/yed/ (there is a webstart link)
If you are looking for free source code you could take a look at the JGraphPad implementation of the Sugiyama layout. Although this is a very rudimentary and not at all optimized version it could be of use for you to get into it.
>
> I have a series of nodes and lines with no geometrical
> data. My project is to assign these appropriate
> geometrical data which will generate a graph that
> would be suitable for analytical purposes.
Please be aware that this is anything but trivial, you might want to consider using one of the commercial libraries, depending on what kind of project yours is.
Regards, Sebastian
>> I would prefer not to have edges cross, although that
>> may be impossible in some circumstances.
> Not only may this be impossible (very often),
Offhand, I know it is possible to determine if a graph is planar in O(n) time. Offhand, I thought there existed an algorithm to perform the planarity test and layout at the same time.
However, an NP problem is to determine the minimum thickness of the graph (I think).
I appreciate all of your responses very much. I'm going to start looking into them right now.
Please be aware though that I am doing this as part of my co-op placement, so I'm not interested in using other software. I have to design this on my own. I'm also aware that this is not trivial and could take me quite awhile. I'm assuming this is probably the equivalent of a 4th year honors project!
Thanks for the help.
>>In our graph layout library yFiles, we are using clever heuristics for finding 'good' solutions, but they may >>not be optimal. You may give our free graph editor yEd a shot: among other layout styles it >>demonstrates the hierarchic layout style nicely:
>>http://www.yworks.com/products/yed/ (there is a webstart link)
I'm assuming that although this is a free download that the source code is not public?
Does the hierarchical layout on yEd implement the Sugiyama layout?
> >>demonstrates the hierarchic layout style nicely:
> >>http://www.yworks.com/products/yed/ (there is a
> webstart link)
>
> I'm assuming that although this is a free download
> that the source code is not public?
that's right (although you *can* purchase a source code license, but well, it is not too inexpensive for private use ;-) )
> Does the hierarchical layout on yEd implement the
> Sugiyama layout?
yes, it does - although we have modified most of the parts of the algorithm, the basic structure is that of sugiyama.
If you take a look at the API, you will recognize the different sugiyama layout stages:
http://www.yworks.com/products/yfiles/doc/api-gif/y/layout/hierarchic/package-summary.html
(BTW, the UML graphic at the bottom of that page has been calculated using a variant of the hierarchic layout algorithm)
Maybe the API will give you some hints on what you have to (or could) consider during your implementation.
Regards, Sebastian
> Offhand, I know it is possible to determine if a graph
> is planar in O(n) time. Offhand, I thought there
> existed an algorithm to perform the planarity test and
> layout at the same time.
yeah, but the resulting layout is truely ugly :D (this is a theoretic layout only!)
> However, an NP problem is to determine the minimum
> thickness of the graph (I think).
The thing that is NP complete in the hierarchic layout algorithm is the stage where you determine how to sequence the node in one layer. Consider the following:
N1 N2 N3 N4 N5
|/\ |//\ |/
N6 N7 N8 N9
(not a very good ascii art, I must admit. This is supposed to be two layers of nodes interconnected with an arbitrary number of edges.
The nodes n1 to n5 reside in one layer and nodes n6 to n9 reside in the next adjacent layer.
It is NP complete to compute the order of the nodes N1 to N5 and N6 to N9 so that the number of the crossings generated by the edges going from one layer to the other is minimal.
In the hierarchic layout, you need to perform this computation for k layers, not only for two.
Sebastian
Sebastian,It is possible that my graph will have cycles. Is it still okay in this case to use the Suiyama method, or will I need to look into something else?
hi,
take a look at yEd: it *is* ok. although you will have to reverse some edges for the ordinary algorithm to work, i.e. make the graph acyclic by reversing some edges.
Basically, after you have assigned each node a layer using whatever strategy (in yEd: Layout->Hierarchical->Node Rank->Ranking Policy), you should make sure that for the time of the computation, every edge points downwards - this will ease up implementation drastically.
BTW: our source code for the hierarchic layout algorithm is more than 10.000 lines of code not counting any of the framework classes, so you better start coding now :D
regards, sebastian
Sebastian,I must say yEd is fantastic. I can't believe how nice the output is.Yes, I realize this is going to be a lot of code!! I laughed when I read what you said. Are you available for contact if I have any questions for you? Or do you prefer to just use this forum?
> I must say yEd is fantastic. I can't believe how nice
> the output is.
:D
> Are you available for contact if I have any questions
> for you? Or do you prefer to just use this forum?
well, you could reach me via email at my office address. it is the canonic email address for
sebastian mueller at yworks com (the one with the dots and the @ )
but since you are not (yet ;-) ) a customer of our company, I don't think this is the best way, so we should stick to this forum :D
also you should knwo, that I will not and cannot tell you any secrets about our software, however I may answer some more general questions.
Regards, Sebastian
Ok, no problem. I do have a question for you though.
I've found a couple different pseudo-code versions of the Sugiyama algorithm. The basic version of it seems quite straight forward, however, one of the first steps is to assign nodes to layers.
I guess my quesion is simply: how would I go about doing that? or getting some ideas on how to do that?
I would be starting off with a series of lines and nodes, and I know which nodes are assigned to which lines already, but I'm not sure how to go about layering them.
Hope my question is clear.
> I guess my quesion is simply: how would I go about
> doing that? or getting some ideas on how to do that?
Since you want most of the lines/edges pointing downwards, you will have to find an ordering of the nodes so that for each edge e (v -> w) layer(v) > layer(w) (if this cannot be satisfied, you will have to reverse some edges).
this can be done by sorting the nodes (google for:) topologically. this leads to acceptable results. you can also use linear programming techniques (simplex algorithm), which leads to very good results, but I don't think you will have to go that deep into it. use a topological sorting on the nodes: this is quite simple and sufficient.
The yFiles API provides different layering strategies: y.layout.hierarchic.Layerer implementations
(see http://www.yworks.com/products/yfiles/docs/ )
among them are Topological sorting variants (using DFS like traversals), a BFS variant, a "Tight Tree" variant and a near optimal "Simplex" variant (called WeightedLayerer) plus some special purpose layering strategies.
regards, Sebastian
> Since you want most of the lines/edges pointing
> downwards, you will have to find an ordering of the
> nodes so that for each edge e (v -> w) layer(v) >
> layer(w) (if this cannot be satisfied, you will have
> to reverse some edges).
What if I have a scenario where there are 6 nodes and 6 edges, where the last edge connects the 6th node back to the first one? I ran this on your program and it seemed to work fine. Will I still be able to do a topological sort? This would be an unusual case for me, but still quite possible.
Actually, to answer my own question, I've come to the realization that I'm working with an undirected, cyclic graph. I realize this is going to make things even more difficult for me! I guess a topological sort won't do, so I'll have to look up some others!
For undirected graphs, you should look into Kamada-Kawai and/or the Fruchterman-Reingold algorithms. There is plenty of pseudo code around for either of these if I recall.
Actually hierarchic layout is not very well suited for undirected graphs (they don't have any inherent hierarchy).
But you could nevertheless use topological sorting: Pick one node at random (maybe you have one "important node" or "start node" or whatever special kind of node) and do a topological sort. Whenever you encounter a problem (i.e. a cycle) discard the edge and just go on sorting topologically. You will end up with a layer assignment with some edges pointing "upwards" - the ones you discarded previously. Just "reverse" them (think of them as directed during the layout) and you can go on with the algorithm.
However for a truely undirected graph, I would recommend different layout algorithms. yEd offers one of the best available springembedder algorithm (fast and very good results). It is called "Organic Layout" or "Smart Organic Layout". For a more "technical" diagram, you could have a look at the "Orthogonal Layout". If you want to implement one of them: Basic Springembedders are relatively simple, but don't even think about trying to reimplement "Orthogonal Layout": it took us years of development and research to come this far and compared to this implementation, the >10.000 lines of source code for the Hierarchic Layouter are just a laugh :D
Regards, Sebastian
Well the only problem with a spring-type algorithm is that it doesn't necessarily minimize edge crossing. But I will still look into implementing a topological sort.
I'm thinking I'll just throw an exception if a cycle is found, and then I'll remove the edge, but store it to be used later once the graph is generated.
When I said "hierarchical" earlier, I undestood that there was no inherent hierarchy in my situation, however, it is still the "look" of such a layout that I am looking for.
Sebastian,
I was thinking of trying just a simple top. sort to get going. After adding one node to a queue, this would be my main loop:
while (!q.empty()) {
v = q.dequeue();
v.topNum = ++counter;
for each w adjacent to v
if (--w.indegree==0)
q.enqueue(w);
}
if (counter != NUM_VERTICES) {
throw new CycleFound();
}
So what you're saying is to just remove an edge if a cycle is found. So should I add a check in the main loop like this:
for each w adjacent to v
if (--w.indegree==0)
q.enqueue(w);
else if (w.indegree < 0)
throw new CycleFound();
(the else is the added part)
It seems to me that if a cycle exists, I am going to re-enumerate a node which was previously added to the queue, which means it's # of indegrees will already be at zero.
What do you think?
It is even simpler: if you traverse an edge and reach a node that has already been handled (been in the queue), just do nothing, i.e. ignore the edge for the purpose of the topsort. For bookkeeping purposes however, I would collect all of these edges (these are edges, which must be "reversed" for the algorithm to work).
Ok, makes sense. One more question and then I'll leave you alone for awhile!
In the top. sort, all that I see happening is that a node gets assigned a number according to when it was dequeued. What does this have to do with layering? Every node will receive a unique number, so obviously this is not a layer number.
Hope this makes sense?!?
By the way, you've been more than helpful and I really appreciate it.
(Nevermind on the last question... got it figured out)
You may like to take a look at http://gef.tigris.org this is the graph drawing toolkit used by http://argouml.tigris.org
They are both open source projects and good form the basis for you to demonstrate you algorithms with.
ArgoUML does use some "layouters", I'm not sure if these are built into base GEF or in ArgoUML.
If you can provide any better algorithms then they would be of interest to these teams.
Bob.
Yes, I liked the web-site for Y.
NOW ABOUT THE PRICE!!!
$6,000 US dollars seems a little hefty, for personal use, don't think!? And then there is the conversion....
Perhaps you want to backdoor me a copy for say, $60.00 (canadian!). I need just the treelayout.
Thanks in advance,
Andrew
This is not the right place for talking about product pricings. I certainly don't want to get banned by the forum administrators. For commercial information, please contact the corresponding companies directly.
If you are interested in general layout questions, however, I am sure that we can use this forum, since many of its users seem to be interested in such questions.
> Yes, I liked the web-site for Y.
>
> NOW ABOUT THE PRICE!!!
>
> $6,000 US dollars seems a little hefty, for personal
> use, don't think!? And then there is the
> conversion....
Ok, since you asked for it I will make a short statement that should be true in general:
This might seem a lot of money, but it is ridiculously cheap compared with the amount of work you would have to invest to get something that is not even close to as powerful, versatile, tested ....
Also, you don't have to invest 6,000 US dollars, if you are interested in the tree layout only, the Layout package should be sufficient for you and cost only a bit more than 4.300 US dollars. I don't know what project you are working at, but if you are working for an academic institution, the price is 80% *OFF*.
That is for an academic license covering the layout package only, you would have to pay as little as about 800 US$ dollars. Please be aware, that this is the price for a developers license, i.e. you are allowed to use it in as many projects as you like and distribute your finished products to as many people as you like without having to pay any royalty fees!
Talking about conversion: the price of the US$ hasn't been that low for quite a long time, so you should be lucky!
> Perhaps you want to backdoor me a copy for say, $60.00
> (canadian!). I need just the treelayout.
:)
If this is all you want to invest, I suggest you better save the money and try implementing this layout yourself. Layouting a tree is (apart from random layout) by far the simplest layout one can implement. There is a lot of literature that will help you in creating a *simple* tree layout algorithm. Use google and (hint:) recursion for the layout - it IS more or less trivial.
> Thanks in advance,
>
> Andrew
PS: Now, please don't start a flame war about commercial software/ open source and all that stuff, this is DEFINITELY the WRONG place.
Regards, Sebastian Mueller
ya, I know, I know.I got all excited looking at the cool stuf on the web site. The discovered I had to use something else...Andrew
Hey Sebastian,
Quick question for you. I've managed to perform a topological sort on my nodes, assign them to appropriate levels, and then apply the Sugiyama method doing the up and down barycentres.
The one question I have right now is this... if the first level has say 50 nodes, and the second has 10, I would like the 10 nodes to be centred under the 50 nodes, not have both levels starting drawing from the left of the screen. Do you have any suggestions for this type of positioning?
Thanks
Joel
Hi again,
First of all: Congratulations, you seem to have come quite far!
There are quite a number of different possible solutions to your problem. In yFiles / yEd this stage of the algorithm is called the Drawer and implements the y.layout.hierarchic.Drawer interface.
You can use algorithmic approaches for this kind of problem (using Linear Programming for example) or algorithms that simulate the physical behavior of masses that are interconnected by springs. However if you want to have them centered, you can simply calculate the widths of each level/layer and align all layers at their centers, although this may lead to very bad results.
There is not too much literature about node/vertex placing or node placement (the last stage/ the drawing stage/ the third sugiyama layout stage), but you might get some hits in google using these terms.
Hi again,
First of all: Congratulations, you seem to have come quite far!
There are quite a number of different possible solutions to your problem. In yFiles / yEd this stage of the algorithm is called the Drawer and implements the y.layout.hierarchic.Drawer interface.
You can use algorithmic approaches for this kind of problem (using Linear Programming for example) or algorithms that simulate the physical behavior of masses that are interconnected by springs. However if you want to have them centered, you can simply calculate the widths of each level/layer and align all layers at their centers, although this may lead to very bad results.
There is not too much literature about node/vertex placing or node placement (the last stage/ the drawing stage/ the third sugiyama layout stage), but you might get some hits in google using these terms.
Whoops, I am sorry for posting twice, I received a server error, the first time I posted :-(
Sebastian,
Now it's time for me to move on and try another algorithm. I've been able to deterine that the Sugiyama method is not the best for what I'm working on. I think its mostly because I can have up to hundreds of node that need to be layed out appropriately.
Maybe I'll look into a SpringLayout algorithm or something. Do you have a suggestion?
Thx.
> I think its mostly because I can have up to
> hundreds of node that need to be layed out
> appropriately.
This is not a problem: in yFiles / yEd, we use the sugiyama algorithm to layout thousands of nodes. Although I doubt Sugiyama is a good algorithm for undirected graphs, as it is in your case.
> Maybe I'll look into a SpringLayout algorithm or
> something. Do you have a suggestion?
The style of spring layouts (in yFiles: "OrganicLayouter" or "SmartOrganicLayouter") differs completely, but is relatively easy to implement. Be aware that using a generic implementation this layout will take O(n^3) running time, which is a lot for "hundreds of nodes". The yFiles OrganicLayouter (and especially SmartOrganicLayouter) is highly optimized and can lay out thousands of nodes in acceptable short time (usually a few seconds at most) (even hundreds of thousands of nodes are possible - but this may take a day and several gigs of memory).
In order to give you the best advice I would need to know more about the graph structure and the semantics of it as well as what especially should be visualized.
'hope this helps - Sebastian
I think I've come to the realization that I'm going to have to completely rethink my approach!
My graphs just have too many cycles for any of the algorithms I've tried to work well. Maybe one idea would be too handle just the cycles first, and then add on any strands later on using a Spring Embedded layout.
What do you think?
I've even tried some messy layouts on yEd and it doesn't seem to do that great of a job either, but I realize that messy is messy and there's only so much you can do.
> I've even tried some messy layouts on yEd and it
> doesn't seem to do that great of a job either, but I
> realize that messy is messy and there's only so much
> you can do.
This I cannot believe until I have seen it; could you provide me with some of these mysterious "unlayoutable" graph structures?!
Sorry I think I came across the wrong way! I wasn't dissing your program or anything. I never said the graphs were "unlayoutable"!
I just noticed that sometimes there are "unnecessary" edge crossings in some larger graphs - but I would assume that to be typical.
As for my assumption that I was having problems because I'm dealing with too many cycles - I'm not sure sure that was correct. I've run a simple DFS traversal on some of my graphs - and even on a larger one it only seemed to find one cycle.
So obviously I'm having other problems!
Here's a yes-or-no answer question:
If a cycle is found, is it possible to determine all of the nodes that make up the cycle?
> Here's a yes-or-no answer question:
> If a cycle is found, is it possible to determine all
> of the nodes that make up the cycle?
Yes
well....
(that's easy: use DFS to detect cycles and if you find one, you can easily traverse the dfs tree back to the root until your paths cross and there is your cycle. BUT: as far as I can remember it is NP-complete finding the longest cycle, i.e. it will take you a long time and you may be just as fast by simply guessing cycles. However using the DFS method you will detect one cycle after another, remove it and continue until no more cycles are found.)
Yes, DFS is what I've been working on since I posted that message. I'm not worried about the longest cycle by any means.
I was just contemplating an approach whereby I would layout the cycles first, and then perhaps apply some sort of Spring algorithm and lay out the rest of the nodes (which are not part of a cycle) next.
Sebastian,Is it possible to generate a graph with yEd which is both connected and undirected? I can't seem to find any settings for this.ThanksJoel
EDIT:Sorry - I meant :cyclic, undirected, connected, and random.
> cyclic, undirected, connected, and random.
yes, it is, yEd itself has no direct notion of directedness, each edge has source node and a target node, so one could argue that graphs in yEd are directed. But actually it depends on the algorithms whether they *treat* edges as undirected or directed. E.g. the organic layout algorithms all together totally ignore the direction of the edges, hence they think of graphs as being undirected, while the hierarchical layout algorithms treats them as directed.
You can use yEd's builtin random graph generator to create cyclic, (undirected), and random graphs. Just go to Tools->Create Graph->Random, check "allow cycles" and specify more edges than nodes. This will generate a random graph that can be very well treated as "undirected", however it might not necessarily be connected (if the number of edges is small compared to the number of nodes for example). In that case you have to make it connected manually .
If you want to create a graph that is connected, cyclic undirected and random, you can use Tools->Create Graph->Planar, check "Connected" and enter a larger number of edges than the number of nodes. This will be a random *planar* graph, so not every kind of graph will be allowed, but it is nevertheless a random graph.
Ok Sebastian, I have an example for you.
On yEd - create a random graph of 300 nodes and about 320 vertices. The picture you will get is basically what I'm trying to deal with here.
I know the graph will not be connected - but that's fine (most of mine are connected - but that's besides the point).
Then select - Layout > Organic > Smart. Perhaps make the desired edge length around 50 or something.
You will see that the Layout (although much improved) is still not to the point where it could be analyzed in very much detail.
Just wanted to get your thoughts on that.
Thanks
Joel
> You will see that the Layout (although much improved)
> is still not to the point where it could be analyzed
> in very much detail.
Do a Layout->Edge Router->Organic after the steps you described and you will see that the results will be a lot better. I agree, that you still cannot see any structure in the graph, but the reason for this is that there simply *is no structure*, after all it is a random graph, so it should not contain any regular structure. Laying out a random (or near random) graph adequately without having any additional hints is more or less impossible. In these cases we always suggest creating an interactive graph browser that helps the user to explore the structure (by highlighting, focusing, selectively displaying subgraphs....) simply because it *cannot* be displayed adequately in a static fashion.
'hope this helps, Sebastian
> Laying out a random (or near random) graph
> adequately without having any additional hints is more
> or less impossible.
Yes I would agree. The only hints I really have before I do anything are which nodes belong to which lines. Maybe there's something I can do with that so I don't have to begin with a totally random layout.
So, in essence, for my graph the node placements are random - but the line placements are only random because of the random placement of the nodes they connect. But I do not randomly assign lines to nodes.
And w.r.t the edge router - it does curve the edges - but my goal would be to somehow furthur reduce crossings - but I did get your point.
Thanks for the communication!
Joel
> Yes I would agree. The only hints I really have before> I do anything are which nodes belong to which lines.w.t.f is a "line"?
Sorry! You talk in vertices and edges - I talk in nodes and lines because I'm dealing with an electrical system. I didn't think it would be so conspicuous.
Hi Sebastian,
I have to do auto routing of connections into our graphical editor.
I have tried to use the OrthogonalEdgeRouter for that purpose with the following way:
OrthogonalEdgeRouter orthogonalEdgeRouter = new OrthogonalEdgeRouter();
orthogonalEdgeRouter.setSphereOfAction(OrthogonalEdgeRouter.ROUTE_ALL_EDGES);
orthogonalEdgeRouter.setMinimumDistanceToNode(10);
orthogonalEdgeRouter.setCoupledDistances(true);
orthogonalEdgeRouter.setMinimumDistance(5);
orthogonalEdgeRouter.setGridSpacing(2);
orthogonalEdgeRouter.setCenterToSpaceRatio(0.5);
orthogonalEdgeRouter.setGridRoutingEnabled(true);
orthogonalEdgeRouter.setReroutingEnabled(true);
orthogonalEdgeRouter.setCrossingCost(2.0);
orthogonalEdgeRouter.setLocalCrossingMinimizationEnabled(true);
BufferedLayouter bufferedLayouter = new BufferedLayouter(orthogonalEdgeRouter);
bufferedLayouter.doLayout(graph);
Unfortunately this code does not layout the connections into our diagram in orthogonal way, but changed the connections to direct connections(straight lines) between nodes.
I changed a lot of upper mentioned method invocations, but without success.
BTW: version of yFiles which I can use is 2.0.0.7
Do you have any ideas where I am wrong?
Thanks in advance and best regards,
Aleksandar
