Graphs in Python and Prolog for Shortest Paths

Category Data Engineering

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 prolog



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 inline

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import pylab

# initialise a directed graph
G = 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 nodes
val_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()]
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()}

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.
nx.draw_networkx_labels(G, pos, labels=node_labels)
nx.draw(G,pos, node_color = values, node_size=1500,edge_color=edge_colors,

xmax = 1.2
ymax = 1.1
plt.xlim(-0.1, xmax)
plt.ylim(-0.1, ymax)
del fig

To 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 queues

Just write the relationships between the nodes and edges in a simple, clean manner.







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 W
findapath(X, Y, W, [X|P], V) :-                % else findapath between X and Y
        \+ member(X, V),                       % is true
edge(X, Z, W1),                        % if we can findapath between X and Z with weight W1
findapath(Z, Y, W2, P, [X|V]),         % and there is findapat between Z and Y of weight W2
W is W1 + W2.                          % where W is W1 + W2

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 :-
    write('the minimum cost that we must pay.'),
    write('path that has the minimum cost.'),
    nl, halt.

A huge shout-out to Rodney who has made a brilliant description of the above code.

Last Thoughts

In 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.


Ready to embark on a transformative journey? Connect with our experts and fuel your growth today!