GitHub

Graphs

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.

build.py
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.

walk.py
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.

paths.py
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.