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

Graphs

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

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.

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.