Aggregate cost for a directed graph in Prolog

Question

I've come up with a simple graph traversal algorithm to calculate the aggregated cost of a directed graph or its subgraphs. Given a directed graph, the code visits all reachable nodes and sums up the cost related to the node paying attention to already visited nodes. The return value is the total cost of (sub)graph.

For example, for the graph embedded in the code below all the following is true:

graphCost(a, 63).
graphCost(b, 26).
graphCost(c, 60).
graphCost(f, 32).

As you can see, I wasn't able to avoid duplicated paths without using global variables. I'm new to Prolog, so would like to have someone more experienced to look at it and check whether or not it's reasonable. Perhaps there's a ready to use function to do the same? Is there a more effective way to do it?

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

cost(a, 1).
cost(b, 2).
cost(c, 4).
cost(d, 8).
cost(e, 16).
cost(f, 32).

visitAndMove2(A) :-
  \+edge(A, _),
  nb_getval('Visited', Visited),
  ( \+member(A, Visited) ->
    nb_setval('Visited', [A | Visited]),
    cost(A, C),
    nb_getval('Cost', Cost),
    TC is Cost + C,
    nb_setval('Cost', TC),
    write(' --> '), write(A), write(': '), writeln([A | Visited])
  ;
    write(A), writeln(' --|')).

visitAndMove2(A) :-
  edge(A, Child),
  A \== Child,
  nb_getval('Visited', Visited),
  \+member(Child, Visited),
  nb_setval('Visited', [Child | Visited]),
  cost(Child, C),
  nb_getval('Cost', Cost),
  TC is Cost + C,
  nb_setval('Cost', TC),
  write(A), write(' --> '), write(Child), write(': '), writeln([Child | Visited]),
  visitAndMove2(Child).

graphCost(A, Cost) :-
  nb_setval('Visited', [A]),
  cost(A, C),
  nb_setval('Cost', C),
  visitAndMove2(A),
  nb_getval('Cost', Cost).

Answer 1

Using global variables is a sure sign that you are not working within the declarative paradigm. A declarative way to solve this is to keep track of the already visited variables via an argument of your predicate.

Also, please_use_a_readable_naming_convention insteadOfMakingEverythingHardToReadAsInJava.

For example, suppose you have a relation visited_and_move(Vs0, Vs, Vertex0, Vertex), where:

• Vs0 is the list of vertices that are already visited
• Vs is the next list of such vertices
• Vertex0 is the previous vertex
• Vertex is the next vertex.

This is only an example; you may not need all arguments. However, the general approach should be clear: Think in terms of relations between entities, such as the relation between a previous list and the next one.

Such pure predicates can be used in all directions, and tested in isolation without needing to store an implicit global state.