5
\$\begingroup\$

I'm trying to procedurally model tree-like network structures with the following properties:

  • A root with variable number of nodes
  • A variable depth of nodes
  • When graphically laid out, edges or nodes must never intersect or overlap

I don't have a background in maths or programming, so I am not sure that I am using the correct terminology. Maybe a picture would better explain what I am after:

enter image description here

I know my way around Ruby pretty well, so I think I should be able to implement a basic algorithm that generates these models. Any pointers or recommendations?

\$\endgroup\$
  • \$\begingroup\$ "Recommendation" questions are very tricky. It'd recommend doing some more background research and then coming back here when you figure a little more out or have some really messed up algorithms :P And by that point, you may be better off on the main site. \$\endgroup\$ – TheNickmaster21 Oct 1 '13 at 11:22
  • \$\begingroup\$ Sorry, but it isn't really clear what your problem is. Please be a bit more specific. Nevertheless, I would recommend you to read up a bit on graph theory. It's a well-researched field. \$\endgroup\$ – Philipp Oct 1 '13 at 12:03
  • \$\begingroup\$ @TheNickmaster21, Phillip valid points. Apologies for the vagueness. I suppose I was using this question to get more clarity myself. I understand that it's not the right way though. \$\endgroup\$ – emilesilvis Oct 2 '13 at 12:09
  • \$\begingroup\$ Do you already have nodes and adjacencies between them established, or you need to generate completely random trees? Do you have any cycles? (if so, please remove the <tree> tag) \$\endgroup\$ – teodron Oct 4 '13 at 10:38
5
\$\begingroup\$

Graph drawing is a little more directly relevant than the whole field of graph theory.

In particular, I'm a fan of force-based layout. See this demo from the D3 library for an introduction.

The basic idea is that you model the graph edges with springs or repulsors, and use a physics integration method to "resolve" the positions of all the nodes. You can do this in real-time like the previous demo, which is kind of fun but also distracting, or you can do a number of physics iterations before rendering a final static layout.

That D3 library has a large number of other layout modes to inspire you with, and being JavaScript-based is a great way to prototype or experiment with any layout algorithms you're interested in.

\$\endgroup\$
  • 1
    \$\begingroup\$ My graph theory is rusty, but I believe the relevant principle for drawing with no edge overlap is that the graph must not contain a K5 or a K3,3. \$\endgroup\$ – kevintodisco Oct 3 '13 at 23:35
  • \$\begingroup\$ @ktodisco Spot on en.wikipedia.org/wiki/Kuratowski's_theorem !! \$\endgroup\$ – teodron Oct 4 '13 at 10:33
1
\$\begingroup\$

First, in order for your graph to obey the crucial property of any two edges do not cross, it must be a planar graph.

A tiny tutorial on the graph drawing topic is given here.

Using force driven layouts may not guarantee convergence to a planar graph: (for example, if a vertex is inside a face, apply an elastic spring force and push the vertex outside the face using the nearest edge normal). This approach would be interesting to animate, but it might not converge (unless it has been proven somewhere..?).

So, while I cannot reproduce here an algorithm for untangling a planar graph (or downright drawing it in its canonical form), there are plenty of resources dealing with the issue (some in linear time):

NOTE: if your graph is a tree, then I suggest reading this.

RELATED: "Untangle"-Game AI

\$\endgroup\$
1
\$\begingroup\$

You could use some form of Space Colonisation.

Examples ProcWorld and Sea of Memes show growing 'real trees', but could probably be adapted for arbitrary tree structures.

Space Colonisation assumes you have some limited area to be filled by a competitive 'lifeform' which grows over one or more iterations. This competitive aspect might not fit what you're wanting to do, if you're just wanting to generate random trees/graphs with no overlap.

EDIT:

Space Colonisation has certain conditions on the growth that I think pretty much guarantee no overlapping edges (and normally you'd process the tree afterwards anyway) - but it will only help you if you don't already have a graph/tree.

So if you already have a graph, Space Colonisation will not help you - see other answers like @Sean's force-based layout. If you are generating a graph while also needing to lay it out (or can store some position information for later) - this might to what you need.

\$\endgroup\$
  • \$\begingroup\$ Nice links, but could you briefly explain (a phrase or two) how the procedural generation of tree graphs could be adapted to more general, planar graphs? That should solve the OP's problem directly. Mind you, the OP already has the vertices and edges in place, but they don't know how to actually place the nodes and edges in a 2D plane without having overlaps. While a tree has no cycles and is trivial to draw, a more general graph might requires something more complicated. \$\endgroup\$ – teodron Oct 4 '13 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.