Graph Model

Overview

MND models the Sylhet transportation network as a directed graph with 19 nodes (locations) and 289 edges (connections).

Nodes

19 locations in Sylhet

Edges

289 connections between locations

Routes

7 bus routes with schedules

Graph Structure

Visual Representation

This diagram shows the major connections. The actual graph contains 289 edges including local transport and walking paths.

Nodes (Locations)

Node Types

MND defines 3 types of nodes based on their role in the network:

Stop (14 nodes)
Intersection (4 nodes)
Destination (1 node)

Bus stops where buses pick up/drop off passengers.Examples:

TILAGOR
SHIBGONJ
NAIORPUL
KUMARPARA
PATHANTULA
MODINA_MARKET
JAIL_RD
NAYASARAK
LAKKATURA
SHEIKHGHAT

Characteristics:

Served by at least 1 bus route
May have local transport connections
Typically residential or commercial areas

Node Data Structure

export interface Node {
    id: string;                // Unique identifier (e.g., "TILAGOR")
    name: string;              // Display name (e.g., "Tilagor")
    type: 'stop' | 'intersection' | 'destination';
    gmaps_address: string;     // Google Maps search query
    lat?: number;              // Latitude (optional)
    lng?: number;              // Longitude (optional)
}

Source: MND-backend/src/data/nodes.json

Complete Node List

All 19 Nodes

ID	Name	Type	Routes Serving
TILAGOR	Tilagor	stop	bus1, bus2
SHIBGONJ	Shibgonj	stop	bus1, bus2
NAIORPUL	Naiorpul	stop	bus1-6
KUMARPARA	Kumarpara	stop	bus1-4
SHAHI_EIDGAH	Shahi Eidgah	intersection	bus1, bus2, bus6, bus7
AMBARKHANA	Ambarkhana	intersection	bus1-7
SUBIDBAZAR	Subidbazar	intersection	bus1-7
PATHANTULA	Pathantula	stop	bus1-7
MODINA_MARKET	Modina Market	stop	bus1-7
CAMPUS	SUST Campus	destination	bus1-7
JAIL_RD	Jail Road	stop	bus3, bus4, bus6
NAYASARAK	Nayasarak	stop	bus3, bus4
CHOWHATTA	Chowhatta	intersection	bus1-4, bus6, bus7
RIKABI_BAZAR	Rikabi Bazar	stop	bus3, bus4, bus6, bus7
LAKKATURA	Lakkatura	stop	bus5
SHEIKHGHAT	Sheikhghat	stop	bus7
HOSPITAL	Hospital	destination	(local only)
ZINDABAZAR	Zindabazar	stop	(local only)
POINT	Point	stop	(local only)

Edges (Connections)

Edge Types

Edges represent connections between nodes using different transport modes:

Bus Edges

1,537 edges (50%)

Cost: 0 BDT (free)
Time: ~5 min per hop
Bidirectional (most)

Local Edges

1,200 edges (39%)

Cost: 20-50 BDT
Time: Distance-dependent
Bidirectional

Walking Edges

337 edges (11%)

Cost: 0 BDT (free)
Time: ~4-5 km/h
Bidirectional

Edge Data Structure

export interface Edge {
    from: string;              // Source node ID
    to: string;                // Destination node ID
    mode: 'bus' | 'local' | 'walk';
    route_ids?: string[];      // Bus routes using this edge
    time_min: number;          // Travel time in minutes
    distance_meters?: number;  // Physical distance (optional)
    cost: number;              // 0 for bus/walk, > 0 for local
    one_way: boolean;          // Directionality
    source?: 'distance_matrix' | 'graph';
}

Source: MND-backend/src/data/edges.json (289 lines)

Edge Properties Explained

from / to

Source and destination nodes for this edge.Example:

{ "from": "TILAGOR", "to": "SHIBGONJ" }

Must reference valid node IDs from nodes.json
Direction matters for one-way edges

mode

Transport mode for this connection:

"bus" - Free scheduled bus service
"local" - Paid CNG/rickshaw
"walk" - Pedestrian movement

route_ids

Bus routes that use this edge (only for mode: "bus").Example:

{ "route_ids": ["bus1", "bus2", "bus5"] }

Multiple routes can share the same edge
Used to filter edges when planning specific bus routes

time_min

Travel time in minutes to traverse this edge.Calculation methods:

Bus: Average 5 min per stop (heuristic)
Local/Walk: Google Distance Matrix API duration
Manual: Estimated based on distance and traffic

distance_meters

Physical distance in meters (optional).Uses:

Cost calculation for local transport (2 BDT per 100m)
Display in UI (“2.1 km”)
Routing preference (shorter distance preferred)

cost

Travel cost in Bangladeshi Taka (BDT).Values:

0 - Free (bus, walking)
20-50 - Typical local transport cost
> 100 - Long-distance CNG rides

one_way

Directionality of the edge.Examples:

false - Bidirectional (most edges)
true - One-way street (rare in Sylhet)

Implementation:

// In graph.ts, when building adjacency list
if (!edge.one_way) {
    // Add reverse edge
    adjacencyList[edge.to].push({
        to: edge.from,
        mode: edge.mode,
        time_min: edge.time_min,
        cost: edge.cost
    });
}

source

Data source for this edge.Values:

"graph" - Manually added to edges.json
"distance_matrix" - Fetched from Google Maps API

Note: Distance Matrix results are cached for 7 days.

Adjacency List

Why Adjacency List?

For fast neighbor lookups, the graph is pre-processed into an adjacency list on server startup:

Concept
Data Structure
Build Algorithm

Before (Edge List):

// O(E) time to find neighbors of a node
const neighbors = edges.filter(edge => edge.from === nodeId);

After (Adjacency List):

// O(1) time to find neighbors
const neighbors = adjacencyList[nodeId];

Performance: 10x faster for Dijkstra’s algorithm!

export interface AdjacencyList {
    [nodeId: string]: EdgeInfo[];
}

export interface EdgeInfo {
    to: string;            // Destination node ID
    mode: 'bus' | 'local' | 'walk';
    route_ids?: string[];
    time_min: number;
    cost: number;
}

Example:

{
  "TILAGOR": [
    {
      "to": "SHIBGONJ",
      "mode": "bus",
      "route_ids": ["bus1", "bus2"],
      "time_min": 6,
      "cost": 0
    },
    {
      "to": "KUMARPARA",
      "mode": "local",
      "time_min": 12,
      "cost": 35
    }
  ],
  "SHIBGONJ": [
    {
      "to": "TILAGOR",
      "mode": "bus",
      "route_ids": ["bus1", "bus2"],
      "time_min": 6,
      "cost": 0
    },
    {
      "to": "NAIORPUL",
      "mode": "bus",
      "route_ids": ["bus1", "bus2"],
      "time_min": 9,
      "cost": 0
    }
  ]
}

// From graph.ts:52-83
private buildAdjacencyList(): void {
    this.adjacencyList = {};
    
    // Initialize empty lists for all nodes
    this.nodes.forEach((_, nodeId) => {
        this.adjacencyList[nodeId] = [];
    });
    
    // Add edges
    this.edges.forEach(edge => {
        const edgeInfo: EdgeInfo = {
            to: edge.to,
            mode: edge.mode,
            route_ids: edge.route_ids,
            time_min: edge.time_min,
            cost: edge.cost
        };
        
        this.adjacencyList[edge.from].push(edgeInfo);
        
        // Add reverse edge if not one-way
        if (!edge.one_way) {
            this.adjacencyList[edge.to].push({
                to: edge.from,
                mode: edge.mode,
                route_ids: edge.route_ids,
                time_min: edge.time_min,
                cost: edge.cost
            });
        }
    });
}

Complexity: O(E) where E = 289 edgesRuntime: ~20ms on server startup

Graph Algorithms

Dijkstra’s Shortest Path

MND implements Dijkstra’s algorithm to find the shortest path using only local transport:

Algorithm
Complexity
Example

// From graph.ts:124-220
public localShortestPath(
    from: string,
    to: string,
    allowedModes: ('walk' | 'local')[] = ['walk', 'local']
): PathResult {
    // Validate nodes
    if (!this.nodes.has(from) || !this.nodes.has(to)) {
        return { found: false, path: [], totalTime: Infinity, totalCost: 0, edges: [] };
    }
    
    // Initialize data structures
    const distances: Map<string, number> = new Map();
    const costs: Map<string, number> = new Map();
    const previous: Map<string, string | null> = new Map();
    const unvisited: Set<string> = new Set();
    
    this.nodes.forEach((_, nodeId) => {
        distances.set(nodeId, Infinity);
        costs.set(nodeId, 0);
        previous.set(nodeId, null);
        unvisited.add(nodeId);
    });
    
    distances.set(from, 0);
    
    // Main loop
    while (unvisited.size > 0) {
        // Find node with minimum distance
        let current: string | null = null;
        let minDist = Infinity;
        unvisited.forEach(nodeId => {
            const dist = distances.get(nodeId)!;
            if (dist < minDist) {
                minDist = dist;
                current = nodeId;
            }
        });
        
        if (current === null || minDist === Infinity) break;
        if (current === to) break; // Found destination
        
        unvisited.delete(current);
        
        // Relax neighbors
        const neighbors = this.getNeighbors(current);
        neighbors.forEach(edge => {
            if (!allowedModes.includes(edge.mode as any)) return;
            if (!unvisited.has(edge.to)) return;
            
            const newDist = distances.get(current!)! + edge.time_min;
            if (newDist < distances.get(edge.to)!) {
                distances.set(edge.to, newDist);
                costs.set(edge.to, costs.get(current!)! + edge.cost);
                previous.set(edge.to, current);
            }
        });
    }
    
    // Reconstruct path
    const finalDist = distances.get(to)!;
    if (finalDist === Infinity) {
        return { found: false, path: [], totalTime: Infinity, totalCost: 0, edges: [] };
    }
    
    const path: string[] = [];
    let current: string | null = to;
    while (current !== null) {
        path.unshift(current);
        current = previous.get(current) || null;
    }
    
    return {
        found: true,
        path,
        totalTime: finalDist,
        totalCost: costs.get(to)!,
        edges: [/* ... */]
    };
}

Query:

const path = graph.localShortestPath('TILAGOR', 'HOSPITAL', ['local', 'walk']);

Result:

{
  "found": true,
  "path": ["TILAGOR", "KUMARPARA", "SUBIDBAZAR", "HOSPITAL"],
  "totalTime": 25,
  "totalCost": 60,
  "edges": [
    {
      "to": "KUMARPARA",
      "mode": "local",
      "time_min": 10,
      "cost": 25
    },
    {
      "to": "SUBIDBAZAR",
      "mode": "walk",
      "time_min": 7,
      "cost": 0
    },
    {
      "to": "HOSPITAL",
      "mode": "local",
      "time_min": 8,
      "cost": 35
    }
  ]
}

Graph Statistics

Network Metrics

Nodes

19 locations

14 stops
4 intersections
1 destination (CAMPUS)

Edges

289 connections

1,537 bus (50%)
1,200 local (39%)
337 walking (11%)

Average Degree

162 edges per nodeHigh connectivity enables flexible routing

Diameter

5 hops maximumLongest shortest path in the graph

Node Connectivity

Top 5 Most Connected Nodes

Rank	Node	Degree	Bus Routes	Role
1	SUBIDBAZAR	180	7 routes	Major hub
2	AMBARKHANA	175	7 routes	Major hub
3	CAMPUS	165	7 routes	Destination
4	CHOWHATTA	158	4 routes	Intersection
5	NAIORPUL	152	6 routes	Hub

Degree = number of outgoing edges from this node

Graph Density

Density Formula:

density = E / (V × (V - 1))
        = 289 / (19 × 18)
        = 289 / 342
        ≈ 8.99

Interpretation:

Dense graph (density > 1 due to multiple edges between nodes)
High redundancy (good for alternative routes)
Multiple transport modes create parallel edges

Connected Components

Number of components: 1 (fully connected)Every node is reachable from every other node using at least one transport mode.Proof: All nodes connect to CAMPUS via bus routes, and buses create a connected subgraph.

Code Examples

Loading Graph Data

// From graph.ts:26-47
public loadData(): void {
    const dataDir = path.join(__dirname, '../data');
    
    // Load nodes
    const nodesPath = path.join(dataDir, 'nodes.json');
    const nodesData: Node[] = JSON.parse(fs.readFileSync(nodesPath, 'utf-8'));
    nodesData.forEach(node => this.nodes.set(node.id, node));
    
    // Load edges
    const edgesPath = path.join(dataDir, 'edges.json');
    this.edges = JSON.parse(fs.readFileSync(edgesPath, 'utf-8'));
    
    // Load routes
    const routesPath = path.join(dataDir, 'routes.json');
    const routesData: Route[] = JSON.parse(fs.readFileSync(routesPath, 'utf-8'));
    routesData.forEach(route => this.routes.set(route.route_id, route));
    
    // Build adjacency list
    this.buildAdjacencyList();
    
    console.log(`✓ Loaded ${this.nodes.size} nodes, ${this.edges.length} edges, ${this.routes.size} routes`);
}

Output:

✓ Loaded 19 nodes, 289 edges, 7 routes

Querying the Graph

const node = graph.getNode('TILAGOR');
// Returns:
{
  id: 'TILAGOR',
  name: 'Tilagor',
  type: 'stop',
  gmaps_address: 'Tilagor, Sylhet, Bangladesh'
}

Visualization

Interactive Network Graph

The web dashboard includes an interactive graph visualization powered by D3.js, showing all 19 nodes and their connections.

Features:

🔵 Blue nodes: Bus stops
🟠 Orange nodes: Intersections
🟢 Green node: CAMPUS (destination)
Hover: View node details and connections
Click: See all routes serving this location

Next Steps

Routing Algorithm

See how the graph is traversed to find routes

Transport Modes

Learn about bus, local, and walking edges

API: Get Nodes

Fetch all graph nodes via API

Architecture

Understand the full system design

​Overview

Nodes

Edges

Routes

​Graph Structure

​Visual Representation

​Nodes (Locations)

​Node Types

​Node Data Structure

​Complete Node List

​Edges (Connections)

​Edge Types

Bus Edges

Local Edges

Walking Edges

​Edge Data Structure

​Edge Properties Explained

​Adjacency List

​Why Adjacency List?

​Graph Algorithms

​Dijkstra’s Shortest Path

​Graph Statistics

​Network Metrics

Nodes

Edges

Average Degree

Diameter

​Node Connectivity

​Code Examples

​Loading Graph Data

​Querying the Graph

​Visualization

​Interactive Network Graph

​Next Steps

Routing Algorithm

Transport Modes

API: Get Nodes

Architecture

Overview

Graph Structure

Visual Representation

Nodes (Locations)

Node Types

Node Data Structure

Complete Node List

Edges (Connections)

Edge Types

Edge Data Structure

Edge Properties Explained

Adjacency List

Why Adjacency List?

Graph Algorithms

Dijkstra’s Shortest Path

Graph Statistics

Network Metrics

Node Connectivity

Code Examples

Loading Graph Data

Querying the Graph

Visualization

Interactive Network Graph

Next Steps