4
\$\begingroup\$

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).
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yes, I tried that with Visited nodes and Accumulated cost much like in one of the Prolog tutorials. The trouble was that I wasn't able to get the true total cost because backtracking removed some of the leaf nodes of my Visitedlist (your Vs0). For a certain path I wasn't able to pass the complete Visited list which would then be used to search sibling paths. I can share my previous attempt which does not work, if you like. \$\endgroup\$ – Jacek May 24 '16 at 10:48
  • \$\begingroup\$ Just to let you know, I added some explanation about my issue to my StackOverflow question. \$\endgroup\$ – Jacek May 24 '16 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.