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          ]).

   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*/

 vertices(+S_Graph, -Vertices) is det

Strips off the neighbours lists of an S-representation to produce a list of the vertices of the graph. (It is a characteristic of S-representations that every vertex appears, even if it has no neighbours.). Vertices is in the standard order of terms.

  140vertices([], []) :- !.
  141vertices([Vertex-_|Graph], [Vertex|Vertices]) :-
  142    vertices(Graph, Vertices).

 vertices_edges_to_ugraph(+Vertices, +Edges, -UGraph) is det

Create a UGraph from Vertices and edges. Given a graph with a set of Vertices and a set of Edges, Graph must unify with the corresponding S-representation. Note that the vertices without edges will appear in Vertices but not in Edges. Moreover, it is sufficient for a vertice to appear in Edges.

?- vertices_edges_to_ugraph([],[1-3,2-4,4-5,1-5], L).
L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[]]

In this case all vertices are defined implicitly. The next example shows three unconnected vertices:

?- vertices_edges_to_ugraph([6,7,8],[1-3,2-4,4-5,1-5], L).
L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[], 6-[], 7-[], 8-[]]

  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).

 del_vertices(+Graph, +Vertices, -NewGraph) is det

Unify NewGraph with a new graph obtained by deleting the list of Vertices and all the edges that start from or go to a vertex in Vertices to the Graph. Example:

?- del_vertices([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[2,6],8-[]],
                [2,1],
                NL).
NL = [3-[],4-[5],5-[],6-[],7-[6],8-[]]

Compatibility

- Upto 5.6.48 the argument order was (+Vertices, +Graph, -NewGraph). Both YAP and SWI-Prolog have changed the argument order for compatibility with recent SICStus as well as consistency with del_edges/3.

  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).

 ugraph_union(+Set1, +Set2, ?Union)

Is true when Union is the union of Set1 and Set2. This code is a copy of set union

  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).

 graph_subtract(+Set1, +Set2, ?Difference)

Is based on ord_subtract

  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).

 edges(+UGraph, -Edges) is det

Edges is the set of edges in UGraph. Each edge is represented as a pair From-To, where From and To are vertices in the graph.

  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([], _, _, []).

 transpose_ugraph(Graph, NewGraph) is det

Unify NewGraph with a new graph obtained from Graph by replacing all edges of the form V1-V2 by edges of the form V2-V1. The cost is O(|V|*log(|V|)). Notice that an undirected graph is its own transpose. Example:

?- transpose([1-[3,5],2-[4],3-[],4-[5],
              5-[],6-[],7-[],8-[]], NL).
NL = [1-[],2-[],3-[1],4-[2],5-[1,4],6-[],7-[],8-[]]

Compatibility

- This predicate used to be known as transpose/2. Following SICStus 4, we reserve transpose/2 for matrix transposition and renamed ugraph transposition to transpose_ugraph/2.

  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).

 compose(G1, G2, Composition)

Calculates the composition of two S-form graphs, which need not have the same set of vertices.

  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).

 top_sort(+Graph, -Sorted) is semidet

 top_sort(+Graph, -Sorted, ?Tail) is semidet

Sorted is a topological sorted list of nodes in Graph. A toplogical sort is possible if the graph is connected and acyclic. In the example we show how topological sorting works for a linear graph:

?- top_sort([1-[2], 2-[3], 3-[]], L).
L = [1, 2, 3]

The predicate top_sort/3 is a difference list version of top_sort/2.

  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).

 neighbors(+Vertex, +Graph, -Neigbours) is det

 neighbours(+Vertex, +Graph, -Neigbours) is det

Neigbours is a sorted list of the neighbours of Vertex in Graph.

  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).

 connect_ugraph(+UGraphIn, -Start, -UGraphOut) is det

Adds Start as an additional vertex that is connected to all vertices in UGraphIn. This can be used to create an topological sort for a not connected graph. Start is before any vertex in UGraphIn in the standard order of terms. No vertex in UGraphIn can be a variable.

Can be used to order a not-connected graph as follows:

top_sort_unconnected(Graph, Vertices) :-
    (   top_sort(Graph, Vertices)
    ->  true
    ;   connect_ugraph(Graph, Start, Connected),
        top_sort(Connected, Ordered0),
        Ordered0 = [Start|Vertices]
    ).

  550connect_ugraph([], 0, []) :- !.
  551connect_ugraph(Graph, Start, [Start-Vertices|Graph]) :-
  552    vertices(Graph, Vertices),
  553    Vertices = [First|_],
  554    before(First, Start).

 before(+Term, -Before) is det

Unify Before to a term that comes before Term in the standard order of terms.

Errors

- instantiation_error if Term is unbound.

  563before(X, _) :-
  564    var(X),
  565    !,
  566    instantiation_error(X).
  567before(Number, Start) :-
  568    number(Number),
  569    !,
  570    Start is Number - 1.
  571before(_, 0).

 complement(+UGraphIn, -UGraphOut)

UGraphOut is a ugraph with an edge between all vertices that are not connected in UGraphIn and all edges from UGraphIn removed.

To be done

- Simple two-step algorithm. You could be smarter, I suppose.

  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).

 reachable(+Vertex, +UGraph, -Vertices)

True when Vertices is an ordered set of vertices reachable in UGraph, including Vertex.

  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)