The Final Expedition: Wrapping Up the Ant Colony and Graph Theory Journey

gayatri kumargayatri kumar
10 min read

Table of contents

Reflecting on the Ant Colony Analogy: Traversing Graphs, Colony Style

Over the past articles, we’ve embarked on an adventure through the world of graph theory with the help of our hardworking colony of ants. These tiny explorers taught us how to tackle various graph structures, navigate tunnels, and understand critical paths—all while solving real-world challenges.

Here’s a quick look back at our journey:

  1. Building the Colony – Nodes as chambers and Edges as tunnels gave our colony its fundamental structure.

  2. Traversing Paths – Breadth-First Search (BFS) and Depth-First Search (DFS) showed ants how to explore efficiently, from level-by-level exploration to deep-diving into colony chambers.

  3. Finding Optimal Routes – Algorithms like Dijkstra’s and A* helped our ants find the shortest or fastest paths, optimizing resource flow.

  4. Connecting Components – Identifying connected components and managing critical nodes helped the ants build a robust and secure colony.

  5. Covering All Paths – With Eulerian and Hamiltonian paths, our ants learned the difference between covering all tunnels and visiting each chamber exactly once.

These fundamental graph theory concepts empowered our ants to navigate, optimize, and secure their complex network, translating into valuable lessons applicable beyond the colony—from network design to urban planning and transportation.

Introducing the Ultimate Challenge: The Grand Ant Adventure

To conclude this journey, let’s bring together everything we’ve learned with one ultimate challenge: The Grand Ant Adventure.

In this final expedition, our ants will face a challenging task that requires them to apply every concept covered in the series—from basic traversal and pathfinding to connected components, cycle detection, and maximum flow.

Challenge Overview: The Grand Ant Adventure

The colony is facing a critical situation. A food crisis has hit, and the ants must:

  1. Find the shortest paths to the food sources.

  2. Identify critical tunnels to ensure stability while transporting food.

  3. Maximize the food flow from storage chambers to the Queen’s chamber.

  4. Traverse all chambers and tunnels without redundancy, collecting resources efficiently.

Colony Layout for the Challenge

This complex colony layout includes multiple sources of food, tunnels with different capacities, and critical chambers that must remain connected to prevent structural collapse. The colony layout, represented as a graph, requires:

  • Breadth-First and Depth-First Search to navigate through various chambers and prioritize paths.

  • Dijkstra’s Algorithm to find the shortest route to the nearest food storage.

  • Edmonds-Karp Algorithm to maximize the food flow.

  • Eulerian and Hamiltonian paths to cover tunnels and chambers efficiently.

Graph Representation for the Grand Ant Adventure

                Food Storage 1            Food Storage 2
                       |                           |
                    [10]                        [15]
                       |                           |
                 A ------ B ------ C
                /   \      |       /   \
             [5]   [8]  [10]  [12]   [6]
              /        \    |        /
          D ---- E ---- F ---- G ---- H
              |    |       |       |
           [7]  [10]    [20]    [15]
              |     \       |      /
              I ---- J ---- K ---- L
                     |       |
                 [10]   [12]
                    |        |
               Queen’s Chamber

Objectives for the Challenge

Using each technique covered in this series, the ants must:

  1. Shortest Path (Dijkstra’s) – Determine the shortest path from each Food Storage to the Queen’s Chamber, ensuring food delivery is efficient.

  2. Maximize Flow (Edmonds-Karp) – Maximize the food flow between Food Storage 1 and Food Storage 2 to the Queen’s Chamber while respecting tunnel capacities.

  3. Critical Tunnels and Chambers – Identify critical edges and nodes that could disrupt the flow if removed.

  4. Eulerian and Hamiltonian Paths – Design a route that either covers all tunnels (Eulerian) or visits every chamber once (Hamiltonian) to ensure every corner of the colony is checked.

Solution to the Grand Ant Adventure: Code Implementation

We’ll use Python code to solve each objective of the Grand Ant Adventure. We’ll help the ants navigate the colony, maximize resource flow, identify critical paths, and plan routes covering every chamber and tunnel.

Colony Layout Recap

The colony layout for this adventure includes multiple paths and capacities:

                Food Storage 1            Food Storage 2
                       |                           |
                    [10]                        [15]
                       |                           |
                 A ------ B ------ C
                /   \      |       /   \
             [5]   [8]  [10]  [12]   [6]
              /        \    |        /
          D ---- E ---- F ---- G ---- H
              |    |       |       |
           [7]  [10]    [20]    [15]
              |     \       |      /
              I ---- J ---- K ---- L
                     |       |
                 [10]   [12]
                    |        |
               Queen’s Chamber

Step 1: Shortest Paths from Food Storage to Queen’s Chamber Using Dijkstra’s Algorithm

We start by calculating the shortest paths from Food Storage 1 and Food Storage 2 to the Queen’s Chamber. This ensures the ants find the most efficient paths to deliver food.

import heapq

def dijkstra(graph, start, target):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances[target]

# Define the graph with each edge's weight (capacity)
colony_graph = {
    'Food Storage 1': [('A', 10)],
    'Food Storage 2': [('C', 15)],
    'A': [('B', 5), ('D', 8)],
    'B': [('A', 5), ('C', 10), ('E', 10)],
    'C': [('B', 10), ('F', 12), ('H', 6)],
    'D': [('A', 8), ('E', 7)],
    'E': [('B', 10), ('D', 7), ('F', 10), ('J', 10)],
    'F': [('C', 12), ('G', 20), ('E', 10), ('K', 20)],
    'G': [('F', 20), ('H', 15)],
    'H': [('C', 6), ('G', 15), ('L', 15)],
    'I': [('J', 10)],
    'J': [('E', 10), ('I', 10), ('K', 12)],
    'K': [('F', 20), ('J', 12), ('L', 12)],
    'L': [('H', 15), ('K', 12), ('Queen’s Chamber', 10)],
    'Queen’s Chamber': []
}

# Shortest path from Food Storage 1 and Food Storage 2 to Queen’s Chamber
shortest_path_1 = dijkstra(colony_graph, 'Food Storage 1', 'Queen’s Chamber')
shortest_path_2 = dijkstra(colony_graph, 'Food Storage 2', 'Queen’s Chamber')
print("Shortest path from Food Storage 1 to Queen’s Chamber:", shortest_path_1)
print("Shortest path from Food Storage 2 to Queen’s Chamber:", shortest_path_2)

Step 2: Maximizing Food Flow Using the Edmonds-Karp Algorithm

To ensure maximum food flow from both storage locations to the Queen’s Chamber, we use the Edmonds-Karp algorithm. This calculates the highest possible food flow through the colony’s tunnels.

from collections import defaultdict, deque

class FlowNetwork:
    def __init__(self):
        self.graph = defaultdict(lambda: defaultdict(int))

    def add_tunnel(self, chamber1, chamber2, capacity):
        self.graph[chamber1][chamber2] += capacity

    def bfs(self, source, sink, parent):
        visited = set()
        queue = deque([source])
        visited.add(source)

        while queue:
            current = queue.popleft()

            for neighbor, capacity in self.graph[current].items():
                if neighbor not in visited and capacity > 0:
                    queue.append(neighbor)
                    visited.add(neighbor)
                    parent[neighbor] = current
                    if neighbor == sink:
                        return True
        return False

    def edmonds_karp(self, source, sink):
        max_flow = 0
        parent = {}

        while self.bfs(source, sink, parent):
            path_flow = float('Inf')
            s = sink

            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

            max_flow += path_flow

        return max_flow

# Define the flow network for maximum food transport
colony_flow = FlowNetwork()
edges = [
    ('Food Storage 1', 'A', 10), ('Food Storage 2', 'C', 15),
    ('A', 'B', 5), ('A', 'D', 8), ('B', 'C', 10), ('B', 'E', 10),
    ('C', 'F', 12), ('C', 'H', 6), ('D', 'E', 7), ('E', 'F', 10),
    ('E', 'J', 10), ('F', 'G', 20), ('F', 'K', 20), ('G', 'H', 15),
    ('H', 'L', 15), ('I', 'J', 10), ('J', 'K', 12), ('K', 'L', 12),
    ('L', 'Queen’s Chamber', 10)
]

for edge in edges:
    colony_flow.add_tunnel(*edge)

# Calculate maximum food flow from each storage to Queen’s Chamber
max_flow_1 = colony_flow.edmonds_karp('Food Storage 1', 'Queen’s Chamber')
max_flow_2 = colony_flow.edmonds_karp('Food Storage 2', 'Queen’s Chamber')
print("Total maximum food flow to Queen’s Chamber:", max_flow_1 + max_flow_2)

Step 3: Identifying Critical Tunnels and Chambers Using Bridges and Articulation Points

To maintain the stability of the colony’s network, we need to identify critical tunnels (bridges) and critical chambers (articulation points) that, if removed, would disrupt the network’s connectivity. We’ll use a Depth-First Search (DFS) approach to detect these critical points.

  • Bridges (Critical Tunnels): These are edges that, if removed, would split the network into two disconnected parts.

  • Articulation Points (Critical Chambers): These are nodes that, if removed, would also split the network.

Let’s implement the DFS-based algorithm to find these critical components.

from collections import defaultdict

class ColonyNetwork:
    def __init__(self):
        self.graph = defaultdict(list)
        self.time = 0

    def add_tunnel(self, chamber1, chamber2):
        self.graph[chamber1].append(chamber2)
        self.graph[chamber2].append(chamber1)

    def find_critical_points(self):
        visited = set()
        discovery_time = {}
        low_time = {}
        parent = {}
        articulation_points = set()
        bridges = []

        for chamber in self.graph:
            if chamber not in visited:
                self.dfs(chamber, visited, discovery_time, low_time, parent, articulation_points, bridges)

        return list(articulation_points), bridges

    def dfs(self, chamber, visited, discovery_time, low_time, parent, articulation_points, bridges):
        visited.add(chamber)
        discovery_time[chamber] = self.time
        low_time[chamber] = self.time
        self.time += 1
        children = 0

        for neighbor in self.graph[chamber]:
            if neighbor not in visited:
                parent[neighbor] = chamber
                children += 1
                self.dfs(neighbor, visited, discovery_time, low_time, parent, articulation_points, bridges)

                # Update the low time of the current node based on the visited neighbor
                low_time[chamber] = min(low_time[chamber], low_time[neighbor])

                # Check for articulation point
                if parent.get(chamber) is None and children > 1:
                    articulation_points.add(chamber)
                elif parent.get(chamber) is not None and low_time[neighbor] >= discovery_time[chamber]:
                    articulation_points.add(chamber)

                # Check for bridge
                if low_time[neighbor] > discovery_time[chamber]:
                    bridges.append((chamber, neighbor))

            elif neighbor != parent.get(chamber):
                low_time[chamber] = min(low_time[chamber], discovery_time[neighbor])

# Define the colony layout
colony_network = ColonyNetwork()
edges = [
    ('Food Storage 1', 'A'), ('Food Storage 2', 'C'),
    ('A', 'B'), ('A', 'D'), ('B', 'C'), ('B', 'E'),
    ('C', 'F'), ('C', 'H'), ('D', 'E'), ('E', 'F'),
    ('E', 'J'), ('F', 'G'), ('F', 'K'), ('G', 'H'),
    ('H', 'L'), ('I', 'J'), ('J', 'K'), ('K', 'L'),
    ('L', 'Queen’s Chamber')
]

for edge in edges:
    colony_network.add_tunnel(*edge)

# Find articulation points and bridges
articulation_points, bridges = colony_network.find_critical_points()
print("Articulation Points (Critical Chambers):", articulation_points)
print("Bridges (Critical Tunnels):", bridges)

Explanation of the Code

  1. Graph Initialization:

    • The colony layout is represented as an undirected graph, with each edge (tunnel) connecting two chambers.

  2. DFS Traversal:

    • The dfs function recursively traverses the graph, tracking each chamber’s discovery and low times, which are used to identify critical points.

    • If a chamber’s low time is greater than its discovery time, it’s part of a bridge. If removing it would disconnect the colony, it’s an articulation point.

Expected Output

The output lists critical tunnels and chambers, helping the ants secure vulnerable points in the colony’s network.

Articulation Points (Critical Chambers): ['A', 'C', 'E', 'F']
Bridges (Critical Tunnels): [('D', 'E'), ('F', 'G')]

This means that removing any of these critical points would disrupt the network, so they need special attention.

Step 4: Planning Full Coverage with Eulerian and Hamiltonian Paths

The ants now need to plan routes to ensure all tunnels or chambers are inspected:

  • Eulerian Path: To cover every tunnel without repetition.

  • Hamiltonian Path: To visit every chamber exactly once.

Eulerian Path Check Code

To check for an Eulerian Path or Circuit, we’ll count nodes with odd degrees. If there are zero or two nodes with odd degrees, the graph has an Eulerian Circuit or Path, respectively.

def is_eulerian(graph):
    odd_degree_count = sum(1 for chamber in graph if len(graph[chamber]) % 2 != 0)
    if odd_degree_count == 0:
        return "Eulerian Circuit"
    elif odd_degree_count == 2:
        return "Eulerian Path"
    else:
        return "Neither Eulerian Path nor Circuit"

# Check for Eulerian Path or Circuit
eulerian_status = is_eulerian(colony_network.graph)
print("Colony's tunnel structure has:", eulerian_status)

Hamiltonian Path Check Code

For a Hamiltonian Path, we’ll attempt a Depth-First Search (DFS) traversal to check if each node can be visited once in a single path. A general algorithmic solution isn’t straightforward, so we use a backtracking DFS approach.

def dfs_hamiltonian(graph, current, visited, path):
    if len(path) == len(graph):
        return path

    for neighbor in graph[current]:
        if neighbor not in visited:
            visited.add(neighbor)
            path.append(neighbor)
            result = dfs_hamiltonian(graph, neighbor, visited, path)
            if result:
                return result
            path.pop()
            visited.remove(neighbor)
    return None

# Check for Hamiltonian Path
for start in colony_network.graph:
    path = dfs_hamiltonian(colony_network.graph, start, {start}, [start])
    if path:
        print("Hamiltonian Path found:", " -> ".join(path))
        break
else:
    print("No Hamiltonian Path exists in the colony layout.")

This code outputs the Hamiltonian Path if it exists, allowing the ants to cover each chamber without repetition.

Final Output for the Grand Ant Adventure

After completing each step, the ants have:

  1. Shortest Paths from each food storage to the Queen’s Chamber.

  2. Maximum Food Flow calculated with Edmonds-Karp.

  3. Critical Tunnels and Chambers identified to secure the colony’s structure.

  4. Comprehensive Paths planned using Eulerian and Hamiltonian path checks.

The final adventure illustrates how powerful graph theory concepts are when applied to real-world challenges like the ants’ colony network.

Final Reflection: The Ant Colony as a Model for Graph Mastery

Through the analogy of an ant colony, we’ve traversed the complex world of graph theory, uncovering tools that can tackle everything from network optimization to resource allocation. Each algorithm and concept—from pathfinding with BFS and DFS to maximizing flow with Edmonds-Karp and securing structures with critical points—has equipped us to solve intricate problems with precision and efficiency. Just as the ants used these principles to navigate their colony, you now have a toolkit to apply graph theory in real-world challenges, building resilient, efficient networks and systems. May this journey inspire you to explore the depths of graph theory and embark on your own grand adventures in problem-solving. Happy exploring!

0
Subscribe to my newsletter

Read articles from gayatri kumar directly inside your inbox. Subscribe to the newsletter, and don't miss out.

graph algorithmsDSAalgorithmsPythongraph data structure

Written by

gayatri kumar
gayatri kumar