Bahia.py

'''
Maxwell Mowbray 2020

This simple program traverses an acyclic, weighted, and directed graph of flights across Canada.
It finds all of the valid paths from the source to the destination city, and prints all the hops and the total time.

'''


# edge
class Flight:

    def __init__(self, destination_city, flight_duration):
        self.destination_city = destination_city
        self.flight_duration = flight_duration

# node
class City:

    def __init__(self, name):
        self.name = name
        self.flights_out = []

    def add_destination(self, destination_city, flight_duration):
        self.flights_out.append(Flight(destination_city, flight_duration))


class DirectedWeightedAcyclicGraph:
    nodes = []

    def __init__(self):
        pass

    def add_node(self, node):
        self.nodes.append(node)

    def get_fastest_route(self, src, dst):
        all_paths = list()
        self.traverse_graph(src, dst, [], 0, all_paths)

        print("Found " + str(len(all_paths)) + " paths from: " + src.name + " to: " + dst.name)

        for valid_path in all_paths:
            print("Path found totalling this many hours: " + str(valid_path[1]) + "\n")

            for city in valid_path[0]:
                print(city.name)

            print("\n")

        return None

    def traverse_graph(self, current_city, destination_city, current_path, current_path_duration, all_paths):

        #we reached the destination
        if current_city == destination_city:
            #each successful walk represented as a pair, where the first element is all the steps (City[])
            #and the second element is the total time
            this_successful_walk = (current_path + [destination_city], current_path_duration)
            all_paths.append(this_successful_walk)
            return

        #we have already visited this city (cycle)
        if current_city in current_path:
            return

        #this city has no flights out
        if len(current_city.flights_out) == 0:
            return

        #continue visiting every flight out
        for flight in current_city.flights_out:
            self.traverse_graph(flight.destination_city, destination_city,
                                current_path + [current_city],
                                current_path_duration + flight.flight_duration, all_paths)


if __name__ == '__main__':

    montreal = City("Montreal")
    toronto = City("Toronto")
    calgary = City("Calgary")
    vancouver = City("Vancouver")
    nanaimo = City("Nanaimo")

    montreal.add_destination(calgary, 3)
    montreal.add_destination(toronto, 1.5)
    toronto.add_destination(calgary, 2.5)
    toronto.add_destination(vancouver, 3.5)
    calgary.add_destination(vancouver, 1)
    calgary.add_destination(nanaimo, 1.5)
    vancouver.add_destination(nanaimo, 0.5)

    graph = DirectedWeightedAcyclicGraph()

    graph.add_node(montreal)
    graph.add_node(toronto)
    graph.add_node(calgary)
    graph.add_node(vancouver)
    graph.add_node(nanaimo)

    graph.get_fastest_route(montreal, nanaimo)

'''
Found 5 paths from: Montreal to: Nanaimo
Path found totalling this many hours: 4.5

Montreal
Calgary
Vancouver
Nanaimo


Path found totalling this many hours: 4.5

Montreal
Calgary
Nanaimo


Path found totalling this many hours: 5.5

Montreal
Toronto
Calgary
Vancouver
Nanaimo


Path found totalling this many hours: 5.5

Montreal
Toronto
Calgary
Nanaimo


Path found totalling this many hours: 5.5

Montreal
Toronto
Vancouver
Nanaimo



Process finished with exit code 0
'''