What I need is a JavaScript implementation of pure mathematical graphs. To be clear I DON'T mean graph visualization libraries like sigma.js or d3.js.
The library I'm looking for would implement following features:
- creation of directed and undirected graph objects
- creation of weighted and unweighted graps objects
- adding/removing vertices and edges to/from the graph
- adding labels to vertices and edges (i.e. additional meta data)
- implementation of basic graph search and traversal algorithms like depth-first-search, breadth-first search, Dijkstra's algorithm, A* and others.
Does anyone know if one already exists?
Now there is a library: graphlib
Graphlib is a JavaScript library that provides data structures for undirected and directed multi-graphs along with algorithms that can be used with them.
Implements:
- directed and undirected graphs (does A -> B imply B -> A)
- multigraphs (multiple distinct named edges from A -> B)
- compound graphs (nodes can have children that form a "subgraph")
- Dijkstra algorithm (shortest path)
- Floyd-Warshall algorithm (shortest path supporting negative weights)
- Prim's algorithm (minimum spanning tree)
- Tarjan's algorithm (strongly connected components)
- Topological sorting (dependency sort for directed acyclic graphs)
- Pre- and postorder traversal (callback on every node)
- Finding all cycles and testing if a graph is acyclic
- Finding all connected components
NPM, Bower and browser supported, MIT license.
Before few months I created a repository with implementations of different CS algorithms in JavaScript. There are also few algorithms with graphs. I plan to extend it (spanning trees, heuristic algorithms probably chromatic graphs) but since then I think that there are still few algorithms which could help you.
With help of StackOverflow's similar question recommendations I found couple questions with similar topic.
First one, Javascript directed acyclic graph library? (Graph visualization is NOT necessary), is close. There nrabinowitz suggests checking out data.js. I quickly browsed through the source of data.js. It really gives interface for handling graphs but only in very basic manner. No traversal algorithms there. It also seems that the goal of data.js is something other than a comprehensive graph library.
Second one, Javascript library for graph operations, almost same question as this but has no real answers yet (at 2013-01-23 17:32). The author c0dem4gnetic references to NetworkX which is very much what I need but unfortunately implemented only in Python.
I would be somewhat excited to implement such a library by myself. Graphs are so cool.
I have made a graph algorithms library https://github.com/devenbhooshan/graph.js in javascript. Library is clean and very simple. It is very easy to use. Just plug the graph.js file in your project and start using it.
We have algos in our Java library, we're just trying to find a free slot to add them to our JavaScript library. That doesn't help you now, but might be some use to later viewers.
There is also js-graph-algorithms, which seems pretty clean and has several algorithms. Its api is pretty basic though.
