graph
stableIn-memory directed or undirected weighted graph with BFS, DFS, Dijkstra, PageRank, MST, SCC, cycle detection, coloring, and more.
use plugin graph::{Graph, add_node, add_edge, …} Functions (30)
- Graph Creates a new graph handle.
- add_node Adds a node with the given label and returns its unique integer id.
- add_edge Adds a weighted edge from node from to node to.
- remove_node Removes a node and every edge that touches it (both incoming and outgoing).
- remove_edge Removes the edge between two nodes.
- neighbors Returns a list of node ids directly reachable from id along outgoing edges.
- has_edge Returns true if there is an edge from from to to.
- node_count Returns the number of nodes currently in the graph.
- edge_count Returns the number of edges.
- bfs Returns node ids in breadth-first traversal order starting from start.
- dfs Returns node ids in depth-first traversal order starting from start.
- dijkstra Finds the shortest path between two nodes using Dijkstra's algorithm.
- is_connected Returns true if every node is reachable from an arbitrary starting node (a single connected component).
- degree Returns the number of edges incident on node.
- topological_sort Returns node ids in topological order for a directed acyclic graph.
- minimum_spanning_tree Computes the minimum spanning tree using Kruskal's algorithm (undirected graphs only).
- strongly_connected_components Finds strongly connected components using Kosaraju's algorithm (directed graphs only).
- betweenness_centrality Computes betweenness centrality for every node using Brandes' algorithm.
- pagerank Computes PageRank for all nodes.
- shortest_paths_all Runs Dijkstra from start to every reachable node.
- floyd_warshall Computes all-pairs shortest paths using the Floyd-Warshall algorithm.
- has_cycle Returns true if the graph contains a cycle.
- articulation_points Returns the node ids whose removal would increase the number of connected components (cut vertices), in sorted order.
- bridges Returns the edges whose removal would disconnect the graph as a list of {from, to} tables.
- graph_coloring Assigns each node a color (an integer starting at 0) so that no two adjacent nodes share a color, using a greedy strategy.
- connected_components Returns the connected components of the graph as a list of groups, each a list of node ids.
- get_label Returns the label string assigned to a node when it was created.
- get_nodes Returns all nodes as a list of {id, label} tables, sorted by id.
- get_edges Returns all edges as a list of {from, to, weight} tables.
- is_directed Returns true if the graph was created as directed.
Overview
graph is an in-memory adjacency-list graph that can be either directed or
undirected and carries an optional weight on every edge. Each graph is a
handle returned by the Graph(directed) constructor, and you mutate it through
methods on that handle. Nodes are not named by you directly: add_node(label)
returns an auto-incrementing integer id, and every other call refers to nodes by
that id while keeping the human-readable label alongside.
On top of the basic build-and-query operations the plugin bundles a full
algorithm toolbox: traversals (bfs, dfs), shortest paths (dijkstra,
shortest_paths_all, floyd_warshall), structural analysis (connected_components,
strongly_connected_components, articulation_points, bridges, has_cycle),
ordering (topological_sort), trees (minimum_spanning_tree), ranking
(pagerank, betweenness_centrality), and graph_coloring. Reach for it
whenever you need to model relationships — dependency graphs, road networks,
social graphs, task schedulers — and run classic graph algorithms over them
without pulling in an external library.
Common patterns
Build a weighted graph and find the shortest route between two nodes:
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 2.0)
g.add_edge(a, c, 5.0)
let route = g.dijkstra(a, c)
print("distance A->C: {route["distance"]}")
print("first hop: {route["path"][1]}")
Model a dependency graph and resolve a build order, guarding against cycles:
use plugin graph::{Graph}
let g = Graph(true)
let lib = g.add_node("lib")
let core = g.add_node("core")
let app = g.add_node("app")
g.add_edge(lib, core, 1.0)
g.add_edge(core, app, 1.0)
if g.has_cycle() {
print("dependency cycle detected")
} else {
let order = g.topological_sort()
print("build first: {g.get_label(order[1])}")
}
Build an undirected network and inspect its structure:
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
print("connected: {g.is_connected()}")
let cut = g.articulation_points()
print("critical nodes: {cut[1]}")
Creates a new graph handle.
Creates a new graph handle. Pass true for a directed graph or false for an
undirected one; in an undirected graph every edge you add is mirrored
automatically.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
g.add_edge(a, b, 1.0)
print("nodes: {g.node_count()}, edges: {g.edge_count()}")
Adds a node with the given label and returns its unique integer id.
Adds a node with the given label and returns its unique integer id. Ids start at 1 and increase with each node added.
use plugin graph::{Graph}
let g = Graph(false)
let id = g.add_node("server-1")
print("node id: {id}")
Adds a weighted edge from node from to node to.
Adds a weighted edge from node from to node to. For undirected graphs, the
reverse edge is added automatically. Errors if either node id does not exist.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
g.add_edge(a, b, 2.5)
Weights drive the shortest-path algorithms, so pick them to reflect distance or cost:
use plugin graph::{Graph}
let g = Graph(false)
let home = g.add_node("home")
let work = g.add_node("work")
g.add_edge(home, work, 12.4)
print("edge exists: {g.has_edge(home, work)}")
Removes a node and every edge that touches it (both incoming and outgoing).
Removes a node and every edge that touches it (both incoming and outgoing).
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
g.add_edge(a, b, 1.0)
g.remove_node(b)
print("nodes left: {g.node_count()}")
Removes the edge between two nodes.
Removes the edge between two nodes. For undirected graphs the mirrored edge is removed too.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
g.add_edge(a, b, 1.0)
g.remove_edge(a, b)
print("still connected: {g.has_edge(a, b)}")
Returns a list of node ids directly reachable from id along outgoing edges.
Returns a list of node ids directly reachable from id along outgoing edges.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(a, c, 1.0)
let ns = g.neighbors(a)
print("first neighbor: {ns[1]}")
Returns true if there is an edge from from to to.
Returns true if there is an edge from from to to.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
g.add_edge(a, b, 1.0)
print(g.has_edge(a, b))
print(g.has_edge(b, a))
Returns the number of nodes currently in the graph.
Returns the number of nodes currently in the graph.
use plugin graph::{Graph}
let g = Graph(false)
g.add_node("A")
g.add_node("B")
print("nodes: {g.node_count()}")
Returns the number of edges.
Returns the number of edges. For undirected graphs each mirrored pair counts once.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
g.add_edge(a, b, 1.0)
print("edges: {g.edge_count()}")
Returns node ids in breadth-first traversal order starting from start.
Returns node ids in breadth-first traversal order starting from start.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
let order = g.bfs(a)
print(order[1])
Returns node ids in depth-first traversal order starting from start.
Returns node ids in depth-first traversal order starting from start.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
let order = g.dfs(a)
print("visited {g.node_count()} nodes, first: {order[1]}")
Finds the shortest path between two nodes using Dijkstra's algorithm.
Finds the shortest path between two nodes using Dijkstra's algorithm. Returns a
table with path (list of node ids) and distance (total weight). Errors if no
path exists.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 2.0)
g.add_edge(a, c, 5.0)
let result = g.dijkstra(a, c)
print("distance: {result["distance"]}")
Because the result carries the full path, you can walk it to print the route by label:
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
let r = g.dijkstra(a, c)
print("{g.get_label(r["path"][1])} -> {g.get_label(r["path"][2])}")
Returns true if every node is reachable from an arbitrary starting node (a single connected component).
Returns true if every node is reachable from an arbitrary starting node (a single connected component).
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
g.add_edge(a, b, 1.0)
print(g.is_connected())
Returns the number of edges incident on node.
Returns the number of edges incident on node.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(a, c, 1.0)
print("degree of A: {g.degree(a)}")
Returns node ids in topological order for a directed acyclic graph.
Returns node ids in topological order for a directed acyclic graph. Errors if the graph is undirected or contains a cycle.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
let order = g.topological_sort()
print(order[1])
Computes the minimum spanning tree using Kruskal's algorithm (undirected graphs only).
Computes the minimum spanning tree using Kruskal's algorithm (undirected graphs
only). Returns a list of {from, to, weight} edge tables. Errors on directed
graphs.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 3.0)
g.add_edge(b, c, 1.0)
g.add_edge(a, c, 2.0)
let mst = g.minimum_spanning_tree()
print(mst[1]["weight"])
Finds strongly connected components using Kosaraju's algorithm (directed graphs only).
Finds strongly connected components using Kosaraju's algorithm (directed graphs only). Returns a list of components, each a list of node ids. Errors on undirected graphs.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
g.add_edge(c, a, 1.0)
let sccs = g.strongly_connected_components()
print("components: {sccs[1][1]}")
Computes betweenness centrality for every node using Brandes' algorithm.
Computes betweenness centrality for every node using Brandes' algorithm. Returns
a list of {node, centrality} entries sorted by node id; higher scores mark
nodes that more shortest paths pass through.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
let cent = g.betweenness_centrality()
print("B centrality: {cent[2]["centrality"]}")
Computes PageRank for all nodes.
Computes PageRank for all nodes. damping is typically 0.85, iterations is
typically 20. Returns a list of {node, rank} entries sorted by node id.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
g.add_edge(c, a, 1.0)
let ranks = g.pagerank(0.85, 20)
print(ranks[1]["rank"])
A lower damping factor spreads importance more evenly and converges faster:
use plugin graph::{Graph}
let g = Graph(true)
let hub = g.add_node("hub")
let leaf = g.add_node("leaf")
g.add_edge(leaf, hub, 1.0)
let ranks = g.pagerank(0.5, 10)
print("hub rank: {ranks[1]["rank"]}")
Runs Dijkstra from start to every reachable node.
Runs Dijkstra from start to every reachable node. Returns a list of
{node, distance} entries sorted by node id.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 4.0)
let dists = g.shortest_paths_all(a)
print("to {dists[3]["node"]}: {dists[3]["distance"]}")
Computes all-pairs shortest paths using the Floyd-Warshall algorithm.
Computes all-pairs shortest paths using the Floyd-Warshall algorithm. Returns a
list of {from, to, distance} entries for every reachable pair.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 2.0)
let pairs = g.floyd_warshall()
print("pairs found: {pairs[1]["distance"]}")
Returns true if the graph contains a cycle.
Returns true if the graph contains a cycle. Uses three-color DFS for directed graphs and back-edge detection for undirected graphs.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
g.add_edge(a, b, 1.0)
g.add_edge(b, a, 1.0)
print(g.has_cycle())
Returns the node ids whose removal would increase the number of connected components (cut vertices), in sorted order.
Returns the node ids whose removal would increase the number of connected components (cut vertices), in sorted order. Undirected graphs only.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
let cut = g.articulation_points()
print("cut vertex: {cut[1]}")
Returns the edges whose removal would disconnect the graph as a list of {from, to} tables.
Returns the edges whose removal would disconnect the graph as a list of
{from, to} tables. Undirected graphs only.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
let br = g.bridges()
print("bridge from {br[1]["from"]} to {br[1]["to"]}")
Assigns each node a color (an integer starting at 0) so that no two adjacent nodes share a color, using a greedy strategy.
Assigns each node a color (an integer starting at 0) so that no two adjacent
nodes share a color, using a greedy strategy. Returns a list of {node, color}
entries sorted by node id; errors if more than max_colors colors are needed.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
g.add_edge(b, c, 1.0)
let colors = g.graph_coloring(3)
print("color of A: {colors[1]["color"]}")
Returns the connected components of the graph as a list of groups, each a list of node ids.
Returns the connected components of the graph as a list of groups, each a list of node ids.
use plugin graph::{Graph}
let g = Graph(false)
let a = g.add_node("A")
let b = g.add_node("B")
let c = g.add_node("C")
g.add_edge(a, b, 1.0)
let comps = g.connected_components()
print("number of components: {comps[2][1]}")
Returns the label string assigned to a node when it was created.
Returns the label string assigned to a node when it was created. Errors if the node id does not exist.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("router")
print(g.get_label(a))
Returns all nodes as a list of {id, label} tables, sorted by id.
Returns all nodes as a list of {id, label} tables, sorted by id.
use plugin graph::{Graph}
let g = Graph(true)
g.add_node("alpha")
g.add_node("beta")
let nodes = g.get_nodes()
print(nodes[1]["label"])
Returns all edges as a list of {from, to, weight} tables.
Returns all edges as a list of {from, to, weight} tables. For undirected graphs
each edge appears once.
use plugin graph::{Graph}
let g = Graph(true)
let a = g.add_node("A")
let b = g.add_node("B")
g.add_edge(a, b, 4.2)
let edges = g.get_edges()
print(edges[1]["weight"])
Returns true if the graph was created as directed.
Returns true if the graph was created as directed.
use plugin graph::{Graph}
let g = Graph(false)
print(g.is_directed())