class Graph[N, E, K: Kind = Literal['directed']]
An immutable graph of nodes N and edges E. Change one with
mutate (or begin_mutation / end_mutation), which returns a
new graph. Two graphs are == when they have the same kind and the
same nodes and edges at the same indexes (payloads compared as Effect's
Equal does; an undirected edge either way round).
Functions#
__init__#
__init__(store) -> None| Parameter | Type | Description |
|---|---|---|
store | Store |
def __init__(self, store: Store) -> None:
self._store = storebegin_mutation#
begin_mutation[N2, E2, K2: Kind]() -> MutableGraph[N2, E2, K2]A mutable copy; this graph never changes.
Returns MutableGraph[N2, E2, K2]
def begin_mutation[N2, E2, K2: Kind](self: Graph[N2, E2, K2]) -> MutableGraph[N2, E2, K2]:
"""A mutable copy; this graph never changes."""
return MutableGraph(self._store.clone(True))mutate#
mutate[N2, E2, K2: Kind](f) -> Graph[N2, E2, K2]The graph f makes of a mutable copy of this one. The handle is
finalized afterwards, also when f raises.
| Parameter | Type | Description |
|---|---|---|
f | Callable[[MutableGraph[N2, E2, K2]], object] |
Returns Graph[N2, E2, K2]
def mutate[N2, E2, K2: Kind](
self: Graph[N2, E2, K2], f: Callable[[MutableGraph[N2, E2, K2]], object]
) -> Graph[N2, E2, K2]:
"""The graph ``f`` makes of a mutable copy of this one. The handle is
finalized afterwards, also when ``f`` raises."""
return _scoped(self.begin_mutation(), f)compose#
compose[N2, E2, K2: Kind](that, *, node_identity=None, edge_identity=None) -> Graph[N2, E2, K2]The union of both graphs, nodes and edges matched by identity
(default: their data); that's payloads win.
| Parameter | Type | Description |
|---|---|---|
that | Graph[N2, E2, K2] | |
node_identity | Callable[[N2], object] | None = None | |
edge_identity | Callable[[E2], object] | None = None |
Returns Graph[N2, E2, K2]
def compose[N2, E2, K2: Kind](
self: Graph[N2, E2, K2],
that: Graph[N2, E2, K2],
*,
node_identity: Callable[[N2], object] | None = None,
edge_identity: Callable[[E2], object] | None = None,
) -> Graph[N2, E2, K2]:
"""The union of both graphs, nodes and edges matched by identity
(default: their data); ``that``'s payloads win."""
return Graph(_combine.compose(self._store, that._store, node_identity, edge_identity))intersection#
intersection[N2, E2, K2: Kind](that, *, node_identity=None, edge_identity=None) -> Graph[N2, E2, K2]The nodes (this graph's payloads) and edges (that's) in both.
| Parameter | Type | Description |
|---|---|---|
that | Graph[N2, E2, K2] | |
node_identity | Callable[[N2], object] | None = None | |
edge_identity | Callable[[E2], object] | None = None |
Returns Graph[N2, E2, K2]
def intersection[N2, E2, K2: Kind](
self: Graph[N2, E2, K2],
that: Graph[N2, E2, K2],
*,
node_identity: Callable[[N2], object] | None = None,
edge_identity: Callable[[E2], object] | None = None,
) -> Graph[N2, E2, K2]:
"""The nodes (this graph's payloads) and edges (``that``'s) in both."""
return Graph(_combine.intersection(self._store, that._store, node_identity, edge_identity))difference#
difference[N2, E2, K2: Kind](that, *, node_identity=None, edge_identity=None) -> Graph[N2, E2, K2]Every node of this graph, and its edges that lacks.
| Parameter | Type | Description |
|---|---|---|
that | Graph[N2, E2, K2] | |
node_identity | Callable[[N2], object] | None = None | |
edge_identity | Callable[[E2], object] | None = None |
Returns Graph[N2, E2, K2]
def difference[N2, E2, K2: Kind](
self: Graph[N2, E2, K2],
that: Graph[N2, E2, K2],
*,
node_identity: Callable[[N2], object] | None = None,
edge_identity: Callable[[E2], object] | None = None,
) -> Graph[N2, E2, K2]:
"""Every node of this graph, and its edges ``that`` lacks."""
return Graph(_combine.difference(self._store, that._store, node_identity, edge_identity))symmetric_difference#
symmetric_difference[N2, E2, K2: Kind](that, *, node_identity=None, edge_identity=None) -> Graph[N2, E2, K2]Every node of both, and the edges in exactly one.
| Parameter | Type | Description |
|---|---|---|
that | Graph[N2, E2, K2] | |
node_identity | Callable[[N2], object] | None = None | |
edge_identity | Callable[[E2], object] | None = None |
Returns Graph[N2, E2, K2]
def symmetric_difference[N2, E2, K2: Kind](
self: Graph[N2, E2, K2],
that: Graph[N2, E2, K2],
*,
node_identity: Callable[[N2], object] | None = None,
edge_identity: Callable[[E2], object] | None = None,
) -> Graph[N2, E2, K2]:
"""Every node of both, and the edges in exactly one."""
return Graph(
_combine.symmetric_difference(self._store, that._store, node_identity, edge_identity)
)complement#
complement[N2, E2, K2: Kind](create_edge) -> Graph[N2, E2, K2]The same nodes, with an edge (from create_edge(source, target))
wherever this graph has none; no self-loops.
| Parameter | Type | Description |
|---|---|---|
create_edge | Callable[[N2, N2], E2] |
Returns Graph[N2, E2, K2]
def complement[N2, E2, K2: Kind](
self: Graph[N2, E2, K2], create_edge: Callable[[N2, N2], E2]
) -> Graph[N2, E2, K2]:
"""The same nodes, with an edge (from ``create_edge(source, target)``)
wherever this graph has none; no self-loops."""
return Graph(_combine.complement(self._store, create_edge))neighborhood#
neighborhood(node, *, radius=None, direction='outgoing') -> Graph[N, E, K]The subgraph of the nodes within radius (default 1) edges of
node, re-indexed in breadth-first order.
| Parameter | Type | Description |
|---|---|---|
node | int | |
radius | float | None = None | |
direction | TraversalDirection = 'outgoing' |
Returns Graph[N, E, K]
def neighborhood(
self,
node: int,
*,
radius: float | None = None,
direction: TraversalDirection = "outgoing",
) -> Graph[N, E, K]:
"""The subgraph of the nodes within ``radius`` (default 1) edges of
``node``, re-indexed in breadth-first order."""
return Graph(_combine.neighborhood(self._store, node, radius, direction))induced_subgraph#
induced_subgraph(nodes) -> Graph[N, E, K]The given nodes and the edges among them, indexes kept.
| Parameter | Type | Description |
|---|---|---|
nodes | Iterable[int] |
Returns Graph[N, E, K]
def induced_subgraph(self, nodes: Iterable[int]) -> Graph[N, E, K]:
"""The given nodes and the edges among them, indexes kept."""
return Graph(_combine.induced_subgraph(self._store, nodes))sum#
sum[N2, E2, K2: Kind](that) -> Graph[N2, E2, K2]This graph and that side by side, that re-indexed after it.
| Parameter | Type | Description |
|---|---|---|
that | Graph[N2, E2, K2] |
Returns Graph[N2, E2, K2]
def sum[N2, E2, K2: Kind](
self: Graph[N2, E2, K2], that: Graph[N2, E2, K2]
) -> Graph[N2, E2, K2]:
"""This graph and ``that`` side by side, ``that`` re-indexed after it."""
return Graph(_combine.disjoint_sum(self._store, that._store))pipe#
pipe[B](f) -> B| Parameter | Type | Description |
|---|---|---|
f | Callable[[Self], B] |
Returns B
def pipe[B](self, f: Callable[[Self], B], /) -> B:
return f(self)to_snapshot#
to_snapshot() -> Snapshot[N, E, K]Returns Snapshot[N, E, K]
def to_snapshot(self) -> Snapshot[N, E, K]:
return cast("Snapshot[N, E, K]", _snapshot.to_snapshot(self._store))get_node#
get_node(index) -> Option[N]| Parameter | Type | Description |
|---|---|---|
index | int |
Returns Option[N]
def get_node(self, index: int) -> Option[N]:
nodes = self._store.nodes
return Some(nodes[index]) if index in nodes else Nonehas_node#
has_node(index) -> bool| Parameter | Type | Description |
|---|---|---|
index | int |
Returns bool
def has_node(self, index: int) -> bool:
return index in self._store.nodesnode_count#
node_count() -> intReturns int
def node_count(self) -> int:
return len(self._store.nodes)find_node#
find_node(predicate) -> int | NoneThe first node, in index order, whose data matches.
| Parameter | Type | Description |
|---|---|---|
predicate | Callable[[N], bool] |
Returns int | None
def find_node(self, predicate: Callable[[N], bool]) -> int | None:
"""The first node, in index order, whose data matches."""
return _query.find_node(self._store, predicate)find_nodes#
find_nodes(predicate) -> list[int]| Parameter | Type | Description |
|---|---|---|
predicate | Callable[[N], bool] |
Returns list[int]
def find_nodes(self, predicate: Callable[[N], bool]) -> list[int]:
return _query.find_nodes(self._store, predicate)find_edge#
find_edge(predicate) -> int | NoneThe first edge whose (data, source, target) matches (the
stored orientation, also for an undirected edge).
| Parameter | Type | Description |
|---|---|---|
predicate | Callable[[E, int, int], bool] |
Returns int | None
def find_edge(self, predicate: Callable[[E, int, int], bool]) -> int | None:
"""The first edge whose ``(data, source, target)`` matches (the
stored orientation, also for an undirected edge)."""
return _query.find_edge(self._store, predicate)find_edges#
find_edges(predicate) -> list[int]| Parameter | Type | Description |
|---|---|---|
predicate | Callable[[E, int, int], bool] |
Returns list[int]
def find_edges(self, predicate: Callable[[E, int, int], bool]) -> list[int]:
return _query.find_edges(self._store, predicate)get_edge#
get_edge(index) -> Edge[E] | None| Parameter | Type | Description |
|---|---|---|
index | int |
Returns Edge[E] | None
def get_edge(self, index: int) -> Edge[E] | None:
return self._store.edges.get(index)has_edge#
has_edge(source, target) -> boolWhether an edge leads from source to target (either way
for an undirected graph).
| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int |
Returns bool
def has_edge(self, source: int, target: int) -> bool:
"""Whether an edge leads from ``source`` to ``target`` (either way
for an undirected graph)."""
return _query.has_edge(self._store, source, target)edge_count#
edge_count() -> intReturns int
def edge_count(self) -> int:
return len(self._store.edges)incident_edges#
incident_edges(node) -> list[int]Every edge touching node, in index order, a self-loop once.
| Parameter | Type | Description |
|---|---|---|
node | int |
Returns list[int]
def incident_edges(self, node: int) -> list[int]:
"""Every edge touching ``node``, in index order, a self-loop once."""
return _query.incident_edges(self._store, node)outgoing_edges#
outgoing_edges(node) -> list[int]| Parameter | Type | Description |
|---|---|---|
node | int |
Returns list[int]
def outgoing_edges(self: GraphView[Any, Any, Directed], node: int) -> list[int]:
return _query.directed_edges(self._store, node, "outgoing")incoming_edges#
incoming_edges(node) -> list[int]| Parameter | Type | Description |
|---|---|---|
node | int |
Returns list[int]
def incoming_edges(self: GraphView[Any, Any, Directed], node: int) -> list[int]:
return _query.directed_edges(self._store, node, "incoming")edges_between#
edges_between(source, target) -> list[int]| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int |
Returns list[int]
def edges_between(self, source: int, target: int) -> list[int]:
return _query.edges_between(self._store, source, target)degree#
degree(node) -> intThe edges at node, a self-loop counting twice.
| Parameter | Type | Description |
|---|---|---|
node | int |
Returns int
def degree(self: GraphView[Any, Any, Undirected], node: int) -> int:
"""The edges at ``node``, a self-loop counting twice."""
return _query.degree(self._store, node)out_degree#
out_degree(node) -> int| Parameter | Type | Description |
|---|---|---|
node | int |
Returns int
def out_degree(self: GraphView[Any, Any, Directed], node: int) -> int:
return _query.directed_degree(self._store, node, "outgoing")in_degree#
in_degree(node) -> int| Parameter | Type | Description |
|---|---|---|
node | int |
Returns int
def in_degree(self: GraphView[Any, Any, Directed], node: int) -> int:
return _query.directed_degree(self._store, node, "incoming")neighbors#
neighbors(node) -> list[int]Distinct neighbors (successors for a directed graph), in the order of the first edge reaching each.
| Parameter | Type | Description |
|---|---|---|
node | int |
Returns list[int]
def neighbors(self, node: int) -> list[int]:
"""Distinct neighbors (successors for a directed graph), in the
order of the first edge reaching each."""
return _query.neighbors(self._store, node)successors#
successors(node) -> list[int]| Parameter | Type | Description |
|---|---|---|
node | int |
Returns list[int]
def successors(self: GraphView[Any, Any, Directed], node: int) -> list[int]:
return _query.kind_neighbors(self._store, node, "outgoing", "successors")predecessors#
predecessors(node) -> list[int]| Parameter | Type | Description |
|---|---|---|
node | int |
Returns list[int]
def predecessors(self: GraphView[Any, Any, Directed], node: int) -> list[int]:
return _query.kind_neighbors(self._store, node, "incoming", "predecessors")neighbors_directed#
neighbors_directed(node, direction) -> list[int]| Parameter | Type | Description |
|---|---|---|
node | int | |
direction | Direction |
Returns list[int]
def neighbors_directed(
self: GraphView[Any, Any, Directed], node: int, direction: Direction
) -> list[int]:
return _query.kind_neighbors(self._store, node, direction, "directed neighbors")to_graph_viz#
to_graph_viz(*, node_label=None, edge_label=None, graph_name='G') -> strGraphViz DOT; labels default to JavaScript's String(data).
| Parameter | Type | Description |
|---|---|---|
node_label | Callable[[N], str] | None = None | |
edge_label | Callable[[E], str] | None = None | |
graph_name | str = 'G' |
Returns str
def to_graph_viz(
self,
*,
node_label: Callable[[N], str] | None = None,
edge_label: Callable[[E], str] | None = None,
graph_name: str = "G",
) -> str:
"""GraphViz DOT; labels default to JavaScript's ``String(data)``."""
return _render.to_graph_viz(self._store, node_label, edge_label, graph_name)to_mermaid#
to_mermaid(*, node_label=None, edge_label=None, diagram_type=None, direction='TD', node_shape=None) -> strA Mermaid flowchart (directed) or graph (undirected).
| Parameter | Type | Description |
|---|---|---|
node_label | Callable[[N], str] | None = None | |
edge_label | Callable[[E], str] | None = None | |
diagram_type | MermaidDiagramType | None = None | |
direction | MermaidDirection = 'TD' | |
node_shape | Callable[[N], MermaidNodeShape] | None = None |
Returns str
def to_mermaid(
self,
*,
node_label: Callable[[N], str] | None = None,
edge_label: Callable[[E], str] | None = None,
diagram_type: MermaidDiagramType | None = None,
direction: MermaidDirection = "TD",
node_shape: Callable[[N], MermaidNodeShape] | None = None,
) -> str:
"""A Mermaid ``flowchart`` (directed) or ``graph`` (undirected)."""
return _render.to_mermaid(
self._store,
node_label=node_label,
edge_label=edge_label,
diagram_type=diagram_type,
direction=direction,
node_shape=node_shape,
)find_cycle#
find_cycle() -> CycleResult | NoneReturns CycleResult | None
def find_cycle(self) -> CycleResult | None:
return _cycles.find_cycle(self._store)is_acyclic#
is_acyclic() -> boolReturns bool
def is_acyclic(self) -> bool:
return _cycles.is_acyclic(self._store)is_bipartite#
is_bipartite() -> boolReturns bool
def is_bipartite(self: GraphView[Any, Any, Undirected]) -> bool:
return _cycles.is_bipartite(self._store)maximum_bipartite_matching#
maximum_bipartite_matching() -> list[BipartiteMatch]A maximum matching; raises GraphError for a graph that is not bipartite.
Returns list[BipartiteMatch]
def maximum_bipartite_matching(
self: GraphView[Any, Any, Undirected],
) -> list[BipartiteMatch]:
"""A maximum matching; raises ``GraphError`` for a graph that is not bipartite."""
return _matching.maximum_bipartite_matching(self._store)unweighted_distances#
unweighted_distances(source, *, direction='outgoing') -> dict[int, int]Edges from source to each node it reaches, in node order.
| Parameter | Type | Description |
|---|---|---|
source | int | |
direction | TraversalDirection = 'outgoing' |
Returns dict[int, int]
def unweighted_distances(
self, source: int, *, direction: TraversalDirection = "outgoing"
) -> dict[int, int]:
"""Edges from ``source`` to each node it reaches, in node order."""
return _components.unweighted_distances(self._store, source, direction)has_path#
has_path(source, target, *, direction='outgoing') -> bool| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int | |
direction | TraversalDirection = 'outgoing' |
Returns bool
def has_path(
self, source: int, target: int, *, direction: TraversalDirection = "outgoing"
) -> bool:
return _components.has_path(self._store, source, target, direction)connected_components#
connected_components() -> list[list[int]]Returns list[list[int]]
def connected_components(self: GraphView[Any, Any, Undirected]) -> list[list[int]]:
return _components.connected_components(self._store)bridges#
bridges() -> list[int]Returns list[int]
def bridges(self: GraphView[Any, Any, Undirected]) -> list[int]:
return analyze(self._store).bridgesarticulation_points#
articulation_points() -> list[int]Returns list[int]
def articulation_points(self: GraphView[Any, Any, Undirected]) -> list[int]:
return analyze(self._store).articulation_pointsbiconnected_components#
biconnected_components() -> list[list[int]]Each sorted, sorted; a self-loop is a component of its own.
Returns list[list[int]]
def biconnected_components(self: GraphView[Any, Any, Undirected]) -> list[list[int]]:
"""Each sorted, sorted; a self-loop is a component of its own."""
return analyze(self._store).biconnected_componentsmaximum_flow#
maximum_flow[E2](*, source, target, capacity) -> MaximumFlowResult| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int | |
capacity | Callable[[E2], float] |
Returns MaximumFlowResult
def maximum_flow[E2](
self: GraphView[Any, E2, Directed],
*,
source: int,
target: int,
capacity: Callable[[E2], float],
) -> MaximumFlowResult:
return _flow.maximum_flow(self._store, source, target, capacity)minimum_cut#
minimum_cut[E2](*, source, target, capacity) -> MinimumCutResult| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int | |
capacity | Callable[[E2], float] |
Returns MinimumCutResult
def minimum_cut[E2](
self: GraphView[Any, E2, Directed],
*,
source: int,
target: int,
capacity: Callable[[E2], float],
) -> MinimumCutResult:
return _flow.minimum_cut(self._store, source, target, capacity)weakly_connected_components#
weakly_connected_components() -> list[list[int]]Returns list[list[int]]
def weakly_connected_components(self: GraphView[Any, Any, Directed]) -> list[list[int]]:
return _components.weakly_connected_components(self._store)strongly_connected_components#
strongly_connected_components() -> list[list[int]]Returns list[list[int]]
def strongly_connected_components(self: GraphView[Any, Any, Directed]) -> list[list[int]]:
return _components.strongly_connected_components(self._store)is_connected#
is_connected() -> boolReturns bool
def is_connected(self: GraphView[Any, Any, Undirected]) -> bool:
return _components.is_connected(self._store)is_weakly_connected#
is_weakly_connected() -> boolReturns bool
def is_weakly_connected(self: GraphView[Any, Any, Directed]) -> bool:
return _components.is_weakly_connected(self._store)is_strongly_connected#
is_strongly_connected() -> boolReturns bool
def is_strongly_connected(self: GraphView[Any, Any, Directed]) -> bool:
return _components.is_strongly_connected(self._store)is_tree#
is_tree() -> boolReturns bool
def is_tree(self: GraphView[Any, Any, Undirected]) -> bool:
return _components.is_tree(self._store)minimum_spanning_forest#
minimum_spanning_forest[N2, E2](cost) -> Graph[N2, E2, Undirected]Every node, and the edges of a minimum spanning tree of each component.
| Parameter | Type | Description |
|---|---|---|
cost | Callable[[E2], float] |
Returns Graph[N2, E2, Undirected]
def minimum_spanning_forest[N2, E2](
self: GraphView[N2, E2, Undirected], cost: Callable[[E2], float]
) -> Graph[N2, E2, Undirected]:
"""Every node, and the edges of a minimum spanning tree of each component."""
return _graph(_forest.minimum_spanning_forest(self._store, cost))transitive_reduction#
transitive_reduction[N2, E2]() -> Graph[N2, E2, Directed]Returns Graph[N2, E2, Directed]
def transitive_reduction[N2, E2](
self: GraphView[N2, E2, Directed],
) -> Graph[N2, E2, Directed]:
return _graph(_forest.transitive_reduction(self._store))dijkstra#
dijkstra(*, source, target, cost) -> PathResult[E] | NoneA cheapest path, or None when target is unreachable.
| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int | |
cost | Callable[[E], float] |
Returns PathResult[E] | None
def dijkstra(
self, *, source: int, target: int, cost: Callable[[E], float]
) -> PathResult[E] | None:
"""A cheapest path, or ``None`` when ``target`` is unreachable."""
return _shortest.dijkstra(self._store, source, target, cost)astar#
astar(*, source, target, cost, heuristic) -> PathResult[E] | Noneheuristic(node, target) estimates the cost left.
| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int | |
cost | Callable[[E], float] | |
heuristic | Callable[[N, N], float] |
Returns PathResult[E] | None
def astar(
self,
*,
source: int,
target: int,
cost: Callable[[E], float],
heuristic: Callable[[N, N], float],
) -> PathResult[E] | None:
"""``heuristic(node, target)`` estimates the cost left."""
return _shortest.astar(self._store, source, target, cost, heuristic)bellman_ford#
bellman_ford(*, source, target, cost) -> PathResult[E] | NoneAllows negative weights; a negative cycle the path could use raises.
| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int | |
cost | Callable[[E], float] |
Returns PathResult[E] | None
def bellman_ford(
self, *, source: int, target: int, cost: Callable[[E], float]
) -> PathResult[E] | None:
"""Allows negative weights; a negative cycle the path could use raises."""
return _shortest.bellman_ford(self._store, source, target, cost)floyd_warshall#
floyd_warshall(cost) -> AllPairsResult[E]| Parameter | Type | Description |
|---|---|---|
cost | Callable[[E], float] |
Returns AllPairsResult[E]
def floyd_warshall(self, cost: Callable[[E], float]) -> AllPairsResult[E]:
return _all_pairs.floyd_warshall(self._store, cost)simple_paths#
simple_paths(*, source, target, limit=None) -> Iterable[PathResult[E]]Every path visiting no node twice, lazily, depth-first in edge
order; limit caps how many.
| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int | |
limit | float | None = None |
Returns Iterable[PathResult[E]]
def simple_paths(
self, *, source: int, target: int, limit: float | None = None
) -> Iterable[PathResult[E]]:
"""Every path visiting no node twice, lazily, depth-first in edge
order; ``limit`` caps how many."""
return _enumerate.simple_paths(self._store, source, target, limit)all_shortest_paths#
all_shortest_paths(*, source, target, cost, limit=None) -> Iterable[PathResult[E]]| Parameter | Type | Description |
|---|---|---|
source | int | |
target | int | |
cost | Callable[[E], float] | |
limit | float | None = None |
Returns Iterable[PathResult[E]]
def all_shortest_paths(
self,
*,
source: int,
target: int,
cost: Callable[[E], float],
limit: float | None = None,
) -> Iterable[PathResult[E]]:
return _enumerate.all_shortest_paths(self._store, source, target, cost, limit)dfs#
dfs(*, start=None, direction='outgoing', radius=None) -> Walker[int, N]Depth-first from each of start in turn (none: nothing).
| Parameter | Type | Description |
|---|---|---|
start | Sequence[int] | None = None | |
direction | TraversalDirection = 'outgoing' | |
radius | float | None = None |
Returns Walker[int, N]
def dfs(
self,
*,
start: Sequence[int] | None = None,
direction: TraversalDirection = "outgoing",
radius: float | None = None,
) -> Walker[int, N]:
"""Depth-first from each of ``start`` in turn (none: nothing)."""
return _traverse.dfs(self._store, start, direction, radius)bfs#
bfs(*, start=None, direction='outgoing', radius=None) -> Walker[int, N]| Parameter | Type | Description |
|---|---|---|
start | Sequence[int] | None = None | |
direction | TraversalDirection = 'outgoing' | |
radius | float | None = None |
Returns Walker[int, N]
def bfs(
self,
*,
start: Sequence[int] | None = None,
direction: TraversalDirection = "outgoing",
radius: float | None = None,
) -> Walker[int, N]:
return _traverse.bfs(self._store, start, direction, radius)dfs_post_order#
dfs_post_order(*, start=None, direction='outgoing', radius=None) -> Walker[int, N]| Parameter | Type | Description |
|---|---|---|
start | Sequence[int] | None = None | |
direction | TraversalDirection = 'outgoing' | |
radius | float | None = None |
Returns Walker[int, N]
def dfs_post_order(
self,
*,
start: Sequence[int] | None = None,
direction: TraversalDirection = "outgoing",
radius: float | None = None,
) -> Walker[int, N]:
return _traverse.dfs_post_order(self._store, start, direction, radius)topo#
topo[N2](*, initials=None) -> Walker[int, N2]Topological order (Kahn), initials first, then the other
sources in index order.
| Parameter | Type | Description |
|---|---|---|
initials | Sequence[int] | None = None |
Returns Walker[int, N2]
def topo[N2](
self: GraphView[N2, Any, Directed], *, initials: Sequence[int] | None = None
) -> Walker[int, N2]:
"""Topological order (Kahn), ``initials`` first, then the other
sources in index order."""
return _traverse.topo(self._store, initials)nodes#
nodes() -> Walker[int, N]The nodes, live: a running iteration sees nodes added later.
Returns Walker[int, N]
def nodes(self) -> Walker[int, N]:
"""The nodes, live: a running iteration sees nodes added later."""
return _traverse.nodes(self._store)edges#
edges() -> Walker[int, Edge[E]]Returns Walker[int, Edge[E]]
def edges(self) -> Walker[int, Edge[E]]:
return _traverse.edges(self._store)externals#
externals(*, direction='outgoing') -> Walker[int, N]Nodes without outgoing edges (sinks), or incoming ones (sources).
| Parameter | Type | Description |
|---|---|---|
direction | Direction = 'outgoing' |
Returns Walker[int, N]
def externals(self, *, direction: Direction = "outgoing") -> Walker[int, N]:
"""Nodes without outgoing edges (sinks), or incoming ones (sources)."""
return _traverse.externals(self._store, direction)On This Page
Functions__init__begin_mutationmutatecomposeintersectiondifferencesymmetric_differencecomplementneighborhoodinduced_subgraphsumpipeto_snapshotget_nodehas_nodenode_countfind_nodefind_nodesfind_edgefind_edgesget_edgehas_edgeedge_countincident_edgesoutgoing_edgesincoming_edgesedges_betweendegreeout_degreein_degreeneighborssuccessorspredecessorsneighbors_directedto_graph_vizto_mermaidfind_cycleis_acyclicis_bipartitemaximum_bipartite_matchingunweighted_distanceshas_pathconnected_componentsbridgesarticulation_pointsbiconnected_componentsmaximum_flowminimum_cutweakly_connected_componentsstrongly_connected_componentsis_connectedis_weakly_connectedis_strongly_connectedis_treeminimum_spanning_foresttransitive_reductiondijkstraastarbellman_fordfloyd_warshallsimple_pathsall_shortest_pathsdfsbfsdfs_post_ordertoponodesedgesexternals