Graph traversal

Implementation in Python 3 of the graph traversal algorithms seen during the course and during the TD 1.

Copy/past the code and the tests to a Python file you open in your favorite IDE.

Exercise plan:

• Breadth-First Search ;
• Depth-First Search ;
• Bipartite graphs
• 2-coloring ;

Before starting the exercises, please install the Python module networkx to be able to display graphs. Depending on your distribution/OS, you may use the Anaconda GUI or try this command: pip3 --user install "networkx>=2.2"

A set of functions are defined in the first cells. They help to load data to test and to verify the produced solutions, etc. Run the following cell/code to import these modules that we provide but we hide:

# TO RUN 
import zlib, base64
exec(zlib.decompress(base64.b64decode(b'eJzNV82O47gRPq+fguM5WNpWvHbPzs50A50gWSSNPW2A7M1oGLREydyRRIWS2nYa/T7pfYOc/WL5iqT+3ZNGkEMM2JbIqmL9flWMtcqY5nmEP5kVSlfmTebVzL3mojoo/eXIeMnyY7Oa8apIVZXK3bI40RNtF2nV298HTvBsFonYPW8TzYu9lwcsC9hByGRfleyO/YWnpfBvZwyf+Xxu/n/UgldS5Yyn5xdeKakFixZ1zowIwfijCFnOSpVlAkIEDmVcn3+rRLk0AlIBlZSMSlbW2ry5bfDkFRM5UwUd8M03g3MT6PMkb5+eWaw0k0zmpHsivNx/NgSj5czpTZ8jeJ3/vFWQ/27tt1un17cOe5kKEEBksjk+MMiHoDt26gRPhbOBiOkJdt/ZRh8Ztw4fyj0MNfs2G4ollTanBxAdRuunB9K2vy4QxpH0jv0XXYtXJLRbWlS1hhtmNmlSxSOXMol/ywZxioQoWKiKUz8rGgo2+czan2RruBDlvIlybnzfhde+d4bQWmbjkz+M7DPSsLzJyJLEPg2MsecxZ1MkyyLlJ2dW5h4ClvId3Hf39IzQqUiAKVXavIoomby21KOq+WMcyxDV0dUJ8ryuZCpLjqRPOUPNtkVtC+XnnBWirlhZnF9CGUuh4dzSKYQSctWTK1FHZWD2bF21W66wjLRQ1amo9YSRKnS6N6jYH7Egczg7M5XvCrWsVPjl/IK9iGONjo9kSAQ5Byg4XvPzVw7Vzy8xhzW9k40YreoExOwn2JQLsvhRYLngpBmwZZfyPGQhJABzLIHdDfdKlpJ8wtKFqgF6uVgOnG7hhu8Iyp5GINEE+LZfiGbH+XeYTiRlIymTFvmCXcF47Ul/WReF0J7Prha3iytas8yg9L9WfF+XNrPgkJvUAs3Gpi306xKQcOjpuZPaEi/0YtacOiyUV8zum96TD+DpvRpl79hqyNYdvORQPY+8BTCzEoshUon0TfLfvUU+lD9NxPctfYVPi6hjM//3cFZ+XN6bcrdb90seRVvSqtzG6MAtCiy/iFPp+X6bQsfLvqStU38LMDrxdG/PALCF2akFVhtCFe8YsNNbjB6xNK0clg4P9bvy6EBsW54yUyjtHplTB49kUEfmfNEdPpSw8R6D2qfU7tY3HqT4D6PzkO4Rr4Q35LeqiTb3e/SJqDwjKWBzoEL4Ze4bFc0aKXm/JGoo99DZV6jSBjrWdbivBDAs32oh80SlEeD6BOTw7gNWChHdXfvsPeM1K2TcSQBvpPmBiBy6U/kGQ+fHgLJtKf8h7tZr1yjM26fVakQJhe7wHa32WovN3EF7EW7pIKNqf7defuwFEBnV6zy9sDjg6222wMCmZLAS/jW5s+VVpeWuBv7D6IXNIVc9zhnbplNte+JBTIb1+6CRbjkxhS7LvTqg1mzDNXXmmax02eQaM3pi5Q3rznGQJjulHVdwdHwGGStblKOK1FzC3D8fQ2FmSm9h6p1FynQh6nx5xR0ysVtmQfzoKn2iD6qnUalxv4nD7D019hJDNgbGgmv0UzRTQb1EJ2is7O+1BOLhQGpt1AHBgYGjQmsTtnW6lviIlladX0qSAuULM7Vzmg80D9HgjB92GMGRCNtY6hJZJ3DgfnuQWGllOg+huyoq/5XzlBEvoq4fVmpr1qjUPCIOQGvLx46/qci9hshnv+9DtBcGkQ/GZntZqMJbdTiFsITGyfCvO3gIWW5xExJcRIMtqmsDPOOYs9Cf4l6rgYN7YFB0tR5G0R3mUumRp5LQZ7uLSw/fbVzj8pPvfhFlVboT3tPEkYhcYArhqbB3nYwi6Oho9ED2pHBTYib1koY5cek28iEYyqZP4gb89volm6vZspv7PfmtJ3Fl+O67a9+f3s1wkzBqYpSVFKz2FlZjZCqZOv/LpNv5JT3/8xEPlIBkQWSIMxWZubJ3HUlIq8F8P2v34EKTYaB4UwpSLvWZic+62kvsZj9XKNNA5NMg4J6NsKbihmEvNPln/nNdYPQFiKOkTa7tcf9kFTygTefL62yHuVnFNv7lu7l/ScyJ5l5MsQfQynIeEDW6DAWRZMUqTdUBPcO6d+73RQzkDW8RyfAwm4md0ST+1y5HGgcg2reIKwIbifrYIANBCKCsrKWZjyNl//kjspLwIUNqwhyFThQR5MAlOwkIWuMeJjA+V+M5pPHvBg+bXx/MADZcu1pjlQa1CekVxF4kn9bmIFAAGjTarDQRyziykGO20FrpcWB6rH9TsGwv0gIAjSgTaw1PcIzNGALYH17n/J+F9T+Gdhxep8CfNOLzjszGjaWke1Wa0tHzFmugTmWwxNvRVQ83wtTkMadYqthfwrqZOXK1JtherBa3+P0evzQ2Bmzx0T3iCrpYm82bbvO6e/zQPX7uHnuCPvUEXRtB627zhyn3sxM6oPt8WbHvDd2q21xP6XqnPLvlAcuHi1rfXDy7L+gHI+j6IvfHy+Z/+or5Nz26z2O6y/7+eJn7Zsx9QZu+v5+bTLh+ayZcNvq/D/RbQ/rWOP4fBO/6sv9uBvb2T0AU/g0fvUBP')))

The next cell/code allows the loading of a graph to test and displays it.

my_graph=load_graph(graph01)
display_graph(my_graph)

Breadth-First Search

Complete the function breadth_first_search(graph, root). It takes as parameter a graph and the label(number) of a root vertex. It returns a list of vertices in the order of visit.

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

• nodes (graph): returns the list of vertices of graph.
• neighbors (graph, x): returns the list of neighboring vertices of x in the graph.

def breadth_first_search(graph, root = '0'):
    visited = []

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


    return visited

my_bfs=breadth_first_search(my_graph, '0')
print('the order of visit is :', my_bfs)
display_graph(my_graph, labels={v: my_bfs.index(v) for v in my_bfs})

To verify that your algorithm is working properly, we will perform a set of tests, run the following cell:

validate_bfs(breadth_first_search, nbTests = 10)

Bipartite graphs

In this part we will determine if a graph is bipartite. As we studied in TD1, we can rely on the BFS algorithm. We compute the depth/distance of each node starting from any root. A graph is bipartite if there is no edge between two nodes having the same depth.

Adapt your BFS algorithm so that it returns a dictionary depth which entries are of the form vertex: depth.

def breadth_first_search_depth(graph, root):
    depth = { root : 0 }

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


    return depth

depth=breadth_first_search_depth(my_graph,'0')
print('the depths are :',  depth)
display_graph(my_graph, labels=depth)

Write a function is_bipartite(graph) to test whether the graph given as parameter is bipartite.

def is_bipartite(graph):

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


    return True

my_graph1=load_graph(graph01) 
assert not is_bipartite(my_graph1)

my_graph2=load_graph(graph02) 
assert is_bipartite(my_graph2)

2-Coloring

We want to write a recursive algorithm, which takes as input a graph and returns a pair result, color where:

• result is True if the graph is 2-colorable, False if not and
• color is a dictionary associating to each vertex a color 0 that is white or 1 that is gray.

This algorithm should may stop when the graph is not 2-colorable.

# recursive function called by coloring
def coloring2_rec(graph, n, color):

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


    return True

# the main call function for recursive version
def coloring(graph):
    root = nodes(graph)[0]
    color = {root:0}
    return coloring2_rec(graph, root, color), color

# tests
res, color = coloring(my_graph)
print('the colors are :',  color)
assert not res
display_graph(my_graph, node_color=color) # red = not colored

my_graph2=load_graph(graph02) 
res, color = coloring(my_graph2)
print('the colors are :',  color)
assert res
display_graph(my_graph2, node_color=color)