Home.... | log in.... | Pub my question! | Sign-up....

Java-index >> Other Topics >> Algorithms

Spring Embedded Layout Algorithm

Does anyone know where I can find pseudocode for this? I've found code, but I want to come up with my own. I've been told this algorithm is not too difficult, but I'm not having any luck searching for pseudocode.Please help!

[241 byte] By [joel24a] at [2007-9-30 1:09:55]

«« HELP ME WITH SCHOOL!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
»» Class.forName and .newInstance - what's wrong ?

# 1

Quite simple.

Just traverse all of the edges in your graph and then move the nodes that edge connects in the direction of the

edge by a factor proportional to the length of the edge. (move the nodes towards each other)

Rise

Repeat.

There are additional heuristics you can apply to improve the rate of convergence such as an exponetially

decaying movement factor or adding a momentum term to the movement. Lots of other stuff too. Go for the

basic approach and see how it works for you. (you may then want to add terms to bias the edges towards

horizontal or vertical layouts if that is important to you (basically you encourage the movement of the nodes

if it tends to bring you closer to you desired goal)

A simple example of this was given as one of the applet demos from sun. Can't find the link at the moment though.

matfud

matfuda at 2007-7-16 5:44:30 >

top of Java-index,Other Topics,Algorithms...

# 2

> Quite simple.

> Just traverse all of the edges in your graph and then

> move the nodes that edge connects in the direction of

> the

> edge by a factor proportional to the length of the

> edge. (move the nodes towards each other)

> Rise

> Repeat.

Seems to me all that would accomplish is a compression of the nodes.

For one thing, my graph is not directed. Also, what if the nodes need to go out and not come in? Also, should the not react to nodes around them? All the demos i've seen seem to demonstrate this.

Thanks

joel24a at 2007-7-16 5:44:30 >

# 3

Yep the code I gave will, in general pull all the nodes into a bunch in the middle.

There are a number of ways around this:

First. Fix the position of some nodes. The can be useful for some applications. Circuit layout for example

were you may want to specify the positions of some of the components.

Second. Add a term to the code that tries to seperate nodes. Therefore nodes are pulled together by thier

common edges but the effect is countered by another term if they get too close together.

Often a combination of the two is used as the first approach is generally useful but its a pain to require

users to specify the fixed nodes. The second works in general but it is often useful for the users to be able

to specify some fixed nodes, if they want to, ala the first approach.

How you implement this "push" factor depends on your needs. It may be a global value in which each

node tries to seperate itself from all other nodes (this can be expensive O(n^2)) or more simply that

each node has a gradually increasing "push" factor applied the closer it gets to nodes it is directly linked to.

Also the weight of the edges can be incorporated into the calculation if they have such a thing.

I should also say that if your graph contains many edges per node then it can be more efficient to iterate

through the nodes (rather then the edges) and compute the combined pull exterted on that node by all of the

edges that connect to it.

matfuda at 2007-7-16 5:44:30 >

# 4

Hi,

I suggest googling for the following terms:

Fruchtermann-Reingold, GEM, GRIP, Kamada-Kawai (not so sure about the spelling, but google will correct you), ACE ... look for other references in nec's citeseer.

For best results, you should combine most of the techniques used in these algorithms (that's what "yEd" / "yFiles" does (e.g.: yEd: Menu-> Layout-> Organic -> Smart).

Regards, Sebastian

SebastianMa at 2007-7-16 5:44:31 >

# 5

I've done extensive searching on those terms. Maybe I'm looking in the wrong places - or maybe there just isn't any pseudocode! I don't really understand how that CiteSeer site works.

What I have found are some formulae to use for attractive and repulsive forces, which is fine. But I don't know much when it comes to physics and such, so I am having a hard time understanding how to apply those forces to change the distances between nodes.

What I'm assuming so for is that I will have to traverse each node in the graph.

For each node, I will calculate its Fa and Fr based on the distance between this node and all the other nodes in the graph.

Then I will update this node's location based on its calculated displacement.

Am I on the right track?!?

joel24a at 2007-7-16 5:44:31 >

# 6

try this thesis. It seems to contain pseudo code

http://citeseer.nj.nec.com/cache/papers/cs/20281/http:zSzzSzwww.atkinson.yorku.cazSz~lbehzadizSzmyThesis.pdf/behzadi99improved.pdf

or this papar http://citeseer.nj.nec.com/cache/papers/cs/26266/http:zSzzSzwww.cs.ukc.ac.ukzSzpubszSz2002zSz1372zSzcontent.pdf/mutton02spring.pdf

There is also a demo of a very simple applet implementation that comes with the sun JDK

It is in the directory

j2sdk1.4.2\demo\applets\GraphLayout

and is called example4.html (well Graph.java really)

matfud

matfuda at 2007-7-16 5:44:31 >

# 7

Sebastian,When applying the force formulae, there is a variable for rest length of spring. If I know the actual length of each edge (which I do), is this length the value of the named variable?

joel24a at 2007-7-16 5:44:31 >

# 8

> When applying the force formulae, there is a variable

> for rest length of spring. If I know the actual length

> of each edge (which I do), is this length the value of

> the named variable?

I am not absolutely sure, since I don't know which formula you are using and where you got it from, but I would say the rest length of the spring is its "preferred length", the length where the resulting force is zero. That is the desired distance between two nodes that are interconnected by an edge in the final diagram.

Hence in the yEd editor, this would be "Preferred Edge Length". This is normally a predefined constant or a "per edge" constant. So the answer would be: No, that is not the actual spring length but the desired spring length.

SebastianMa at 2007-7-16 5:44:31 >

# 9

Yes, you are correct.Now I am just reviewing my Vector arithmetic to get some math going!Thanks for your help.

joel24a at 2007-7-16 5:44:31 >

# 10

Thanks for everyone's help on this so far. I've been able to generate a suitable looking graph now.

The only thing I can think of to do to make it look even better would be to minimize SOME edge crossings.

I definitely do not want to have an O(N^2) traversal on all edges. Does anyone have any suggestions on how to simply minimize edge crossings, perhaps where there are a lot of crossings only?

Fore example, sometimes I'll have a node with a large number of degrees at one end of the graph, and it will have a couple edges which extend to the complete other end of the graph simply because the nodes on the other end also have a large number of degrees.

Thanks for any suggestions!

joel24a at 2007-7-16 5:44:31 >

# 11

> I definitely do not want to have an O(N^2) traversal

> on all edges. Does anyone have any suggestions on how

> to simply minimize edge crossings, perhaps where there

> are a lot of crossings only?

What do you mean by an O(n^2) traversal on all edges? Could you explain in more detail or give some pseudo code?

> Fore example, sometimes I'll have a node with a large

> number of degrees at one end of the graph, and it will

> have a couple edges which extend to the complete other

> end of the graph simply because the nodes on the other

> end also have a large number of degrees.

I don't get this one either, could you post an URL to an image or describe in more detail?

By "a large number of degrees", do you mean "a great degree", i.e. a lot of adjacent edges/links?!

SebastianMa at 2007-7-16 5:44:31 >

# 12

I'm sorry - I was not thinking too much about what I was saying obviously!

First, about the edge traversal.

foreach Edge e {

foreach Edge u {

if u and e cross {

uncross

}

I'm hoping to avoid something like this (if possible).

And for the second part, I meant a "Large Degree" not a large number of degrees. Sorry!

joel24a at 2007-7-16 5:44:31 >

# 13

> I'm sorry - I was not thinking too much about what I

> was saying obviously!

> foreach Edge e {

>foreach Edge u {

>if u and e cross {

>uncross

> }

if only it was that simple .... just "uncross" and you're done.... even if this took O(m^2) I would love to see that "uncross" method's implementation.

well actually I am glad that it is not that simple; otherwise my company wouldn't exist I wouldn't have my fabolous job ;-)

> I'm hoping to avoid something like this (if

> possible).

There are modifications to the springembedder algorithms that include repulsive forces between edges and nodes in their calculation, but this is not a trivial and often not very good solution.

> And for the second part, I meant a "Large Degree" not

> a large number of degrees. Sorry!

I am sorry, because I still don't get it.... What's the problem you are experiencing and what would you like to achieve?

SebastianMa at 2007-7-16 5:44:32 >

# 14

> if only it was that simple .... just "uncross"

> and you're done.... even if this took O(m^2) I would

> love to see that "uncross" method's implementation.

I didn't mean to imply that uncrossing would be trivial. I just put that there for content but it had nothing to do with my question at all.

> I am sorry, because I still don't get it.... What's

> the problem you are experiencing and what would you

> like to achieve?

I suppose this will be hard to explain without a picture... but I'll try.

After I run the algorithm, there seem to be little groups of node that stick together. For example, a node may have a degree of 6, and 5 of those nodes only have a degree of 1, and those 5 surround the node which has the degree of 6. However, one node of the group may also have a large degree... say 6 again. But this node is far away from the original group - which is fine, except that this situation occurs often and there are lots of crossings.

So it seems like the nodes contract into these little focus groups, but the lines between these groups are what is causing me problems, since all of the groups are generally connected to each other.

Sorry if I lost you!

joel24a at 2007-7-16 5:44:32 >

# 15

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.

joel24a at 2007-7-19 19:48:35 >

# 16

Hi joel24,I was in process of Spring Embedded Layout algorithm ( Kamada & Kawai) could you just specify the herusitc u applied for your problem Thanks

aby28a at 2007-7-19 19:48:35 >

Java programming resources: FAQs, tutorials, compiler and browser download sites, documentation, books lists, IDEs, etc.

Spring Embedded Layout Algorithm

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified