1. Review
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.)

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.
The classes OrderedDefaultDict
and FlightStorage
lack docstrings.
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.
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.
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).
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.
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.
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.
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.)
return
cases inreassemble_flights
. I mean, why doesreassemble_flights('COM', [])
returns['COM']
but the last doctest returnsNone
? To me, there is no trip in either case, why differenciate the results? \$\endgroup\$reassemble_flights('COM', [])
returns something, because it is possible: you can just not go on any flights. That means you'll stay where you are. The case that returnsNone
does this because there is no way to use all plane tickets with the given startposition. \$\endgroup\$