Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.

Due to spam on this forum, all posts now need moderator approval.

 Entire forum ➜ MUSHclient ➜ Plugins ➜ (mapper drawing) force-directed layout for graphs with default layouts
(mapper drawing) force-directed layout for graphs with default layouts

It is now over 60 days since the last post. This thread is closed.     Refresh page

Pages: 1  2  3 4  

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #30 on Thu 20 May 2010 10:44 PM (UTC)
Message
Tsunami said:
But the important point is that while this may hold true 90% of the time, it there are still points where it doesn't (whether the map designer was having a bad hair day, or its just magic). This means that we can't draw any conclusions from this unless we are sure that the entire graph doesn't have any what I'm calling (perhaps somewhat inaccurately) non-Euclidean geometry.

Yes, this is the biggest problem. It's one thing to lay out 'rational' maps, but it's another to do something reasonable with an 'irrational' maps. (non-Euclidean is probably a decent term, and in any case the one that people tend to use.)

Quote:
I meant in addition to horizontal/vertical, you'd need diagonal. Orthogonal layouts produce very simplistic graphs, I don't think they are appropriate for this use.

Oh, sure. I'd forgotten that they tend to produce only straight lines, and not diagonals.

Quote:
I was complaining more about the efficiency of random guessing than about any unknown complexity :P But in any case, consider the following scenario: Two edges cross, and you have identified these edges. Now you need to manipulate the length of X other edges in such a fashion that the edges no longer cross. How do you identify the edges you need to manipulate and how you need to manipulate them? Going on just intuition, this seems like an NP complete-ish problem.

I'd have to think about this some more. But on intuition, you would pick one of the rooms of the X exit to be "on top". You would then go there, and keep going "down" in its cluster until you find an exit that you can extend such that it avoids the cross. I'm not sure if this would always work, but it's worth a shot.

Heck, even a force-based approach could work. I'm not sure I entirely buy your earlier arguments about it being impossible to fix the angles, etc. I'd have to think about that some more too...

Quote:
I'm just using some Achaean map Nick sent me. I've put it up at http://rapidshare.com/files/389728716/achaea.com_23.db (only 10 downloads allowed, so get it while it's hot...)

Got it, thanks.

Quote:
If you don't mind coding in C# I can send you my stuff so you don't have to write everything from the ground up, and can concentrate on the layout bit :)

Unfortunately, I don't know C# well enough for it to be at all efficient for me to write in it. :) So I'll have to figure out something else. I'm not sure how much time I'll have to play with this, but now I can if I have the time, thanks!
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Tsunami   USA  (204 posts)  Bio
Date Reply #31 on Thu 20 May 2010 11:32 PM (UTC)
Message
David Haley said:

Quote:
I was complaining more about the efficiency of random guessing than about any unknown complexity :P But in any case, consider the following scenario: Two edges cross, and you have identified these edges. Now you need to manipulate the length of X other edges in such a fashion that the edges no longer cross. How do you identify the edges you need to manipulate and how you need to manipulate them? Going on just intuition, this seems like an NP complete-ish problem.

I'd have to think about this some more. But on intuition, you would pick one of the rooms of the X exit to be "on top". You would then go there, and keep going "down" in its cluster until you find an exit that you can extend such that it avoids the cross. I'm not sure if this would always work, but it's worth a shot.


But any edge that is not parallel to the first edge if extended/shrunk would eventually result in the first edge not being crossed any more. How do you choose which edge now? Further, if you want to preserve the existing edge angles, every time you want to change an edge length, you will have to calculate the minimum set of other edges whose length you will also have to change in order to not change ANY edge angles. This seems like a very difficult problem to me.

David Haley said:

Heck, even a force-based approach could work. I'm not sure I entirely buy your earlier arguments about it being impossible to fix the angles, etc. I'd have to think about that some more too...


Consider two nodes joined by an edge. Now consider a force applied to one node orthoganal to that edge. Obviously we cannot just move the node in response to the force, because this would mean changing the angle. We have to calculate that moving one node means moving the other node, and further we are now moving twice the (mass) of nodes, so the acceleration is halved... This is all doable for a simple example.

But now connected those two node to a set of other nodes with various other edge angles and apply the same force. The end result is that moving one node will result in moving N other nodes, and changing the length of M other edges. And the only way to calculate those nodes and edges is to SOLVE the various physics equations.

This is possible for very small orders of functions(wikipedia n-body simulations for some papers I think), but unsolved on larger scales. This is precisely the need for a force directed layout, because FDLs estimate the solutions to these equations iteratively. Honestly, the physics equations in FDLs might possibly be simple enough to solve completely with a computer in some fashion, but it would be extraordinarily difficult and way above my head.

A good parable can be found with graphing calculators and calculus class :) When you use a graphing calculator to find the roots of some function, it does not actually solve the function to find the zeroes, since it might be far to complex to solve; it uses Newton's method, an iterative convergence to obtain an estimate of where the zeroes are.

Nerd moment: it was really cool when I first realized why my calculator asked me to estimate the zeroes visually before telling me what they were :P
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #32 on Fri 21 May 2010 12:20 AM (UTC)
Message
Tsunami said:
Consider two nodes joined by an edge. Now consider a force applied to one node orthoganal to that edge. Obviously we cannot just move the node in response to the force, because this would mean changing the angle. We have to calculate that moving one node means moving the other node, and further we are now moving twice the (mass) of nodes, so the acceleration is halved... This is all doable for a simple example.

But now connected those two node to a set of other nodes with various other edge angles and apply the same force. The end result is that moving one node will result in moving N other nodes, and changing the length of M other edges. And the only way to calculate those nodes and edges is to SOLVE the various physics equations.

This is possible for very small orders of functions(wikipedia n-body simulations for some papers I think), but unsolved on larger scales. This is precisely the need for a force directed layout, because FDLs estimate the solutions to these equations iteratively. Honestly, the physics equations in FDLs might possibly be simple enough to solve completely with a computer in some fashion, but it would be extraordinarily difficult and way above my head.

Yeah, this is basically an expansion on the argument you gave earlier. I'm still not completely sure I buy that this is necessarily the only way to approach this constraint, but not having played with code or FDL algorithms on this specific problem I can't better articulate why I disagree. I might be wrong to disagree, but it seems to me like you've sort of artificially painted yourself into a corner. I'll dig up some code I was working on a few years ago with FDLs and see what's what.

Perhaps a slight variation on FDL algorithms would suffice. It's not like the only way to approach the problem iteratively is with FDL.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Tsunami   USA  (204 posts)  Bio
Date Reply #33 on Fri 21 May 2010 02:08 AM (UTC)
Message
I've tried a variety of things, most of which didn't work that well. This result comes from two changes, imposing a maximum bound on force exerted along edges (allowing for better edge expansion) and doing some post-processing straightening of edges.

Result:
http://i.imgur.com/17ztF.png

I think is about as far as normal FDL can take us. The primary problem from here on out is that our assumption that every edge has a default length of 1 is wildly inaccurate. For better layouts we need better guesses of the true edge length. This could be done by asking the user, or through some other method.

I'll try to explore some of those, when I think of them ;)
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #34 on Fri 21 May 2010 05:30 AM (UTC)
Message
That's a lot better than earlier results; nice job.

To guess the initial edge lengths, here's an idea. Pick some room as the center of the map. Do a depth-first traversal of the map, assigning coordinates to rooms based on how you got there. E.g., 2 W then 2 N means coords (-2, 2). It's ok if a room has multiple coordinates. You can then scan each room and look at its neighbors coordinates; assign an initial exit length proportional to the distance. Of course this will often be funky, but that's ok, because it's just an initial estimation. And it's cheap: it's just two linear scans.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Tsunami   USA  (204 posts)  Bio
Date Reply #35 on Fri 21 May 2010 06:40 PM (UTC)
Message
David Haley said:

That's a lot better than earlier results; nice job.

To guess the initial edge lengths, here's an idea. Pick some room as the center of the map. Do a depth-first traversal of the map, assigning coordinates to rooms based on how you got there. E.g., 2 W then 2 N means coords (-2, 2). It's ok if a room has multiple coordinates. You can then scan each room and look at its neighbors coordinates; assign an initial exit length proportional to the distance. Of course this will often be funky, but that's ok, because it's just an initial estimation. And it's cheap: it's just two linear scans.


Well, I guess I misspoke a bit, this is exactly how I obtain intial layouts at the moment. Traditional FDL uses random initial placement, but we can do a lot better than this, and this is exactly the method I use. So I don't assume every edge length is exactly 1, but generally most of them work out to something like that. It doesn't really help when certain edges should really have lengths in the double digits either, the intial layouts don't reflect that.

One thing I thought of, which would be very slow, is to perform multiple FDL passes, resetting default edge length to what it was at the end of the FDL. This would let edges exapnd and contract more over multiple runs, but it's just so slow...

It also wouldn't help with the intial layout crossing edges in several places, so that node/node repulsion might mean some sections never become uncrossed due to high node density.

I have some ideas for improved layouts using cycle detection or strongly connected components which I'll post once my thoughts are organized.
Top
Posted by Tsunami   USA  (204 posts)  Bio
Date Reply #36 on Fri 21 May 2010 06:53 PM (UTC)

Amended on Fri 21 May 2010 06:55 PM (UTC) by Tsunami

Message
The best method I've thought of is rather complex, and I'm not entirely sure how I would go about implementing it. Basically you perform cycle detection in the graph (where no edge may be used twice in the same cycle) and assign every node to the largest cycle it is part of. Cycles that share nodes are combined. Nodes that are not in a cycle are greedily assigned to the nearest reachable cycle. This leaves you with multiple sets of nodes.

These sets of nodes -seem- equivalent to strongly connected components, and it seems quite likely I've just described a poor algorithm for finding the strongly connected components of the graph. Finding the strongly connected components is somewhat more difficult since they only apply to directed graphs. While we are working with a directed graph, for layout purposes its an undirected graph, which complicates things.

If we found the strongly connected components of the directed graph it would be mostly useless for layout purposes, since it would be 99% of the graph (given that every edge usually has a counterpart in the opposite direction. What I'm thinking about is using a strongly connected components algorithm but enforcing that once an (undirected) edge has been traversed in one direction, it may not be traversed in the other direction during the same detection cycle. I suspect this will give me the strongly connected components I want in the graph because it seems to force the strongly connected components to also be cycles.

We can then perform FDL on each component individually, and then come up with an algorithm to stitch the components back together in such a way as to avoid edge crossings. It would be complicated, but I think it could give quite good results.
Top
Posted by Tsunami   USA  (204 posts)  Bio
Date Reply #37 on Tue 25 May 2010 07:03 PM (UTC)
Message
Well, I was at least partially wrong :) It appears some constraints are possible to apply to force directed layout, as long as they fall under some very specific rules:


  1. One constraint per edge
  2. Constraints can only be applied orthoganal to axes
  3. Constraints must form a Directed Acyclic Graph


Relevant papers are here:
[1] www.csse.monash.edu.au/~tdwyer/LayoutWithOrthConstraints.pdf
[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9200&rep=rep1&type=pdf

This conflicts with my previous goal of speeding the algorithm up through parallelization, since evaluating constraints requires locking larger sections of the graph, making parallelism of reduced efficiency. So, what would be more useful, a faster algorithm, or one with straighter edges?

I also have some thoughts on reducing unwanted edge crossings through cycle detection which I need to think more about, but may provide better overall layouts. I have also had some success with multiple layout passes, which results in a more expanded graph, with -almost- but not quite less edge crossings.

Finally, I hope to put some of my code up soon for anyone that wants to take a look.
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #38 on Tue 25 May 2010 07:09 PM (UTC)
Message
Quote:
So, what would be more useful, a faster algorithm, or one with straighter edges?

Without meaning to be facetious, the better algorithm is the one with straighter edges that is still fast enough. :-)
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Tsunami   USA  (204 posts)  Bio
Date Reply #39 on Fri 28 May 2010 09:29 PM (UTC)
Message
Well, I've made a decent amount of progress since my last post, along with a little story :)

So I've been reading a variety of papers on graph constraints, but none of them really gave me what I needed. In my last post I mentioned a series of conditions under which constraints could be applied, but the conditions were quite restrictive, and hardly lent themselves to angle constraints at all. Anyways, after scouring the web for better ideas, I could find none. I temporarily gave up on constraints and focused on improving the run time of the algorithm.

After caching a variety of common variables, eliminating unnecessary loops, decreasing the amount of heap allocation, and parallelizing the algorithm I have achieved over an order of magnitude increase in speed. Running the algorithm to completion over a graph of 400 nodes and ~900-1000 edges previously took 90-120 seconds. It now completes the same ~3000 iterations in ~3 seconds. This does not even address the worst N^2 part of the algorithm yet which calculates node/node repulsive forces. There are techniques for cutting this down to N log(N) or even simply N (octrees and the fast multipole method), which I hope could result in another order of magnitude increase if I implement them.

As part of the optimization, I was looking at different position integration methods, which have been studied quite a bit in N-body simulations and game design. Verlet integration is the most common, and while not as flexible as the Euler's integration I was using previously, it is more accurate and does not depend directly on velocity, meaning I could remove the velocity derivation from my loop.

This is where things get interesting for me :) One feature of Verlet integration is that it works extremely well when combined with rigid body dynamics. I spent the day reading up on rigid body dynamics, and was convinced I could use this to implement exactly the generic kinds of constraints I wanted. Rigid body dynamics are not as provably convergent as the previous constraint systems, but function much better in practice. Further, researchers in the graph layout field have been looking for this type of generic and flexible constraint model for a while, but I hadn't found a single paper mentioning anything like this. So, images of Noble Peace Prizes and knighthood flashing through my head, I wrote down some of my thoughts. 30 seconds later, I found a paper detailing everything I had just thought of, written by the same guy as many of the other papers I'd been reading! In addition, he apparently now works at the same company as me in a nearby building (small world).

So, the downside is no Nobel Peace Prize for me, the upside is I was only a year late (the paper was from 2009), and I shot him an email which helped me improve the code greatly.

I have now implemented an angle based constraint system in my code. I was originally running it after every step, as most games and simulation code does, but I found this doesn't allow for enough expansion in the graph. The problem is 99% of systems usually only implement distance constraints. Distance constraints either have a large set of values that satisfy the constraint, or if they have only one valid value, they are usually used as angle constraints as well, meaning the layout doesn't care that the angle of an edge is very difficult to change with a distance constraint. I wanted angle constraints, but I also wanted a large degree of freedom for the distance to change, which just was not happening.

The solution was not run the constraints after every step instead of angle forces, but to run the simulation with angle forces and no constraints, which allows for good expansion and a decent ending layout, and then run several constraint iterations to force all angles to be correct.

Final Layout: http://i.imgur.com/73vgP.png

I might throw in some extra layout passes during the final constraints pass to see if that makes things a little more symmetric.

The largest remaining problem is what to do about edge crossings. Applying this to MUD maps is somewhat unique as there are certain edge crossings you want, and certain edge crossing that you don't want. Further, the undesirable ones cannot be solved in the very generic ways most research so far has pointed to. I have some vague ideas around this, but nothing solid as of yet.
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #40 on Fri 28 May 2010 09:41 PM (UTC)
Message
Quote:
Final Layout: http://i.imgur.com/73vgP.png

FWIW I think this looks vastly superior to earlier results -- good job.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Twisol   USA  (2,257 posts)  Bio
Date Reply #41 on Fri 28 May 2010 09:52 PM (UTC)
Message
Oh... wow. That's looking really good.
'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
Top
Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #42 on Fri 28 May 2010 10:09 PM (UTC)

Amended on Fri 28 May 2010 10:10 PM (UTC) by Nick Gammon

Message
By way of comparison, can you render that same part of the map using the existing mapper? Those results look great, I have to say. How long did it take to run? (Or is that map what you said took 3 seconds?)
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Tsunami   USA  (204 posts)  Bio
Date Reply #43 on Fri 28 May 2010 10:53 PM (UTC)

Amended on Fri 28 May 2010 10:58 PM (UTC) by Tsunami

Message
Nick Gammon said:

By way of comparison, can you render that same part of the map using the existing mapper? Those results look great, I have to say. How long did it take to run? (Or is that map what you said took 3 seconds?)


I've zoomed out a bit and only loaded the parts of the map the existing mapper loaded to get an identical test run.

Existing mapper:
http://i.imgur.com/PBZfY.png
My layout:
http://i.imgur.com/WpdYG.png

My layout ran 491 iterations over 211 nodes in 234 milliseconds with 229 constraints. This is all in managed code, and still has an N^2 inner loop.

Machine:

  • Intel Core i7 920 w/ 8 logical cores @ 2.67 GHz
  • 6GB of RAM
  • Windows 7 x64


Your results will vary mostly with the number of cores.
Top
Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #44 on Fri 28 May 2010 11:09 PM (UTC)
Message

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

134,540 views.

This is page 3, subject is 4 pages long:  [Previous page]  1  2  3 4  [Next page]

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum

[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

Home