Directed and undirected graphs with stable indexes: traversals, shortest paths, components, flows and GraphViz or Mermaid output.
pyfect.graph holds nodes and edges with data of any type, as Effect's Graph module
does. A graph is immutable. You build one inside a callback, change it with mutate,
and get a new graph back each time. Nodes and edges are numbered in the order they are
added, an index is never reused, and every algorithm follows that order, so results are
the same on every run.
Building a graph#
graph.directed(build) and graph.undirected(build) call build with a
MutableGraph, then freeze it. add_node and add_edge return the new index.
mutate(f) runs f on a private copy and returns the finished graph; begin_mutation
and end_mutation do the same in two steps. Two immutable graphs are == when they
hold the same data at the same indexes.
from pyfect import graph
def roads(m: graph.MutableUndirectedGraph[str, float]) -> None:
oslo, bergen, trondheim = m.add_node("Oslo"), m.add_node("Bergen"), m.add_node("Trondheim")
m.add_edge(oslo, bergen, 463)
m.add_edge(oslo, trondheim, 494)
m.add_edge(bergen, trondheim, 633)
towns = graph.undirected(roads)
print(towns)
print(towns.neighbors(0), towns.degree(0))
def add_tromso(m: graph.MutableUndirectedGraph[str, float]) -> None:
tromso = m.add_node("Tromsø") # indexes are never reused: this is 3
m.add_edge(tromso, 2, 1140)
# A graph never changes: mutate edits a private copy and returns a new graph.
grown = towns.mutate(add_tromso)
print(towns.node_count(), grown.node_count())
print(grown.dijkstra(source=1, target=3, cost=float))
print(towns == graph.undirected(roads))Some methods only make sense for one kind of graph: degree, is_bipartite and
bridges need an undirected graph, topo, successors and maximum_flow a directed
one. Pyright rejects them on the wrong kind, and at runtime they raise GraphError.
Walking a graph#
dfs, bfs, dfs_post_order and topo return a Walker. Iterate it for
(index, data) pairs, or call indices(), values() or visit(f). start picks the
first nodes, direction can follow edges backwards ("incoming") or ignore their
direction ("undirected"), and radius stops at that many edges. A walker is lazy and
starts over each time you iterate it. On a mutable graph, an iteration already running
keeps the graph as it was when it started.
from pyfect import graph
def tasks(m: graph.MutableDirectedGraph[str, None]) -> None:
fetch, parse, index, report = (m.add_node(t) for t in ("fetch", "parse", "index", "report"))
m.add_edge(fetch, parse, None)
m.add_edge(parse, index, None)
m.add_edge(parse, report, None)
m.add_edge(index, report, None)
pipeline = graph.directed(tasks)
# Walkers are lazy and repeatable; each iteration starts over.
print(list(pipeline.topo().values()))
print(list(pipeline.bfs(start=[0]).indices()))
print(list(pipeline.dfs(start=[3], direction="incoming").values()))
print(pipeline.is_acyclic(), pipeline.find_cycle())
print(pipeline.to_mermaid(edge_label=lambda _: ""))to_graph_viz() writes the graph as GraphViz DOT and to_mermaid() as a Mermaid
flowchart. Both take label functions; by default a label is the data as JavaScript
would print it, so output matches Effect's.
Paths, components and flows#
dijkstra, astar and bellman_ford find one cheapest path, or return None when
the target can't be reached. cost turns an edge's data into a weight; math.inf
means the edge can't be used. floyd_warshall finds all pairs at once, and
simple_paths and all_shortest_paths list paths lazily, with an optional limit.
Negative weights are only accepted by Bellman-Ford and Floyd-Warshall, which raise
GraphError on a negative cycle.
from pyfect import graph
def network(m: graph.MutableDirectedGraph[str, int]) -> None:
a, b, c, d = (m.add_node(name) for name in "ABCD")
m.add_edge(a, b, 4)
m.add_edge(a, c, 1)
m.add_edge(c, b, 2)
m.add_edge(b, d, 1)
m.add_edge(c, d, 5)
g = graph.directed(network)
shortest = g.dijkstra(source=0, target=3, cost=float)
assert shortest is not None
print(shortest.path, shortest.distance)
# None when the target can't be reached.
print(g.dijkstra(source=3, target=0, cost=float))
every = g.floyd_warshall(float)
print(every.distances[0])
for found in g.simple_paths(source=0, target=3):
print(found.path, found.costs)
flow = g.maximum_flow(source=0, target=3, capacity=float)
print(flow.value, flow.cut)The graph has more analyses: connected_components,
strongly_connected_components, bridges and articulation_points,
maximum_bipartite_matching, minimum_cut, minimum_spanning_forest and
transitive_reduction. compose, intersection, difference, complement,
neighborhood and induced_subgraph build new graphs from existing ones.
to_snapshot and graph.from_snapshot turn a graph into plain records and back, with
its indexes kept.