Module 3
A simple network

 

 
Back | Top of this Module | Next

Consider the following network that represents routes from point a to point b. There are several things to notice about this network:  
 

  • the direction of travel is from a to b, and not from b to a.
  • there are no cycles (ie you can't go round in circles)
  • there is more than route from a to b.

 
 

We will first consider how the network should be represented in Prolog. So far, we have seen how to represent facts by encoding them as structured objects, ie a functor with zero or more than arguments.

What do we want to represent? We could consider two methods: encoding the nodes or encoding the paths.

 

 
Encoding the nodes

Each node has a number, so we could start by a functor and a first argument:  
  
     node(a, ...
The first argument is the "name" of the node: the remaining arguments are used to represent each node linked to the first node.  
  
     node(a, 1, 3, 6).
     node(1, 2, 4).
     node(2, 5).
     node(3, 4, 7).
What are the arities of these objects? They are as follows:  
  
     node(a, 1, 3, 6).     arity 4
     node(1, 2, 4).        arity 3
     node(2, 5).           arity 2
     node(3, 4, 7).        arity 3
     ...
We have three different arities, even though we have represented only four nodes so far. It is possible to write Prolog programs that can handle structured objects with differing arities that represent the same kind of object, but it makes the program more complicated than necessary. (We will see when we study list processing in Prolog that it is possible to represent the destination as a single list of nodes, which would reduce the arity of node to two, but it would still be more complicated to program than the method of encoding the paths.) So the important principle is that we should choose a form of structured object that is as simple as possible, while allowing us to write the most efficient program.
 
 
Encoding the paths

Each path has one start node and one end node and thus we can immediately be certain that all path facts will have the same arity.

Here are the path facts for paths starting from node a and from node 1. 

     path(a,1).
     path(a,3).
     path(a,6).

     path(1,2).
     path(1,4).
 
Take time to work through the Self-Test 1
 
Back | Top of this Module | Next