graph
Adjacency-list graphs: build, traverse, and answer reachability and path questions. Pure - no capabilities.
ecko get github.com/ecko-lang/graph
import graph
Pure computation: it declares no capabilities, so it cannot touch the network, the filesystem or the environment.
Version 0.38.0 - source - MIT.
new(directed = true)
Returns an empty graph, directed unless directed: false.
Directed is the default because the questions this package is for - who can approve this, what depends on what - have a direction.
errors: bug/bad_argument when directed is not a Bool.
friends = graph.new(directed: false)
from_edges(pairs, directed = true)
Returns a graph built from a list of [src, dst] pairs, directed unless directed: false.
errors: bug/bad_argument when pairs is not a list of two-element lists or directed is not a Bool; bug/bad_node when a node is not a string.
graph.from_edges([["lex", "parse"], ["parse", "compile"]])
add_node(g, node)
Returns g with a node that has no edges. Adding one that exists changes nothing.
errors: bug/bad_node when node is not a string.
graph.new() |> graph.add_node("solo")
add_edge(g, src, dst)
Returns g with an edge from src to dst, adding either endpoint that is missing. An undirected graph gets the reverse edge too. Adding the same edge twice changes nothing.
errors: bug/bad_node when an endpoint is not a string.
graph.new() |> graph.add_edge("alice", "bob")
remove_edge(g, src, dst)
Returns g without the edge from src to dst (both directions in an undirected graph), leaving both nodes in place. Removing an edge that is not there changes nothing.
graph.remove_edge(g, "alice", "bob")
remove_node(g, node)
Returns g without node and every edge touching it. Removing a node that is not there changes nothing.
graph.remove_node(g, "bob")
has_node(g, node)
Returns true when node is in the graph.
graph.has_node(g, "alice")
has_edge(g, src, dst)
Returns true when there is an edge from src to dst.
graph.has_edge(g, "alice", "bob")
nodes(g)
Returns every node, sorted.
graph.nodes(graph.from_edges([["b", "a"]])) # [a, b]
neighbors(g, node)
Returns the nodes node points at, sorted.
An unknown node raises rather than returning [], because silently returning nothing for a typo is how a traversal quietly explores nothing.
errors: graph/no_such_node when node is not in the graph.
graph.neighbors(g, "alice")
edges(g)
Returns every edge as a sorted list of [src, dst] pairs. An undirected edge appears once, with its endpoints in sorted order.
graph.edges(graph.from_edges([["b", "a"]], directed: false)) # [[a, b]]
order(g)
Returns how many nodes the graph has.
graph.order(g)
size(g)
Returns how many edges the graph has; an undirected edge counts once.
graph.size(g)
out_degree(g, node)
Returns how many edges leave node.
errors: graph/no_such_node when node is not in the graph.
graph.out_degree(g, "alice")
in_degree(g, node)
Returns how many edges arrive at node.
errors: graph/no_such_node when node is not in the graph.
graph.in_degree(g, "dave")
degree(g, node)
Returns the out-degree plus the in-degree of node.
On an undirected graph both count the same edges, so this is twice the neighbour count; use out_degree there instead.
errors: graph/no_such_node when node is not in the graph.
graph.degree(g, "dave")
bfs(g, start)
Returns the nodes in breadth-first order from start, start first.
Layer by layer, so the order doubles as "how far away is each node", which is why path is built on the same walk rather than on dfs.
errors: graph/no_such_node when start is not in the graph.
graph.bfs(g, "alice")
dfs(g, start)
Returns the nodes in depth-first order from start, start first.
errors: graph/no_such_node when start is not in the graph.
graph.dfs(g, "alice")
reachable(g, start)
Returns every node reachable from start, sorted, excluding start itself.
The question it answers: who can approve this spend, directly or by delegation?
errors: graph/no_such_node when start is not in the graph.
graph.reachable(g, "alice")
connected(g, src, dst)
Returns true when src can reach dst by following edges. A node always reaches itself.
errors: graph/no_such_node when src or dst is not in the graph.
graph.connected(g, "alice", "erin")
path(g, src, dst)
Returns the fewest-hops path from src to dst as a list of nodes, or null when there is none.
Breadth-first, so the first time dst is seen is by a shortest route. Every edge counts as one hop; there are no weights.
errors: graph/no_such_node when src or dst is not in the graph.
graph.path(g, "alice", "erin")
distance(g, src, dst)
Returns the number of hops on the shortest path from src to dst, or null when dst is unreachable.
errors: graph/no_such_node when src or dst is not in the graph.
graph.distance(g, "alice", "erin")
components(g)
Returns the connected components, each sorted, the list sorted by first member.
On a directed graph these are the weakly connected components: edges are followed in both directions, so every node is in exactly one component.
graph.components(graph.from_edges([["a", "b"], ["c", "b"]])) # [[a, b, c]]
has_cycle(g)
Returns true when the graph contains a cycle.
On a directed graph that is a directed cycle, a self-loop included; a diamond is not one. On an undirected graph it is a closed walk that does not reuse an edge, so a single edge is not a cycle but a triangle or a self-loop is.
graph.has_cycle(graph.from_edges([["a", "b"], ["b", "a"]])) # true
topo_sort(g)
Returns the nodes ordered so every edge points forwards.
Kahn's algorithm: repeatedly take a node nothing points at. Ties are broken by taking the smallest ready node at each step, so the result is stable rather than merely valid. Linear in nodes plus edges, apart from keeping the ready list sorted.
errors: graph/cycle when the graph has a cycle (a self-loop included); bug/bad_argument when the graph is undirected.
graph.topo_sort(graph.from_edges([["parse", "compile"], ["lex", "parse"]])) # [lex, parse, compile]