nas_maxflow
py
keyboard_arrow_up
School
Arizona State University *
*We aren’t endorsed by this school
Course
551
Subject
Industrial Engineering
Date
Dec 6, 2023
Type
py
Pages
3
Uploaded by DoctorComputerDonkey34
import sys
import pandas as pd
import re
# Class representing a single flight
class Flight:
def __init__(self, source, destination, dept, arr, capacity):
self.source = source
self.destination = destination
self.dept = dept
self.arr = arr
self.capacity = capacity
# Class to calculate the maximum flow through a network
class FlightMaxFlow:
# The number of vertices in the network
total_number_of_hours = 24
total_intermediate_airports = 8
vertices = (total_intermediate_airports*total_number_of_hours) + 2
print("Number of vertices = ", vertices)
# Perform a breadth-first search to find the shortest path from the source
# vertex to the destination vertex in the given residual graph
def bfs(self, residual_graph, s, t, parent):
# Keep track of which vertexs have been visited
visited = [False] * (FlightMaxFlow.vertices)
# Use a queue to perform the search
queue = []
queue.append(s)
visited[s] = True
parent[s] = -1
while len(queue) != 0:
u = queue.pop()
# Consider all unvisited neighbors of u
for v in range(FlightMaxFlow.vertices):
if not visited[v] and residual_graph[u][v] > 0:
queue.append(v)
parent[v] = u
visited[v] = True
# Return true if the destination vertex was reached during the search
return visited[t]
# Calculate the maximum flow from the source vertex to the destination vertex
# in the given graph using the Ford-Fulkerson algorithm
def ford_fulkerson_max_flow(self, graph, s, t):
# Create a residual graph
residual_graph = [[0] * (FlightMaxFlow.vertices) for _ in
range(FlightMaxFlow.vertices)]
for u in range(FlightMaxFlow.vertices):
for v in range(FlightMaxFlow.vertices):
residual_graph[u][v] = graph[u][v]
# Keep track of the path taken by the search
parent = [0] * (FlightMaxFlow.vertices)
# Initialize the maximum flow to 0
max_flow = 0
while self.bfs(residual_graph, s, t, parent):
# The flow along the current path is the minimum capacity of the edges
along the path
path_flow = sys.maxsize
v = t
while v != s:
u = parent[v]
path_flow = min(path_flow, residual_graph[u][v])
v = parent[v]
# Update the residual graph with the flow along the path
v = t
while v != s:
u = parent[v]
residual_graph[u][v] -= path_flow
residual_graph[v][u] += path_flow
v = parent[v]
# Add the flow along the path to the total maximum flow
max_flow += path_flow
# Return the total maximum flow
return max_flow
def main():
# Keep track of the total direct flow (i.e. flights that don't need to be
routed
# through the network)
direct_flow = 0
# Create an adjacency matrix to represent the network
adjacency_matrix = [[0] * (FlightMaxFlow.vertices) for _ in
range(FlightMaxFlow.vertices)]
# Add each flight to the adjacency matrix
for flight in FlightMaxFlow.fetch_data():
row = FlightMaxFlow.get_port(flight.source, flight.dept)
column = FlightMaxFlow.get_port(flight.destination, flight.arr)
if row == 0 and column == FlightMaxFlow.vertices - 1:
# This flight is a direct flight, so add its capacity to the total
direct flow
direct_flow += flight.capacity
else:
# This flight needs to be routed through the network, so add its
capacity
# to the adjacency matrix
adjacency_matrix[row][column] += flight.capacity
# Set the capacities of edges within the same time slot to "infinity" to
prevent
# flights from being routed through the network when they can be scheduled
# directly
for i in range(1, FlightMaxFlow.vertices - 1):
for j in range(1, FlightMaxFlow.vertices - 1):
if i < j:
if(i in range(1, 25) and j in range(1, 25)) or (i in range(25,
49) and j in range(25, 49)) or (i in range(49, 73) and j in range(49, 73)) or (i in
range(73, 97) and j in range(73, 97)) or (i in range(97, 121) and j in range(97,
121)) or (i in range(121, 145) and j in range(121, 145)) or (i in range(145, 169)
and j in range(145, 169)) or (i in range(169, 194) and j in range(169, 194)):
adjacency_matrix[i][j] = sys.maxsize
# Calculate the maximum flow through the network
ff_max = FlightMaxFlow().ford_fulkerson_max_flow(adjacency_matrix, 0,
FlightMaxFlow.vertices - 1)
print("The Largest number of individuals that can travel from LAX to JFK is
" + str(ff_max + direct_flow))
def fetch_data():
# Initialize variables
line = None
flights = []
time_format_pattern = re.compile("^([0-1]?[0-9]|2[0-3]):[0-5][0-9]$")
# Open the file for reading
file = open("flights.txt", "r")
# Read the file line by line until the end
while True:
line = file.readline()
if not line:
break
# Split the line into data fields
data = line.split()
# Parse the departure and arrival times
departure = pd.to_datetime(data[2]).round('H').hour if
time_format_pattern.match(data[2]) else int(data[2])
arrival = pd.to_datetime(data[3]).round('H').hour if
time_format_pattern.match(data[3]) else int(data[3])
# Filter out flights that depart or arrive outside the specified time
window
if ((departure >= 6 and arrival <= 24) or (departure >= 6 and arrival
<= 6) or (departure >= 0 and arrival <= 6)):
# Create a Flight object and add it to the list
flights.append(Flight(data[0], data[1], departure, arrival,
int(data[4])))
# Close the file
file.close()
return flights
def get_port(flight, time):
# define the dictionary of airport codes and their corresponding port
numbers. 24 for each airports.
switcher = {
"LAX": 0,
"SFO": 1 + time,
"PHX": 25 + time,
"SEA": 49 + time,
"DEN": 73 + time,
"ATL": 97 + time,
"ORD": 121 + time,
"BOS": 145 + time,
"IAD": 169 + time,
"JFK": 193,
}
# return the port number for the given airport code, or -1 if the code is
not in the dictionary
return switcher.get(flight, -1)
if __name__ == "__main__":
FlightMaxFlow.main()
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help