Graphlib

Graphlib is a Dart library that provides data structures for undirected and directed multi-graphs along with algorithms that can be used with them.

Graphlib was ported to Dart from a JavaScript library of the same name by Richard Lincoln.

Example

// Create a new empty graph.
var g = new Digraph();

// Add node "A" to the graph with no value.
g.addNode("A");

// This returns true
g.hasNode("A");

// Add node "B" to the graph with a String value.
g.addNode("B", "B's value");

// Prints `B's value`
print(g.node("B"));

// Add node "C" to the graph with a Map value.
g.addNode("C", { 'k': 123 });
g.addNode("D");

// Prints `[ 'A', 'B', 'C', 'D' ]`.
print(g.nodes());

// Add a directed edge with the ID "AB" from "A" to "B", but assign no value.
g.addEdge("AB", "A", "B");

// Add a directed edge with no ID (Diraph will assign one) from "B" to "C".
g.addEdge(null, "B", "C");

// Add a directed edge from "C" to "D" with a Map value.
g.addEdge("CD", "C", "D", { 'k': 456 });

// Since Digraph is a multi-graph, we can have multiple edges incident on the
// same source and target nodes.
g.addEdge("AB2", "A", "B");

// Prints `[ 'AB', '_ANON-1', 'CD', 'AB2' ]`. `_ANON-1` is the edge from "B"
// to "C"
print(g.edges());

// Which edges go from "A" to "B"? This prints `[ 'AB', 'AB2' ]`.
print(g.outEdges("A", "B"));

// Which edges are incident on "D"? This prints `[ 'CD' ]`.
print(g.incidentEdges("D"));

// How about a subgraph?
var g2 = g.subgraph(["A", "B", "C"]);

// Prints `[ 'A', 'B', 'C' ]`.
print(g2.nodes());

// Prints `[ 'AB', '_ANON-1', 'AB2' ]`. Note that edges that have both their
// source and target nodes in the graph are also included in the subgraph.
print(g2.edges());

License

Graphlib is licensed under the terms of the MIT License. See the LICENSE file for details.

Libraries

graphlib
priority_queue