class GraphView[N, E, K: Kind]
The reads of a graph or a mutable graph.
Attributes#
| Attribute | Type | Description |
|---|---|---|
type | K |
|
mutable | bool |
|
Functions#
__init__#
__init__(store) -> None| Parameter | Type | Description |
|---|---|---|
store | Store |
def __init__(self, store: Store) -> None:
self._store = storepipe#
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
AttributesFunctions__init__pipeto_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