In [2]:
%%HTML
<style>
.container { font-size: 17px; line-height: 22px; width: 100%; }
.CodeMirror-code { font-size: 17px; line-height: 20px; }
</style>
The notebook Set.ipynb implements sets as
AVL trees.
The API provided by Set offers the following functions and methods:
Set() creates an empty set.S.isEmpty() checks whether the set Sis empty.S.member(x) checks whether x is an element of the given set S.S.insert(x) inserts x into the set S.
This does not return a new set but rather modifies the given set S.S.delete(x) deletes x from the set S.
This does not return a new set but rather modifies the set S.S.pop() returns the smallest element of the set S.
Furthermore, this element is removed from the given set S.Since sets are implemented as ordered binary trees, the elements of a set need to be comparable, i.e. if
x and y are inserted into a set, then the expression x < y has to be defined and has to return a
Boolean value. Furthermore, the relation < has to be a
linear order.
The class Set can be used to implement a priority queue that supports the
removal of elements.
In [ ]:
%run Set.ipynb
The function call shortest_path takes a node source and a set Edges.
The function shortest_path takes two arguments.
source is the start node. Edges is a dictionary that encodes the set of edges of the graph. For every node x the value of Edges[x] has the form
$$ \bigl[ (y_1, l_1), \cdots, (y_n, l_n) \bigr]. $$
This list is interpreted as follows: For every $i = 1,\cdots,n$ there is an edge
$(x, y_i)$ pointing from $x$ to $y_i$ and this edge has the length $l_i$.The function returns the dictionary Distance. For every node u such that there is a path from source to
u, Distance[u] is the length of the shortest path from source to u. The implementation uses
Dijkstra's algorithm and proceeds as follows:
Distance is a dictionary mapping nodes to their estimated distance from the node
source. If d = Distance[x], then we know that there is a path of length d leading
from source to x. However, in general we do not know whether there is a path shorter
than d that also connects the source to the node x.shortest_path maintains an additional variable called Visited.
This variable contains the set of those nodes that have been visited
by the algorithm.
To be more precise, Visited contains those nodes u that have been removed from the
Fringe and for which all neighboring nodes, i.e. those nodes y such that
there is an edge (u,y), have been examined. It can be shown that once a node u is added to
Visited, Distance[u] is the length of the shortest path from source to u.Fringe is a priority queue that contains pairs of the form (d, x), where x is a node and d
is the distance that x has from the node source. This priority queue is implemented as a set,
which in turn is represented by an ordered binary tree. The fact that we store the node x and the
distance d as a pair (d,x) implies that the distances are used as priorities because pairs are
compared lexicographically.
Initially the only node that is known to be
reachable from source is the node source. Hence Fringe is initialized as the
set { (0, source) }.Fringe is not empty, line 7 of the implementation removes that node u
from the set Fringe that has the smallest distance d from the node source.u are visited. If there is an edge (u, v) that has length l,
then we check whether the node v has already a distance assigned. If the node v already has the
distance dv assigned but the value d + l is less than dv, then we have found a
shorter path from source to v. This path leads from source to u and then proceeds
to v via the edge (u,v).v had already been visited before and hence dv=Distance[v] is defined, we
have to update the priority of the v in the Fringe. The easiest way to do this is to remove
the old pair (dv, v) from the Fringe and replace this pair by the new pair
(d+l, v), because d+l is the new estimate of the distance between source and v and
d+l is the new priority of v.u, u is added to the set of those nodes that have
been Visited.Fringe has been exhausted, the dictionary Distance contains the distances of
every node that is reachable from the node source
In [ ]:
def shortest_path(source, Edges):
Distance = { source: 0 }
Visited = { source }
Fringe = Set()
Fringe.insert( (0, source) )
while not Fringe.isEmpty():
d, u = Fringe.pop() # get and remove smallest element
for v, l in Edges[u]:
dv = Distance.get(v, None)
if dv == None or d + l < dv:
if dv != None:
Fringe.delete( (dv, v) )
Distance[v] = d + l
Fringe.insert( (d + l, v) )
Visited.add(u)
return Distance
The version of shortest_path given below provides a graphical animation of the algorithm.
In [ ]:
def shortest_path(source, Edges):
Distance = { source: 0 }
Visited = { source } # set only needed for visualization
Fringe = Set()
Fringe.insert( (0, source) )
while not Fringe.isEmpty():
d, u = Fringe.pop()
display(toDot(source, u, Edges, Fringe, Distance, Visited))
print('_' * 80)
for v, l in Edges[u]:
dv = Distance.get(v, None)
if dv == None or d + l < dv:
if dv != None:
Fringe.delete( (dv, v) )
Distance[v] = d + l
Fringe.insert( (d + l, v) )
Visited.add(u)
display(toDot(source, None, Edges, Fringe, Distance, Visited))
return Distance
In [ ]:
import graphviz as gv
The function $\texttt{toDot}(\texttt{source}, \texttt{Edges}, \texttt{Fringe}, \texttt{Distance}, \texttt{Visited})$ takes a graph that is represented by
its Edges, a set of nodes Fringe, and a dictionary Distance that has the distance of a node from the node source, and set Visited of nodes that have already been visited.
In [ ]:
def toDot(source, p, Edges, Fringe, Distance, Visited):
V = set()
for x in Edges.keys():
V.add(x)
dot = gv.Digraph(node_attr={'shape': 'record', 'style': 'rounded'})
dot.attr(rankdir='LR', size='8,5')
for x in V:
if x == source:
dot.node(str(x), color='blue', shape='doublecircle')
else:
d = str(Distance.get(x, ''))
if x == p:
dot.node(str(x), label='{' + str(x) + '|' + d + '}', color='magenta')
elif x in Distance and Fringe.member( (Distance[x], x) ):
dot.node(str(x), label='{' + str(x) + '|' + d + '}', color='red')
elif x in Visited:
dot.node(str(x), label='{' + str(x) + '|' + d + '}', color='blue')
else:
dot.node(str(x), label='{' + str(x) + '|' + d + '}')
for u in V:
for v, l in Edges[u]:
dot.edge(str(u), str(v), label=str(l))
return dot
In [ ]:
Edges = { 'a': [ ('c', 2), ('b', 9)],
'b': [('d', 1)],
'c': [('e', 5), ('g', 3)],
'd': [('f', 2), ('e', 4)],
'e': [('f', 1), ('b', 2)],
'f': [('h', 5)],
'g': [('e', 1)],
'h': []
}
In [ ]:
s = 'a'
sp = shortest_path(s, Edges)
sp
Four persons, Alice, Britney, Charly and Daniel have to cross a tunnel. The tunnel is so narrow, that at most two persons can cross it together. In order to cross the tunnel, a torch is needed. Together, they only have a single torch.
What is the fastest plan to cross the tunnel?
We will model this problem as a graph theoretical problem. The nodes of the graph will be sets of people. In particular, it will be the set of people at the entrance of the tunnel. In order to model the torch, the torch can also be a member of these sets.
In [ ]:
All = frozenset({ 'Alice', 'Britney', 'Charly', 'Daniel', 'Torch' })
The timining is modelled by a dictionary.
In [ ]:
Time = { 'Alice': 1, 'Britney': 2, 'Charly': 4, 'Daniel': 5, 'Torch': 0 }
The function $\texttt{power}(M)$ defined below computes the power list of the set $M$, i.e. we have: $$ \texttt{power}(M) = 2^M = \bigl\{A \mid A \subseteq M \bigr\} $$
In [ ]:
def power(M):
if M == set():
return { frozenset() }
else:
C = set(M) # C is a copy of M as we don't want to change the set M
x = C.pop() # pop removes the element x from the set C
P1 = power(C)
P2 = { A | {x} for A in P1 }
return P1 | P2
If $B$ is a set of persons, then $\texttt{duration}(B)$ is the time that this group needs to cross the tunnel.
$B$ also contains 'Torch'.
In [ ]:
def duration(B):
return max(Time[x] for x in B)
$\texttt{left_right}(S)$ describes a crossing of the tunnel from the entrance at the left side left to the exit at the right side of the tunnel.
In [ ]:
def left_right(S):
return [(S - B, duration(B)) for B in power(S) if 'Torch' in B and 2 <= len(B) <= 3]
$\texttt{right_left}(S)$ describes a crossing of the tunnel from right to left.
In [ ]:
def right_left(S):
return [(S | B, duration(B)) for B in power(All - S) if 'Torch' in B and 2 <= len(B) <= 3]
In [ ]:
Edges = { S: left_right(S) + right_left(S) for S in power(All) }
len(Edges)
The function shortest_path is Dikstra's algorithm. It returns both a dictionary Parent containing
the parent nodes and a dictionary Distance with the distances. The dictionary Parent can be used to
compute the shortest path leading from the node source to some other node.
In [ ]:
def shortest_path(source, Edges):
Distance = { source: 0 }
Parent = {}
Fringe = Set()
Fringe.insert( (0, source) )
while not Fringe.isEmpty():
d, u = Fringe.pop()
for v, l in Edges[u]:
dv = Distance.get(v, None)
if dv == None or d + l < dv:
if dv != None:
Fringe.delete( (dv, v) )
Distance[v] = d + l
Fringe.insert( (d + l, v) )
Parent[v] = u
return Parent, Distance
In [ ]:
Parent, Distance = shortest_path(frozenset(All), Edges)
Let us see whether the goal was reachable and how long it takes to reach the goal.
In [ ]:
goal = frozenset()
Distance[goal]
Given to nodes source and goal and a dictionary containing the parent of every node, the function
find_path returns the path from source to goal.
In [ ]:
def find_path(source, goal, Parent):
p = Parent.get(goal)
if p == None:
return [source]
return find_path(source, p, Parent) + [goal]
In [ ]:
Path = find_path(frozenset(All), frozenset(), Parent)
In [ ]:
def print_path():
total = 0
print("_" * 81);
for i in range(len(Path)):
Left = set(Path[i])
Right = set(All) - set(Left)
if Left == set() or Right == set():
print(Left, " " * 25, Right)
else:
print(Left, " " * 30, Right)
print("_" * 81);
if i < len(Path) - 1:
if "Torch" in Path[i]:
Diff = set(Path[i]) - set(Path[i+1])
time = duration(Diff)
total += time
print(" " * 20, ">>> ", Diff, ':', time, " >>>")
else:
Diff = set(Path[i+1]) - set(Path[i])
time = duration(Diff)
total += time
print(" " * 20, "<<< ", Diff, ':', time, " <<<")
print("_" * 81)
print('Total time:', total, 'minutes.')
In [ ]:
print_path()
In [ ]: