5

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
Ondřej Kunc
  • 1,087
  • 9
  • 17

3 Answers3

9

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 this

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.

CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • 1
    A couple of observations. First the OP talks about constructing the graph "at runtime", so either dynamic predicates will be used or some complicated Prolog term will be constructed and passed around. Second the "constant time" access is presumably important just when large graphs are involved. So maybe the strategy should be doing an implementation in Prolog using the second form of representation suggested by chac, then switching to an implementation in C/C++ (or other language supporting pointer arithmetic) if and when speed becomes an issue. Clarity and correctness before optimization! – hardmath Apr 11 '12 at 03:19
7

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.

mat
  • 40,498
  • 3
  • 51
  • 78
  • 2
    this seems really interesting. How about a small example? – CapelliC Apr 16 '12 at 15:05
  • 2
    An example that was discussed in [comp.lang.prolog](http://groups.google.com/group/comp.lang.prolog/topics?lnk=srg) is finding the strongly connected components of a directed graph. The solution that was posted is here: [scc.pl](http://www.logic.at/prolog/scc.pl). For further examples, like maximum matchings and max-flow algorithms, see library(clpfd) in SWI-Prolog. These algorithms (also the SCC example) all require additional information for vertices, for example, whether it is in a stack, whether it was visited etc., and attributed variables let you easily attach and modify such attributes. – mat Apr 17 '12 at 07:09
5

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.

false
  • 10,264
  • 13
  • 101
  • 209