”’I am learning Python with existing internet projects, the code belongs to an algorithm to find out the number of connections. I ask for help since I have not been able to obtain the output of the algorithm
starting @ airport LGA
The following airports are unreachable
BGI
CDG
DEL
DOH
DSM
EWR
EYW
HND
ICN
JFK
LHR
ORD
SAN
SFO
SIN
TLV
BUD
[(‘EYW’, 7), (‘LHR’, 7), (‘SAN’, 7), (‘SFO’, 7), (‘TLV’, 6), (‘DEL’, 5), (‘EWR’, 4), (‘CDG’, 3), (‘DSM’, 3), (‘HND’, 3), (‘SIN’, 3), (‘ICN’, 2), (‘ORD’, 2), (‘BGI’, 1), (‘DOH’, 1), (‘JFK’, 1), (‘BUD’, 1)]
”’

airports = [“BGI”,”CDG”,”DEL”,”DOH”,”DSM”,”EWR”,”EYW”,”HND”,”ICN”,”JFK”,”LGA”,”LHR”,”ORD”,”SAN”,”SFO”,”SIN”,”TLV”,”BUD”,]
routes = [[“DSM”, “ORD”], [“ORD”, “BGI”], [“BGI”, “LGA”], [“SIN”, “CDG”], [“CDG”, “SIN”], [“CDG”, “BUD”], [“DEL”, “DOH”], [“DEL”, “CDG”], [“TLV”, “DEL”], [“EWR”, “HND”], [“HND”, “ICN”], [“HND”, “JFK”], [“ICN”, “JFK”], [“JFK”, “LGA”], [“EYW”, “LHR”], [“LHR”, “SFO”], [“SFO”, “SAN”], [“SFO”, “DSM”], [“SAN”, “EYW”]]
startingAirport = “LGA”
”’
class AirportNode:
def init(self, airport):
self.airport = airport
self.connections = []
self.isReachable = True
self.unreachableConnections = []

def airportConnections(airports, routes, startingAirport):
## build a graph for airports and connections
airportGraph = createAirportGraph(airports, routes)
## find unreachable airports/Nodes
print(“starting @ airport “, startingAirport)
print(” The following airports are unreachable”)
unreachableAirportNodes = getUnreachableAirportNodes(
airportGraph, airports, startingAirport
)
for u in unreachableAirportNodes:
print(u.airport)
## assign a score for each airport of the unreachables
markUnreachableConnections(airportGraph, unreachableAirportNodes)
## now return minimum number of connections
return getMinNumberOfNewConnections(airportGraph, unreachableAirportNodes)

O(a + r) time | O(a + r) space

def createAirportGraph(airports, routes):
airportGraph = {}
for airport in airports:
airportGraph[airport] = AirportNode(airport)
for route in routes:
airport, connection = route
airportGraph[airport].connections.append(connection)
return airportGraph

O(a + r) time | O(a) space

def getUnreachableAirportNodes(airportGraph, airports, startingAirport):
visitedAirports = {}
depthFirstTraverseAirports(airportGraph, startingAirport, visitedAirports)

unreachableAirportNodes = []
for airport in airports:
    if airport in visitedAirports:
        continue
    airportNode = airportGraph[airport]
    airportNode.isReachable = False
    unreachableAirportNodes.append(airportNode)
return unreachableAirportNodes

def depthFirstTraverseAirports(airportGraph, airport, visitedAirports):
if airport in visitedAirports:
return
visitedAirports[airport] = True
connections = airportGraph[airport].connections
for connection in connections:
depthFirstTraverseAirports(airportGraph, connection, visitedAirports)

O(a * (a + r)) time | O(a) space

def markUnreachableConnections(airportGraph, unreachableAirportNodes):
for airportNode in unreachableAirportNodes:
airport = airportNode.airport
unreachableConnections = []
depthFirstAddUnreachableConnections(
airportGraph, airport, unreachableConnections, {}
)
airportNode.unreachableConnections = unreachableConnections

def depthFirstAddUnreachableConnections(airportGraph, airport, unreachableConnections, visitedAirports):
if airportGraph[airport].isReachable:
return
if airport in visitedAirports:
return
visitedAirports[airport] = True
unreachableConnections.append(airport)
connections = airportGraph[airport].connections
for connection in connections:
depthFirstAddUnreachableConnections(
airportGraph, connection, unreachableConnections, visitedAirports
)

O(alog(a) + a + r) time | O(1) space

def getMinNumberOfNewConnections(airportGraph, unreachableAirportNodes):
## loop over unreachableconnections starting with those with the highest number of unreachable connections
## increment newconnections number but mark all those unreachable connections as reachable (by virtue
## of connecting the representative unreachable connection)
unreachableAirportNodes.sort(
key=lambda airport: len(airport.unreachableConnections), reverse=True
)
print([(i.airport, len(i.unreachableConnections)) for i in unreachableAirportNodes])
numberOfNewConnections = 0
for airportNode in unreachableAirportNodes:
if airportNode.isReachable:
continue
numberOfNewConnections += 1
for connection in airportNode.unreachableConnections:
airportGraph[connection].isReachable = True
return numberOfNewConnections