Blog
Graphs in Python and Prolog for Shortest Paths
Graphs are omnipresent in today’s computing world. From implementing compilers to computer games to maps, you will need to use graphs everywhere. In case you are a programmer and not sure what is a graph or any of the major graph algorithms, please take a look at these books on graph algorithms. In this blog, we will be talking about graphs in python and prologGraphs Let’s build a graph and see what the solution using standard techniques look like. First, let’s define a graph. We will define the graph in Python and try to visualize it as well.graph = {'a': {'w': 14, 'x': 7, 'y': 9},'b': {'w': 9, 'z': 6},'w': {'a': 14, 'b': 9, 'y': 2},'x': {'a': 7, 'y': 10, 'z': 15},'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11},'z': {'b': 6, 'x': 15, 'y': 11}}This can be visualized in Python using the libraries networkx and matplotlib.%matplotlib inlineimport networkx as nximport numpy as npimport matplotlib.pyplot as pltimport pylab# initialise a directed graphG = nx.DiGraph()# add the edges and the weights.G.add_edges_from([('A', 'W')], weight=14)G.add_edges_from([('A', 'X')], weight=7)G.add_edges_from([('A', 'Y')], weight=9)G.add_edges_from([('B', 'W')], weight=9)G.add_edges_from([('B', 'Z')], weight=6)G.add_edges_from([('W', 'A')], weight=14)G.add_edges_from([('W', 'B')], weight=9)G.add_edges_from([('W', 'Y')], weight=2)G.add_edges_from([('X', 'A')], weight=7)G.add_edges_from([('X', 'Y')], weight=10)G.add_edges_from([('X', 'Z')], weight=15)G.add_edges_from([('Y', 'A')], weight=9)G.add_edges_from([('Y', 'W')], weight=2)G.add_edges_from([('Y', 'X')], weight=10)G.add_edges_from([('Y', 'Z')], weight=11)G.add_edges_from([('Z', 'B')], weight=6)G.add_edges_from([('Z', 'X')], weight=15)G.add_edges_from([('Z', 'Y')], weight=11)# value map so that we have different colors for different nodesval_map = {'A': 1.0,'B': 0.9,'W': 0.8,'X': 0.7,'Y': 0.6,'Z': 0.5}values = [val_map.get(node, 0.45) for node in G.nodes()]edge_labels=dict([((u,v,),d['weight'])for u,v,d in G.edges(data=True)])red_edges = [('A','Y'),('Y','W'), ('W', 'B')]edge_colors = ['black' if not edge in red_edges else 'red' for edge in G.edges()]node_labels = {node:node for node in G.nodes()}plt.axis('off')fig = plt.figure(1)fig = plt.figure(num=1, figsize=(10, 10), dpi=100)fig.set_size_inches(10.5, 10.5)# draw it out.pos=nx.spring_layout(G)nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)nx.draw_networkx_labels(G, pos, labels=node_labels)nx.draw(G,pos, node_color = values, node_size=1500,edge_color=edge_colors,edge_cmap=plt.cm.Reds)xmax = 1.2ymax = 1.1plt.xlim(-0.1, xmax)plt.ylim(-0.1, ymax)pylab.show()pylab.close()del figTo find the shortest path using python you probably will need to implement a known algorithm such as Dijkstra. You can try to look at the code linked here which I would argue is huge. The implementation will be the same in almost all object oriented and procedural code. But in Prolog, due to many things being handled by the compiler, the code gets reduced a lot.No need to write node classes or priority queuesJust write the relationships between the nodes and edges in a simple, clean manner.edge(a,w,14).edge(a,x,7).edge(a,y,9).edge(b,w,9).edge(b,z,6).edge(w,a,14).edge(w,b,9).edge(w,y,2).edge(x,a,7).edge(x,y,10).edge(x,z,15).edge(y,a,9).edge(y,w,2).edge(y,x,10).edge(y,z,11).edge(z,b,6).edge(z,x,15).edge(z,y,11).Now, looking at the code that crunches the numbers.findapath(X, Y, W, [X,Y], _) :- edge(X, Y, W). % findapath between X and Y has weight W if there is an edge between X and Y of weight Wfindapath(X, Y, W, [X|P], V) :- % else findapath between X and Y \+ member(X, V), % is trueedge(X, Z, W1), % if we can findapath between X and Z with weight W1findapath(Z, Y, W2, P, [X|V]), % and there is findapat between Z and Y of weight W2W is W1 + W2. % where W is W1 + W2:-dynamic(solution/2).findminpath(X, Y, W, P) :-\+ solution(_, _),findapath(X, Y, W1, P1, []),assertz(solution(W1, P1)),!, findminpath(X,Y,W,P).findminpath(X, Y, _, _) :-findapath(X, Y, W1, P1, []),solution(W2, P2),W1 < W2,retract(solution(W2, P2)),asserta(solution(W1, P1)), fail.findminpath(_, _, W, P) :- solution(W,P), retract(solution(W,P)).main :- findminpath(a,b,W,P), write('the minimum cost that we must pay.'), write(W), nl, write('path that has the minimum cost.'), write(P), nl, halt.A huge shout-out to Rodney who has made a brilliant description of the above code.Last ThoughtsIn many cases involving graphs, Prolog helps us in writing clear and concise code. It is easier to express some data structures using Prolog that needs more careful code writing with intricate testing to come to the same solution.In case you found this interesting and would like to talk more on this, just drop me a message @alt227Joydeep. I would be glad to discuss this further. You can also hit the like button and follow me here, on Medium.References:Wikipedia. PrologPython Patterns — Implementing GraphsDjikstra algorithm implementationPython graph implementationFind path between two nodes in graph. Prolog discussion threadSO. create graphs using networkx
Learn More >