1

TL;DR

I need to set a graph's layout programmatically though JavaScript code.

Explanation

I have a graph in this format:

var graph = {
    "nodes": [
        {"x": 0, "y": 0},
        {"x": 0, "y": 0},
        {"x": 0, "y": 0},
        {"x": 0, "y": 0},
    ],
    "edges": [
        {"source":  0, "target":  1},
        {"source":  1, "target":  2},
        {"source":  1, "target":  3},
        {"source":  3, "target":  2},
    ]
};

All these nodes have an X and Y value of 0. If we draw this on canvas, the graph obviously won't look any good.

I want to apply an algorithm on this data-structure so that the X and Y values of all the nodes are auto-adjusted (with minimal edge crossings).

Existing solutions

I have tried force-directed layout of D3.js and some similar solutions. But they require too many iterations and most of my graphs have > 50 nodes with a lot of edges.

The algorithm I am looking for, should create a layout in minimal complexity and time (or it should be atleast faster than the iterative ones).

Matlab has three layout type engines for its biograph. LayoutTypeValue can be either hierarchical, radial and equilibrium. Radial seems like a good idea though.

Thanks.

Improve this question
2
  • Try a search for Graphviz and javascript. Commented Feb 20, 2015 at 9:09
  • Neato engine for Graphviz works great. I would love view the algorithm JS source but unfortunately it's a port via emscripten. Commented Feb 20, 2015 at 13:33

1 Answer 1

Reset to default
1

If this is in a commercial scenario, you might want to take a look at the yFiles for HTML Javascript graph drawing and layout library.

To the best of my knowledge it provides the most complete and most versatile automatic graph layout implementations available for Javascript. They are available via a nice Javascript API and don't feel like a black-box command-line like solution like the "emscripten" suggestion from the comments.

See this extensive interactive automatic layout demo that shows many of the automatic layout options available.

Most (but not all with all settings) algorithms perform very well with graphs of that size (a few hundred elements).

The (non-exhaustive) list of available layouts is

  • hierarchic
  • tree-like
  • force-directed
  • circular
  • balloon
  • orthogonal
  • radial
  • various dedicated edge routing only implementations

Disclosure: I work for the company that creates that library, but I do not represent my employer on SO. This is my own comment and opinion.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.