Is there any JavaScript libraries for graph operations and algorithms?
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?
Answer
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.