1
$\begingroup$

I have a (cyclic undirected) graph stored in a suitable structure (which depends on the language chosen). Nodes represent places in the real world and edges represent connection between them, so I have a sort of initial guess of the drawing.

I have to draw this graph with some constraints and requirements, and from what I have read (scientific literature and books on graph drawing), currently none of the algorithm specifically addresses that requirements, although Sugiyama's magnetized springs are quite close to what I want to achieve. Simulated Annealing, however, could solve that problem, if a suitable cost function is provided, which is not a simple task.

So the question is: could you help me make a program which solve graph drawing problem with the constraints enumerated below?

Constraints and requirements

  1. Edges must be aligned at 45 k degrees, with k between 0 and 7 (or at least integer if this requirement is too strong). However, during the execution of the algorithm, I think there's no reason to prohibite violation of that constraint.
  2. Since the graph represent physical places, the algorithm must keep relative positions (e.g. if node A is north-north east of B in the initial guess, A must be north or north east of B, but exceptions can be made to meet the next requirement).
  3. Node distance should tend to a "natural" predefined length and alignment (if the graph is an open chain, the algorithm should output equally spaced nodes aligned on a line)
  4. Bends should take place at nodes and the angle between two adjacent edges should be 135 degrees, except for forks.
  5. Edge crossings must be avoided.
  6. Labels must not overlap any part of the drawing and should be positioned by the following specs (0 degree = horizontal axis, counterclockwise rotation of the text box):
    • Orthogonal to the super-edge (aggregation of aligned edges) if this one is not horizontal
    • Bend: prefer [convex side, orthogonal to the longest adjacent super-edge]
    • Horizontal edge
      1. 45 degrees
      2. -45 degrees
      3. -135 degrees
      4. Horizontal below
      5. Horizontal above
      6. 135 degrees

I have not chosen the programming language yet, but I think I'll stick to C/C++, Python, Perl or Lua. The input will be the "object" I talked about in the beginning, and the output will be the same "object" with node positions changed by the optimization algorithm.

Typical problems will have about 500 nodes, with small areas densely populated and connected and less dense (but not unique) connections between these areas. I'm not interested in efficiency, at least for the moment.

$\endgroup$
  • $\begingroup$ My understanding is that the techniques used in graph-drawing are almost the same as those used in the field of molecular simulation. It occurs to me that you could use a constant temperature simulation with the SHAKE algorithm to take care of the constraints. $\endgroup$ – Juan M. Bello-Rivas Dec 3 '14 at 2:00
  • 1
    $\begingroup$ Given the number of constraints you have, my best guess is that most graphs cannot actually be drawn with these constraints. You may have to require very specific criteria of the graph you want to draw to ensure there is a solution. $\endgroup$ – Wolfgang Bangerth Dec 3 '14 at 4:00
  • $\begingroup$ @JuanM.BelloRivas the problem is I don't know how to write those constraints: I'm hitting my head against a brick wall since two weeks ago. $\endgroup$ – Astrinus Dec 3 '14 at 7:48
  • $\begingroup$ @WolfgangBangerth I know, but for 99,9% of the graphs I work on I'm sure a solution exists. $\endgroup$ – Astrinus Dec 3 '14 at 7:51
1
$\begingroup$

It sounds like you are trying to draw a subway map. Sure enough, there are several papers on metro/subway graph drawing in the literature. You could start with Alexander Wolff's "Drawing Subway Maps: A Survey" (2007), and then take a look at the more recent "Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming" by Nöllenburg and Wolff (2011).

$\endgroup$
  • $\begingroup$ I haven't thought at all to subway maps! I'll check for sure! I'll wait for other answers before accepting yours, but for time being you deserve a +1! $\endgroup$ – Astrinus Dec 3 '14 at 7:42

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.