TD02 - Paths and trees

Implementation in Python of the Dijkstra algorithm, the Prim algorithm and the Kruskal algorithm seen during the course and during the TD 2. A set of functions are defined and loaded during the execution of the first cell. They help to load data to test and to verify the produced solutions, etc.

Each function you need to complete is followed by tests to verify that the produced result is correct.

The graphs are represented as dictionaries and you can use the following Python functions:

• nodes (graph): returns the list of vertices of graph.
• neighbors (graph, x): returns the list of neighboring vertices of x in the graph.
• distance (graph, x, y): returns the distance between the vertices x and y of the graph, or None if they are not neighbors.

Exercise plan :

• Shortest Path ;
• Minimum Spanning Tree : Prim algorithm ;

Optional :

• Minimum Spanning Tree : Kruskal algorithm ;

The next cell allows the loading of the graph hameau seen in TD2 and displays it using the Python module NetworkX.

import numpy as np

# TO RUN
import zlib, base64
exec(zlib.decompress(base64.b64decode(b'eJy1V0tv4zYQPq9/xTQ9SGpUI4/tZteAD9vtbraXtij2ZhgGI41tIhIpUFRsNfD/afo3/Mc6fOjpJsilAmxSnJlvZsh5UGslc1BMpDTwvJBK2zcu9MS/CtQ7qe73wEoQ+2Y1Z7rIpM743bSozcyQi0z36NvYA08mKa79fLVRrNiGIoY8hh3yzVaXMIcvLCsxmk2AnrOzMzt+Usg0lwJYdnxiWnKFkAaVAAuBwB4wAQGlzHMkECSlwNTxH43l1AJkSCZJnpZQVsq+eTLJCA0oQBZGwZs3A70bsueRzx4PsJYKOHBhbN9gKKKDZRgt595u8+xJ1u9feBGLHy+jllQ/T9pteYbEQJCbxX4JhE9Ac6g74FNwGECcanB075t5+Lrd8CHubmjZD/kQ1pi0qJfEtBut10tjbX8d6RhH6J34N1XhMwgtSaGuFG3DxAVNJlnqQ2YTzWBwTiliAYks6n5UNBxw8kzav83KStEpi+aUhd377njde+eIWcvd+YjlyD+LRsuL3HiycbOBM04feJ9SXhYZq71buZ/EkLE72r7544GOTqZIQplU9hXTzclryz3Kmo/rNU8oO7o8oTivNM94ySjoMwaUs21Su0T5XUCBlYayOD4lfM1R0eaW3iBKIZ89QmKVlrGlubxqST6xLFoiqwwrdSJoMvSUNsjYT7TABW12bjPfJ2qpZXJ/fCJaymjNqE95YhgEo6LgZe3fH4xMPz6tGXnT02xhlKw2xAy/kk8CjccPSMsFM5ZRbbnLmEggIQSqOY7BUZOt5CU3ewJZICsqegKng0135YbdmVL2OCoSzQHP+oloKX5/h+FkUBbcRFIgAjgn51XIo2lVFKjCCM6DWXBu1pwwcUYvJd/LaBNXHIQNLeJZuLAl+7oANHXo8dChtsyBCiaN1mGiPON23/UePhWe3qs1dg4XQ7FO8ZSR6SINA6qZGoNhpcLsVfjfvQafjK9P4PuePiOnMO3E7HhLmyX201ub7o50O2VpujJWlas1deC2CkzvsS7DKGpDaP/fe2lIdZ9EZfRkp3s0W4BdmT31wFljqkq4j6F+jdMjkaaVk6dDpVGXHl0RW5V1bhOlpRl3qvjBONSx+b3olA8RFuFDXEUmtLv1RUgo0XKkj8I9ZRrDobwzDdvY7/FvUIcWKYYzqgrJ/VlkTbRrxsjbqeEm45adf4Us3UGvVZVsNVINEyuFXGxkllK5rqlyhLcxlIjp/CqC74FVUPB1h0CyqWI7w+Sru0nfeLj5ayplq5L/hfPLS98o7NvNxcWIkwya02+02mstLnIH7QX90o6neju/nP7UO0CKqF7n6R2LL3w9YlsY4JSNvKT9tbGzYlorfldR/SenAxdDPnv8ZqyaTrXqwROzcazfBy26k6Rb6LTcyh3lmmu4Ns9CG5U+mnxjpp6ow2HeeQljyZ1UXireezlbGbVLylFGKsbJ3c/7BO2dMgxsvkMqbRcynU9o5isTzMAV8b3P9BN7KHsak5rtt+fg7w+aOhV628DmbHsJcMx/oniQHE27b9jpHmC6XIrVvr0zP5jGRi110Mz+Lyc9bt3iDmrWGNpI1tTvIADuwFl7LCDXLXrdob9Y7E5M/0ZXIysBW/NlI5vLsY+/UfQ2V7lORf/gfpMCfei4wlDQ58/oYqaaI+l9h9ibDt1B6LJGd7acNobuG+XxydzZCqZYfvzbnFkpK8frPoDQBoo5Sne/aTO0UWVt6Pr56HslQ+Hso++DYXEtmy5m6dQqY3CT88ulyY2ex5Z9MtmyHKmMUTEPPgYz+v+Z/t/GEHyh8T3dVe2CIzbLH2i8pfGGxq80XtP4icZL+mYJfjGTq4Nfcngt4frgJ379yrNdeyTL+Jkm7w5+8mjZ33nNN17zu0bzwROcge+9uR+8cMP+9uAnTu1No8QLv+2jfW3ZrhtvGqOuPcr14TD5F+zfcK8=')))

hameau = load_graph(hameau)
display_graph(hameau)

Shortest Path

Complete the function dijkstra (graph, d, a). It takes as parameter a graph, the departure vertex d and the arrival vertex a. It returns a list containing the vertices in the visiting order of the shortest path between d and a. The code to retrieve the path from the parents list is given, you only need to focus and implement the shortest path algorithm in its classical form presented in previous lectures.

Test your code on the hameau example to go from A to E. You should obtain ['A', 'B', 'H', 'E']

def dijkstra(graph, d, a):
    parent = {}
    dist = {}

    # init
    for p in nodes(graph):
        parent[p], dist[p] = None, math.inf
    dist[d]=0

    frontier = [d]

    ############### TODO : complete code #####################



    # retrieve the path from the parent list
    if d == a:
        return []
    elif parent[a] == None:
        return None

    path = [a]
    current = a
    while parent[current] != None:
        current = parent[current]
        path.append(current)

    path.reverse();
    return path

# testing
path_A_E = dijkstra(hameau,'A','E')
assert path_A_E == ['A', 'B', 'H', 'E']

# displaying
edge_color = {e:"red" for e in edges(path_A_E)}
display_graph(hameau, edge_color=edge_color)

Minimum Spanning Tree : Prim algorithm

Complete the prim (graph, d) function. It takes as parameter a graph and the label of a departure vertex. It returns a list of edges corresponding to the minimum spanning tree of graph using the Prim algorithm. An edge is a pair/tuple (u, v).

def prim(graph, d):
    parent = {}
    dist = {}

    # init
    for p in nodes(graph):
        parent[p], dist[p] = None, math.inf
    dist[d]=0

    frontier = nodes(graph)

    ############### TODO : complete code #####################



    # retrieve the edges from the parent list
    edges = []
    for u in nodes(graph):
        if parent[u] != None:
            edges.append((parent[u], u))

    return edges

# testing
prim_edges = prim(hameau, 'H')
assert sum([distance(hameau, u, v) for u,v in prim_edges]) == 26 # the total weight

# displaying
edge_color = {e:"red" for e in prim_edges}
display_graph(hameau, edge_color=edge_color)

[Optional] Minimum Spanning Tree : Kruskal algorithm

Complete the kruskal (graph) function. It takes as parameter a graph and it returns a list of edges corresponding to the minimum spanning tree of graph using the Kruskal algorithm.

def kruskal(graph):

    # we sort edges depending on their weight 
    edges = sorted([(i, j) for i in nodes(graph) for j in neighbors(graph,i) if i < j], 
                   key = lambda e : distance(graph, e[0], e[1]))

    # structure for union-find
    forest = {}
    for i in graph:
        forest[i] = i

    mst = []

    ############### TODO : complete code #####################



    return mst

# testing
kruskal_edges = kruskal(hameau)
assert sum([distance(hameau, u, v) for u,v in kruskal_edges]) == 26 # the total weight

# displaying
edge_color = {e:"red" for e in kruskal_edges}
display_graph(hameau, edge_color=edge_color)