74

To simplify the problem, I have a graph that contains nodes and edges which are on a 2D plane.

What I want to be able to do is click a button and it make the automatically layout the graph to look clean. By that I mean minimal crossing of edges, nice space between nodes, maybe even represent the graph scale (weighted edges).

I know this is completely subjective of what is a clean looking graph, but does anyone know of an algorithm to start with, rather than reinventing the wheel?

Thanks.

osgx
  • 90,338
  • 53
  • 357
  • 513
Cheetah
  • 13,785
  • 31
  • 106
  • 190

6 Answers6

85

You will find http://graphdrawing.org/ and this tutorial, by Roberto Tamassia, professor at Brown University, quite helpful.

I like a lot Force-Directed Techniques (pp. 66-72 in the tutorial) like the Spring Embedder.

You assume there is a spring or other force between any two adjacent nodes and let nature (simulation) do the work :)

Aidenhjj
  • 1,249
  • 1
  • 14
  • 27
ypercubeᵀᴹ
  • 113,259
  • 19
  • 174
  • 235
  • 4
    I thought the question was about algorithms and not frameworks. I fail to understand why not this question was accepted, this is the only one which is about algorithms. – inf3rno May 06 '15 at 20:23
  • Possibly because the accepted answer pointed to the "theory" section of the graphviz documentation, which does address algorithms, as requested? Still, the tutorial you linked looks useful, so be content with the +1s you get. – digitig Jan 12 '17 at 16:08
  • @digitig thnx. I didn't complain by the way. Someone else did! – ypercubeᵀᴹ Jan 12 '17 at 16:21
  • 2
    @xhg thnx! I edited the link, to Roberto Tamassia' pages, in Brown University. – ypercubeᵀᴹ Feb 08 '18 at 20:15
  • Link provided is dead "this tutorial". Please update it accordingly. – LXSoft Jun 11 '18 at 14:44
  • @LXSoft thnx for letting me know. I have updated the link 2 or 3 times in the past, since my first posting here. I can't find it online in any official page of the author. I'll update if I do (find it). – ypercubeᵀᴹ Jun 11 '18 at 18:29
  • The link is now http://cs.brown.edu/people/rtamassi/papers/gd-tutorial/gd-constraints.pdf – Aidenhjj Oct 30 '18 at 11:38
29

I would suggest that you take a look at at graphviz. The dot program can take a specification of a graph and generate an image of the network for you somewhat "cleanly". I've linked to the "theory" page that gives you some links that might be relevant if you're interested in the theoretical background. The library and tools themselves are mature enough if you simply want a solution to a problem with layout that you're facing.

Noufal Ibrahim
  • 71,383
  • 13
  • 135
  • 169
  • 5
    The question is about an Algorithm for graph layout, not application. – Adnan Y Sep 24 '16 at 02:57
  • 14
    That's why I specifically mentioned the theory link on that page. – Noufal Ibrahim Sep 24 '16 at 15:41
  • The answer isn't explicitly referring to the theory link. It's more of an "if you are interested in theory". It would've been better to refer to the theory link and "if you are interested in an application" instead. – Adnan Y Sep 26 '16 at 02:08
  • 3
    Fair enough. I understood the OP as wanting to solve the layout problem (rather than reimplement a solution) and based my answer on that (a well tested, production quality "wheel" that he or she didn't have to reinvent). – Noufal Ibrahim Sep 26 '16 at 16:56
4

Also JGraph if you want the layouts in Java (I work on the project).

Frodo Baggins
  • 8,290
  • 6
  • 45
  • 55
4

I would say as Noufal Ibrahim, but you could also look more precisely at the C API of the graphviz project. It includes a lib to build your graph (libgraph.pdf) with all the nodes and edges, and a lib to layout the graph (libgvc.pdf) (just compute each nodes position), so you can then display it in your own UI for example.

jslap
  • 711
  • 1
  • 6
  • 21
3

A good visual guide how the most popular layouts actually look: follow the link

Sanoop Surendran
  • 3,484
  • 4
  • 28
  • 49
Diana Jobs
  • 31
  • 1
  • 4
    Whilst this may theoretically answer the question, [it would be preferable](//meta.stackoverflow.com/q/8259) to include the essential parts of the answer here, and provide the link for reference. – Kalle Richter Jun 13 '17 at 14:32
0

For javascript I recommend this library from Microsoft: https://microsoft.github.io/msagljs/

Doua Beri
  • 10,612
  • 18
  • 89
  • 138