Directed and undirected graphs with stable node and edge indexes, and
the algorithms Effect's Graph module has::
from pyfect import graph
def build(m: graph.MutableGraph[str, int]) -> None:
a, b, c = m.add_node("A"), m.add_node("B"), m.add_node("C")
m.add_edge(a, b, 1)
m.add_edge(b, c, 2)
g = graph.directed(build)
list(g.bfs(start=[0]).values()) # ["A", "B", "C"]
g.dijkstra(source=0, target=2, cost=lambda w: w).distance # 3A Graph is immutable and compared by structure; mutate (or
begin_mutation / end_mutation) changes a private MutableGraph
copy and returns a new graph. Indexes are allocated in order and never
reused, and every iteration follows them, so results are deterministic.
A method for one kind of graph (degree, topo) takes self typed
with that kind. Effect's dual (data-first / data-last) functions are
methods here, and its config objects keyword arguments.
Types#
| Type | Definition | Description |
|---|---|---|
DirectedGraph | type DirectedGraph[N, E] = Graph[N, E, Directed] | |
UndirectedGraph | type UndirectedGraph[N, E] = Graph[N, E, Undirected] | |
MutableDirectedGraph | type MutableDirectedGraph[N, E] = MutableGraph[N, E, Directed] | |
MutableUndirectedGraph | type MutableUndirectedGraph[N, E] = MutableGraph[N, E, Undirected] | |
Directed | type Directed = Literal['directed'] | |
Direction | type Direction = Literal['outgoing', 'incoming'] | |
Kind | type Kind = Literal['directed', 'undirected'] | |
MermaidDiagramType | type MermaidDiagramType = Literal['flowchart', 'graph'] | |
MermaidDirection | type MermaidDirection = Literal['TB', 'TD', 'BT', 'RL', 'LR'] | |
MermaidNodeShape | type MermaidNodeShape = Literal['rectangle', 'rounded', 'circle', 'diamond', 'hexagon', 'stadium', 'subroutine', 'cylindrical'] | |
TraversalDirection | type TraversalDirection = Literal['outgoing', 'incoming', 'undirected'] | |
Undirected | type Undirected = Literal['undirected'] | |
EdgeWalker | type EdgeWalker[E] = Walker[int, Edge[E]] | |
NodeWalker | type NodeWalker[N] = Walker[int, N] |
Classes#
Functions#
directed#
directed[N = Never, E = Never](build=None) -> Graph[N, E, Directed]make("directed", build).
| Parameter | Type | Description |
|---|---|---|
build | Callable[[MutableGraph[N, E, Directed]], object] | None = None |
Returns Graph[N, E, Directed]
def directed[N = Never, E = Never](
build: Callable[[MutableGraph[N, E, Directed]], object] | None = None,
) -> Graph[N, E, Directed]:
"""``make("directed", build)``."""
return make("directed", build)from_snapshot#
from_snapshot[N, E, K: Kind](snapshot) -> Graph[N, E, K]The graph of a snapshot, its indexes kept; raises GraphError
for a malformed one. New nodes and edges get indexes past the highest.
| Parameter | Type | Description |
|---|---|---|
snapshot | Snapshot[N, E, K] |
Returns Graph[N, E, K]
def from_snapshot[N, E, K: Kind](snapshot: Snapshot[N, E, K]) -> Graph[N, E, K]:
"""The graph of a snapshot, its indexes kept; raises ``GraphError``
for a malformed one. New nodes and edges get indexes past the highest."""
return Graph(_from_snapshot(snapshot))is_graph#
is_graph(value) -> TypeIs[Graph[Any, Any, Kind] | MutableGraph[Any, Any, Kind]]| Parameter | Type | Description |
|---|---|---|
value | object |
Returns TypeIs[Graph[Any, Any, Kind] | MutableGraph[Any, Any, Kind]]
def is_graph(value: object) -> TypeIs[Graph[Any, Any, Kind] | MutableGraph[Any, Any, Kind]]:
return isinstance(value, GraphView)make#
make[K: Kind, N = Never, E = Never](kind, build=None) -> Graph[N, E, K]An empty graph of kind, or the graph build makes of one.
| Parameter | Type | Description |
|---|---|---|
kind | K | |
build | Callable[[MutableGraph[N, E, K]], object] | None = None |
Returns Graph[N, E, K]
def make[K: Kind, N = Never, E = Never](
kind: K, build: Callable[[MutableGraph[N, E, K]], object] | None = None
) -> Graph[N, E, K]:
"""An empty graph of ``kind``, or the graph ``build`` makes of one."""
if kind not in ("directed", "undirected"):
fail("Graph type must be directed or undirected")
if build is None:
return Graph(Store(kind, False))
return _scoped(MutableGraph(Store(kind, True)), build)undirected#
undirected[N = Never, E = Never](build=None) -> Graph[N, E, Undirected]make("undirected", build).
| Parameter | Type | Description |
|---|---|---|
build | Callable[[MutableGraph[N, E, Undirected]], object] | None = None |
Returns Graph[N, E, Undirected]
def undirected[N = Never, E = Never](
build: Callable[[MutableGraph[N, E, Undirected]], object] | None = None,
) -> Graph[N, E, Undirected]:
"""``make("undirected", build)``."""
return make("undirected", build)