How to represent directed cyclic graph in Prolog with direct access to neighbour verticies

Question

I need to construct directed graph (at runtime) with cycles in Prolog and I am not sure know how to represent it. My requirement is that I need to get from one vertex to his neigbour in a constant time.

Is it possible to represent it as a tree, e.g.:

t(left_son,V,right_son)

but how to solve the cycles?

I can make a list of edges:

graph([a,b,c,d],[e(a,b),e(b,c),e(c,a),e(c,d)])

OR just

[a->[b],b->[c],c->[a,d],d->[]]

but how to avoid calling function 'member' on list while searching for neighbours, which cost linear time?

Thanks for your help

Answer 1

If your graph has less vertices than max arity allowed by your Prolog (for instance SWI-Prolog has unlimited arity), you could represent the edges as indices of arguments:

could be

G = graph(a-[2],b-[3],c-[1,4],d-[2]).

then use arg(Edge, G, Vert-Edges) to access neighbours.

Of course any Prolog will let you describe the graph using facts. This is also the preferred way for very large graphs.

:- dynamic edge/2.

edge(a,b).
edge(b,c).
edge(c,a).
edge(c,d).
edge(d,b).

edit The edge/2 relational representation also get the (potentially large) benefits of automatic indexing.

more edit I totally forgot RDF and Semantic Web. Really powerful, we are going toward that.

Answer 2

In addition to the representation that @chac suggests, you can also consider using attributed variables (if your Prolog system supports it), especially if you need to attach further attributes to vertices or edges during your calculations. In this representation, you would use a unique variable for each vertex, attach (with put_attr/3) an attribute like "name" to it if necessary, and attach an additional attribute like "edges" which may for example be a list of vertices, or a list of terms edge(E,Vertex), where E is again a variable to which you can attach further attributes if you need to keep track of information that affects edges.

Answer 3

There is library(ugraphs) in many Prolog systems like YAP, SWI, SICStus, Ciao. (Please feel free to add further references here!) There, graphs are represented as a list of pairs Vertex-Neighbours. At first sight you might get the impression that this is not a very efficient representation. After all, access to a single vertex is proportional to the list's length. However, direct access to a vertex is rarely of interest. Most of the time a graph will be processed in one fell swoop - which often amortizes access costs.