dig is end-of-life. For graph algorithms, please see graphlib. For graph layout, please see dagre
cpettitt / dig.js Goto Github PK
View Code? Open in Web Editor NEWGraph algorithms for JavaScript
License: MIT License
Graph algorithms for JavaScript
License: MIT License
My initial thought on this is that we could annotate edges with the 2 bends that are generated by the Brandes Kopf algorithm.
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.
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.
Source: Gansner, et al., A Technique for Drawing Directed Graphs
Currently we ignore the height attribute in dig.dot.layout.
This may be a separate glue layer. Initial things we need:
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;
}
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.
"Simple and efficient bilayer crosscounting", Barth, et al. looks to be a good approach.
Per Moz Dev Net this was standardized in ECMAscript, fifth edition. In particular, it is not supported before IE 9.
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.
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.
The current implementation is naively greedy - it assumes that the shortest paths discovered at the beginning are optimal. Once an edge has been relaxed, the algorithm needs to update the cost in the queue.
In particular, these would be handy to ensure that test execution does not alter the data under test.
We could use this to get an asymptotically faster implementation of Dijkstra's algorithm
This feature would add the ability to create a subgraph from a source graph such that the subgraph includes only a specified subset of nodes from the source graph. Edges are only included if they are entirely incident on nodes in the subgraph.
has(x) should be O(1).
Use more consistent naming. In some places we use from / to and others u / v or v / w
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.