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.