Haven't posted here in a while but I lurk from time to time :) In my spare time currently I've written an implementation of a force-directed graph layout engine for graphs with well-defined node/node angles (i.e. MUD maps). For those interested I've basically taken the Fruchterman-Reingold algorithm, tweaked it a bit, and added the notion of edge torque.
It would be quite useful for visually displaying maps since it can untangle a lot of the messiness of not quite Euclidean geometry of many MUD layouts without user aid (though user aid can improve layouts as well).
It's currently in C#, because I like that for prototyping and I wanted to experiment with CLRv4 code contracts anyways (IMHO, not very easy to use, and of marginal benefit without an extraordinary amount of work).
So my question is what format would make this easiest to integrate with whatever mapping features exist today? I was thinking of rewriting in c++ and exposing it as a dll, but I'd have to look at how that integrates with lua (and then I'd be tempted to try to integrate the boost graph library instead of the one I rolled myself), so I'm open to suggestions.
Once/If I rewrite it I'll prolly stick it up on github or google code and start looking for large graphs to test it on, as so far I've only tested it on a couple simple layouts and edge cases (no more than 6 nodes).
I would also want to experiment with a single pass whole graph layout vs multi pass graph subset layout. Anyways, questions, comments, etc, all welcome :)
Sound interesting, but I note from Wikipedia that "the typical force-directed algorithms are generally considered to have a running time equivalent to O(V^3), where V is the number of nodes of the input graph".
That is, the running time goes up as the cube of the number of rooms, so 6 rooms could be OK (ie. running time of 216 x O, whatever O is), but for say 40 rooms it would be 64,000 x O, so that could be difficult to run interactively. Could be OK if you built the map offline perhaps.
The notation O(V^3) means "on the order of V^3"; O isn't a value but just notation to give the order of the algorithm's run time.
To be a little more precise (while still waving hands somewhat) it means that A*V^3 + B is a bound for the function's run time, for constant values A and B.
In short, it means that the function will be very slow for large enough input sets. :P
I thought it meant something like that. So if for instance, O is a millisecond, then 216 milliseconds would be OK, but 64 seconds might be a bit slow. ;)
O isn't a variable, and it doesn't have a value. It's just a notation for algorithmic complexity. O(1) means constant time, O(x) means linear time. The O itself is just a marker, called Big-O Notation.
In general the algorithm is bad, but you have constraints on the input that you can probably exploit. For example, it's extremely unlikely that nodes on the fringe of the graph will somehow link all the way back to the center. I can't articulate precisely how this will help, but basically you have a special case of the graph layout problem and surely this can be used to give serious hints to the mapper. For example, you know that the directions really should be to the north, south, east, west, etc., and this can be very useful: it knows that it needs to stretch exits rather than go nuts with arbitrary node positioning.
This algorithms doesn't have a great running time abstractly true, but as with all algorithms, there are lots of ways to make this workable.
Only run the simulation on visible rooms - this cuts down on the number of rooms enormously. Even for 100 rooms or so, modern computing makes this trivial. This does mean however, that map layout could change as the view adjusts, and new edges and nodes come into play. Still, this is a problem at the moment, so at least we're not going backwards.
Run the algorithm once to layout. This seems like a good idea, but there are a number of problems in practice. Mostly, I don't know how well it will handle large numbers of one way exits and unsolvable non-euclidean geometries.
Force-directed layouts are somewhat unique in terms user experience in that they are also n-body simulations. This means they can be displayed in a meaningful manner to the user DURING the simulation. So we don't necessarily have to block drawing until the simulation completes, we can update the drawing as we go along without overly displeasing a user. This means updating, layout out, and drawing the graph continuously in parallel.
I think #3 might be the best overall solution, but for now I'm just going with #1 since I'm basically prototyping. I also wanted to add that the running time is usually dominated by the calculation of node/node repulsion, which references every other node in the graph. If this can be eliminated or optimized (via Barnes-Hut techniques) running time may drop dramatically. Especially since MUD maps are rarely pathalogically densely connected ;)
I've done some initial layouts on a map of Achaea Nick was kind enough to send me. For those familiar, this is within the city of Shallam, limited to 60 rooms.
Initial layout: http://i.imgur.com/yk21M.png
Result layout: http://i.imgur.com/dDgyJ.png
Green lines represent one way exits, which unfortunately, the algorithms doesn't handle well (at all) at the moment, which is why they seem to have some odd layouts. The characters associated with each edge are for debugging to tell me what the desired orientation for that edge is (n, ne, e, etc...).
The most dramatic improvement is clear in the expansion of the left side of the map I think. Because I haven't gotten around to implementing some outside energy sink, larger simulations have a tendency to run forever if you let them at the moment. This means I can't give you a great idea of the speed of the algorithm, other than to say the initial layout happens extremely fast, and its basically oscillations from there on out :)
Quote: Even for 100 rooms or so, modern computing makes this trivial.
100^3 = 100*100*100 = 1,000,000
Maybe I'm being picky, but this isn't really "trivial". What makes this problem tractable is the set of assumptions that constrain the problem. As you said, MUD maps aren't pathological and the algorithm doesn't need to handle those cases well.
Dammit, Nick, your forum won't let me edit my posts :P
...
Also, if there is a way to turn the links above into true links, please feel free to edit those for me Nick. Thanks!
If you log in you should be able to edit your posts. I do it all the time. You can't edit without logging in.
Even older computers these days should not have a problem handling a mere million floating point operations. See how long it takes your comp to run 2 or 3 million trigonometric functions. Further, big O notation should be used as an estimate of an algorithms growth rate and efficiency, not running time.
O(.000000000000000001 * N^3 + 100000000000) is still O(N^3) despite the fact that for non-large N's it is dominated by a linear term.
Even older computers these days should not have a problem handling a mere million floating point operations.
As easy as it is to play the "modern computers are fast" game, it just doesn't replace making your code more efficient. It is so easy to demonstrate scripts that just want to do more computing than even a nearly new computer can handle in between frames. A mere million floating point operations 10 times per second in an interpreted language with significant loop and data access overhead can become difficult to accomplish.
Tsunami said: Even older computers these days should not have a problem handling a mere million floating point operations. See how long it takes your comp to run 2 or 3 million trigonometric functions. Further, big O notation should be used as an estimate of an algorithms growth rate and efficiency, not running time.
This statement doesn't make a lot of sense, I'm afraid. If it's a measure of growth rate and efficiency, it is by extension a measure of running time, if at the very least a measure of how running time changes with input size.
Regarding the mere million floating point operations, I actually measured it on an older computer I have lying around, a Celeron 2.4GHz (bought around 2003-04).
$ cat test.lua
require 'math'
local sin = math.sin
local total = 0
for x = 1, 3000000 do
total = total + sin(0.2)
end
print (total)
$ time lua test.lua
596007.99239525
lua test.lua 0.86s user 0.00s system 99% cpu 0.865 total
$
As you can see, you wouldn't be able to do this more than once per second. And chances are rather high that you're doing more than just trivial floating point operations. Changing it from a trig function to pow(1.1, 2.7) (where pow = math.pow) changes the runtime from 0.86s to 1.64s.
Quote: O(.000000000000000001 * N^3 + 100000000000) is still O(N^3) despite the fact that for non-large N's it is dominated by a linear term.
This statement, while technically true, is rather irrelevant to the point at hand.
Anyhow, the point here is that your algorithm might not be N^3 on average in the first place due to the constraints placed on the input size, but if it truly is N^3 average case (as opposed to worst case) that's not something to sneeze at.
Tsunami said: Even older computers these days should not have a problem handling a mere million floating point operations. See how long it takes your comp to run 2 or 3 million trigonometric functions. Further, big O notation should be used as an estimate of an algorithms growth rate and efficiency, not running time.
This statement doesn't make a lot of sense, I'm afraid. If it's a measure of growth rate and efficiency, it is by extension a measure of running time, if at the very least a measure of how running time changes with input size.
Regarding the mere million floating point operations, I actually measured it on an older computer I have lying around, a Celeron 2.4GHz (bought around 2003-04).
$ cat test.lua
require 'math'
local sin = math.sin
local total = 0
for x = 1, 3000000 do
total = total + sin(0.2)
end
print (total)
$ time lua test.lua
596007.99239525
lua test.lua 0.86s user 0.00s system 99% cpu 0.865 total
$
As you can see, you wouldn't be able to do this more than once per second. And chances are rather high that you're doing more than just trivial floating point operations. Changing it from a trig function to pow(1.1, 2.7) (where pow = math.pow) changes the runtime from 0.86s to 1.64s.
Quote: O(.000000000000000001 * N^3 + 100000000000) is still O(N^3) despite the fact that for non-large N's it is dominated by a linear term.
This statement, while technically true, is rather irrelevant to the point at hand.
Anyhow, the point here is that your algorithm might not be N^3 on average in the first place due to the constraints placed on the input size, but if it truly is N^3 average case (as opposed to worst case) that's not something to sneeze at.
Frankly, I'm curious to see how much of that is Lua overhead. If you have time, could you run the same thing in pure C, and perhaps under LuaJIT? In unoptimized C# the same program ran in 90ms and 290ms for Math.Pow(...). Admittedly, I have a more modern processor which prolly doesn't compare with your test machine.
While it is of course technically correct that the Big-O complexity of a program affects running time, personally I regard thinking of speed optimization in terms of Big-O is a sin on the terms of premature optimization.
Simply picking an algorithm with a better Big-O has nothing to do with actual optimization, and in many cases can actually result in worse running times when one hasn't taken the effort to understand the problem domain.
A common example is quicksort vs mergesort. Most beginning CS students know that quicksort is better. Why would anyone ever use merge sort? Although it has a worse average case, merge sort has a better worst case, making it ideal for presorted data. Further quicksort is great for in-memory data, but terrible for large data sets which cannot be stored on disk, which is why most database programs use variants on mergesort.
I agree that Big-O is quite useful and definitely something to be always aware of, but it is far from the first thing one should consider when it comes to optimization.
Edit: Sidenote @ Fiendish, this isn't the sort of thing I would plan to run in Lua in any case :)
Quote: Frankly, I'm curious to see how much of that is Lua overhead. If you have time, could you run the same thing in pure C, and perhaps under LuaJIT? In unoptimized C# the same program ran in 90ms and 290ms for Math.Pow(...). Admittedly, I have a more modern processor which prolly doesn't compare with your test machine.
It will be faster in C and LuaJIT but I haven't tried it. And yes, a lot of it is probably Lua overhead. But then again, MUSHclient plugins are usually in Lua...
Running on a faster processor didn't really make a huge difference, for what it's worth.
Quote: While it is of course technically correct that the Big-O complexity of a program affects running time, personally I regard thinking of speed optimization in terms of Big-O is a sin on the terms of premature optimization.
Simply picking an algorithm with a better Big-O has nothing to do with actual optimization, and in many cases can actually result in worse running times when one hasn't taken the effort to understand the problem domain.
I'm sorry but I read statements like this and my mind kind of boggles. Obviously big-O analysis doesn't take into account the constant-time factors of the particular details of a function's implementation. But going from that to saying that big-O shouldn't be considered an important factor in choosing an algorithm seems kind of, well, preposterous. If your input is large enough -- where "large enough" isn't necessarily that large -- the constant factors become noise, because in the real world you don't have algorithms bounded by 0.0000001*N^3.
In my experience as a programmer, professionally, academically and otherwise, many considerable speed improvements are gained precisely by realizing that big-O performance is poor and using a better algorithm. In fact, this can make the difference between being able to run a program and not being able to run it at all!
I don't know why you say that picking a better big-O algorithm will "in many cases" result in worse running time -- do you have more examples of this? Of course there are special cases, like when you have particular constraints on the problem domain, but in general your statement seems quite wrong.
Quote: A common example is quicksort vs mergesort. Most beginning CS students know that quicksort is better. Why would anyone ever use merge sort? Although it has a worse average case, merge sort has a better worst case, making it ideal for presorted data. Further quicksort is great for in-memory data, but terrible for large data sets which cannot be stored on disk, which is why most database programs use variants on mergesort.
Sure -- and in this case, the algorithm choice is made because the problem domain is very particular. In general, it is still usually better to recommend quicksort over straight mergesort.
I'm not sure why it's sinful premature optimization to look at big-O performance, but fine to look at things like where a data set is stored (RAM vs. disk), and so forth. :-) It's all just part of the algorithm selection process once you start thinking about it.
If you're looking at an algorithm whose average case is O(N^3), for example, and you know that your input size is large, then you really should consider if you have no choice but to use an O(N^3) algorithm because there necessarily will come a point where no amount of optimization trickery will help you speed up the algorithm.
In my experience as a programmer, professionally, academically and otherwise, many considerable speed improvements are gained precisely by realizing that big-O performance is poor and using a better algorithm. In fact, this can make the difference between being able to run a program and not being able to run it at all!
I don't know why you say that picking a better big-O algorithm will "in many cases" result in worse running time -- do you have more examples of this? Of course there are special cases, like when you have particular constraints on the problem domain, but in general your statement seems quite wrong.
Quote: A common example is quicksort vs mergesort. Most beginning CS students know that quicksort is better. Why would anyone ever use merge sort? Although it has a worse average case, merge sort has a better worst case, making it ideal for presorted data. Further quicksort is great for in-memory data, but terrible for large data sets which cannot be stored on disk, which is why most database programs use variants on mergesort.
Sure -- and in this case, the algorithm choice is made because the problem domain is very particular. In general, it is still usually better to recommend quicksort over straight mergesort.
I'm not sure why it's sinful premature optimization to look at big-O performance, but fine to look at things like where a data set is stored (RAM vs. disk), and so forth. :-) It's all just part of the algorithm selection process once you start thinking about it.
I think I should differentiate; when it comes to picking an algorithm, I'm all for knowing its complexity and understanding why that is so. When it comes to optimization, I think you should still know the relevant big-O factors, but I contend that it's largely useless for optimization.
Why? Because perf optimization is about profiling, testing, understanding the bottlenecks, and knowing your hardware. Big-O tells you nothing about any of that. You ask why it's sinful premature optimization to look at big-O performance, but fine to look at things like where a data set is stored (RAM vs. disk), and so forth; I answer because looking at the big-O complexity tells you nothing about what the algorithm actually does or how it operates, where as looking at things such as where a data set is stored assumes a detailed knowledge of exactly what is happening and how hardware is affecting it.
This is why I object to statements which for instance, dismiss Fruchterman/Reingold because it has a base O(N^3) complexity. It's complexity alone tells us -nothing- about how useful it may be. It may take a million second or a millisecond for one node, it may be disk bound or cpu bound, we don't know.
The fact is, our problem domain is dealing with <100 nodes visible, and <10000 node maps (usually). This is a strongly CPU bound application, and depends heavily on the current CPU/FPU and very little on hardware bandwidth or seek times. Now that we know this, we can profile the algorithm, check which loops take longest, apply our knowledge of big-O, and modify the data structures to allow O(n log(n)). We can cut down on unneccesary power and trigonometric usage, etc...
Quote:
If you're looking at an algorithm whose average case is O(N^3), for example, and you know that your input size is large, then you really should consider if you have no choice but to use an O(N^3) algorithm because there necessarily will come a point where no amount of optimization trickery will help you speed up the algorithm.
I think this is exactly what I'm talking about. Before you look at the complexity, first you need to profile. Maybe the best case is O(1), maybe the average data size is <10, maybe there is a O(log(n)) algorithm elsewhere in your code with an average data size of 1000000. Maybe this is an algorithm that applies itself to caching extremely well, or maybe your algorithm is O(N^3) with a large data set, but its disk bound, and decreasing its time complexity won't help.
Assuming automatically that big-O is anything other than a vague guide to an algorithm's performance in a specific real-world case is a mistake to me. I don't want to sound like I don't care about categorizing algorithms' complexity, because I think this is an irreplacable and extremely important tool in a very broad and wide range of areas. Frankly, I'm usually a lot happier working in those areas than caring about perf :P But it's not a good metric when it comes down to the nuts and bolts in the specific area of perf optimization.
Quote: You ask why it's sinful premature optimization to look at big-O performance, but fine to look at things like where a data set is stored (RAM vs. disk), and so forth; I answer because looking at the big-O complexity tells you nothing about what the algorithm actually does or how it operates, where as looking at things such as where a data set is stored assumes a detailed knowledge of exactly what is happening and how hardware is affecting it.
Big-O necessarily tells you how something operates with respect to the input, that's the whole point of the big-O analysis. You don't just make it up because you feel like it; you derive it from what the algorithm is actually doing.
For example, big-O analysis can change depending on the data structures used to store intermediate results. The very same algorithm might be O(nlogn) with a binary tree and become O(n) with a hash table.
I agree that it doesn't tell you what is going on with the hardware or whether you will be running into disk I/O bottlenecks, but I feel that you are considerably exaggerating when you say that asymptotic complexity analysis tells you "nothing" about what an algorithm is doing or how it will perform...
Quote: This is why I object to statements which for instance, dismiss Fruchterman/Reingold because it has a base O(N^3) complexity. It's complexity alone tells us -nothing- about how useful it may be. It may take a million second or a millisecond for one node, it may be disk bound or cpu bound, we don't know.
I don't think that anybody made such a statement; you might have misunderstood... nobody said it was useless or should be dismissed. Nick just raised a flag about performance, but that's it. Besides, as I said earlier, sometimes you have no choice but to use a "poor" algorithm w.r.t. asymptotic performance, because there simply are no alternatives. (I'm not convinced that this is such a case, but that's beside the point.)
Quote: Maybe the best case is O(1), maybe the average data size is <10, maybe there is a O(log(n)) algorithm elsewhere in your code with an average data size of 1000000. Maybe this is an algorithm that applies itself to caching extremely well, or maybe your algorithm is O(N^3) with a large data set, but its disk bound, and decreasing its time complexity won't help.
All of these "maybes" sound like somewhat contrived scenarios designed to prove a point, not describe real-world situations. For example, if an algorithm lends itself well to caching, that can be taken into account in an average-case (or even worse case) complexity analysis. If the I/O time complexity is worse than CPU time complexity, that can be taken into account. Even something that is disk-bound will be dominated by the time complexity for large enough inputs: disk reads are (basically) linear and eventually time will catch up (of course, that might be quite a while away).
Quote: Assuming automatically that big-O is anything other than a vague guide to an algorithm's performance in a specific real-world case is a mistake to me. I don't want to sound like I don't care about categorizing algorithms' complexity, because I think this is an irreplacable and extremely important tool in a very broad and wide range of areas. Frankly, I'm usually a lot happier working in those areas than caring about perf :P But it's not a good metric when it comes down to the nuts and bolts in the specific area of perf optimization.
I don't think that anybody said it was a nuts-and-bolts type of metric. Perhaps this last paragraph clarifies your position best. It sounded an awful lot like you were saying (even in the first sentence of this paragraph) that big-O analysis is basically useless and an afterthought; now you're saying it's irreplaceable and extremely important. Perhaps you're simply being too emphatic elsewhere in saying how useless it is, and painting with too wide of a brush?
If the question is simply: is big-O a nuts-and-bolts metric for optimization, I think that the answer is pretty obviously that it's not. But if the question is whether it should be on your mind as you design/choose an algorithm, well, I think it should and I'm not sure if you do or not (you seem to have said both things), but if not I suppose we should just agree to disagree and move on here...
Perhaps I was to emphatic in my earlier statements :) I didn't mean to imply I think Big-O is not useful or anything, only that I think it can often be used to naively, without a full understanding of what it implies.
Anyways, some more screenshots of the layout in action. Again, Shallam, this time expanded to 400 rooms.
Initial Layout: http://i.imgur.com/BlBn8.png
Final Layout: http://i.imgur.com/8zwVJ.png
The full layout stopped after about 2 minutes, but frankly, the most useful part was done at 5 seconds, everything after that was expansion. I think I will need to come up with a new heurisitic on when to end the layout which is perhaps more aggresive w/ respect to the number of nodes, so that the simulation is able to end sooner. I could also increase the node/node repulsive force to see if I could get expansion to happen quicker. Right now I am using a bad approximation of the total acceleration within (at least whatever you call acceleration without a directional component...?) the system to check when to finish layout.
As you can see, the layout has about reached the limits of what it can do without human intervention. With some human aid, such as setting various edge lengths to an appropriate default, even better layouts could be obtained.
I can also see there might be some value in a post-processing step, which adjusts edge angles closer to exact verticals/horizontals/diagonals. This would make it look prettier in the final rendering.
I think it would look better if edges were allowed to stretch in addition to or instead of changing the angles of exits. I find that the end result actually doesn't look as nice, even if it separates rooms more clearly. It just looks very messy with all the irregular angles.
I think it would look better if edges were allowed to stretch in addition to or instead of changing the angles of exits. I find that the end result actually doesn't look as nice, even if it separates rooms more clearly. It just looks very messy with all the irregular angles.
If you look at it, you will notice that edges are already allowed to strech or compact like springs. I could decrease the spring force constant along edges, but that might lead to increased simulation run time, it's still something I am playing with. At the moment I have no good rules for adjusting the constants in various force equations, I just play around with them until something works.
It is easy enough to balance edge and node/node forces, since both operate in the direction of their local energy minima. It is more difficult to balance edge torque forces, since these operate on an angle to their local minima. I have given some thought to trying to point them towards their local minima, but this seems far to error prone and difficult at the moment.
As for your suggestion of not changing angles, if you think that through you will realize that the only way of doing that is to effectively increase angle torque to infinity. That isn't possible, so we have to make do with raising the torque constant quite high, and post-processing edge angles. I'm already considering both of these :)
I've also found some articles on parallel layout algorithms, which may be promising :)
Quote: As for your suggestion of not changing angles, if you think that through you will realize that the only way of doing that is to effectively increase angle torque to infinity. That isn't possible, so we have to make do with raising the torque constant quite high, and post-processing edge angles. I'm already considering both of these :)
Well, perhaps this is a failing of the force-directed approach for this kind of input, which isn't an abstract graph but a strongly spatially oriented and directed map. If post-processing edge angles and increasing the torque constant high enough works, that would be fine. (It's ok to change by a degree or two, but some of the changes in that final result image are much higher.)
Quote: As for your suggestion of not changing angles, if you think that through you will realize that the only way of doing that is to effectively increase angle torque to infinity. That isn't possible, so we have to make do with raising the torque constant quite high, and post-processing edge angles. I'm already considering both of these :)
Well, perhaps this is a failing of the force-directed approach for this kind of input, which isn't an abstract graph but a strongly spatially oriented and directed map. If post-processing edge angles and increasing the torque constant high enough works, that would be fine. (It's ok to change by a degree or two, but some of the changes in that final result image are much higher.)
The only other approach I can imagine would involve mapping groups of nodes into metanodes, where a metanode could be moved only along a certain vector common to all the contained nodes (and edges). This means vectors for all the cardinal directions, plus two more for expansion and shrinking. Forces would then be decomposed and applied to any applicable metanodes containing the node in question. It seems that you could easily run into metanode conflicts which would prevent any movement short of an advanced analysis however.
Perhaps a more fruitful approach would be to use metanodes to disallow movement rather than allow it, so that a metanode would track what directions contained nodes were not allowed to move.
Interesting thoughts, but I don't think I have the time at the moment to write a research paper on MUD specific layout techniques at the moment :P At least, I'm having a hard time thinking of any other domain that could apply to!
Edit: Actually, something I just thought of, perhaps I can reduce edge forces to zero if there is any other force acting along the edge axis, and raise them otherwise. This might have the effect of letting edge angles be directed without regard to edge length, and avoid creating awkward angles solely due to the edge spring force. It would still allow odd angles due to node/node repulsion.
Out of curiosity, why is it necessary to use a force-directed layout in the first place? It's fine if the answer is "because I feel like it and learning about it", but I'm curious why you feel that this is the best kind of algorithm. For example, I could easily imagine that an algorithm that simply stretches edges to minimize intersection could work quite well in many cases, although clearly any geometry where exit directions are "funky" (I won't define that precisely for now) would confuse this algorithm.
Out of curiosity, why is it necessary to use a force-directed layout in the first place? It's fine if the answer is "because I feel like it and learning about it", but I'm curious why you feel that this is the best kind of algorithm.
MUD maps generally differ from theoretical graphs only in that they associate an angle with an edge. Whatever layout algorithm we chose must have some way to respect this then.
This immediately eliminates:
Spectral Layouts
Symmetric Layouts
Tree Layouts
Hierarchical Layouts
This leaves only orthogonal and force-directed. We can eliminate orthogonal, since modifying it to support another axis would be quite difficult, and it probably still wouldn't give the type of layout we want. This leaves force-directed layouts, which are extremely flexible and customizable, not to mention simple to implement (I also don't have to retake some of my college math classes to understand it :P ).
There are several different starting algorithms for force-directed layout, along with several optional heuristic methods of searching for local energy minima (simulated annealing, genetic algorithms, maybe neural networks). Fruchterman-Reingold and Kamada-Kawai are the most popular algorithms; I chose Fruchterman-Reingold because I felt it applied itself better to the types of final layouts I want to see. I have not gotten to the stage of thinking about additional heuristic to find better energy minima, but I suspect they wouldn't do much in this specific domain since default layouts tend to give us the local minima we want anyways for a layout closest to the ideal map.
David Haley said:
For example, I could easily imagine that an algorithm that simply stretches edges to minimize intersection could work quite well in many cases, although clearly any geometry where exit directions are "funky" (I won't define that precisely for now) would confuse this algorithm.
Approaching this from a non-force directed layout direction sounds incredibly complicated (unless you pick edges to stretch at random, compare edge crossing before and after, and wait a couple days for your results), though I'm open to ideas if you have any. The simplest way of doing this seems to me to assign force fields to edges which interact with the field produced by other edges such as to push them away at orthogonal angles. This lets the rest of the graph correct itself automatically to accommodate the newly uncrossed edges. In fact, this is an approach some FDL algorithms have already taken. I'm not particularly interested in it because it's complicated (how would you pick which orthogonal direction to exert forces in? If you pick the wrong direction even once you would end up with terrible results), it would have a terrible perf impact, and it wouldn't improve layouts all that much.
Quote: MUD maps generally differ from theoretical graphs only in that they associate an angle with an edge.
I'm sorry, I don't agree with this at all, really. MUD maps tend to have all kinds of extra properties about the spatial relationship between rooms. You don't often find areas such that going west then north then west lands you in the original room. You don't often find egregious overlap, which is entirely possible in theoretical maps. So no, I can't agree that MUD maps are really so similar to the abstract theoretical graph.
Quote: We can eliminate orthogonal, since modifying it to support another axis would be quite difficult,
Then don't; just stack each Z-axis plane on top of the others.
Quote: Approaching this from a non-force directed layout direction sounds incredibly complicated (unless you pick edges to stretch at random, compare edge crossing before and after, and wait a couple days for your results)
How amusing that you use an algorithmic complexity argument... ;)
But no, you wouldn't pick edges at random. Off the top of my head, you could pick the edges that are "worst", as in have the most overlap, and work around those.
The main problem is what to do when stretching simply won't work anymore, such as when you have "irrational" layouts where you go west and to go back you need to go not east but north, or where going north, east and south lands you in the same spot.
Well, if somebody can give me the data set we're working with, I can play with it and see what happens...
Quote: MUD maps generally differ from theoretical graphs only in that they associate an angle with an edge.
I'm sorry, I don't agree with this at all, really. MUD maps tend to have all kinds of extra properties about the spatial relationship between rooms. You don't often find areas such that going west then north then west lands you in the original room. You don't often find egregious overlap, which is entirely possible in theoretical maps. So no, I can't agree that MUD maps are really so similar to the abstract theoretical graph.
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.
David Haley said:
Quote: We can eliminate orthogonal, since modifying it to support another axis would be quite difficult,
Then don't; just stack each Z-axis plane on top of the others.
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.
David Haley said:
Quote: Approaching this from a non-force directed layout direction sounds incredibly complicated (unless you pick edges to stretch at random, compare edge crossing before and after, and wait a couple days for your results)
How amusing that you use an algorithmic complexity argument... ;)
But no, you wouldn't pick edges at random. Off the top of my head, you could pick the edges that are "worst", as in have the most overlap, and work around those.
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.
David Haley said:
Well, if somebody can give me the data set we're working with, I can play with it and see what happens...
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...)
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 :)
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!
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
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.
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 ;)
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.
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.
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.
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:
One constraint per edge
Constraints can only be applied orthoganal to axes
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.
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.
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?)
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.
Let me know if there are any problems; its the first time I've used git, so bear with me :) Requires .NETv4 to compile, the project is openable in VS2010. If you don't have it, try the Express edition, no guarantees though. You can always compile from the command line, or recreate the project in an older version of VS, which should work if you can get it to recognize .NETv4.
I've also provided a download of the program I wrote to display the graphs:
Takes two command line arguments, first, the path to a map database in Nick's format, second the room id to start loading from. It will load the area that room is in and lay it out. Command line output is an approximation of the energy remaining in the system at each frame update and a summary at the end.
I'm open to suggestions on the best way to integrate this with MUSHclient. At the moment, I'm trying to port it to C++, but I expect this to take a bit, since I will probably try to integrate it with the boost graphing library rather than rewrite my own (plus I hate writing stl boilerplate).
Also taking suggestions for improvements and so forth :)
Nick, quick question, what SKU of Visual Studio are you using to compile? The reason being I'm looking at using OpenMP for some parallelized code, but it's only supported on 2005 Professional or Team System and above.
I use Visual Studio 2005, myself, and MUSH more or less compiles under it. If I remember, the main issue is that Nick doesn't want to dish out several hundred dollars when what he has does just fine.
Yes, around $AUD 500, and there is no real guarantee that I won't then spend 4 weeks making it compile without errors (unless someone here says they have got this version to work OK).
If I remember, the main issue is that Nick doesn't want to dish out several hundred dollars when what he has does just fine.
What, is the express edition not sufficient for some reason? Visual C++ Express is free and quite complete. The features that differentiate Express from the costly versions are all corporate-y things, like back-end integration with a clearcase server, that I've never found useful.
Fiendish said: The features that differentiate Express from the costly versions are all corporate-y things, like back-end integration with a clearcase server, that I've never found useful.
