Programming paradigms

Pathfinding in directed graphs – brief introduction to Prolog

Let’s imagine, that you have directed graph (like this I drawn and pasted below) and you have to write some part of code to find all paths between two nodes. Why not to do that using another paradigm than those to which we have got used to?

untitled-diagram

You may have heard about programming in logic or logic programming. Languages, that realize this paradigm demands from you another approach than imperative ones. Today I am going to show you how to write application in Prolog, that find paths in graph. Developing in Prolog is like telling WHAT we want, but not HOW to achieve demanded results.

Let’s begin with defining nodes, that are on our beautiful picture:

node(1).
node(2).
node(3).
node(4).
node(5).

As you can see it was pretty simple. The only thing you have to know at this stage is that those 5 instructions above are not function calls, but terms. As a side note, we could also write something like:

foo(“bar”).

It is also correct term. What is more – you could use this term in the way you want, because term is relation between its name and parameter(s). For Prolog it does not matter how stupid relation defined by developer is:

barks(“dog”).
barks(“tree”).

Since we know now how to write terms in Prolog, we can define edges between nodes:

edge(1,2).
edge(2,4).
edge(1,4).
edge(2,3).
edge(3,4).
edge(2,1).
edge(1,1).
edge(4,5).

If you analyze lines above it becomes straight forward. Each term edge describes edge between two nodes, which maps lines between nodes in the picture.

Our next step is to define rule, that will go step by step from one node (Start) to another (Stop). Each and every rule is defined using other rules and terms in the way:

rule :- termA, termB.

Which means, that rule is true if termA and termB are also true. What is important here is that each and every rule and term return true (yes) or false (no) value. Always. That is the reason there is joke about Prolog:

– How many prolog programmers does it take to change a lightbulb?

– Yes.

The rule that we want takes four parameters:

  • first node (Start)
  • last node (Stop)
  • list with nodes from Start to next node, that will be expanded within each step (CurrPath – initially contains Start node)
  • list with nodes from Start to Stop, which will contain whole path at the end of processing (Path – initially empty)

Searching path in graph demands from us recursive rule. To do that, we need to define finishing step of recursion beforehand:

path(Stop,Stop,Path,Path).

Above term means, that path finishes when Start and Stop nodes are the same one and when CurrPath is equal to Path, which means, that there is no other nodes to go from current visited. If it is unclear, it should become when you read rule that goes afterwards:

path(Start,Stop,CurrPath,Path):- Start\=Stop, edge(Start,Next),\+member(Next,CurrPath),append(CurrPath,[Next],L),path(Next,Stop,L,Path).

This rule means, that when we are looking for path:

  • Start and Stop nodes should not be the same one
  • there is edge between Start and some other node (Next)
  • other node (Next) does not exist in current analyzed path (CurrPath)

If all of these conditions are fulfilled we can finally concatenate Next to current analyzed path and put it to new list (L) and call path searching from Next node to Stop with modified analyzed path (L). As a reminder – resulting path will be available under Path name at the end.

At this step we have working application and we can start asking questions to interpreter, but we will write more rules, that allow us to write shorter queries:

findPath(Start,Stop):- node(Start),node(Stop),forall(path(Start,Stop,[Start],P), writeln(P)).

By calling findPath(X,Y) we will get listed all paths from X to Y nodes. This rule will check beforehand if both passed values are nodes and then will look for paths initializing analyzed paths with X node. forall and writeln are predefined rules.

showNodes:- forall(node(X), writeln(X)).
showEdges:- forall(edge(X,Y), writeln(X – Y)).
showEdges(X):- forall(edge(X,Y), writeln(X – Y)).

We can also define shortcuts for writing all nodes, all edges and also all edges from specific node like I did above. I think, that at this step everything is more or less understandable, but will become pretty clear, when we run those queries using some interpreter.

For running our code we will use online interpreter for SWI-Prolog (Prolog implementation) which is called SWISH.

On the start page you have to choose Program and paste our code on the left side:

screenshot-from-2017-02-10-11-54-25

screenshot-from-2017-02-10-12-04-21

On the right bottom side we will write our queries and run them with Run! button:

screenshot-from-2017-02-10-12-09-13

You can also check table results checkbox to have results listed in table:

screenshot-from-2017-02-10-12-10-37

As you can see, we ask Prolog to show us all edges by writing terms or rules with uppercase letters/words, because lower or camelCase will be treated as string values:

screenshot-from-2017-02-10-12-11-29

Finally, to find all paths between two nodes, we have to call something like below:

screenshot-from-2017-02-10-12-17-15

I hope, that trying another programming paradigm was interesting for you and you will come back to programming in prolog or at least try to implement some other interesting examples on your own. At the very end remember one thing – if you can come problem down to graph, it is probably solvable using Prolog.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s