Recover flights from found tickets

Question

I just found a whole bunch of plane tickets that only have a start and destination on them. I also know the route started in a certain city. I would like to recover the (alphabetically) first possible route a person took using these tickets. I added some examples in the doctests.

from collections import OrderedDict, defaultdict


class OrderedDefaultDict(OrderedDict):
    def __missing__(self, key):
        self[key] = value = 0
        return value


class FlightStorage():
    amount = 0

    def __init__(self):
        self.storage = defaultdict(OrderedDefaultDict)

    def add(self, start, destination):
        self.storage[start][destination] += 1
        self.amount += 1

    def list(self, start):
        return (destination for destination, amount in self.storage[start].items() if amount > 0)

    def remove(self, start, destination):
        self.storage[start][destination] -= 1
        self.amount -= 1

    def __len__(self):
        return self.amount


def reassemble_flights(start, flights):
    '''Reassembles a series of flights.

    >>> reassemble_flights('YUL', [('YUL', 'SFO'), ('SFO', 'HKO')])
    ['YUL', 'SFO', 'HKO']
    >>> reassemble_flights('YUL', [('SFO', 'HKO'), ('YYZ', 'SFO'), ('YUL', 'YYZ'), ('HKO', 'ORD')])
    ['YUL', 'YYZ', 'SFO', 'HKO', 'ORD']

    Returns the first (alphabetically sorted) route:
    >>> reassemble_flights('A', [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'A')])
    ['A', 'B', 'C', 'A', 'C']

    If no solution is available, returns None:
    >>> reassemble_flights('COM', [('SFO', 'COM'), ('COM', 'YYZ')]) is None
    True
    '''
    storage = FlightStorage()
    for flight in sorted(flights):
        storage.add(*flight)
    return backtrack_flights(start, storage)


def backtrack_flights(start, storage):
    if len(storage) == 0:
        return [start]
    if not any(storage.list(start)):
        return
    for destination in storage.list(start):
        storage.remove(start, destination)
        result = backtrack_flights(destination, storage)
        if result is not None:
            return [start] + result
        storage.add(start, destination)

Answer 1

1. Review

1. The problem of putting the tickets in order is the same as that of constructing an Eulerian path on the directed graph whose edges correspond to the tickets. (An Eulerian path is a path in a graph that follows every edge exactly once.)

   

2. Since this is really a graph problem, it would make things clearer if the code used graph terminology rather than flight terminology. Thus: FlightStorage → Graph, start → vertex (or node), destination → neighbour, list → neighbours, flights → edges and so on.

   The reason for using graph terminology (rather than flight ticket terminology) is that there is a body of computer science literature about graphs, and translating your problem into graph terminology helps you to see how your problem relates to this body of literature, and helps you discover and implement the best data structures and algorithms for your problem.

3. The classes OrderedDefaultDict and FlightStorage lack docstrings.

4. The list method returns an iterator (not a list) over the neighbours of a vertex. This means that in this code:

   for destination in storage.list(start):
       storage.remove(start, destination)
       # ...
   

   the loop is modifying the dictionary storage.storage at the same time as it is iterating over it. This is not guaranteed to work in Python (though it might happen to do so in some cases). For reliability you need to avoid this.

5. In the remove method there ought to be a check that self.storage[start][destination] is greater than zero, before decrementing it. This would catch attempts to remove non-existent edges from the graph.

6. The test not any(storage.list(start)) only works if the vertices of the graph are represented by objects that test as true. This prevents us from (say) representing vertices as integers starting at zero (because vertex zero will test as false).

7. In any case there is no need for the special case if not any(storage.list(start)) because that is already handled correctly — if start has no neighbours then there will be no iterations of the for loop.

8. Returning None when the graph has no Eulerian path is risky. It would be easy for caller to forget to check. It is better to raise an exception in an exceptional case like this.

9. When constructing the graph, it would be faster to sort the neighbours of each vertex, rather than sorting all the edges in one big list.

10. The examples can be written more tersely. Instead of:

    [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'A')]
    

    write:

    'AB AC BC CA'.split()
    

2. Algorithm

The problem of constructing an Eulerian path can be solved using Hierholzer's algorithm. This algorithm works by following edges until a dead end is reached. For example, if we are given this graph:

Then following edges starting at A reaches a dead end at F:

This initial step may leave some vertices which still have unused edges. We pick one of the vertices (for example, vertex E) and follow unused edges again until we reach a dead end. Necessarily this dead end must be where we started (otherwise there is no Eulerian path), and so we get a loop:

Continue to find loops until there are no more unused edges. In this example, if we pick vertex D then we get one more loop:

Now all the edges have been used, so we stitch together the result, by inserting each of the loops into the path we found at the first step, getting the Eulerian path:

In order to ensure that this procedure yields the lexicographically first path, we need to take some care about the order we choose edges and vertices. In particular, when following edges, we should choose the unused edge to the lexicographically earliest neighbour, and when choosing a vertex with unused edges, we should choose the last such vertex along the path constructed so far.

3. Implementation

This uses a linked list to maintain the path, so that we can efficiently insert new vertices into the middle of the path as we go along. The graph itself is represented as a defaultdict(list) mapping each vertex to a list of its neighbours. The neighbours for each vertex are sorted into reverse order, so that when we pop the list we get the lexicographically smallest neighbour.

from collections import defaultdict

class Link:
    "A link in a linked list."
    def __init__(self, vertex):
        self.vertex = vertex
        self.next = None

    def insert(self, link):
        "Insert link after self in the linked list and return link."
        link.next = self.next
        self.next = link
        return link

    def __repr__(self):
        return '{0.vertex!r}->{0.next!r}'.format(self)

def eulerian_path(start, edges):
    """Given an iterable of edges in a graph, return a list of the
    vertices in the lexicographically first Eulerian path in the graph
    starting at the start vertex. Edges must be represented as an
    iterables of two vertices, and a vertex may be any hashable
    object.

        >>> ''.join(eulerian_path('A', 'BC AB CD'.split()))
        'ABCD'

        >>> ''.join(eulerian_path('A', 'AB BC CA AC'.split()))
        'ABCAC'

    If the graph has no Eulerian path, raise ValueError.

        >>> ''.join(eulerian_path('A', 'AB CD'.split()))
        Traceback (most recent call last):
        ...
        ValueError: No Eulerian path

        >>> ''.join(eulerian_path('B', 'AB BC CA AC'.split()))
        Traceback (most recent call last):
        ...
        ValueError: No Eulerian path

    """
    # Build directed graph.
    graph = defaultdict(list)
    for v, w in edges:
        graph[v].append(w)

    # Sort neighbours of each vertex in reverse order.
    for neighbours in graph.values():
        neighbours.sort(reverse=True)

    start = Link(start)    # First vertex on the Eulerian path.
    unvisited = [start]    # Stack of vertices that might have unvisited edges.
    while unvisited:
        cur = loop = unvisited.pop()
        # Follow edges until a dead end is reached.
        neighbours = graph[cur.vertex]
        while neighbours:
            if len(neighbours) > 1:
                unvisited.append(cur)
            cur = cur.insert(Link(neighbours.pop()))
            neighbours = graph[cur.vertex]
        # Each dead end (except possibly the first) must complete a loop.
        if cur.vertex != loop.vertex and cur.next is not None:
            raise ValueError("No Eulerian path")

    # All edges must be traversed.
    if any(graph.values()):
        raise ValueError("No Eulerian path")

    # Reconstruct path from linked list.
    path = []
    while start is not None:
        path.append(start.vertex)
        start = start.next
    return path

4. Performance

Hierholzer's algorithm requires no backtracking, and solves the problem in time that's linear in the size of the graph. Whereas the code in the post potentially follows all simple paths in the graph, and in the worst cases takes time that's exponential in the size of the graph.

Here's one way to generate some test graphs that demonstrate the problem.

from itertools import product

def test_graph(n):
    "Generate edges in a test graph with n vertices."
    yield from product(range(2, n), repeat=2)
    yield 1, 2
    yield 1, n
    yield n, 1

The code in the post takes nearly 3 seconds to find an Eulerian path in the test graph with six vertices:

>>> from timeit import timeit
>>> timeit(lambda:reassemble_flights(1, test_graph(6)), number=1)
2.905132247833535

By comparison, eulerian_path is 30,000 times faster on the same graph:

>>> timeit(lambda:eulerian_path(1, test_graph(6)), number=1)
9.236903861165047e-05

(See this answer for an explanation of why following all simple paths in a graph leads to exponential runtime.)