---

Mastering Graph Traversal: Find the Degree of Separation in Common Lisp

Calculating the degree of separation in Common Lisp involves modeling a family tree as an undirected graph. By using a Breadth-First Search (BFS) algorithm, you can efficiently find the shortest path between any two individuals, which represents their exact relational distance within the complex network.

Imagine you're the lead developer for "Noble Knots," a new, exclusive dating app for the aristocracy. The clientele is... complicated. With centuries of royal intermarriage, the family trees look less like trees and more like tangled wreaths. Your primary mission is to prevent disastrously awkward matches by calculating just how closely related two potential partners are. A simple mistake could lead to a PR nightmare.

This isn't just a fanciful problem; it's a real-world challenge solved by applications like Iceland's "Íslendinga-App," which helps Icelanders avoid accidentally dating a close relative. You're tasked with building the core logic for this feature. The goal is to take a complex web of family connections and return a single, simple number: the degree of separation. This guide will walk you through solving this classic graph theory problem from zero to hero, using the power and elegance of Common Lisp.

---

What is the Degree of Separation?

The "degree of separation" is a concept from social network analysis that measures the shortest distance between two nodes in a graph. You've likely heard of it through the "Six Degrees of Kevin Bacon" game, which posits that any actor can be linked to Kevin Bacon through their film roles in six steps or fewer.

In our context, the nodes are individuals, and the connections (or edges) are direct family ties—parent to child. The degree of separation is the minimum number of these direct ties you need to traverse to get from one person to another. For example:

• A parent and child have a separation of 1.
• Siblings share a common parent, so the path is Child A → Parent → Child B. This is a separation of 2.
• First cousins would have a separation of 4 (You → Your Parent → Your Grandparent → Your Aunt/Uncle → Your Cousin).

To solve this, we must first represent the family tree in a way a computer can understand. The most effective data structure for this task is a graph.

---

Why Use a Graph to Model a Family Tree?

A family tree might seem hierarchical, but the relationships are bidirectional. While a parent has a child, that child also has a parent. This network of interconnected relationships is perfectly modeled by an undirected graph.

• Nodes (or Vertices): Each unique person in the family tree is a node.
• Edges: An edge represents a direct relationship between two nodes. In our case, an edge connects a parent to their child.

Crucially, we treat these edges as undirected. The "distance" from a parent to a child is 1, and the distance from that child back to the parent is also 1. This is because we are measuring connections, not directionality or hierarchy. By building this graph, we transform the problem from a genealogical puzzle into a classic computer science problem: finding the shortest path between two nodes.

From Family Data to an Adjacency List

The most common way to represent a graph in code is using an adjacency list. An adjacency list is essentially a map (or a hash table) where each key is a node, and its value is a list of all the nodes it's directly connected to. In Common Lisp, nested hash-tables are an excellent tool for this.

Here is a conceptual diagram of this transformation:

    ● Input: Family Data
    │  (Parent . Children)
    │  ('A' . ('B', 'C'))
    │  ('B' . ('D'))
    │
    ▼
  ┌───────────────────┐
  │   Process Input   │
  │  (Build Graph)    │
  └─────────┬─────────┘
            │
            ▼
    ● Output: Adjacency List (Undirected Graph)
    │
    ├─ A ⟶ [B, C]
    ├─ B ⟶ [A, D]
    ├─ C ⟶ [A]
    └─ D ⟶ [B]

Notice how the connection is mutual. Since 'A' is a parent of 'B', we add 'B' to 'A's list of neighbors. Simultaneously, we must add 'A' to 'B's list of neighbors to make the graph undirected.

---

How to Build the Graph and Find the Path in Common Lisp

To solve this problem from the kodikra.com exclusive curriculum, we need two main components: a function to build the graph from the input data, and a function to traverse that graph to find the shortest path. The algorithm of choice for the shortest path in an unweighted graph is Breadth-First Search (BFS).

BFS explores the graph layer by layer from a starting node. It finds all neighbors at distance 1, then all their unvisited neighbors at distance 2, and so on. This guarantees that the first time we encounter our target person, we will have found the shortest possible path.

The Complete Common Lisp Solution

Here is the full code. We will break down each part in detail below.

(defpackage :relative-distance
  (:use :cl)
  (:export :degree-of-separation))

(in-package :relative-distance)

(defun build-graph (family-tree)
  "Builds an undirected graph (adjacency list) from family tree data."
  (let ((neighbors (make-hash-table :test 'equal)))
    (loop for (parent . children) in family-tree
          do (loop for child in children
                   do (pushnew parent (gethash child neighbors '()) :test 'equal)
                      (pushnew child (gethash parent neighbors '()) :test 'equal)))
    neighbors))

(defun degree-of-separation (family-tree person1 person2)
  "Calculates the degree of separation using Breadth-First Search (BFS)."
  (when (equal person1 person2)
    (return-from degree-of-separation 0))

  (let ((graph (build-graph family-tree))
        (queue (list (list person1 0))) ; Queue stores (person . distance)
        (visited (make-hash-table :test 'equal)))

    (unless (and (gethash person1 graph) (gethash person2 graph))
      (return-from degree-of-separation nil)) ; One or both not in the tree

    (setf (gethash person1 visited) t)

    (loop while queue
          do (let* ((current-path (pop queue))
                    (current-person (first current-path))
                    (distance (second current-path)))

               (when (equal current-person person2)
                 (return-from degree-of-separation distance))

               (loop for neighbor in (gethash current-person graph)
                     do (unless (gethash neighbor visited)
                          (setf (gethash neighbor visited) t)
                          (setf queue (append queue (list (list neighbor (+ distance 1)))))))))))

Code Walkthrough: The build-graph Function

This function is the foundation of our solution. Its only job is to convert the input list into a usable graph representation.

(let ((neighbors (make-hash-table :test 'equal))) ... )

We start by initializing an empty hash-table. The :test 'equal argument is critical because our keys will be strings (names), and equal correctly compares string content. The default, eql, would compare memory locations, which would fail.

(loop for (parent . children) in family-tree ... )

This is the main loop that iterates through each entry in the family-tree data. Lisp's destructuring capabilities allow us to neatly assign the first element of each sublist to parent and the rest to children.

do (loop for child in children ... )

For each parent, we then loop through their list of children.

do (pushnew parent (gethash child neighbors '()) :test 'equal)
(pushnew child (gethash parent neighbors '()) :test 'equal)

This is the core logic for creating the undirected graph. Let's break down the first line:

• (gethash child neighbors '()): We look up the child in our neighbors hash table. If the child doesn't exist as a key yet, gethash returns the default value, which we've specified as an empty list '().
• (pushnew parent ... :test 'equal): This command adds the parent to the list of the child's neighbors, but only if they aren't already present. This prevents duplicate entries. This establishes the child -> parent connection.

The second line does the exact same thing but in reverse, establishing the parent -> child connection. After iterating through all the data, the neighbors hash table is a complete adjacency list representing our family network.

Code Walkthrough: The degree-of-separation Function

This function implements the BFS algorithm to find the shortest path.

Initial Setup and Edge Cases

(when (equal person1 person2) (return-from degree-of-separation 0))

First, a simple edge case: if the two people are the same, their distance is 0. We handle this immediately and exit.

(let ((graph (build-graph family-tree)) ... )

We call our helper function to get the graph. The rest of the logic operates on this graph.

(queue (list (list person1 0)))

We initialize our queue. Instead of just storing the person's name, we store a list containing both the person and their current distance from the start (person1). The starting node is at distance 0 from itself.

(visited (make-hash-table :test 'equal)))

The visited hash table is crucial for preventing infinite loops in cyclic graphs and for ensuring we don't process the same person multiple times. It acts as a set to keep track of nodes we've already added to the queue.

(unless (and (gethash person1 graph) (gethash person2 graph)) ... )

Another important edge case. If either person doesn't exist in the graph, a connection is impossible. We check for their existence as keys in the graph and return nil if they are not found.

The BFS Algorithm Logic

The following ASCII diagram illustrates the core mechanics of the BFS traversal, showing how the queue and visited set evolve.

    ● Start BFS from 'A'
    │
    ├─ Queue:  [['A', 0]]
    └─ Visited: {'A'}
    │
    ▼
  ┌─────────────────┐
  │ Dequeue ['A', 0] │
  │ A's Neighbors: B, C │
  └────────┬────────┘
           │
           ▼
    ● Enqueue Neighbors
    │
    ├─ Queue:  [['B', 1], ['C', 1]]
    └─ Visited: {'A', 'B', 'C'}
    │
    ▼
  ┌─────────────────┐
  │ Dequeue ['B', 1] │
  │ B's Neighbors: A, D │
  │ (A is visited, skip) │
  └────────┬────────┘
           │
           ▼
    ● Enqueue Neighbor 'D'
    │
    ├─ Queue:  [['C', 1], ['D', 2]]
    └─ Visited: {'A', 'B', 'C', 'D'}
    │
    ▼
    ... continues until target is found or queue is empty.

This process is implemented in the main loop of the function.

(loop while queue do ... )

The loop continues as long as there are people in our queue to process.

(let* ((current-path (pop queue)) ... )

We dequeue the first element. In Lisp, using a list as a queue, pop removes and returns the first element. current-path will be a list like ("person-name" 2).

(when (equal current-person person2) (return-from degree-of-separation distance))

This is our success condition. If the person we just dequeued is our target (person2), we have found the shortest path. We return their accumulated distance and the function terminates.

(loop for neighbor in (gethash current-person graph) ... )

If it's not the target, we get all of the current person's neighbors from the graph.

do (unless (gethash neighbor visited) ... )

For each neighbor, we first check if we have visited them before. If we have, we do nothing and move to the next neighbor. This is the step that prevents cycles and redundant work.

(setf (gethash neighbor visited) t)
(setf queue (append queue (list (list neighbor (+ distance 1))))))

If the neighbor is unvisited, we mark them as visited immediately. Then, we enqueue them. Crucially, we enqueue them with a distance that is one greater than the current person's distance. The append function adds the new element to the end of our list, maintaining the queue's First-In-First-Out (FIFO) behavior.

If the loop finishes (the queue becomes empty) and we never found person2, it means they are in a disconnected part of the graph. The function will implicitly return nil, correctly indicating no path exists.

---

Pros and Cons of This Approach

Every technical solution has trade-offs. This implementation is efficient and idiomatic for Common Lisp, but it's worth understanding its characteristics.

Aspect	Pros	Cons
Algorithm (BFS)	Guaranteed to find the shortest path in an unweighted graph. It is both complete and optimal.	Can consume significant memory for graphs that are very "wide" (have nodes with a very high number of connections), as the queue can grow large.
Data Structure (Hash Table)	Provides average O(1) time complexity for lookups, insertions, and deletions, making neighbor access very fast.	Higher memory overhead compared to other structures like arrays. The constant factor for operations can be higher than array indexing.
Queue Implementation (List)	Simple and easy to implement using `pop` and `append`. Very clear and readable.	Using `append` to add to the end of a list is an O(n) operation, where n is the length of the list. For very large queues, this can become a performance bottleneck. A dedicated queue data structure would be more performant.

Potential Optimization: A Better Queue

For most cases, using a list as a queue is perfectly fine. However, in performance-critical applications with massive graphs, the O(n) nature of `append` is suboptimal. A more efficient queue could be implemented using a structure that maintains pointers to both the head and the tail of the list, allowing for O(1) enqueue and dequeue operations.

However, for the scope of the problem in the kodikra Common Lisp learning path, the current implementation is an excellent balance of clarity, simplicity, and sufficient performance.

---

Frequently Asked Questions (FAQ)

Why use Breadth-First Search (BFS) instead of Depth-First Search (DFS)?

BFS explores the graph level by level, guaranteeing that it finds the shortest path in terms of the number of edges for an unweighted graph. DFS, on the other hand, explores as far as possible down one branch before backtracking. It might find a path to the target node, but it's not guaranteed to be the shortest one first.

What does :test 'equal do in make-hash-table and why is it important?

The :test argument specifies the function used to compare keys. The default is eql, which checks if two objects are the same object in memory. Since we are using strings (names) as keys, we need equal, which compares the actual content of the strings. Without :test 'equal', two different string objects with the same characters (e.g., "John" and "John") would be treated as different keys.

How does this solution scale with very large family trees?

The time complexity of BFS is O(V + E), where V is the number of vertices (people) and E is the number of edges (relationships). The space complexity is O(V) to store the `visited` set and the `queue`. This is generally very efficient and scales well for even very large datasets. The main bottleneck, as mentioned, could be the list-based queue for extremely wide graphs.

What happens if the input data contains a cycle (e.g., a person is listed as their own ancestor)?

The BFS algorithm is robust against cycles thanks to the visited hash table. When BFS encounters a node it has already visited, it simply ignores it and does not add it to the queue again. This prevents the algorithm from getting stuck in an infinite loop.

Could this logic be applied to other problems besides family trees?

Absolutely. This exact logic is used in a wide range of applications, such as finding the shortest route in a GPS system (where cities are nodes and roads are edges), analyzing social networks (like LinkedIn or Facebook connections), and determining dependencies in software package management.

What if a person has only one parent listed in the data?

The algorithm handles this perfectly. The graph building process will simply create a connection between the child and that one parent. The graph doesn't require complete data to function; it works with whatever connections are provided.

---

Conclusion: Graphs are Everywhere

You have successfully built the core feature for "Noble Knots," capable of navigating complex family histories with precision. By transforming an abstract problem into a concrete graph data structure, you unlocked a powerful and efficient algorithmic solution: Breadth-First Search.

The key takeaways are profound and applicable across software development. First, choosing the right data structure is half the battle; the graph was a natural fit for our interconnected data. Second, understanding fundamental algorithms like BFS provides a robust toolkit for solving a wide array of pathfinding and connectivity problems. Finally, Common Lisp, with its powerful features like hash tables, destructuring, and the loop macro, provides an expressive and effective environment for implementing such algorithms.

This module from the kodikra.com curriculum demonstrates a practical application of computer science theory, turning a complex requirement into clean, functional, and efficient code.

Disclaimer: The code in this article is written for clarity based on modern Common Lisp standards (ANSI Common Lisp). Performance and specific syntax may vary slightly between different implementations like SBCL, CCL, or LispWorks, but the core logic remains universal.

Ready to tackle the next challenge? Continue your journey in the kodikra Common Lisp learning path or explore more advanced Common Lisp concepts on our platform.

---

Published by Kodikra — Your trusted Common-lisp learning resource.