GitHub

GraphView

API reference for GraphView.

class GraphView[N, E, K: Kind]

The reads of a graph or a mutable graph.

Attributes

AttributeTypeDescription
typeK

"directed" or "undirected".

mutablebool

True for a mutable graph until it is finalized.

Functions

__init__

__init__(store) -> None
ParameterTypeDescription
storeStore
def __init__(self, store: Store) -> None:
    self._store = store

pipe

pipe[B](f) -> B
ParameterTypeDescription
fCallable[[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]
ParameterTypeDescription
indexint

Returns Option[N]

def get_node(self, index: int) -> Option[N]:
    nodes = self._store.nodes
    return Some(nodes[index]) if index in nodes else None

has_node

has_node(index) -> bool
ParameterTypeDescription
indexint

Returns bool

def has_node(self, index: int) -> bool:
    return index in self._store.nodes

node_count

node_count() -> int

Returns int

def node_count(self) -> int:
    return len(self._store.nodes)

find_node

find_node(predicate) -> int | None

The first node, in index order, whose data matches.

ParameterTypeDescription
predicateCallable[[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]
ParameterTypeDescription
predicateCallable[[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 | None

The first edge whose (data, source, target) matches (the stored orientation, also for an undirected edge).

ParameterTypeDescription
predicateCallable[[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]
ParameterTypeDescription
predicateCallable[[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
ParameterTypeDescription
indexint

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) -> bool

Whether an edge leads from source to target (either way for an undirected graph).

ParameterTypeDescription
sourceint
targetint

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() -> int

Returns 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.

ParameterTypeDescription
nodeint

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]
ParameterTypeDescription
nodeint

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]
ParameterTypeDescription
nodeint

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]
ParameterTypeDescription
sourceint
targetint

Returns list[int]

def edges_between(self, source: int, target: int) -> list[int]:
    return _query.edges_between(self._store, source, target)

degree

degree(node) -> int

The edges at node, a self-loop counting twice.

ParameterTypeDescription
nodeint

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
ParameterTypeDescription
nodeint

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
ParameterTypeDescription
nodeint

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.

ParameterTypeDescription
nodeint

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]
ParameterTypeDescription
nodeint

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]
ParameterTypeDescription
nodeint

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]
ParameterTypeDescription
nodeint
directionDirection

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') -> str

GraphViz DOT; labels default to JavaScript's String(data).

ParameterTypeDescription
node_labelCallable[[N], str] | None = None
edge_labelCallable[[E], str] | None = None
graph_namestr = '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) -> str

A Mermaid flowchart (directed) or graph (undirected).

ParameterTypeDescription
node_labelCallable[[N], str] | None = None
edge_labelCallable[[E], str] | None = None
diagram_typeMermaidDiagramType | None = None
directionMermaidDirection = 'TD'
node_shapeCallable[[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 | None

Returns CycleResult | None

def find_cycle(self) -> CycleResult | None:
    return _cycles.find_cycle(self._store)

is_acyclic

is_acyclic() -> bool

Returns bool

def is_acyclic(self) -> bool:
    return _cycles.is_acyclic(self._store)

is_bipartite

is_bipartite() -> bool

Returns 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.

ParameterTypeDescription
sourceint
directionTraversalDirection = '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
ParameterTypeDescription
sourceint
targetint
directionTraversalDirection = '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).bridges

articulation_points

articulation_points() -> list[int]

Returns list[int]

def articulation_points(self: GraphView[Any, Any, Undirected]) -> list[int]:
    return analyze(self._store).articulation_points

biconnected_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_components

maximum_flow

maximum_flow[E2](*, source, target, capacity) -> MaximumFlowResult
ParameterTypeDescription
sourceint
targetint
capacityCallable[[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
ParameterTypeDescription
sourceint
targetint
capacityCallable[[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() -> bool

Returns bool

def is_connected(self: GraphView[Any, Any, Undirected]) -> bool:
    return _components.is_connected(self._store)

is_weakly_connected

is_weakly_connected() -> bool

Returns bool

def is_weakly_connected(self: GraphView[Any, Any, Directed]) -> bool:
    return _components.is_weakly_connected(self._store)

is_strongly_connected

is_strongly_connected() -> bool

Returns bool

def is_strongly_connected(self: GraphView[Any, Any, Directed]) -> bool:
    return _components.is_strongly_connected(self._store)

is_tree

is_tree() -> bool

Returns 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.

ParameterTypeDescription
costCallable[[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] | None

A cheapest path, or None when target is unreachable.

ParameterTypeDescription
sourceint
targetint
costCallable[[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] | None

heuristic(node, target) estimates the cost left.

ParameterTypeDescription
sourceint
targetint
costCallable[[E], float]
heuristicCallable[[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] | None

Allows negative weights; a negative cycle the path could use raises.

ParameterTypeDescription
sourceint
targetint
costCallable[[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]
ParameterTypeDescription
costCallable[[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.

ParameterTypeDescription
sourceint
targetint
limitfloat | 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]]
ParameterTypeDescription
sourceint
targetint
costCallable[[E], float]
limitfloat | 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).

ParameterTypeDescription
startSequence[int] | None = None
directionTraversalDirection = 'outgoing'
radiusfloat | 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]
ParameterTypeDescription
startSequence[int] | None = None
directionTraversalDirection = 'outgoing'
radiusfloat | 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]
ParameterTypeDescription
startSequence[int] | None = None
directionTraversalDirection = 'outgoing'
radiusfloat | 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.

ParameterTypeDescription
initialsSequence[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).

ParameterTypeDescription
directionDirection = '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)