Router Network Simulation & Routing Engine

This project demonstrates the design and implementation of a router network simulator with path-finding algorithms in Python. It emphasizes algorithmic reasoning, data structure design, and software architecture, providing both unoptimized and optimized implementations for comparative analysis.

---

Table of Contents

• Project Overview
• Key Features
• Data Structures & Algorithms
• Implementation Versions
• Usage
• Sample Output
• Refactoring & Analysis
• Skills Demonstrated

---

Project Overview

The project simulates a network of routers connected by weighted links (latency/cost). It allows:

• Adding routers and links
• Generating synthetic router networks (sparse and dense)
• Finding shortest paths using BFS (unweighted) and Dijkstra (weighted)
• analyzing algorithmic trade-offs
• Comparing unoptimized procedural code vs. modular, optimized implementations

This project is designed for research assistant / industry skill demonstration.

---

Key Features

• Network Generator: Create random router networks with configurable density and weight ranges.
• Path-Finding Algorithms:
  • BFS (unweighted shortest path)
  • Dijkstra (heap-based, weighted shortest path)
  • Naive Dijkstra (for comparative analysis)
• Graph Data Structures: Implemented from scratch:
  • DynamicArray (resizable array)
  • HashTable (separate chaining)
  • MinHeap (priority queue)
  • Graph (adjacency list using custom structures)
• Refactoring Demonstration: Includes unoptimized procedural version and fully modular, object-oriented engine.

---

Data Structures & Algorithms

Component	Description	Purpose
DynamicArray	Resizable array	Stores nodes, edges, and traversal queues
HashTable	Custom hash table with separate chaining	Efficient key-value mapping for graph adjacency and distances
MinHeap	Binary heap for priority queue	Optimized Dijkstra performance
Graph	Adjacency list graph	Stores routers and weighted links
BFS	Unweighted shortest path	O(V + E), simple traversal
Dijkstra (Heap)	Weighted shortest path	O(E log V), optimized routing
Dijkstra (Naive)	Weighted path baseline	O(V² + VE), for trade-off demonstration

---

Implementation Versions

1. Unoptimized / Procedural Version

   • Global lists for routers and links
   • Naive Dijkstra scanning all nodes and edges
   • O(V³) worst-case complexity
   • Poor separation of concerns, tight coupling

2. Fully Optimized / Modular RoutingEngine

   • Encapsulates graph and routing logic in a class
   • Modular, testable, and reusable
   • Clean separation of concerns
   • Algorithmically and memory optimized

---

Usage

Generate Network and Find Best Path

from src.network_generator import generate_router_network
from algorithms.dijkstra import dijkstra_heap
from data_structures.graph import Graph
from utils.display import print_graph, print_path

# Generate random network
graph = generate_router_network(num_routers=10, density=0.4, directed=False)

# Print network
print_graph(graph)

# Find best path between two routers
start, target = "R0", "R5"
path = dijkstra_heap(graph, start, target)

# Print best path
print_path(path)

Sample Output

Generated Router Network:
Router: R0
  -> R1 (weight=5)
  -> R3 (weight=10)
Router: R1
  -> R2 (weight=3)
  -> R0 (weight=5)
...

Finding best route from R0 to R5...
Best path: R0 -> R3 -> R5, Total weight: 15

Refactoring & Analysis

• Before: Procedural, tightly coupled code with global lists, O(V³) complexity, redundant data structures.

• After: Modular RoutingEngine class, optimized data structures, heap-based Dijkstra (O(E log V)), single source of truth for graph, testable, reusable.

• Benefits:

  • Reduced computational complexity

  • Improved memory efficiency

  • Clear separation of concerns

  • Lifecycle and state management controlled

Skills Demonstrated

• Algorithmic Reasoning: BFS, Dijkstra, complexity trade-offs

• Data Structures Mastery: Custom DynamicArray, HashTable, MinHeap, Graph

• Code Refactoring: Modularization, separation of concerns, object lifecycle reasoning

• Memory & Performance Analysis: Sparse vs dense network, adjacency list efficiency

• Industry-Level Software Design: Clean abstractions, benchmarking, testable architecture