repository·master·Indexed 23 days ago
https://github.com/dagrejs/graphlibA JavaScript library for managing directed and undirected multi-graphs. It provides the Graph class for creating and manipulating graph structures, a json namespace for serialization, and an alg namespace containing algorithms such as Dijkstra's shortest path, Floyd-Warshall, Prim's MST, topological sorting, and cycle detection.
A multigraph allows multiple edges between the same pair of nodes. To use this feature, you must initialize the graph with { multigraph: true }.
To distinguish between multiple edges connecting the same nodes, you must provide a name parameter when creating the edge. You can then use this name to retrieve or remove specific edges.
var g = new Graph({ multigraph: true })
g.setEdge("a", "b", "edge1-label", "edge1")
g.setEdge("a", "b", "edge2-label", "edge2")
g.edge("a", "b", "edge1")
g.edge("a", "b", "edge2")
g.edges()
/**
* return [
* { v: "a", w: "b", name: "edge1" },
* { v: "a", w: "b", name: "edge2" }
* ]
*/Graphlib is a JavaScript library that provides data structures and algorithms for undirected and directed multigraphs.
The primary abstraction is the Graph. You create a new instance using new Graph(). By default, it creates a directed graph that does not allow multiple edges (multigraphs) or compound nodes.
You can configure the graph behavior via an options object in the constructor:
directed (boolean): If true, the graph is directed (order of nodes in an edge matters). If false, it is undirected (g.edge("a", "b") === g.edge("b", "a")). Defaults to true.multigraph (boolean): If true, allows multiple edges between the same pair of nodes. Defaults to false.compound (boolean): If true, allows nodes to be parents of other nodes (creating subgraphs). Defaults to false.edgeObj consisting of:v: Source ID (or tail node).w: Target ID (or head node).name (optional): A unique identifier used to distinguish multiple edges between the same two nodes in a multigraph.A compound graph allows a node to act as a parent to other nodes, effectively forming a subgraph. You must enable this by setting { compound: true } in the constructor. Use setParent(v, parent) to establish the hierarchy.
var g = new Graph({ compound: true });
g.setParent("a", "parent");
g.setParent("b", "parent");
g.parent("a"); // returns "parent"@dagrejs organization is currently receiving updates. To ensure you are using the most up-to-date version, install @dagrejs/graphlib.Graphlib provides a json utility to convert a graph into a JSON-compatible object and back again. This is useful for saving graph state or transmitting it over a network.
json.write(g): Returns a JSON representation of the graph.json.read(json): Reconstructs a graph from a JSON object.To use Graphlib in your project, install the package using npm:
$ npm install @dagrejs/graphlibIn a compound graph (enabled via new Graph({ compound: true })), nodes can be organized into a hierarchy of parents and children. This allows for representing subgraphs within nodes.
setParent(v: string, parent?: string): Sets node v to be a child of parent. If parent is undefined, v becomes a top-level node. This method throws an error if it would create a cycle or if used in a non-compound graph.parent(v: string): Returns the identifier of the parent of node v.children(v: string = GRAPH_NODE): Returns an array of direct children of node v. If v is the special GRAPH_NODE constant, it returns all top-level nodes.Note: In a compound graph, nodes() returns all nodes, but filterNodes() and edges() may treat subgraphs differently depending on the operation.
The graphlib.alg.dijkstra(graph, source, weightFn, edgeFn) function implements Dijkstra's algorithm to find the shortest path from a source node to all other reachable nodes in a graph.
Parameters:
graph: The graph to traverse.source: The starting node ID.weightFn(e): A function that returns the weight of edge e. Defaults to 1 if not provided. Note: If any edge has a negative weight, the function will throw an error.edgeFn(v): A function that returns all edge IDs associated with node v. Defaults to g.outEdges.Returns:
A map structure: v -> { distance, predecessor } where:
distance: The sum of weights on the shortest path from source to v. If no path exists, the distance is Infinity.predecessor: The ID of the previous node in the shortest path, allowing you to traverse the path in reverse from v back to source.function weight(e) { return g.edge(e); }
graphlib.alg.dijkstra(g, "A", weight);
// => { A: { distance: 0 },
// B: { distance: 6, predecessor: 'C' },
// C: { distance: 4, predecessor: 'A' },
// D: { distance: 2, predecessor: 'A' },
// E: { distance: 8, predecessor: 'F' },
// F: { distance: 4, predecessor: 'D' } }The graphlib.alg.dijkstraAll(graph, weightFn, edgeFn) function finds the shortest distance from every node to every other reachable node.
Returns:
A map mapping source -> alg.dijkstra(g, source, weightFn, edgeFn). Essentially, it returns a map of maps containing the results of Dijkstra's algorithm for every node in the graph.
Parameters:
weightFn(e): Returns the weight of edge e. Defaults to 1. Throws an error if negative weights are encountered.edgeFn(u): Returns all edge IDs associated with node u. Defaults to g.outEdges.Use graphlib.alg.components(graph) to find all connected parts of a graph. It returns an array of arrays, where each inner array contains the IDs of the nodes belonging to a specific connected component.
graphlib.alg.components(g);
// => [ [ 'A', 'B', 'C', 'D' ],
// [ 'E', 'F', 'G' ],
// [ 'H', 'I' ] ]These functions perform depth-first traversals starting from a specific node vs.
alg.preorder(graph, vs): Performs a preorder traversal. For each visited node v, a callback is executed.alg.postorder(graph, vs): Performs a postorder traversal. For each visited node v, a callback is executed.