1.4.2 - Directed and undirected graphs

Choose direction from the relationship

A graph has vertices representing entities and edges representing relationships between them. Unlike a rooted tree, a general graph need not have a root or a parent hierarchy. It can contain cycles and disconnected parts. A vertex with no edges is isolated, but is still stored data.

A friendship model might be undirected, while a one-way road or a follows relationship is directed. Direction should represent the actual relationship, not the page layout.

[DIAGRAM: Four-vertex undirected graph and directed cycle with an incoming edge; asset_slug: directed-and-undirected-edges; caption: Undirected branches work both ways. Directed arrows permit only their shown direction.]

In the left example, edges are A—B, B—C and A—D. All four vertices are reachable from A. In the right example, edges are A→B, B→C, C→A and D→A. A, B and C form a cycle. Starting at A cannot reach D: D's arrow points into A. Starting at D can reach all four vertices. Reachability asks whether a path of permitted edges exists, not whether two nodes are close on the page.

Edges may also have a weight, such as travel time or cost. Direction and weighting are separate choices: a graph can be weighted and undirected, or weighted and directed. A weight is a property of the relationship, not a vertex's label. The small implementations below deliberately use unweighted simple graphs: no parallel edges and no self-loops. Other graph contracts can permit those features.

Record adjacency as lists or a matrix

An adjacency list records each vertex and its neighbours. For a directed graph, its neighbour collection lists outgoing destinations. Every vertex needs an entry, even if its collection is empty; otherwise an isolated vertex could disappear from the model.

The right-hand diagram can be recorded as A: [B], B: [C], C: [A], D: [A]. In an undirected adjacency list, each edge occurs at both endpoints. The left-hand example is A: [B,D], B: [A,C], C: [B], D: [A]. Those six neighbour entries represent three edges, not six independent undirected edges.

An adjacency matrix fixes a vertex order and allocates one cell per ordered pair. In this unweighted matrix, row is source, column is destination, 1 means an edge and 0 means no edge. For the directed example:

The A,B cell is 1 while B,A is 0: direction need not be symmetric. An undirected graph's matrix is symmetric because the two ordered cells describe the same edge. A zero diagonal follows our no-self-loop contract, not a rule for every graph. A weighted matrix can store weights, but must distinguish absent edges from genuine zero-weight edges, for example by using NULL for absence. Zero is a safe absence marker only if zero-weight edges are forbidden.

Create an empty matrix by setting every cell to the absence marker and retaining the vertex-order table. Create an empty adjacency-list representation by allocating one empty collection for each known vertex. To find a directed edge u→v, inspect cell [u,v] or look for v in u's neighbour collection. Finding a vertex by label needs the label/index map or the adjacency dictionary; that is different from following paths to find a reachable vertex.

Add and remove vertices and edges consistently

Changing graph data means changing all records of the relationship. For directed u→v, add v to u's outgoing neighbours only. For undirected u—v, add each endpoint to the other's neighbours. Removing an undirected edge must remove both entries. A duplicate insertion should follow a stated policy: this simple graph retains one edge and returns false when no change is made.

Python dictionaries represent vertex entries and sets represent neighbour collections here. Sets prevent duplicates and have no meaningful stored order. Both endpoints must already exist; unknown endpoints and self-loops are rejected without mutation. The caller states whether the graph is directed and keeps that choice consistent for all operations.

def add_edge(graph, u, v, directed):
    if u not in graph or v not in graph or u == v:
        return False
    if v in graph[u]:
        return False
    graph[u].add(v)
    if not directed:
        graph[v].add(u)
    return True

def remove_edge(graph, u, v, directed):
    if u not in graph or v not in graph or v not in graph[u]:
        return False
    graph[u].remove(v)
    if not directed:
        graph[v].remove(u)
    return True

graph = {v: set() for v in ["A", "B", "C", "D"]}
for u, v in [("A", "B"), ("B", "C"), ("A", "D")]:
    add_edge(graph, u, v, False)
remove_edge(graph, "A", "B", False)
print({v: sorted(graph[v]) for v in sorted(graph)})

The output is {'A': ['D'], 'B': ['C'], 'C': ['B'], 'D': ['A']}. Removing A—B retains the vertices and other edges. The undirected removal routine assumes the representation was already symmetric; it does not repair an inconsistent graph silently. In a matrix, perform the same operation by changing both symmetric cells to 0; removing a directed edge changes just its source/destination cell.

Experiment with edge direction

In this ungraded sandbox, compare the same relationship changes under two direction choices. Predict the final neighbour collections and rejected-operation results, then run. Sorted output makes the sets readable; their internal order has no meaning.