Graph Algorithms

Overview

This subpackage provides the four classic graph algorithms: two traversals and two optimization algorithms on weighted graphs.

Function

Computes

Accepts

Time

bfs()

Nodes reachable from a source, by distance in edges

any AbstractGraph

\(O(V + E)\)

dfs()

Nodes reachable from a source, deepest first

any AbstractGraph

\(O(V + E)\)

dijkstra()

Shortest distances and paths from a source

any AbstractWeightedGraph

\(O((V + E) \log V)\)

kruskal()

Minimum spanning forest

WeightedGraph

\(O(E \log E)\)

Each function reads the graph through its public interface and never modifies it. Each one accepts the broadest abstraction that offers what it needs: the traversals only need neighbors(), Dijkstra needs weighted outgoing edges, and Kruskal needs an undirected weighted graph plus a way to build its result, which only the concrete WeightedGraph provides.

Note

Results are reproducible. Graphs yield neighbors in edge insertion order, so a traversal visits nodes in the same order on every run, and ties between equal paths or equal weights are always broken the same way.

Traversals

Both traversals start from a source node and visit every node reachable from it exactly once. They differ in the data structure holding the nodes still to explore: a queue for breadth-first search, a stack for depth-first search.

        graph LR
    A((a)) --- B((b))
    A --- C((c))
    B --- D((d))
    B --- E((e))
    C --- E

    style A fill:#3498db,color:#fff
Visiting order from a (edges inserted a-b, a-c, b-d, b-e, c-e)

Traversal

Order

Why

bfs

a, b, c, d, e

distance 0, then distance 1 (b, c), then distance 2 (d, e)

dfs

a, b, d, e, c

follows a-b-d, backtracks to b, goes to e, reaches c from e

On a directed graph, both follow arcs from source to target only.

sds.algorithms.graph_algorithms.bfs(graph, source)[source]

Yield the nodes reachable from source in breadth-first order.

Parameters:

  • graph (AbstractGraph) – Any graph. For a directed graph, edges are followed from source to target only (neighbors() yields successors).

  • source (GraphNode) – The starting node, yielded first.

Yields:

GraphNode – Every node reachable from source, exactly once, by non-decreasing number of edges from the source. Nodes at the same distance come in the order their discoverer’s neighbors are listed, i.e. edge insertion order.

Raises:

ElementNotFoundError – If source is not in the graph (raised on the first next()).

Examples

>>> from sds.graph import Edge, Graph, GraphNode
>>> a, b, c, d = (GraphNode(x, x) for x in "abcd")
>>> g = Graph()
>>> for n in (a, b, c, d):
...     g.add_node(n)
>>> for u, v in ((a, b), (a, c), (b, d)):
...     g.add_edge(Edge(u, v))
>>> [n.id for n in bfs(g, a)]
['a', 'b', 'c', 'd']

Notes

Time complexity: O(V + E) over the reachable part of the graph. Space complexity: O(V) for the visited set and the queue.

Nodes not reachable from source are not visited; call bfs() again from one of them to explore another connected component.

sds.algorithms.graph_algorithms.dfs(graph, source)[source]

Yield the nodes reachable from source in depth-first preorder.

Parameters:

  • graph (AbstractGraph) – Any graph. For a directed graph, edges are followed from source to target only (neighbors() yields successors).

  • source (GraphNode) – The starting node, yielded first.

Yields:

GraphNode – Every node reachable from source, exactly once, in the order a recursive DFS first reaches them, exploring neighbors in the order the graph lists them (edge insertion order).

Raises:

ElementNotFoundError – If source is not in the graph (raised on the first next()).

Examples

>>> from sds.graph import Edge, Graph, GraphNode
>>> a, b, c, d = (GraphNode(x, x) for x in "abcd")
>>> g = Graph()
>>> for n in (a, b, c, d):
...     g.add_node(n)
>>> for u, v in ((a, b), (a, c), (b, d)):
...     g.add_edge(Edge(u, v))
>>> [n.id for n in dfs(g, a)]
['a', 'b', 'd', 'c']

Notes

Time complexity: O(V + E) over the reachable part of the graph. Space complexity: O(V) for the visited set and the stack.

Shortest Paths: Dijkstra

Given a weighted graph with non-negative weights, Dijkstra’s algorithm computes the shortest distance from a source to every reachable node. It repeatedly settles the unsettled node closest to the source, then relaxes each of its outgoing edges \((u, v, w)\):

\[d(v) \leftarrow \min\big(d(v),\; d(u) + w\big)\]

Once settled, a node’s distance never changes: any other path to it would leave the settled region through a node at least as far away, and non-negative weights cannot make that path shorter. This is why a negative weight breaks the algorithm, and why the implementation raises ValueError when it meets one.

        graph LR
    S((s)) -- 10 --> T((t))
    S -- 5 --> Y((y))
    T -- 1 --> X((x))
    T -- 2 --> Y
    Y -- 3 --> T
    Y -- 9 --> X
    Y -- 2 --> Z((z))
    X -- 4 --> Z
    Z -- 7 --> S
    Z -- 6 --> X

    style S fill:#3498db,color:#fff

From s: \(d(y) = 5\), \(d(z) = 7\), \(d(t) = 8\) (through y), \(d(x) = 9\) (through y then t).

The function returns two dictionaries: the distances, and for each node its predecessor on a shortest path. Following predecessors back from a node rebuilds the path:

from sds.algorithms.graph_algorithms import dijkstra

dist, pred = dijkstra(graph, source)

path, node = [], target
while node is not None:
    path.append(node)
    node = pred[node]
path.reverse()                    # source ... target
sds.algorithms.graph_algorithms.dijkstra(graph, source)[source]

Compute shortest distances and paths from source.

Parameters:

  • graph (AbstractWeightedGraph) – A weighted graph, directed or not, with non-negative weights. On an undirected graph every edge can be followed both ways.

  • source (GraphNode) – The node distances are measured from.

Returns:

  • distances (dict of GraphNode to float) – The shortest distance from source to every reachable node (distances[source] == 0). Unreachable nodes are absent.

  • predecessors (dict of GraphNode to GraphNode or None) – For every reachable node, the previous node on one shortest path from source (None for source itself). Following it back from a node rebuilds that path in reverse.

Raises:
Return type:

Tuple[Dict[GraphNode, float], Dict[GraphNode, GraphNode | None]]

Examples

>>> from sds.graph import GraphNode, WeightedEdge, WeightedGraph
>>> a, b, c = (GraphNode(x, x) for x in "abc")
>>> g = WeightedGraph()
>>> for n in (a, b, c):
...     g.add_node(n)
>>> g.add_edge(WeightedEdge(a, b, 4.0))
>>> g.add_edge(WeightedEdge(a, c, 1.0))
>>> g.add_edge(WeightedEdge(c, b, 2.0))
>>> dist, pred = dijkstra(g, a)
>>> dist[b], pred[b].id, pred[c].id
(3.0, 'c', 'a')

Rebuilding the path to b:

>>> path, node = [], b
>>> while node is not None:
...     path.append(node.id)
...     node = pred[node]
>>> path[::-1]
['a', 'c', 'b']

Notes

Time complexity: O((V + E) log V) with a binary heap. Space complexity: O(V + E) in the worst case (lazy deletion lets the heap hold one entry per successful relaxation).

Among several shortest paths, the one recorded is the first found; since neighbors are visited in edge insertion order, the result is deterministic. Parallel edges are fine: only the lightest can relax.

Negative weights break the greedy argument (a settled distance could later be improved), hence the ValueError; use Bellman-Ford for such graphs.

Minimum Spanning Forest: Kruskal

A minimum spanning tree (MST) of a connected undirected graph connects all its \(V\) nodes with \(V - 1\) edges of minimum total weight. On a graph with \(C\) connected components, the same construction gives a minimum spanning forest of \(V - C\) edges.

Kruskal’s algorithm scans the edges by increasing weight and keeps an edge whenever its two endpoints are not yet connected. A disjoint-set (sds.advanced.DisjointSet) answers that question in near-constant time. The result is optimal by the cut property: for any split of the nodes into two groups, the lightest edge crossing between them belongs to some MST.

        graph LR
    A((a)) -- 1 --- B((b))
    B -. 4 .- C((c))
    A -- 3 --- C
    C -- 2 --- D((d))

%% Kept: a-b (1), c-d (2), a-c (3). Rejected: b-c (4) would close a cycle.

Edges are sorted with merge_sort(), which is stable, so among edges of equal weight the one inserted first wins: the forest returned is always the same.

sds.algorithms.graph_algorithms.kruskal(graph)[source]

Return a minimum spanning forest of an undirected weighted graph.

Parameters:

graph (WeightedGraph) – An undirected weighted graph. It is not modified. Directed graphs are not accepted: spanning trees are defined on undirected graphs (the directed analogue, the minimum arborescence, needs a different algorithm).

Returns:

A new graph holding every node of graph and the edges of a minimum spanning forest: V - C edges, with C the number of connected components. The edge objects are those of graph, shared rather than copied.

Return type:

WeightedGraph

Raises:

StructureTypeError – If graph is not a WeightedGraph.

Examples

>>> from sds.graph import GraphNode, WeightedEdge, WeightedGraph
>>> a, b, c, d = (GraphNode(x, x) for x in "abcd")
>>> g = WeightedGraph()
>>> for n in (a, b, c, d):
...     g.add_node(n)
>>> for u, v, w in ((a, b, 1.0), (b, c, 4.0), (a, c, 3.0), (c, d, 2.0)):
...     g.add_edge(WeightedEdge(u, v, w))
>>> mst = kruskal(g)
>>> mst.edge_count(), mst.total_weight()
(3, 6.0)

Notes

Time complexity: O(E log E) for sorting the edges, plus O(E α(V)) for the union-find operations. Space complexity: O(V + E).

The parameter is typed on the concrete WeightedGraph rather than on AbstractWeightedGraph (#86): the algorithm needs an undirected weighted graph and a way to build the result, which no single abstract interface provides.

Edges are sorted with merge_sort(), which is stable: among edges of equal weight, the one inserted first in graph is considered first, so the forest returned is deterministic.

Usage Example: Road Network

from sds.graph import GraphNode, WeightedEdge, WeightedGraph
from sds.algorithms.graph_algorithms import bfs, dijkstra, kruskal

cities = {name: GraphNode(name, name) for name in
          ["Paris", "Lyon", "Lille", "Nantes", "Bordeaux"]}
roads = WeightedGraph()
for city in cities.values():
    roads.add_node(city)
for a, b, km in [("Paris", "Lyon", 465), ("Paris", "Lille", 225),
                 ("Paris", "Nantes", 385), ("Nantes", "Bordeaux", 345),
                 ("Lyon", "Bordeaux", 555), ("Paris", "Bordeaux", 585)]:
    roads.add_edge(WeightedEdge(cities[a], cities[b], km))

# Which cities can be reached from Lille, closest (in hops) first?
[c.id for c in bfs(roads, cities["Lille"])]

# Shortest driving distance from Lille to Bordeaux
dist, pred = dijkstra(roads, cities["Lille"])
dist[cities["Bordeaux"]]          # 810: Lille - Paris - Bordeaux

# Cheapest set of roads keeping every city connected
network = kruskal(roads)
network.total_weight()            # 1420

Best Practices

✅ Use bfs for shortest paths counted in edges; use dijkstra as soon as edges carry weights.

✅ Keep the predecessor dictionary of dijkstra: it holds every shortest path from the source, not only one.

✅ Materialize a traversal with list(...) if the graph may change afterwards: the traversals are lazy.

❌ Do not run dijkstra on graphs with negative weights; it raises ValueError as soon as it meets one.

❌ Do not pass a directed graph to kruskal: minimum spanning trees are defined on undirected graphs.

References