6
\$\begingroup\$

Airlines need to provide their customers with flights to every corner, so they need an app that allows them to do so. The customer must be able to transfer when there is no direct connection.

The developer's task is to prepare the following functionalities:

  • selection of airport A and airport B
  • showing the shortest possible connection to a list of all airports

Note! In the list of available connections, flights are performed in both directions, i.e. from ATH you can get to EDI and from EDI you can get to ATH

Here is my solution, I'm looking forward for some feedback, and obviously, better solutions!

data_set = (
['ATH','EDI'], ['ATH','GLA'], ['ATH','CTA'],
['BFS','CGN'], ['BFS','LTN'], ['BFS','CTA'],
['BTS','STN'], ['BTS','BLQ'],
['CRL','BLQ'], ['CRL','BSL'], ['CRL','LTN'],
['DUB','LCA'], 
['LTN','DUB'], ['LTN','MAD'],
['LCA','HAM'],
['EIN','BUD'], ['EIN','MAD'],
['HAM','BRS'], 
['KEF','LPL'], ['KEF','CGN'],
['SUF','LIS'], ['SUF','BUD'], ['SUF','STN'],
['STN','EIN'],['STN','HAM'], ['STN','DUB'], ['STN','KEF'])


airports = {}

class Airport:
    def __init__(self, name):
        self.name = name
        self.con = []

    def add_con(self, con):
        if con not in self.con:
            self.con.append(con)
        else:
            "already there"

    def __str__(self):
        con = [x.name for x in self.con]
        return self.name + "\t" + " ".join(con)


def already_exist(name):
    if name in airports.keys():
        return True
    return False

for x in data_set:
    if not already_exist(x[0]):
        airports[x[0]] = Airport(x[0])

    if not already_exist(x[1]):
        airports[x[1]] = Airport(x[1])
    
    airports[x[0]].add_con(airports[x[1]])
    airports[x[1]].add_con(airports[x[0]])

for key in airports.keys():
    print(airports[key])

def get_shortest_path(A, B):
    A,B = B, A
    checked = []
    path = [B]
    lvl = 7

    def find(A, B, lvl):
        checked.append(A)

        if lvl == 1: return

        elif lvl > 1:
            to_check = [a for a in A.con if a not in checked]
            if to_check:
                for x in to_check:
                    if x not in checked:
                        if x.name == B.name:
                            path.append(A)
                            return True
                        if find(x, B, lvl - 1):
                            path.append(A)
                            return True

    find(A, B, lvl)

    return path

path = get_shortest_path(airports['ATH'], airports['KEF'])
print([airport.name for airport in path])

\$\endgroup\$

3 Answers 3

4
\$\begingroup\$

data_set (which could get a better name) has inner lists when those should be inner tuples for immutability.

Airport needing to be a class is dubious.

con = [x.name for x in self.con] should have a generator () and not a list comprehension [].

Add PEP484 type hints.

This:

for key in airports.keys():
    print(airports[key])

seems like debug output and should be deleted.

lvl = 7 is concerning. Will your program still work for paths above seven edges? It seems not: try for example ATH -> BRS, which for your implementation outputs only ['ATH'].

You recurse on find(). For several reasons, Python is not good at recursion: it's slow since there is no tail optimisation, and the Python default stack is very shallow so it's easy for a recursive algorithm to overflow it.

There are stock algorithms in standard (albeit not built-in) libraries that offer various levels of increased efficiency and convenience. scipy.sparse has a good one. It is able to pre-calculate a predecession matrix that can then be used to find any shortest path in linear time, paying for the more difficult calculation up front. This would be appropriate for (say) a web server where the airport connections do not change often, but there are hundreds of requests a second for shortest flight path. If your use case is expected to remain as-is with a single path request, you can modify the call to shortest_path only supplying the endpoints of interest. If you ever have uni-directional flight paths or want to optimise for shortest land distance covered, scipy will make it easy.

Suggested

from itertools import chain
from typing import Iterator

import numpy as np
import scipy.sparse


def load_connections() -> tuple[
    tuple[str, ...],          # airport names, sorted alphabetically
    dict[str, int],           # airport index by name
    scipy.sparse.csr_matrix,  # connection adjacencies, symmetric
]:
    connection_names = (
        ('ATH', 'EDI'), ('ATH', 'GLA'), ('ATH', 'CTA'),
        ('BFS', 'CGN'), ('BFS', 'LTN'), ('BFS', 'CTA'),
        ('BTS', 'STN'), ('BTS', 'BLQ'),
        ('CRL', 'BLQ'), ('CRL', 'BSL'), ('CRL', 'LTN'),
        ('DUB', 'LCA'),
        ('EIN', 'BUD'), ('EIN', 'MAD'),
        ('HAM', 'BRS'),
        ('KEF', 'LPL'), ('KEF', 'CGN'),
        ('LTN', 'DUB'), ('LTN', 'MAD'),
        ('LCA', 'HAM'),
        ('STN', 'EIN'), ('STN', 'HAM'), ('STN', 'DUB'), ('STN', 'KEF'),
        ('SUF', 'LIS'), ('SUF', 'BUD'), ('SUF', 'STN'),
    )

    airport_names = tuple(sorted(set(chain.from_iterable(connection_names))))
    airport_indices = {
        name: i for i, name in enumerate(airport_names)
    }
    N = len(airport_names)

    sources, dests = [], []
    for source, dest in connection_names:
        sources.append(airport_indices[source])
        dests.append(airport_indices[dest])

    connections = scipy.sparse.csr_matrix(
        (
            np.ones(len(sources), dtype=np.int32),  # All connections have equal weight
            (sources, dests),
        ),
        shape=(N, N),
    )
    # All connections have the same weight in the other direction
    connections += connections.T

    return airport_names, airport_indices, connections


airport_names, airport_indices, connections = load_connections()


def load_predecessors() -> np.ndarray:
    distances, predecessors = scipy.sparse.csgraph.shortest_path(
        csgraph=connections, directed=False, unweighted=True, return_predecessors=True,
    )
    return predecessors


predecessors = load_predecessors()


def get_path_by_index(source: int, dest: int) -> Iterator[int]:
    while source != dest:
        yield dest
        dest = predecessors[source, dest]

    yield source


def get_path(source: str, dest: str) -> Iterator[str]:
    for index in get_path_by_index(
        airport_indices[source],
        airport_indices[dest],
    ):
        yield airport_names[index]


if __name__ == '__main__':
    for source in airport_names:
        print(' <- '.join(get_path(source, dest='ATH')))

Output

ATH
ATH <- CTA <- BFS
ATH <- CTA <- BFS <- LTN <- CRL <- BLQ
ATH <- CTA <- BFS <- CGN <- KEF <- STN <- HAM <- BRS
ATH <- CTA <- BFS <- LTN <- CRL <- BSL
ATH <- CTA <- BFS <- LTN <- CRL <- BLQ <- BTS
ATH <- CTA <- BFS <- LTN <- MAD <- EIN <- BUD
ATH <- CTA <- BFS <- CGN
ATH <- CTA <- BFS <- LTN <- CRL
ATH <- CTA
ATH <- CTA <- BFS <- LTN <- DUB
ATH <- EDI
ATH <- CTA <- BFS <- LTN <- MAD <- EIN
ATH <- GLA
ATH <- CTA <- BFS <- CGN <- KEF <- STN <- HAM
ATH <- CTA <- BFS <- CGN <- KEF
ATH <- CTA <- BFS <- LTN <- DUB <- LCA
ATH <- CTA <- BFS <- CGN <- KEF <- STN <- SUF <- LIS
ATH <- CTA <- BFS <- CGN <- KEF <- LPL
ATH <- CTA <- BFS <- LTN
ATH <- CTA <- BFS <- LTN <- MAD
ATH <- CTA <- BFS <- CGN <- KEF <- STN
ATH <- CTA <- BFS <- CGN <- KEF <- STN <- SUF

Note that this "tells the truth" because the predecession matrix defines paths in reverse order. However, since your adjacency is symmetric you could just lie and supply the source for the destination and the destination for the source when iterating the path, and you'll get a forward path at no extra cost.

Alternate adjacency literals

An alternate and more condensed way of expressing your adjacency literals is to use a dictionary of tuples:

def load_connections() -> tuple[
    tuple[str, ...],          # airport names, sorted alphabetically
    dict[str, int],           # airport index by name
    scipy.sparse.csr_matrix,  # connection adjacencies, symmetric
]:
    connection_names = {
        'ATH': ('EDI', 'GLA', 'CTA'),
        'BFS': ('CGN', 'LTN', 'CTA'),
        'BTS': ('STN', 'BLQ'),
        'CRL': ('BLQ', 'BSL', 'LTN'),
        'DUB': ('LCA',),
        'EIN': ('BUD', 'MAD'),
        'HAM': ('BRS',),
        'KEF': ('LPL', 'CGN'),
        'LTN': ('DUB', 'MAD'),
        'LCA': ('HAM',),
        'STN': ('EIN', 'HAM', 'DUB', 'KEF'),
        'SUF': ('LIS', 'BUD', 'STN'),
    }

    airport_names = tuple(sorted({
        *connection_names.keys(),
        *chain.from_iterable(connection_names.values()),
    }))
    airport_indices = {
        name: i for i, name in enumerate(airport_names)
    }
    N = len(airport_names)

    sources, dests = [], []
    for source, destinations in connection_names.items():
        for dest in destinations:
            sources.append(airport_indices[source])
            dests.append(airport_indices[dest])

    connections = scipy.sparse.csr_matrix(
        (
            np.ones(len(sources), dtype=np.int32),  # All connections have equal weight
            (sources, dests),
        ),
        shape=(N, N),
    )
    # All connections have the same weight in the other direction
    connections += connections.T

    return airport_names, airport_indices, connections
\$\endgroup\$
3
\$\begingroup\$

Thanks to @Reinderien solution and tips, I've recreated my solution:

from collections import deque, defaultdict

data_set = (
    ['ATH','EDI'], ['ATH','GLA'], ['ATH','CTA'],
    ['BFS','CGN'], ['BFS','LTN'], ['BFS','CTA'],
    ['BTS','STN'], ['BTS','BLQ'],
    ['CRL','BLQ'], ['CRL','BSL'], ['CRL','LTN'],
    ['DUB','LCA'], 
    ['LTN','DUB'], ['LTN','MAD'],
    ['LCA','HAM'],
    ['EIN','BUD'], ['EIN','MAD'],
    ['HAM','BRS'], 
    ['KEF','LPL'], ['KEF','CGN'],
    ['SUF','LIS'], ['SUF','BUD'], ['SUF','STN'],
    ['STN','EIN'],['STN','HAM'], ['STN','DUB'], ['STN','KEF']
)

graph = defaultdict(list)
for connection in data_set:
    source, destination = connection
    graph[source].append(destination)
    graph[destination].append(source)  

def shortest_path(graph, start, end):
    queue = deque([[start]])
    
    visited = set()

    while queue:
        path = queue.popleft()
        airport = path[-1]

        if airport == end:
            return path

        if airport not in visited:
            visited.add(airport)
            for neighbour in graph[airport]:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)

    return None

shortest_path(graph, "ATH", "LIS")

Output:

['ATH', 'CTA', 'BFS', 'CGN', 'KEF', 'STN', 'SUF', 'LIS']
\$\endgroup\$
3
\$\begingroup\$

tuple vs list

data_set = (
    ['ATH', 'EDI'],
    ['ATH', 'GLA'],
    ...
)

In python we use a fixed-length tuple in places that C would tend to use a struct, where different things are each stored in their own position, such as "source" followed by "destination" that we see here. In contrast we use a list for an arbitrarily long collection of same things, such as the "connection" list we see here. So better to phrase it as:

connection_names = [
    ("ATH", "EDI"),
    ("ATH", "GLA"),
    ...
    ("STN", "KEF"),
]

graph libraries

The Airport class is nice enough, but despite the lack of an OP tag it is definitely "reinventing the wheel". Consider leveraging one of the general graph libraries out there, such as networkX or igraph. Then a single call to one of the library's solvers may suffice:

import matplotlib.pyplot as plt
import networkx as nx
    ...
    g = nx.Graph(connection_names)
    print(nx.shortest_path(g, "ATH", "LIS"))

Displaying the adjacencies is pretty straightforward, as well.

    nx.draw(g, node_size=1, width=0.1, with_labels=True)
    plt.show()

airline routes

strings are not comments

        if con not in self.con:
            self.con.append(con)
        else:
            "already there"

You are computing a string constant and then discarding it, where a # comment would have been more appropriate. Please delete the else clause.

same name, different meanings

        con = [x.name for x in self.con]
        return self.name + "\t" + " ".join(con)

Choosing the identifier con for a local variable could be fine, but here it has different type, different meaning, from the .con attribute. Prefer to invent a new identifier, such as names.

return a bool expression

    if name in airports.keys():
        return True
    return False

This is tediously long. Prefer to simply

    return name in airports.keys()

(Phrasing it return bool(name in airports.keys()) might make it slightly easier for you to see what's going on.)

tuple unpack

The for x in ... loop uses inconvenient [0] and [1] subscripts a great many times.

Prefer for src, dst in ... so you can conveniently talk about the source and destination airports.

defaultdict

Rather than testing whether a key already_exists, prefer to use a defaultdict.

nested functions

def get_shortest_path(A, B):
    ...
    def find(A, B, lvl):

I understand that you were trying to avoid needlessly polluting the global namespace with private identifiers, and I appreciate the sentiment.

But nested functions are often more trouble than they're worth. Avoid nesting, unless you can write down a comment that explains the benefit for the particular function you're writing.

The two big disadvantages tend to be:

  1. Inner function sees outer function's identifiers, similar to the trouble that global variables can cause. Though on occasion certain functions may find this is a benefit.
  2. Inner function is not easily accessible to a second caller, such as a unit test.

Prefer to def _find, so it's accessible if needed but folks will understand it is _private, it's not part of the Public API you're exporting.

main guard

print([airport.name for airport in path])

Prefer to put side-effecting statements like this within a guard:

if __name__ == "__main__":
    print( ... )

That way your module can be safely imported by others. For example, by a test suite.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.