View source with raw comments or as raw
   1/*  Part of SWI-Prolog
   2
   3    Author:        R.A.O'Keefe, Vitor Santos Costa, Jan Wielemaker
   4    E-mail:        J.Wielemaker@vu.nl
   5    WWW:           http://www.swi-prolog.org
   6    Copyright (c)  1984-2012, VU University Amsterdam
   7    All rights reserved.
   8
   9    Redistribution and use in source and binary forms, with or without
  10    modification, are permitted provided that the following conditions
  11    are met:
  12
  13    1. Redistributions of source code must retain the above copyright
  14       notice, this list of conditions and the following disclaimer.
  15
  16    2. Redistributions in binary form must reproduce the above copyright
  17       notice, this list of conditions and the following disclaimer in
  18       the documentation and/or other materials provided with the
  19       distribution.
  20
  21    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  25    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  29    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  31    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32    POSSIBILITY OF SUCH DAMAGE.
  33*/
  34
  35:- module(ugraphs,
  36          [ add_edges/3,                % +Graph, +Edges, -NewGraph
  37            add_vertices/3,             % +Graph, +Vertices, -NewGraph
  38            complement/2,               % +Graph, -NewGraph
  39            compose/3,                  % +LeftGraph, +RightGraph, -NewGraph
  40            del_edges/3,                % +Graph, +Edges, -NewGraph
  41            del_vertices/3,             % +Graph, +Vertices, -NewGraph
  42            edges/2,                    % +Graph, -Edges
  43            neighbors/3,                % +Vertex, +Graph, -Vertices
  44            neighbours/3,               % +Vertex, +Graph, -Vertices
  45            reachable/3,                % +Vertex, +Graph, -Vertices
  46            top_sort/2,                 % +Graph, -Sort
  47            top_sort/3,                 % +Graph, -Sort0, -Sort
  48            transitive_closure/2,       % +Graph, -Closure
  49            transpose_ugraph/2,         % +Graph, -NewGraph
  50            vertices/2,                 % +Graph, -Vertices
  51            vertices_edges_to_ugraph/3, % +Vertices, +Edges, -Graph
  52            ugraph_union/3              % +Graph1, +Graph2, -Graph
  53          ]).
  54
  55/** <module> Graph manipulation library
  56
  57The S-representation of a graph is  a list of (vertex-neighbours) pairs,
  58where the pairs are in standard order   (as produced by keysort) and the
  59neighbours of each vertex are also  in   standard  order (as produced by
  60sort). This form is convenient for many calculations.
  61
  62A   new   UGraph   from    raw    data     can    be    created    using
  63vertices_edges_to_ugraph/3.
  64
  65Adapted to support some of  the   functionality  of  the SICStus ugraphs
  66library by Vitor Santos Costa.
  67
  68Ported from YAP 5.0.1 to SWI-Prolog by Jan Wielemaker.
  69
  70@author R.A.O'Keefe
  71@author Vitor Santos Costa
  72@author Jan Wielemaker
  73@license GPL+SWI-exception or Artistic 2.0
  74*/
  75
  76:- use_module(library(lists), [
  77        append/3,
  78        member/2
  79   ]).
  80
  81:- use_module(library(ordsets), [
  82        ord_add_element/3,
  83        ord_subtract/3,
  84        ord_union/3,
  85        ord_union/4
  86   ]).
  87
  88
  89/*
  90
  91:- public
  92        p_to_s_graph/2,
  93        s_to_p_graph/2, % edges
  94        s_to_p_trans/2,
  95        p_member/3,
  96        s_member/3,
  97        p_transpose/2,
  98        s_transpose/2,
  99        compose/3,
 100        top_sort/2,
 101        vertices/2,
 102        warshall/2.
 103
 104:- mode
 105        vertices(+, -),
 106        p_to_s_graph(+, -),
 107            p_to_s_vertices(+, -),
 108            p_to_s_group(+, +, -),
 109                p_to_s_group(+, +, -, -),
 110        s_to_p_graph(+, -),
 111            s_to_p_graph(+, +, -, -),
 112        s_to_p_trans(+, -),
 113            s_to_p_trans(+, +, -, -),
 114        p_member(?, ?, +),
 115        s_member(?, ?, +),
 116        p_transpose(+, -),
 117        s_transpose(+, -),
 118            s_transpose(+, -, ?, -),
 119                transpose_s(+, +, +, -),
 120        compose(+, +, -),
 121            compose(+, +, +, -),
 122                compose1(+, +, +, -),
 123                    compose1(+, +, +, +, +, +, +, -),
 124        top_sort(+, -),
 125            vertices_and_zeros(+, -, ?),
 126            count_edges(+, +, +, -),
 127                incr_list(+, +, +, -),
 128            select_zeros(+, +, -),
 129            top_sort(+, -, +, +, +),
 130                decr_list(+, +, +, -, +, -),
 131        warshall(+, -),
 132            warshall(+, +, -),
 133                warshall(+, +, +, -).
 134
 135*/
 136
 137
 138%!  vertices(+S_Graph, -Vertices) is det.
 139%
 140%   Strips off the  neighbours  lists   of  an  S-representation  to
 141%   produce  a  list  of  the  vertices  of  the  graph.  (It  is  a
 142%   characteristic of S-representations that *every* vertex appears,
 143%   even if it has no  neighbours.).   Vertices  is  in the standard
 144%   order of terms.
 145
 146vertices([], []) :- !.
 147vertices([Vertex-_|Graph], [Vertex|Vertices]) :-
 148    vertices(Graph, Vertices).
 149
 150
 151%!  vertices_edges_to_ugraph(+Vertices, +Edges, -UGraph) is det.
 152%
 153%   Create a UGraph from Vertices and edges.   Given  a graph with a
 154%   set of Vertices and a set of   Edges,  Graph must unify with the
 155%   corresponding S-representation. Note that   the vertices without
 156%   edges will appear in Vertices but not  in Edges. Moreover, it is
 157%   sufficient for a vertice to appear in Edges.
 158%
 159%   ==
 160%   ?- vertices_edges_to_ugraph([],[1-3,2-4,4-5,1-5], L).
 161%   L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[]]
 162%   ==
 163%
 164%   In this case all  vertices  are   defined  implicitly.  The next
 165%   example shows three unconnected vertices:
 166%
 167%   ==
 168%   ?- vertices_edges_to_ugraph([6,7,8],[1-3,2-4,4-5,1-5], L).
 169%   L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[], 6-[], 7-[], 8-[]]
 170%   ==
 171
 172vertices_edges_to_ugraph(Vertices, Edges, Graph) :-
 173    sort(Edges, EdgeSet),
 174    p_to_s_vertices(EdgeSet, IVertexBag),
 175    append(Vertices, IVertexBag, VertexBag),
 176    sort(VertexBag, VertexSet),
 177    p_to_s_group(VertexSet, EdgeSet, Graph).
 178
 179
 180add_vertices(Graph, Vertices, NewGraph) :-
 181    msort(Vertices, V1),
 182    add_vertices_to_s_graph(V1, Graph, NewGraph).
 183
 184add_vertices_to_s_graph(L, [], NL) :-
 185    !,
 186    add_empty_vertices(L, NL).
 187add_vertices_to_s_graph([], L, L) :- !.
 188add_vertices_to_s_graph([V1|VL], [V-Edges|G], NGL) :-
 189    compare(Res, V1, V),
 190    add_vertices_to_s_graph(Res, V1, VL, V, Edges, G, NGL).
 191
 192add_vertices_to_s_graph(=, _, VL, V, Edges, G, [V-Edges|NGL]) :-
 193    add_vertices_to_s_graph(VL, G, NGL).
 194add_vertices_to_s_graph(<, V1, VL, V, Edges, G, [V1-[]|NGL]) :-
 195    add_vertices_to_s_graph(VL, [V-Edges|G], NGL).
 196add_vertices_to_s_graph(>, V1, VL, V, Edges, G, [V-Edges|NGL]) :-
 197    add_vertices_to_s_graph([V1|VL], G, NGL).
 198
 199add_empty_vertices([], []).
 200add_empty_vertices([V|G], [V-[]|NG]) :-
 201    add_empty_vertices(G, NG).
 202
 203%!  del_vertices(+Graph, +Vertices, -NewGraph) is det.
 204%
 205%   Unify NewGraph with a new graph obtained by deleting the list of
 206%   Vertices and all the edges that start from  or go to a vertex in
 207%   Vertices to the Graph. Example:
 208%
 209%   ==
 210%   ?- del_vertices([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[2,6],8-[]],
 211%                   [2,1],
 212%                   NL).
 213%   NL = [3-[],4-[5],5-[],6-[],7-[6],8-[]]
 214%   ==
 215%
 216%   @compat Upto 5.6.48 the argument order was (+Vertices, +Graph,
 217%   -NewGraph). Both YAP and SWI-Prolog have changed the argument
 218%   order for compatibility with recent SICStus as well as
 219%   consistency with del_edges/3.
 220
 221del_vertices(Graph, Vertices, NewGraph) :-
 222    sort(Vertices, V1),             % JW: was msort
 223    (   V1 = []
 224    ->  Graph = NewGraph
 225    ;   del_vertices(Graph, V1, V1, NewGraph)
 226    ).
 227
 228del_vertices(G, [], V1, NG) :-
 229    !,
 230    del_remaining_edges_for_vertices(G, V1, NG).
 231del_vertices([], _, _, []).
 232del_vertices([V-Edges|G], [V0|Vs], V1, NG) :-
 233    compare(Res, V, V0),
 234    split_on_del_vertices(Res, V,Edges, [V0|Vs], NVs, V1, NG, NGr),
 235    del_vertices(G, NVs, V1, NGr).
 236
 237del_remaining_edges_for_vertices([], _, []).
 238del_remaining_edges_for_vertices([V0-Edges|G], V1, [V0-NEdges|NG]) :-
 239    ord_subtract(Edges, V1, NEdges),
 240    del_remaining_edges_for_vertices(G, V1, NG).
 241
 242split_on_del_vertices(<, V, Edges, Vs, Vs, V1, [V-NEdges|NG], NG) :-
 243    ord_subtract(Edges, V1, NEdges).
 244split_on_del_vertices(>, V, Edges, [_|Vs], Vs, V1, [V-NEdges|NG], NG) :-
 245    ord_subtract(Edges, V1, NEdges).
 246split_on_del_vertices(=, _, _, [_|Vs], Vs, _, NG, NG).
 247
 248add_edges(Graph, Edges, NewGraph) :-
 249    p_to_s_graph(Edges, G1),
 250    ugraph_union(Graph, G1, NewGraph).
 251
 252%!  ugraph_union(+Set1, +Set2, ?Union)
 253%
 254%   Is true when Union is the union of Set1 and Set2. This code is a
 255%   copy of set union
 256
 257ugraph_union(Set1, [], Set1) :- !.
 258ugraph_union([], Set2, Set2) :- !.
 259ugraph_union([Head1-E1|Tail1], [Head2-E2|Tail2], Union) :-
 260    compare(Order, Head1, Head2),
 261    ugraph_union(Order, Head1-E1, Tail1, Head2-E2, Tail2, Union).
 262
 263ugraph_union(=, Head-E1, Tail1, _-E2, Tail2, [Head-Es|Union]) :-
 264    ord_union(E1, E2, Es),
 265    ugraph_union(Tail1, Tail2, Union).
 266ugraph_union(<, Head1, Tail1, Head2, Tail2, [Head1|Union]) :-
 267    ugraph_union(Tail1, [Head2|Tail2], Union).
 268ugraph_union(>, Head1, Tail1, Head2, Tail2, [Head2|Union]) :-
 269    ugraph_union([Head1|Tail1], Tail2, Union).
 270
 271del_edges(Graph, Edges, NewGraph) :-
 272    p_to_s_graph(Edges, G1),
 273    graph_subtract(Graph, G1, NewGraph).
 274
 275%!  graph_subtract(+Set1, +Set2, ?Difference)
 276%
 277%   Is based on ord_subtract
 278
 279graph_subtract(Set1, [], Set1) :- !.
 280graph_subtract([], _, []).
 281graph_subtract([Head1-E1|Tail1], [Head2-E2|Tail2], Difference) :-
 282    compare(Order, Head1, Head2),
 283    graph_subtract(Order, Head1-E1, Tail1, Head2-E2, Tail2, Difference).
 284
 285graph_subtract(=, H-E1,     Tail1, _-E2,     Tail2, [H-E|Difference]) :-
 286    ord_subtract(E1,E2,E),
 287    graph_subtract(Tail1, Tail2, Difference).
 288graph_subtract(<, Head1, Tail1, Head2, Tail2, [Head1|Difference]) :-
 289    graph_subtract(Tail1, [Head2|Tail2], Difference).
 290graph_subtract(>, Head1, Tail1, _,     Tail2, Difference) :-
 291    graph_subtract([Head1|Tail1], Tail2, Difference).
 292
 293%!  edges(+UGraph, -Edges) is det.
 294%
 295%   Edges is the set of edges in UGraph. Each edge is represented as
 296%   a pair From-To, where From and To are vertices in the graph.
 297
 298edges(Graph, Edges) :-
 299    s_to_p_graph(Graph, Edges).
 300
 301p_to_s_graph(P_Graph, S_Graph) :-
 302    sort(P_Graph, EdgeSet),
 303    p_to_s_vertices(EdgeSet, VertexBag),
 304    sort(VertexBag, VertexSet),
 305    p_to_s_group(VertexSet, EdgeSet, S_Graph).
 306
 307
 308p_to_s_vertices([], []).
 309p_to_s_vertices([A-Z|Edges], [A,Z|Vertices]) :-
 310    p_to_s_vertices(Edges, Vertices).
 311
 312
 313p_to_s_group([], _, []).
 314p_to_s_group([Vertex|Vertices], EdgeSet, [Vertex-Neibs|G]) :-
 315    p_to_s_group(EdgeSet, Vertex, Neibs, RestEdges),
 316    p_to_s_group(Vertices, RestEdges, G).
 317
 318
 319p_to_s_group([V1-X|Edges], V2, [X|Neibs], RestEdges) :- V1 == V2,
 320    !,
 321    p_to_s_group(Edges, V2, Neibs, RestEdges).
 322p_to_s_group(Edges, _, [], Edges).
 323
 324
 325
 326s_to_p_graph([], []) :- !.
 327s_to_p_graph([Vertex-Neibs|G], P_Graph) :-
 328    s_to_p_graph(Neibs, Vertex, P_Graph, Rest_P_Graph),
 329    s_to_p_graph(G, Rest_P_Graph).
 330
 331
 332s_to_p_graph([], _, P_Graph, P_Graph) :- !.
 333s_to_p_graph([Neib|Neibs], Vertex, [Vertex-Neib|P], Rest_P) :-
 334    s_to_p_graph(Neibs, Vertex, P, Rest_P).
 335
 336
 337transitive_closure(Graph, Closure) :-
 338    warshall(Graph, Graph, Closure).
 339
 340warshall([], Closure, Closure) :- !.
 341warshall([V-_|G], E, Closure) :-
 342    memberchk(V-Y, E),      %  Y := E(v)
 343    warshall(E, V, Y, NewE),
 344    warshall(G, NewE, Closure).
 345
 346
 347warshall([X-Neibs|G], V, Y, [X-NewNeibs|NewG]) :-
 348    memberchk(V, Neibs),
 349    !,
 350    ord_union(Neibs, Y, NewNeibs),
 351    warshall(G, V, Y, NewG).
 352warshall([X-Neibs|G], V, Y, [X-Neibs|NewG]) :-
 353    !,
 354    warshall(G, V, Y, NewG).
 355warshall([], _, _, []).
 356
 357%!  transpose_ugraph(Graph, NewGraph) is det.
 358%
 359%   Unify NewGraph with a new graph obtained from Graph by replacing
 360%   all edges of the form V1-V2 by edges of the form V2-V1. The cost
 361%   is O(|V|*log(|V|)). Notice that an undirected   graph is its own
 362%   transpose. Example:
 363%
 364%     ==
 365%     ?- transpose([1-[3,5],2-[4],3-[],4-[5],
 366%                   5-[],6-[],7-[],8-[]], NL).
 367%     NL = [1-[],2-[],3-[1],4-[2],5-[1,4],6-[],7-[],8-[]]
 368%     ==
 369%
 370%   @compat  This  predicate  used  to   be  known  as  transpose/2.
 371%   Following  SICStus  4,  we  reserve    transpose/2   for  matrix
 372%   transposition    and    renamed    ugraph    transposition    to
 373%   transpose_ugraph/2.
 374
 375transpose_ugraph(Graph, NewGraph) :-
 376    edges(Graph, Edges),
 377    vertices(Graph, Vertices),
 378    flip_edges(Edges, TransposedEdges),
 379    vertices_edges_to_ugraph(Vertices, TransposedEdges, NewGraph).
 380
 381flip_edges([], []).
 382flip_edges([Key-Val|Pairs], [Val-Key|Flipped]) :-
 383    flip_edges(Pairs, Flipped).
 384
 385
 386%!  compose(G1, G2, Composition)
 387%
 388%   Calculates the composition of two S-form  graphs, which need not
 389%   have the same set of vertices.
 390
 391compose(G1, G2, Composition) :-
 392    vertices(G1, V1),
 393    vertices(G2, V2),
 394    ord_union(V1, V2, V),
 395    compose(V, G1, G2, Composition).
 396
 397
 398compose([], _, _, []) :- !.
 399compose([Vertex|Vertices], [Vertex-Neibs|G1], G2,
 400        [Vertex-Comp|Composition]) :-
 401    !,
 402    compose1(Neibs, G2, [], Comp),
 403    compose(Vertices, G1, G2, Composition).
 404compose([Vertex|Vertices], G1, G2, [Vertex-[]|Composition]) :-
 405    compose(Vertices, G1, G2, Composition).
 406
 407
 408compose1([V1|Vs1], [V2-N2|G2], SoFar, Comp) :-
 409    compare(Rel, V1, V2),
 410    !,
 411    compose1(Rel, V1, Vs1, V2, N2, G2, SoFar, Comp).
 412compose1(_, _, Comp, Comp).
 413
 414
 415compose1(<, _, Vs1, V2, N2, G2, SoFar, Comp) :-
 416    !,
 417    compose1(Vs1, [V2-N2|G2], SoFar, Comp).
 418compose1(>, V1, Vs1, _, _, G2, SoFar, Comp) :-
 419    !,
 420    compose1([V1|Vs1], G2, SoFar, Comp).
 421compose1(=, V1, Vs1, V1, N2, G2, SoFar, Comp) :-
 422    ord_union(N2, SoFar, Next),
 423    compose1(Vs1, G2, Next, Comp).
 424
 425%!  top_sort(+Graph, -Sorted) is semidet.
 426%!  top_sort(+Graph, -Sorted, ?Tail) is semidet.
 427%
 428%   Sorted is a  topological  sorted  list   of  nodes  in  Graph. A
 429%   toplogical sort is possible  if  the   graph  is  connected  and
 430%   acyclic. In the example we show   how  topological sorting works
 431%   for a linear graph:
 432%
 433%   ==
 434%   ?- top_sort([1-[2], 2-[3], 3-[]], L).
 435%   L = [1, 2, 3]
 436%   ==
 437%
 438%   The  predicate  top_sort/3  is  a  difference  list  version  of
 439%   top_sort/2.
 440
 441top_sort(Graph, Sorted) :-
 442    vertices_and_zeros(Graph, Vertices, Counts0),
 443    count_edges(Graph, Vertices, Counts0, Counts1),
 444    select_zeros(Counts1, Vertices, Zeros),
 445    top_sort(Zeros, Sorted, Graph, Vertices, Counts1).
 446
 447top_sort(Graph, Sorted0, Sorted) :-
 448    vertices_and_zeros(Graph, Vertices, Counts0),
 449    count_edges(Graph, Vertices, Counts0, Counts1),
 450    select_zeros(Counts1, Vertices, Zeros),
 451    top_sort(Zeros, Sorted, Sorted0, Graph, Vertices, Counts1).
 452
 453
 454vertices_and_zeros([], [], []) :- !.
 455vertices_and_zeros([Vertex-_|Graph], [Vertex|Vertices], [0|Zeros]) :-
 456    vertices_and_zeros(Graph, Vertices, Zeros).
 457
 458
 459count_edges([], _, Counts, Counts) :- !.
 460count_edges([_-Neibs|Graph], Vertices, Counts0, Counts2) :-
 461    incr_list(Neibs, Vertices, Counts0, Counts1),
 462    count_edges(Graph, Vertices, Counts1, Counts2).
 463
 464
 465incr_list([], _, Counts, Counts) :- !.
 466incr_list([V1|Neibs], [V2|Vertices], [M|Counts0], [N|Counts1]) :-
 467    V1 == V2,
 468    !,
 469    N is M+1,
 470    incr_list(Neibs, Vertices, Counts0, Counts1).
 471incr_list(Neibs, [_|Vertices], [N|Counts0], [N|Counts1]) :-
 472    incr_list(Neibs, Vertices, Counts0, Counts1).
 473
 474
 475select_zeros([], [], []) :- !.
 476select_zeros([0|Counts], [Vertex|Vertices], [Vertex|Zeros]) :-
 477    !,
 478    select_zeros(Counts, Vertices, Zeros).
 479select_zeros([_|Counts], [_|Vertices], Zeros) :-
 480    select_zeros(Counts, Vertices, Zeros).
 481
 482
 483
 484top_sort([], [], Graph, _, Counts) :-
 485    !,
 486    vertices_and_zeros(Graph, _, Counts).
 487top_sort([Zero|Zeros], [Zero|Sorted], Graph, Vertices, Counts1) :-
 488    graph_memberchk(Zero-Neibs, Graph),
 489    decr_list(Neibs, Vertices, Counts1, Counts2, Zeros, NewZeros),
 490    top_sort(NewZeros, Sorted, Graph, Vertices, Counts2).
 491
 492top_sort([], Sorted0, Sorted0, Graph, _, Counts) :-
 493    !,
 494    vertices_and_zeros(Graph, _, Counts).
 495top_sort([Zero|Zeros], [Zero|Sorted], Sorted0, Graph, Vertices, Counts1) :-
 496    graph_memberchk(Zero-Neibs, Graph),
 497    decr_list(Neibs, Vertices, Counts1, Counts2, Zeros, NewZeros),
 498    top_sort(NewZeros, Sorted, Sorted0, Graph, Vertices, Counts2).
 499
 500graph_memberchk(Element1-Edges, [Element2-Edges2|_]) :-
 501    Element1 == Element2,
 502    !,
 503    Edges = Edges2.
 504graph_memberchk(Element, [_|Rest]) :-
 505    graph_memberchk(Element, Rest).
 506
 507
 508decr_list([], _, Counts, Counts, Zeros, Zeros) :- !.
 509decr_list([V1|Neibs], [V2|Vertices], [1|Counts1], [0|Counts2], Zi, Zo) :-
 510    V1 == V2,
 511    !,
 512    decr_list(Neibs, Vertices, Counts1, Counts2, [V2|Zi], Zo).
 513decr_list([V1|Neibs], [V2|Vertices], [N|Counts1], [M|Counts2], Zi, Zo) :-
 514    V1 == V2,
 515    !,
 516    M is N-1,
 517    decr_list(Neibs, Vertices, Counts1, Counts2, Zi, Zo).
 518decr_list(Neibs, [_|Vertices], [N|Counts1], [N|Counts2], Zi, Zo) :-
 519    decr_list(Neibs, Vertices, Counts1, Counts2, Zi, Zo).
 520
 521
 522%!  neighbors(+Vertex, +Graph, -Neigbours) is det.
 523%!  neighbours(+Vertex, +Graph, -Neigbours) is det.
 524%
 525%   Neigbours is a sorted list of the neighbours of Vertex in Graph.
 526
 527neighbors(Vertex, Graph, Neig) :-
 528    neighbours(Vertex, Graph, Neig).
 529
 530neighbours(V,[V0-Neig|_],Neig) :-
 531    V == V0,
 532    !.
 533neighbours(V,[_|G],Neig) :-
 534    neighbours(V,G,Neig).
 535
 536
 537%
 538% Simple two-step algorithm. You could be smarter, I suppose.
 539%
 540complement(G, NG) :-
 541    vertices(G,Vs),
 542    complement(G,Vs,NG).
 543
 544complement([], _, []).
 545complement([V-Ns|G], Vs, [V-INs|NG]) :-
 546    ord_add_element(Ns,V,Ns1),
 547    ord_subtract(Vs,Ns1,INs),
 548    complement(G, Vs, NG).
 549
 550
 551
 552reachable(N, G, Rs) :-
 553    reachable([N], G, [N], Rs).
 554
 555reachable([], _, Rs, Rs).
 556reachable([N|Ns], G, Rs0, RsF) :-
 557    neighbours(N, G, Nei),
 558    ord_union(Rs0, Nei, Rs1, D),
 559    append(Ns, D, Nsi),
 560    reachable(Nsi, G, Rs1, RsF).