Efficient Mutable Graph Representation in Prolog?

Question

I would like to represent a mutable graph in Prolog in an efficient manner. I will searching for subsets in the graph and replacing them with other subsets.

I've managed to get something working using the database as my 'graph storage'. For instance, I have:

:- dynamic step/2.
% step(Type, Name).

:- dynamic sequence/2.
% sequence(Step, NextStep).

I then use a few rules to retract subsets I've matched and replace them with new steps using assert. I'm really liking this method... it's easy to read and deal with, and I let Prolog do a lot of the heavy pattern-matching work.

The other way I know to represent graphs is using lists of nodes and adjacency connections. I've seen plenty of websites using this method, but I'm a bit hesitant because it's more overhead.

Execution time is important to me, as is ease-of-development for myself.

What are the pros/cons for either approach?

Badalona

Answer 1

As usual: Using the dynamic database gives you indexing, which may speed things up (on look-up) and slow you down (on asserting). In general, the dynamic database is not so good when you assert more often than you look up. The main drawback though is that it also significantly complicates testing and debugging, because you cannot test your predicates in isolation, and need to keep the current implicit state of the database in mind. Lists of nodes and adjacancy connections are a good representation in many cases. A different representation I like a lot, especially if you need to store further attributes for nodes and edges, is to use one variable for each node, and use variable attribtues (get_attr/3 and put_attr/3 in SWI-Prolog) to store edges on them, for example [edge_to(E1,N_1),edge_to(E2,N_2),...] where N_i are the variables representing other nodes (with their own attributes), and E_j are also variables onto which you can attach further attributes to store additional information (weight, capacity etc.) about each edge if needed.

Dupuy

Thank you... I think I will stay with the dynamic database. It's easier to work with, easier to explain to other developers, and graph searching (I believe) will take up most of the execution time. The attributes on each node, however, I may use in another part of the program. Thanks for letting me know about that! – Badalona

Answer 2

Have you considered using SWI-Prolog's RDF database ? http://www.swi-prolog.org/pldoc/package/semweb.html

Flagrant

Answer 3

as mat said, dynamic predicates have an extra cost.
in case however you can construct the graph and then you dont need to change it, you can compile the predicate and it will be as fast as a normal predicate.

usually in sw-prolog the predicate lookup is done using hash tables on the first argument. (they are resized in case of dynamic predicates)

another solution is association lists where the cost of lookup etc is o(log(n))
after you understand how they work you could easily write an interface if needed.

in the end, you can always use a SQL database and use the ODBC interface to submit queries (although it sounds like an overkill for the application you mentioned)

Sarchet