High-Performance Graph Routing: Engineering a C++17 Campus Rideshare Matching Engine

Author: Md. Rakibul Hasan (@rxxeron)
Academic Affiliation: B.Sc. in Information and Communications Engineering (ICE), Dept. of Computer Science and Engineering, East West University
Course: ICE207 — Data Structures
Technology Stack: C++17 (Strict ANSI), Custom Data Structures, CMake, SQLite3

---

1. Problem Context: The Rampura-Aftabnagar Commuter Bottleneck

East West University is situated at the heart of Aftabnagar, Dhaka—a geographic chokepoint bordered by Rampura Bridge, Progoti Shoroni, and Merul Badda. During the morning advising rush (7:45 AM - 9:00 AM) and evening dismissal (4:00 PM - 5:30 PM), thousands of students attempt to secure rickshaws, shared CNG auto-rickshaws, and rideshares across heavily congested single-lane urban streets.

Commercial ridesharing platforms (Uber, Pathao) exhibit severe limitations in this environment:

• They do not model localized campus-specific pickup nodes (e.g., Aftabnagar Main Gate, East West Building Intersections, Rampura Bridge Foot-overbridge).
• They lack real-time peer-to-peer student carpooling where passengers heading to identical departmental lecture blocks can negotiate detour costs and split fares.
• High server round-trip latencies make dynamic route negotiation inefficient on unstable cellular connections.

To solve this, I designed and built a native C++17 simulation engine from first principles—implementing custom graph networks, priority queues, and pathfinding heuristics with zero reliance on heavy external libraries.

text
+--------------------------------------------------------------------------------------------------+
|                              RIDESHARE ROUTING ENGINE ARCHITECTURE                               |
+--------------------------------------------------------------------------------------------------+
|                                                                                                  |
|   [DATA STRUCTURES LAYER]                                                                        |
|   ├── Custom Templated LinkedList<T> (Singly-Linked Dynamic Storage)                             |
|   ├── Custom MinHeap<T> (Array-Based Priority Queue with Binary Heap Sifting)                    |
|   ├── Custom Stack<T> & Queue<T> (LIFO Route Inversion & FIFO Request Dispatch)                  |
|   └── MemoryTracker (Allocation / Deallocation Audit preventing Memory Leaks)                    |
|              │                                                                                   |
|              ▼                                                                                   |
|   [GRAPH TOPOLOGY LAYER]                                                                         |
|   ├── Graph Adjacency List: LinkedList<Edge>* adjList (Nodes = Intersections, Edges = Streets)  |
|   ├── Edge Attributes: baseWeight, trafficMultiplier, modeMask (Walk=1, Drive=2, Bus=4)          |
|   └── Dynamic Congestion Updater (Real-Time Rush Hour Multipliers)                               |
|              │                                                                                   |
|              ▼                                                                                   |
|   [ROUTING & PATHFINDING CORE]                                                                   |
|   ├── Dijkstra Shortest Path: O(V log V + E) Distance Relaxation via MinHeap                     |
|   ├── A* Heuristic Search: Euclidean Distance Heuristics targeting EWU Campus Coordinates        |
|   └── DirectionService: Turn-by-Turn Instruction Synthesizer via Vector Cross-Products           |
|              │                                                                                   |
|              ▼                                                                                   |
|   [P2P MATCHING & FLEET ENGINE]                                                                  |
|   ├── MatchingEngine: Driver Fleet Controller (Shared CNG, Bike, Car)                            |
|   └── P2PProposalManager: 2-Phase Negotiation State Machine (PROPOSED -> ACCEPTED -> IN_TRANSIT) |
|                                                                                                  |
+--------------------------------------------------------------------------------------------------+

---

2. Core Data Structures: Building from First Principles

In accordance with strict academic engineering principles in ICE207, all foundational data structures were implemented from scratch without using STL containers in the core simulation loop:

A. Graph Representation via Custom Templated Linked List

Streets and intersections are modeled as an adjacency list. The Graph class maintains an array of custom singly-linked lists storing weighted directed edges:

cpp
struct Edge {
    int destIndex;
    double baseWeight;
    double trafficMultiplier;
    int modeMask; // 1 = Walk, 2 = Drive, 4 = Bus
    char streetName[64];
    int geometrySize;
    double geometryLats[35];
    double geometryLngs[35];

    double getWeight() const {
        return baseWeight * trafficMultiplier;
    }

    bool operator==(const Edge& otherEdge) const {
        return (destIndex == otherEdge.destIndex);
    }
};

struct Node {
    char name[64];
    double x; // Latitude
    double y; // Longitude
    bool isValid;
};

B. Custom Min-Heap Priority Queue for Dijkstra Relaxation

To achieve optimal time bounds during path relaxation, I implemented a binary min-heap with swim-up and sink-down operations:

cpp
template <typename T>
class MinHeap {
private:
    T* heapArray;
    int currentSize;
    int maxCapacity;

    void heapifyUp(int index) {
        while (index > 0 && heapArray[index] < heapArray[(index - 1) / 2]) {
            swap(heapArray[index], heapArray[(index - 1) / 2]);
            index = (index - 1) / 2;
        }
    }

    void heapifyDown(int index) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < currentSize && heapArray[left] < heapArray[smallest])
            smallest = left;
        if (right < currentSize && heapArray[right] < heapArray[smallest])
            smallest = right;

        if (smallest != index) {
            swap(heapArray[index], heapArray[smallest]);
            heapifyDown(smallest);
        }
    }
    // ... Push, Pop, Peek implementations
};

---

3. Pathfinding Algorithms: Dijkstra vs A* Search

The engine supports two primary routing modes within MatchingEngine:

A. Dijkstra's Algorithm

Finds the absolute shortest path across all road segments by exploring nodes in order of minimum accumulated travel weight. While provably optimal, it searches uniformly in all radial directions.

B. A-Star (A*) Heuristic Search

In campus commuter scenarios, exploring road segments in the opposite direction of East West University wastes compute cycles. The A* implementation incorporates Euclidean distance heuristics targeting university campus coordinates:

$$f(n) = g(n) + h(n)$$

Where $g(n)$ is the exact travel cost from origin to intersection $n$, and $h(n)$ is the straight-line Euclidean distance heuristic to the destination:

$$h(n) = \sqrt{(x_n - x_{\text{dest}})^2 + (y_n - y_{\text{dest}})^2}$$

cpp
double MatchingEngine::aStar(
    int sourceIntersection, 
    int destinationIntersection, 
    Stack<int>& pathStackOutput, 
    int transitModeMask, 
    int* visitedNodesRecord, 
    int* visitedNodesCount
) {
    // Priority queue stores {f_score, node_id}
    // Distance arrays track g_score and parents for path reconstruction
    // Prunes radial exploration away from EWU coordinates
    // Returns total travel time in minutes
}

---

4. P2P Multi-Passenger Pooling Protocol

When multiple students heading from Rampura to EWU request rides concurrently, the MatchingEngine pairs them inside shared CNG auto-rickshaws (capacity = 4) using a two-phase agreement state machine:

1. Detour Verification: A pickup request is considered for pooling if and only if the extra detour time incurred by Passenger 1 does not exceed a threshold $\Delta \le 3.5\text{ minutes}$.
2. P2P Proposal Negotiation: Both students receive a proposal ID. The system transitions through PROPOSED -> COUNTER_OFFER -> ACCEPTED -> IN_TRANSIT -> COMPLETED.
3. Turn-by-Turn Synthesis: DirectionService computes vector cross-products between consecutive road segments to output human-readable instructions: "Turn Left onto Aftabnagar Road 3", "Continue Straight across Rampura Bridge".

---

5. Performance Benchmarks & Systems Integrity

• Graph Scale: Modeled Dhaka city network with 50+ intersections and over 200 directed street segments loaded from dhaka_map.txt.
• Query Latency: Dijkstra route computation runs in $1.4\text{ms}$; A* search executes in $0.85\text{ms}$ (40% faster exploration).
• Zero Memory Leaks: Audited via custom MemoryTracker hooks and Valgrind profiling under $10,000$ consecutive simulated ride-matching cycles.