CODEWITHSUNDEEP
prolog
Suraj Nair
Suraj Nair

Reputation: 33

Deletion of Attribute Variables in Prolog

I am working on a project involving graphs, and I have a list of attribute variables, each representing a node in the graph. Each node has several attributes, such as adjacent nodes, distance to start node, etc. I want to remove a single node from the list, but when I use delete, I get the following error:

ERROR: uhook/3: Undefined procedure: adjs:attr_unify_hook/2

For example, I get this error if I include delete(OldVertices, Node, NewVertices) in my program.

I also get the exact same error if I am storing my vertices in a binary heap, and try to delete a vertex from the heap using delete_from_heap.

I was able to successfully use delete and delete_from_heap on the node if I first delete all of its attributes, but this causes problems for my program because I want to use the attributes later on; I just don't want the node to be contained in the list or binary heap.

Is this a bug, or am I handling attribute variables incorrectly?

EDIT:

Thanks! That works for lists. Now I am trying to do something similar for deleting attribute variables from binary heaps. I have a rule 

delheap(Heap, Key, NewHeap) :-  
    delete_from_heap(Heap, A1, A0, NewHeap),
    get_attr(Key, dist, A1),
    A0 == Key.

However when I am testing I get the following results:

?- TLO = [3-A, 4-B], put_attr(A, dist, 3), put_attr(B, dist, 4), list_to_heap(TLO, H), delheap(H, A, Hq).
Correct to: "dijkstra_av:delheap(H,A,Hq)"? yes
TLO = [3-A, 4-B],  H = heap(t(A, 3, [t(B, 4, [])]), 2),  Hq = heap(t(B, 4, []), 1),  put_attr(A, dist, 3),  put_attr(B, dist, 4).

Which works fine, but when I try with B :

?- TLO = [3-A, 4-B], put_attr(A, dist, 3), put_attr(B, dist, 4), list_to_heap(TLO, H), delheap(H, B, Hq).
Correct to: "dijkstra_av:delheap(H,A,Hq)"? yes
TLO = [3-A, 4-B], false.

EDIT 2:

I was able to get it working by calling delete_from_heap with the priority and not the key, however, this does cause problems if two items has the same priority and it picks the wrong one. In my application this problem does not often arise, but it does seem like generally there should be a better way of using attribute variables with existing rules.

Upvotes: 3

Views: 146

Answers (2)

CapelliC
CapelliC

Reputation: 60014

my own test using attributed variables for graph representation. I remember I found difficult to adapt to the particular programming style required. HTH

/*  File:    dijkstra_av.pl
    Author:  Carlo,,,
    Created: Aug  3 2012
    Modified:Oct 28 2012
    Purpose: learn graph programming with attribute variables
*/

:- module(dijkstra_av, [dijkstra_av/3,
            dijkstra_edges/3]).

dijkstra_av(Graph, Start, Solution) :-
    setof(X, Y^D^(member(d(X,Y,D), Graph) ; member(d(Y,X,D), Graph)), Xs),
    length(Xs, L),
    length(Vs, L),
    aggregate_all(sum(D), member(d(_, _, D), Graph), Infinity),
    catch((algo(Graph, Infinity, Xs, Vs, Start, Solution),
           throw(sol(Solution))
          ), sol(Solution), true).

dijkstra_edges(Graph, Start, Edges) :-
    dijkstra_av(Graph, Start, Solution),
    maplist(nodes_to_edges(Graph), Solution, Edges).

nodes_to_edges(Graph, s(Node, Dist, Nodes), s(Node, Dist, Edges)) :-
    join_nodes(Graph, Nodes, Edges).

join_nodes(_Graph, [_Last], []).
join_nodes(Graph, [N,M|Ns], [e(N,M,D)|Es]) :-
    aggregate_all(min(X), member(d(N, M, X), Graph), D),
    join_nodes(Graph, [M|Ns], Es).

algo(Graph, Infinity, Xs, Vs, Start, Solution) :-
    pairs_keys_values(Ps, Xs, Vs),
    maplist(init_adjs(Ps), Graph),
    maplist(init_dist(Infinity), Ps),
    %ord_memberchk(Start-Sv, Ps),
    memberchk(Start-Sv, Ps),
    put_attr(Sv, dist, 0),
    time(main_loop(Vs)),
    maplist(solution(Start), Vs, Solution).

solution(Start, V, s(N, D, [Start|P])) :-
    get_attr(V, name, N),
    get_attr(V, dist, D),
    rpath(V, [], P).

rpath(V, X, P) :-
    get_attr(V, name, N),
    (   get_attr(V, previous, Q)
    ->  rpath(Q, [N|X], P)
    ;   P = X
    ).

init_dist(Infinity, N-V) :-
    put_attr(V, name, N),
    put_attr(V, dist, Infinity).

init_adjs(Ps, d(X, Y, D)) :-
    %ord_memberchk(X-Xv, Ps),
    %ord_memberchk(Y-Yv, Ps),
    memberchk(X-Xv, Ps),
    memberchk(Y-Yv, Ps),
    adj_add(Xv, Yv, D),
    adj_add(Yv, Xv, D).

adj_add(X, Y, D) :-
    (   get_attr(X, adjs, L)
    ->  put_attr(X, adjs, [Y-D|L])
    ;   put_attr(X, adjs, [Y-D])
    ).

main_loop([]).
main_loop([Q|Qs]) :-
    smallest_distance(Qs, Q, U, Qn),
    put_attr(U, assigned, true),
    get_attr(U, adjs, As),
    update_neighbours(As, U),
    main_loop(Qn).

smallest_distance([A|Qs], C, M, [T|Qn]) :-
    get_attr(A, dist, Av),
    get_attr(C, dist, Cv),
    (   Av < Cv
    ->  (N,T) = (A,C)
    ;   (N,T) = (C,A)
    ),
    !, smallest_distance(Qs, N, M, Qn).
smallest_distance([], U, U, []).

update_neighbours([V-Duv|Vs], U) :-
    (   get_attr(V, assigned, true)
    ->  true
    ;   get_attr(U, dist, Du),
        get_attr(V, dist, Dv),
        Alt is Du + Duv,
        (   Alt < Dv
        ->  put_attr(V, dist, Alt),
        put_attr(V, previous, U)
        ;   true
        )
    ),
    update_neighbours(Vs, U).
update_neighbours([], _).

:- begin_tests(dijkstra_av).

small([d(a,b,2),d(a,b,1),d(b,c,1),d(c,d,1),d(a,d,3),d(a,d,2)]).

test(1) :-
    nl,
    small(S),
    time(dijkstra_av(S, a, L)),
    maplist(writeln, L).

test(2) :-
    open(salesman, read, F),
    readf(F, L),
    close(F),
    nl,
    dijkstra_av(L, penzance, R),
    maplist(writeln, R).

readf(F, [d(X,Y,D)|R]) :-
    read(F, dist(X,Y,D)), !, readf(F, R).
readf(_, []).

test(3) :-
    nl, small(S),
    time(dijkstra_edges(S, a, Es)),
    maplist(writeln, Es).

:- end_tests(dijkstra_av).

the presence of test unit allows for:

?- run_tests(dijkstra_av).
% PL-Unit: dijkstra_av 
% 122 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 1015009 Lips)
% 475 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 283613 Lips)
s(a,0,[a])
s(b,1,[a,b])
s(c,2,[a,b,c])
s(d,2,[a,d])
.
ERROR: /home/carlo/prolog/dijkstra_av.pl:115:
    test 2: received error: open/3: source_sink `salesman' does not exist (No such file or directory)

% 122 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 2027285 Lips)
% 619 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 899941 Lips)
s(a,0,[])
s(b,1,[e(a,b,1)])
s(c,2,[e(a,b,1),e(b,c,1)])
s(d,2,[e(a,d,2)])
Warning: /home/carlo/prolog/dijkstra_av.pl:127:
    PL-Unit: Test 3: Test succeeded with choicepoint
 done
% 1 test failed
% 2 tests passed
false.

with time passing, something has been lost... sorry

Upvotes: 2

mat
mat

Reputation: 40768

You are accidentally unifying a variable that has attributes attached with another term. Unifications that involve attributed variables trigger attr_unify_hook/2 in the corresponding modules, and you do not define such hooks, since you only use attributes as a quick way to access data and probably have no interest in any unifications among these variables.

To remove a variable from a list, use for example (==)/2:

list0_var_list(Ls0, V, Ls) :-
        select(V0, Ls0, Ls),
        V0 == V.

Sample query:

?- list0_var_list([A,B,C,D], B, Ls).
Ls = [A, C, D] ;
false.

Note that this still leaves a choicepoint. You can use once/1 to commit to the first and only solution, since you already know that each node in the list is unique:

?- once(list0_var_list([A,B,C,D], B, Ls)).
Ls = [A, C, D].

Using such a predicate instead of delete/3 lets you safely detect equality of variables and remove a given one from a list, without triggering any unification hooks.

Notice also that delete/3 is deprecated (see the documentation), and consider the following case:

?- delete([A,B,C], A, Cs).
Cs = [].

This shows that you cannot safely use delete/3 when variables are involved.

Upvotes: 5

Related Questions