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