Prolog Loves Graphs

How to use prolog to implement graph traversal

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.


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.

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 Djikstra. 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 more easy 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.


Wikipedia. Prolog

Python Patterns — Implementing Graphs

Djikstra algorithm implementation

Python graph implementation

Find path between two nodes in graph. Prolog discussion thread

SO. create graphs using networkx

Joydeep Bhattacharjee