# Generated from the published Markdown; run scripts/build_language_examples.py to refresh.
# Independent examples may reuse top-level names. Python remains the explanation language.


# topics/graphs/graph-representations.md
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B", "E"],
    "E": ["B", "D", "F"],
    "F": ["C", "E", "G"],
    "G": ["F"],
    "H": [],
}

# topics/graphs/graph-representations.md
vertices = list(graph)
index = {v: i for i, v in enumerate(vertices)}
n = len(vertices)
matrix = [[0] * n for _ in range(n)]
for u in vertices:
    for v in graph[u]:
        matrix[index[u]][index[v]] = 1

# topics/graphs/graph-operations.md
def add_vertex(graph, v):
    if v is None:
        raise ValueError("None is reserved for a missing parent")
    if v not in graph:
        graph[v] = []

def _require_endpoints(graph, u, v):
    if u not in graph:
        raise KeyError(u)
    if v not in graph:
        raise KeyError(v)

def add_edge(graph, u, v, *, directed=False):
    _require_endpoints(graph, u, v)
    if u == v:
        raise ValueError("simple graphs have no self-loops")
    if v not in graph[u]:
        graph[u].append(v)
    if not directed and u not in graph[v]:
        graph[v].append(u)

def has_edge(graph, u, v):
    _require_endpoints(graph, u, v)
    return v in graph[u]

def neighbours(graph, u):
    return list(graph[u])

def remove_edge(graph, u, v, *, directed=False):
    _require_endpoints(graph, u, v)
    if v not in graph[u]:
        raise KeyError((u, v))
    graph[u].remove(v)
    if not directed:
        graph[v].remove(u)

def remove_vertex(graph, v):
    if v not in graph:
        raise KeyError(v)
    for u in graph:
        if u != v and v in graph[u]:
            graph[u].remove(v)
    del graph[v]

def vertex_count(graph):
    return len(graph)

def edge_count(graph, *, directed=False):
    entries = sum(len(adjacent) for adjacent in graph.values())
    return entries if directed else entries // 2

def build_graph(vertices, edges, *, directed=False):
    graph = {}
    for v in vertices:
        add_vertex(graph, v)
    for u, v in edges:
        add_edge(graph, u, v, directed=directed)
    return graph

# topics/graphs/breadth-first-search.md
from collections import deque

def bfs(graph, start):
    if start not in graph:
        raise KeyError(start)
    distance = {start: 0}
    parent = {start: None}
    order = []
    queue = deque([start])
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in distance:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    return order, parent, distance

# topics/graphs/breadth-first-search.md
def path_to(parent, target):
    if target not in parent:
        return None
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = parent[current]
    path.reverse()
    return path

# topics/graphs/depth-first-search.md
def dfs(graph, start):
    if start not in graph:
        raise KeyError(start)
    seen = set()
    parent = {start: None}
    discovery, finish = [], []

    def visit(u):
        seen.add(u)
        discovery.append(u)
        for v in graph[u]:
            if v not in seen:
                parent[v] = u
                visit(v)
        finish.append(u)

    visit(start)
    return discovery, finish, parent

# topics/graphs/graph-components.md
from collections import deque

def connected_components(graph):
    seen, groups = set(), []
    for start in graph:
        if start in seen:
            continue
        seen.add(start)
        queue, group = deque([start]), []
        while queue:
            u = queue.popleft()
            group.append(u)
            for v in graph[u]:
                if v not in seen:
                    seen.add(v)
                    queue.append(v)
        groups.append(group)
    return groups

# topics/union-find/parent-forests.md
def find_root(parent, x):
    while parent[x] != x:
        x = parent[x]
    return x

# topics/union-find/union-compression.md
class DisjointSet:
    def __init__(self, n):
        if type(n) is not int or n < 0:
            raise ValueError("n must be a nonnegative integer")
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def _check(self, x):
        if type(x) is not int or not 0 <= x < len(self.parent):
            raise IndexError("member index out of range")

    def find(self, x):
        self._check(x)
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != x:
            next_x = self.parent[x]
            self.parent[x] = root
            x = next_x
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def __len__(self):
        return len(self.parent)

    def is_empty(self):
        return len(self) == 0

    def component_count(self):
        return self.components

    def component_size(self, x):
        return self.size[self.find(x)]

# topics/union-find/union-find-applications.md
def connection_forest(n, edges):
    sets = DisjointSet(n)
    chosen, rejected = [], []
    for a, b in edges:
        if sets.union(a, b):
            chosen.append((a, b))
        else:
            rejected.append((a, b))
    return chosen, rejected, sets.components

# topics/graph-algorithms/topological-order.md
dag = {
    "A": ["C"], "B": ["C", "D"],
    "C": ["E"], "D": ["E"],
    "E": ["F"], "F": [], "G": [],
}

def valid_topological_order(graph, order):
    if len(order) != len(graph) or set(order) != set(graph):
        return False
    position = {v: i for i, v in enumerate(order)}
    return all(position[u] < position[v]
               for u in graph for v in graph[u])

# topics/graph-algorithms/topological-order.md
from collections import deque

def topological_sort(graph):
    degree = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            degree[v] += 1
    ready = deque(v for v in graph if degree[v] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in graph[u]:
            degree[v] -= 1
            if degree[v] == 0:
                ready.append(v)
    if len(order) != len(graph):
        raise ValueError("directed cycle: no complete order")
    return order

# topics/graph-algorithms/shortest-path-state.md
weighted = {
    "A": [("B", 4), ("C", 1)],
    "B": [("D", 1), ("E", 7)],
    "C": [("B", 2), ("D", 5), ("F", 8)],
    "D": [("E", 3)], "E": [("F", 1)],
    "F": [], "G": [],
}

# topics/graph-algorithms/shortest-path-state.md
from math import inf

def weighted_path_to(source, target, distance, parent):
    if distance[target] == inf:
        return None
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = parent[current]
    path.reverse()
    return path

# topics/graph-algorithms/dijkstra.md
from heapq import heappush, heappop
from itertools import count
from math import inf

def dijkstra(graph, source):
    if source not in graph:
        raise KeyError(source)
    if any(w < 0 for edges in graph.values() for _, w in edges):
        raise ValueError("Dijkstra requires nonnegative weights")
    distance = {v: inf for v in graph}
    parent = {v: None for v in graph}
    distance[source] = 0
    sequence = count()
    heap = [(0, next(sequence), source)]
    while heap:
        cost, _, u = heappop(heap)
        if cost != distance[u]:
            continue
        for v, w in graph[u]:
            candidate = cost + w
            if candidate < distance[v]:
                distance[v] = candidate
                parent[v] = u
                heappush(heap, (candidate, next(sequence), v))
    return distance, parent

# topics/graph-algorithms/dag-shortest-paths.md
from math import inf

def dag_shortest_paths(graph, source):
    if source not in graph:
        raise KeyError(source)
    unweighted = {u: [v for v, _ in graph[u]] for u in graph}
    order = topological_sort(unweighted)
    distance = {v: inf for v in graph}
    parent = {v: None for v in graph}
    distance[source] = 0
    for u in order:
        if distance[u] == inf:
            continue
        for v, w in graph[u]:
            candidate = distance[u] + w
            if candidate < distance[v]:
                distance[v] = candidate
                parent[v] = u
    return distance, parent

# topics/graph-algorithms/spanning-trees.md
vertices = list("ABCDEF")
edges = [
    (4, "A", "B"), (2, "A", "C"), (1, "B", "C"),
    (5, "B", "D"), (8, "C", "D"), (10, "C", "E"),
    (2, "D", "E"), (6, "D", "F"), (3, "E", "F"),
]

def weighted_adjacency(vertices, edges):
    graph = {v: [] for v in vertices}
    for weight, u, v in edges:
        graph[u].append((v, weight))
        graph[v].append((u, weight))
    return graph

# topics/graph-algorithms/prim.md
from heapq import heappush, heappop
from itertools import count

def prim_forest(graph):
    seen, chosen = set(), []
    total, components = 0, 0
    sequence = count()
    for root in graph:
        if root in seen:
            continue
        components += 1
        seen.add(root)
        heap = []
        for v, w in graph[root]:
            if v not in seen:
                heappush(heap, (w, next(sequence), root, v))
        while heap:
            w, _, u, v = heappop(heap)
            if v in seen:
                continue
            seen.add(v)
            chosen.append((w, u, v))
            total += w
            for x, cost in graph[v]:
                if x not in seen:
                    heappush(heap, (cost, next(sequence), v, x))
    return chosen, total, components

# topics/graph-algorithms/kruskal.md
def kruskal_forest(vertices, edges):
    vertices = list(vertices)
    index = {v: i for i, v in enumerate(vertices)}
    if len(index) != len(vertices):
        raise ValueError("vertices must be unique")
    sets = DisjointSet(len(vertices))
    chosen, total = [], 0
    for w, u, v in sorted(edges, key=lambda edge: edge[0]):
        if sets.union(index[u], index[v]):
            chosen.append((w, u, v))
            total += w
    return chosen, total, sets.components

# topics/applications/transport-model.md
# Transport prerequisites are included above.

places = {
    "A": "Gate", "B": "Museum", "C": "Library",
    "D": "Market", "E": "Clinic", "F": "Park", "G": "Harbour",
}
# (endpoint, endpoint, travel_minutes, construction_units)
links = [
    ("A", "B", 12, 3), ("A", "C", 3, 6),
    ("B", "C", 2, 2), ("B", "D", 3, 4),
    ("C", "D", 9, 1), ("C", "E", 12, 7),
    ("D", "E", 3, 5), ("D", "F", 8, 2),
    ("E", "F", 2, 3),
]

def adjacency_view(places, links, weight_column=None):
    if weight_column not in (None, 2, 3):
        raise ValueError("choose unweighted, travel time or construction cost")
    graph = {place: [] for place in places}
    for row in links:
        u, v = row[:2]
        if weight_column is None:
            graph[u].append(v)
            graph[v].append(u)
        else:
            weight = row[weight_column]
            graph[u].append((v, weight))
            graph[v].append((u, weight))
    return graph

hop_graph = adjacency_view(places, links)
time_graph = adjacency_view(places, links, 2)
build_graph = adjacency_view(places, links, 3)

# topics/applications/transport-model.md
def route_total(route, links, weight_column):
    if weight_column not in (2, 3):
        raise ValueError("choose travel time or construction cost")
    if route is None:
        return None
    weights = {frozenset((row[0], row[1])): row[weight_column]
               for row in links}
    return sum(weights[frozenset((u, v))]
               for u, v in zip(route, route[1:]))

# topics/applications/transport-hops.md
order, hop_parent, hop_distance = bfs(hop_graph, "A")
fewest_route = path_to(hop_parent, "F")
fewest_minutes = route_total(fewest_route, links, 2)

# topics/applications/transport-times.md
time_distance, time_parent = dijkstra(time_graph, "A")
fastest_route = weighted_path_to("A", "F", time_distance, time_parent)
fastest_minutes = route_total(fastest_route, links, 2)

# topics/applications/transport-connectivity.md
place_index = {place: i for i, place in enumerate(places)}
sets = DisjointSet(len(places))
opening_log = []
for u, v, minutes, build_units in links:
    merged = sets.union(place_index[u], place_index[v])
    opening_log.append((u, v, merged, sets.components))

# topics/applications/transport-design.md
construction_edges = [(cost, u, v) for u, v, minutes, cost in links]
chosen_build, build_total, build_components = kruskal_forest(
    places, construction_edges
)
prim_chosen, prim_total, prim_components = prim_forest(build_graph)

# topics/applications/transport-design.md
chosen_pairs = {frozenset((u, v)) for cost, u, v in chosen_build}
built_links = [row for row in links
               if frozenset((row[0], row[1])) in chosen_pairs]
built_time_graph = adjacency_view(places, built_links, 2)
built_distance, built_parent = dijkstra(built_time_graph, "A")
built_route = weighted_path_to("A", "F", built_distance, built_parent)