# 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