Navigating Pakistan: A Graph Theory Exploration of City Road Networks With Python Networkx
A graph theory exploration of Pakistan’s city road network with Python Networkx
Dive into the heart of Pakistan’s urban landscape with our exploration of graph theory applied to the intricate web of city roads. This article unravels the network that binds the nation’s cities, revealing the fascinating interplay of nodes and edges that govern travel and connectivity in this diverse and dynamic country.
Create A Graph With Networkx
The code generates a random network of cities in Pakistan using the NetworkX library. It defines a function to create a network with specified cities, costs, and edges, incrementing the edge count until a connected network is formed. The script prints the current edge count, visualizes the evolving network, and checks for connectivity using NetworkX and Matplotlib. The loop continues until a fully connected graph is achieved, providing insights into the relationship between edge density and network connectivity in the context of city connections, with the final visualization showcasing the structure of the resulting connected network.
# Import necessary libraries
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import random
import networkx as nx
# Define a function to create a network with given cities, costs, and number of edges
def create_network(cities, costs, n_edges):
G = nx.Graph()
for city in cities:
G.add_node(city)
while G.number_of_edges() < n_edges:
# Randomly select two nodes
c1 = random.choice(list(G.nodes()))
c2 = random.choice(list(G.nodes()))
# Ensure the selected nodes are different and there is no existing edge between them
if c1 != c2 and G.has_edge(c1, c2) == 0:
# Assign a random cost to the edge
w = random.choice(costs)
G.add_edge(c1, c2, Weight=w)
return G
# Define a set of cities in Pakistan
city_set = ["Karachi", "Lahore", "Islamabad", "Rawalpindi", "Faisalabad",
"Multan", "Peshawar", "Quetta"]
# Generate a list of 20 random costs for edges
costs = [random.randint(100, 2000) for _ in range(20)]
# Initialize the edge count
n_edges = 0
# Loop until a connected network is generated
while True:
# Print the current edge count
print("Edge Count: ", n_edges)
# Create a network with the specified cities, costs, and edge count
G = create_network(city_set, costs, n_edges)
# Generate a circular layout for the graph
pos = nx.circular_layout(G)
# Visualize the graph using Matplotlib
nx.draw(G, pos, with_labels=True, font_weight='bold', node_color='skyblue', node_size=1000)
# Draw edge labels on the graph
nx.draw_networkx_edge_labels(G, pos)
# Display the plot
plt.show()
# Check if the generated network is connected
if nx.is_connected(G) is True:
# Break the loop if the network is connected
break
# Increment the edge count for the next iteration
n_edges = n_edges + 1
The following code employs NetworkX to analyze a city network graph (G). It checks graph connectivity, finds the shortest path between "Faisalabad" and "Multan" using Dijkstra's algorithm, computes shortest path lengths considering edge weights, and calculates cumulative distances for a specific city route, providing valuable insights into the network's characteristics.
# Check if the graph G is connected
print(nx.is_connected(G))
# Find the shortest path using Dijkstra's algorithm between "Faisalabad" and "Multan"
print(nx.dijkstra_path(G, "Faisalabad", "Multan"))
# Calculate the length of the shortest path between "Faisalabad" and "Multan"
print(nx.shortest_path_length(G, 'Faisalabad', 'Multan'))
# Calculate the length of the shortest path considering edge weights between "Faisalabad" and "Multan"
print(nx.shortest_path_length(G, 'Faisalabad', 'Multan', weight='Weight'))
# Calculate the shortest path lengths between specified city pairs considering edge weights
x1 = nx.shortest_path_length(G, 'Faisalabad', 'Peshawar', weight='Weight')
x2 = nx.shortest_path_length(G, 'Peshawar', 'Quetta', weight='Weight')
x3 = nx.shortest_path_length(G, 'Quetta', 'Islamabad', weight='Weight')
x4 = nx.shortest_path_length(G, 'Islamabad', 'Karachi', weight='Weight')
x5 = nx.shortest_path_length(G, 'Karachi', 'Rawalpindi', weight='Weight')
x6 = nx.shortest_path_length(G, 'Rawalpindi', 'Multan', weight='Weight')
# Calculate the cumulative distance for the specified city route
print(x1 + x2 + x3 + x4 + x5 + x6)
#------------------------------------ OUTPUT ----------------------------
True
['Faisalabad', 'Peshawar', 'Quetta', 'Islamabad', 'Karachi', 'Rawalpindi', 'Multan']
6
6459
6459Reduce The Travelling Cost By Adding More Edges
At this point, we have a connected graph with 8 edges and the cost of travel from Faisalabad to Multan is 6459. Now we add more edges and analyze the effect of adding more edges on the travel cost.
the following code dynamically expands a city network graph (G) by adding random edges, recording the number of edges and the total cost of the shortest path between two cities. This process is repeated 14 times, visualizing the evolving graph using NetworkX and Matplotlib, offering insights into the network's growth and cost dynamics.
# Lists to store the number of edges and total cost for each iteration
n_edges = [len(G.edges())]
total_cost = [nx.shortest_path_length(G, 'Faisalabad', 'Multan', weight='Weight')]
# Function to add a random edge to the graph and update the lists
def add_nedge(cities, costs):
while True:
# Randomly select two nodes
c1 = random.choice(list(G.nodes()))
c2 = random.choice(list(G.nodes()))
# Ensure the selected nodes are different and there is no existing edge between them
if c1 != c2 and G.has_edge(c1, c2) == 0:
# Assign a random cost to the edge
w = random.choice(costs)
G.add_edge(c1, c2, Weight=w)
# Update the lists with the current number of edges and total cost
n_edges.append(len(G.edges()))
total_cost.append(nx.shortest_path_length(G, 'Faisalabad', 'Multan', weight='Weight'))
# Break the loop after adding a valid edge
break
return G
# Iterate 14 times, adding a random edge in each iteration
for i in range(1, 15):
G = add_nedge(city_set, costs)
# Print the edge count
print("Edge Count: ", len(G.edges()))
# Generate a circular layout for the graph
pos = nx.circular_layout(G)
# Visualize the graph using Matplotlib
nx.draw(G, pos, with_labels=True, font_weight='bold', node_color='skyblue', node_size=1000)
# Draw edge labels on the graph
nx.draw_networkx_edge_labels(G, pos)
# Display the plot
plt.show()
Plotting Number of Edges VS Cost
This code utilizes Matplotlib to create a line graph from given lists representing the relationship between the number of edges and costs. The graph visually illustrates the correlation, with labeled axes and a title for clarity, providing a concise representation of the data.
import matplotlib.pyplot as plt
# Given lists
number_of_edges = [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
cost = [6459, 4821, 418, 418, 418, 418, 418, 418, 418, 418, 418, 418, 418, 418, 418]
# Plotting the line graph
plt.plot(number_of_edges, cost, marker='o', linestyle='-', color='b')
# Adding labels and title
plt.xlabel('Number of Edges')
plt.ylabel('Cost')
plt.title('Cost vs Number of Edges')
# Display the plot
plt.show()
Conclusion
In this exploration of Pakistan’s city road network through graph theory, we delved into the dynamic interplay of edges and nodes, visualizing the evolving connectivity. The analysis extended to pathfinding algorithms, emphasizing the significance of edge weights in determining optimal routes. Furthermore, the cumulative distance metric underscored the impact of varying edge densities on overall network cost. This journey unraveled not only the structural intricacies of the road network but also the critical role of graph theory in deciphering and optimizing complex urban connections. As we conclude, the article highlights the utility of such analyses in urban planning and transportation management.
