cpettitt / dig.js Goto Github PK

View Code? Open in Web Editor NEW

20.0 4.0 4.0 356 KB

Graph algorithms for JavaScript

License: MIT License

JavaScript 98.60% Graphviz (DOT) 1.40%

dig.js's Introduction

dig - Graph Algorithms for JavaScript

dig is end-of-life. For graph algorithms, please see graphlib. For graph layout, please see dagre

dig.js's People

Contributors

Stargazers

Watchers

Forkers

yousk520 pombredanne linearregression

dig.js's Issues

Find polyfill to replace helpers like dig_util_forEach

README: add section about how this works

Support for clustering in dig.dot.layout

dot: edge layout

My initial thought on this is that we could annotate edges with the 2 bends that are generated by the Brandes Kopf algorithm.

Measure perf diff between objects and closures

We're currently using objects for our data structures (DiGraph, UGraph, PriorityQueue, etc.). Initially we used objects because we were creating large numbers of Maps (no longer in the repo). However, now that the number of objects created is lower, closures are more appealing due to their ability to encapsulate state.

dot: implement network simplex algorithm

dot: make acyclic graphs

Add pre-layout step

In this step we'd figure out appropriate values for things like height and width. For now, we'll assume that we have access to a DOM to do this. Later we should look at alternatives like jsdom.

dot: implement barycenter heuristic

Source: Gansner, et al., A Technique for Drawing Directed Graphs

Support for height based layout

Currently we ignore the height attribute in dig.dot.layout.

Integration with D3

This may be a separate glue layer. Initial things we need:

Estimation for text size for nodes. If we want to put names in a box, then we need to properly size the box during layout. We currently size using the node's width attribute.
Edge layout.

dot: support edges with minimum length constraints

Unnecessary type-2 conflicts with example graph

Numerous crossings in this graph, some of which are unnecessary. Note the type-2 conflict between 2 -> 8 and 15 -> 27.

digraph {
    0 -> 4;
    0 -> 5;
    0 -> 6;
    0 -> 29;
    17 -> 3;
    5 -> 3;
    5 -> 4;
    5 -> 26;
    5 -> 14;
    5 -> 10;
    5 -> 2;
    3 -> 4;
    26 -> 18;
    14 -> 10;
    2 -> 8;
    2 -> 23;
    23 -> 24;
    24 -> 15;
    24 -> 12;
    24 -> 28;
    1 -> 12;
    12 -> 6;
    12 -> 19;
    12 -> 9;
    6 -> 13;
    6 -> 29;
    6 -> 25;
    6 -> 21;
    29 -> 25;
    21 -> 22;
    25 -> 11;
    22 -> 8;
    22 -> 9;
    15 -> 27;
    15 -> 16;
    8 -> 16;
    8 -> 20;
    11 -> 16;
    11 -> 9;
    16 -> 27;
    27 -> 13;
    27 -> 19;
    13 -> 20;
    19 -> 9;
    20 -> 4;
    9 -> 4;
    9 -> 28;
    28 -> 7;
}

dot: handle default attributes (node, edge, graph) properly

In the dot language it is possible to specify a set of default attributes using syntax like:

node {
    color=red
}

See dot language specification for details.

dot: bilayer cross counting algorithm

"Simple and eﬃcient bilayer crosscounting", Barth, et al. looks to be a good approach.

Eliminate use of Array.prototype.forEach

Per Moz Dev Net this was standardized in ECMAscript, fifth edition. In particular, it is not supported before IE 9.

Integrate with Travis-CI

Implement Tarjan's SCC algorithm

http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

README: add section with examples using the library

API documentation: dig.Graph

Dot Parser

Provide fallback when Object.defineProperty is not available

This was standardized in ECMAscript, fifth edition. In particular, it is not supported (for non-DOM objects) until IE 9.

defineProperty is definitely what we want when available. It can be used to set an immutable property (like _digId) on an object that does not show up as an enumerable field. When it is not available, the best we can do is provide a mutable, enumerable field. We could make the property immutable by using a function instead of a field to store _digId, but an inconsistent API is worse than the original problem.

dot: undo acyclic changes when no longer needed

dot: investigate improved heuristics for ordering

The current ordering heuristic is not able to find optimal ordering for:

digraph {
    A1 -> B1;
    A1 -> B4;
    A2 -> B2;
    A3 -> B3;
    A3 -> B2;
    A4 -> B4;
    B1 -> C1; 
    B2 -> C2; 
    B3 -> C3; 
    B4 -> C4; 
    C1 -> D1;
    C2 -> D3;
    C3 -> D2;
    C4 -> D4;
}

Removing the A3 -> B2 edge results in a minimal edge crossing. Also, replacing A3 -> B2 with some other edges also sometimes breaks the heuristic's ability to find minimal crossings.

Graphviz uses two heuristics during the order phase. First, they use a similar heuristic to ours (but theirs is median based, while ours is mean based). Second they try to swap pairs of vertices in each rank to find a reduced crossing local to the vertices. They call this transpose function. It may be worth including this second heuristic - the paper claims an additional 20-50% reduction in crossings with it.