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-2021, VU University Amsterdam
    7                              CWI, Amsterdam
    8                              SWI-Prolog Solutions .b.v
    9    All rights reserved.
   10
   11    Redistribution and use in source and binary forms, with or without
   12    modification, are permitted provided that the following conditions
   13    are met:
   14
   15    1. Redistributions of source code must retain the above copyright
   16       notice, this list of conditions and the following disclaimer.
   17
   18    2. Redistributions in binary form must reproduce the above copyright
   19       notice, this list of conditions and the following disclaimer in
   20       the documentation and/or other materials provided with the
   21       distribution.
   22
   23    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   24    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   25    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   26    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   27    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   28    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   29    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   30    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   31    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   32    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   33    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   34    POSSIBILITY OF SUCH DAMAGE.
   35*/
   36
   37:- module(ugraphs,
   38          [ add_edges/3,                % +Graph, +Edges, -NewGraph
   39            add_vertices/3,             % +Graph, +Vertices, -NewGraph
   40            complement/2,               % +Graph, -NewGraph
   41            compose/3,                  % +LeftGraph, +RightGraph, -NewGraph
   42            del_edges/3,                % +Graph, +Edges, -NewGraph
   43            del_vertices/3,             % +Graph, +Vertices, -NewGraph
   44            edges/2,                    % +Graph, -Edges
   45            neighbors/3,                % +Vertex, +Graph, -Vertices
   46            neighbours/3,               % +Vertex, +Graph, -Vertices
   47            reachable/3,                % +Vertex, +Graph, -Vertices
   48            top_sort/2,                 % +Graph, -Sort
   49            top_sort/3,                 % +Graph, -Sort0, -Sort
   50            transitive_closure/2,       % +Graph, -Closure
   51            transpose_ugraph/2,         % +Graph, -NewGraph
   52            vertices/2,                 % +Graph, -Vertices
   53            vertices_edges_to_ugraph/3, % +Vertices, +Edges, -Graph
   54            ugraph_union/3,             % +Graph1, +Graph2, -Graph
   55            connect_ugraph/3            % +Graph1, -Start, -Graph
   56          ]).

   79:- autoload(library(lists),[append/3]).   80:- autoload(library(ordsets),
   81	    [ord_subtract/3,ord_union/3,ord_add_element/3,ord_union/4]).   82:- autoload(library(error), [instantiation_error/1]).

 vertices(+Graph, -Vertices)

Unify Vertices with all vertices appearing in Graph. Example:

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

   91vertices([], []) :- !.
   92vertices([Vertex-_|Graph], [Vertex|Vertices]) :-
   93    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-[]]

  117vertices_edges_to_ugraph(Vertices, Edges, Graph) :-
  118    sort(Edges, EdgeSet),
  119    p_to_s_vertices(EdgeSet, IVertexBag),
  120    append(Vertices, IVertexBag, VertexBag),
  121    sort(VertexBag, VertexSet),
  122    p_to_s_group(VertexSet, EdgeSet, Graph).

 add_vertices(+Graph, +Vertices, -NewGraph)

Unify NewGraph with a new graph obtained by adding the list of Vertices to Graph. Example:

?- add_vertices([1-[3,5],2-[]], [0,1,2,9], NG).
NG = [0-[], 1-[3,5], 2-[], 9-[]]

  135add_vertices(Graph, Vertices, NewGraph) :-
  136    msort(Vertices, V1),
  137    add_vertices_to_s_graph(V1, Graph, NewGraph).
  138
  139add_vertices_to_s_graph(L, [], NL) :-
  140    !,
  141    add_empty_vertices(L, NL).
  142add_vertices_to_s_graph([], L, L) :- !.
  143add_vertices_to_s_graph([V1|VL], [V-Edges|G], NGL) :-
  144    compare(Res, V1, V),
  145    add_vertices_to_s_graph(Res, V1, VL, V, Edges, G, NGL).
  146
  147add_vertices_to_s_graph(=, _, VL, V, Edges, G, [V-Edges|NGL]) :-
  148    add_vertices_to_s_graph(VL, G, NGL).
  149add_vertices_to_s_graph(<, V1, VL, V, Edges, G, [V1-[]|NGL]) :-
  150    add_vertices_to_s_graph(VL, [V-Edges|G], NGL).
  151add_vertices_to_s_graph(>, V1, VL, V, Edges, G, [V-Edges|NGL]) :-
  152    add_vertices_to_s_graph([V1|VL], G, NGL).
  153
  154add_empty_vertices([], []).
  155add_empty_vertices([V|G], [V-[]|NG]) :-
  156    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.

  176del_vertices(Graph, Vertices, NewGraph) :-
  177    sort(Vertices, V1),             % JW: was msort
  178    (   V1 = []
  179    ->  Graph = NewGraph
  180    ;   del_vertices(Graph, V1, V1, NewGraph)
  181    ).
  182
  183del_vertices(G, [], V1, NG) :-
  184    !,
  185    del_remaining_edges_for_vertices(G, V1, NG).
  186del_vertices([], _, _, []).
  187del_vertices([V-Edges|G], [V0|Vs], V1, NG) :-
  188    compare(Res, V, V0),
  189    split_on_del_vertices(Res, V,Edges, [V0|Vs], NVs, V1, NG, NGr),
  190    del_vertices(G, NVs, V1, NGr).
  191
  192del_remaining_edges_for_vertices([], _, []).
  193del_remaining_edges_for_vertices([V0-Edges|G], V1, [V0-NEdges|NG]) :-
  194    ord_subtract(Edges, V1, NEdges),
  195    del_remaining_edges_for_vertices(G, V1, NG).
  196
  197split_on_del_vertices(<, V, Edges, Vs, Vs, V1, [V-NEdges|NG], NG) :-
  198    ord_subtract(Edges, V1, NEdges).
  199split_on_del_vertices(>, V, Edges, [_|Vs], Vs, V1, [V-NEdges|NG], NG) :-
  200    ord_subtract(Edges, V1, NEdges).
  201split_on_del_vertices(=, _, _, [_|Vs], Vs, _, NG, NG).

 add_edges(+Graph, +Edges, -NewGraph)

Unify NewGraph with a new graph obtained by adding the list of Edges to Graph. Example:

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

  217add_edges(Graph, Edges, NewGraph) :-
  218    p_to_s_graph(Edges, G1),
  219    ugraph_union(Graph, G1, NewGraph).

 ugraph_union(+Graph1, +Graph2, -NewGraph)

NewGraph is the union of Graph1 and Graph2. Example:

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

  230ugraph_union(Set1, [], Set1) :- !.
  231ugraph_union([], Set2, Set2) :- !.
  232ugraph_union([Head1-E1|Tail1], [Head2-E2|Tail2], Union) :-
  233    compare(Order, Head1, Head2),
  234    ugraph_union(Order, Head1-E1, Tail1, Head2-E2, Tail2, Union).
  235
  236ugraph_union(=, Head-E1, Tail1, _-E2, Tail2, [Head-Es|Union]) :-
  237    ord_union(E1, E2, Es),
  238    ugraph_union(Tail1, Tail2, Union).
  239ugraph_union(<, Head1, Tail1, Head2, Tail2, [Head1|Union]) :-
  240    ugraph_union(Tail1, [Head2|Tail2], Union).
  241ugraph_union(>, Head1, Tail1, Head2, Tail2, [Head2|Union]) :-
  242    ugraph_union([Head1|Tail1], Tail2, Union).

 del_edges(+Graph, +Edges, -NewGraph)

Unify NewGraph with a new graph obtained by removing the list of Edges from Graph. Notice that no vertices are deleted. Example:

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

  256del_edges(Graph, Edges, NewGraph) :-
  257    p_to_s_graph(Edges, G1),
  258    graph_subtract(Graph, G1, NewGraph).

 graph_subtract(+Set1, +Set2, ?Difference)

Is based on ord_subtract

  264graph_subtract(Set1, [], Set1) :- !.
  265graph_subtract([], _, []).
  266graph_subtract([Head1-E1|Tail1], [Head2-E2|Tail2], Difference) :-
  267    compare(Order, Head1, Head2),
  268    graph_subtract(Order, Head1-E1, Tail1, Head2-E2, Tail2, Difference).
  269
  270graph_subtract(=, H-E1,     Tail1, _-E2,     Tail2, [H-E|Difference]) :-
  271    ord_subtract(E1,E2,E),
  272    graph_subtract(Tail1, Tail2, Difference).
  273graph_subtract(<, Head1, Tail1, Head2, Tail2, [Head1|Difference]) :-
  274    graph_subtract(Tail1, [Head2|Tail2], Difference).
  275graph_subtract(>, Head1, Tail1, _,     Tail2, Difference) :-
  276    graph_subtract([Head1|Tail1], Tail2, Difference).

 edges(+Graph, -Edges)

Unify Edges with all edges appearing in Graph. Example:

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

  285edges(Graph, Edges) :-
  286    s_to_p_graph(Graph, Edges).
  287
  288p_to_s_graph(P_Graph, S_Graph) :-
  289    sort(P_Graph, EdgeSet),
  290    p_to_s_vertices(EdgeSet, VertexBag),
  291    sort(VertexBag, VertexSet),
  292    p_to_s_group(VertexSet, EdgeSet, S_Graph).
  293
  294
  295p_to_s_vertices([], []).
  296p_to_s_vertices([A-Z|Edges], [A,Z|Vertices]) :-
  297    p_to_s_vertices(Edges, Vertices).
  298
  299
  300p_to_s_group([], _, []).
  301p_to_s_group([Vertex|Vertices], EdgeSet, [Vertex-Neibs|G]) :-
  302    p_to_s_group(EdgeSet, Vertex, Neibs, RestEdges),
  303    p_to_s_group(Vertices, RestEdges, G).
  304
  305
  306p_to_s_group([V1-X|Edges], V2, [X|Neibs], RestEdges) :- V1 == V2,
  307    !,
  308    p_to_s_group(Edges, V2, Neibs, RestEdges).
  309p_to_s_group(Edges, _, [], Edges).
  310
  311
  312
  313s_to_p_graph([], []) :- !.
  314s_to_p_graph([Vertex-Neibs|G], P_Graph) :-
  315    s_to_p_graph(Neibs, Vertex, P_Graph, Rest_P_Graph),
  316    s_to_p_graph(G, Rest_P_Graph).
  317
  318
  319s_to_p_graph([], _, P_Graph, P_Graph) :- !.
  320s_to_p_graph([Neib|Neibs], Vertex, [Vertex-Neib|P], Rest_P) :-
  321    s_to_p_graph(Neibs, Vertex, P, Rest_P).

 transitive_closure(+Graph, -Closure)

Generate the graph Closure as the transitive closure of Graph. Example:

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

  333transitive_closure(Graph, Closure) :-
  334    warshall(Graph, Graph, Closure).
  335
  336warshall([], Closure, Closure) :- !.
  337warshall([V-_|G], E, Closure) :-
  338    memberchk(V-Y, E),      %  Y := E(v)
  339    warshall(E, V, Y, NewE),
  340    warshall(G, NewE, Closure).
  341
  342
  343warshall([X-Neibs|G], V, Y, [X-NewNeibs|NewG]) :-
  344    memberchk(V, Neibs),
  345    !,
  346    ord_union(Neibs, Y, NewNeibs),
  347    warshall(G, V, Y, NewG).
  348warshall([X-Neibs|G], V, Y, [X-Neibs|NewG]) :-
  349    !,
  350    warshall(G, V, Y, NewG).
  351warshall([], _, _, []).

 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.

  371transpose_ugraph(Graph, NewGraph) :-
  372    edges(Graph, Edges),
  373    vertices(Graph, Vertices),
  374    flip_edges(Edges, TransposedEdges),
  375    vertices_edges_to_ugraph(Vertices, TransposedEdges, NewGraph).
  376
  377flip_edges([], []).
  378flip_edges([Key-Val|Pairs], [Val-Key|Flipped]) :-
  379    flip_edges(Pairs, Flipped).

 compose(+LeftGraph, +RightGraph, -NewGraph)

Compose NewGraph by connecting the drains of LeftGraph to the sources of RightGraph. Example:

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

  389compose(G1, G2, Composition) :-
  390    vertices(G1, V1),
  391    vertices(G2, V2),
  392    ord_union(V1, V2, V),
  393    compose(V, G1, G2, Composition).
  394
  395compose([], _, _, []) :- !.
  396compose([Vertex|Vertices], [Vertex-Neibs|G1], G2,
  397        [Vertex-Comp|Composition]) :-
  398    !,
  399    compose1(Neibs, G2, [], Comp),
  400    compose(Vertices, G1, G2, Composition).
  401compose([Vertex|Vertices], G1, G2, [Vertex-[]|Composition]) :-
  402    compose(Vertices, G1, G2, Composition).
  403
  404
  405compose1([V1|Vs1], [V2-N2|G2], SoFar, Comp) :-
  406    compare(Rel, V1, V2),
  407    !,
  408    compose1(Rel, V1, Vs1, V2, N2, G2, SoFar, Comp).
  409compose1(_, _, Comp, Comp).
  410
  411
  412compose1(<, _, Vs1, V2, N2, G2, SoFar, Comp) :-
  413    !,
  414    compose1(Vs1, [V2-N2|G2], SoFar, Comp).
  415compose1(>, V1, Vs1, _, _, G2, SoFar, Comp) :-
  416    !,
  417    compose1([V1|Vs1], G2, SoFar, Comp).
  418compose1(=, V1, Vs1, V1, N2, G2, SoFar, Comp) :-
  419    ord_union(N2, SoFar, Next),
  420    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.

  438top_sort(Graph, Sorted) :-
  439    vertices_and_zeros(Graph, Vertices, Counts0),
  440    count_edges(Graph, Vertices, Counts0, Counts1),
  441    select_zeros(Counts1, Vertices, Zeros),
  442    top_sort(Zeros, Sorted, Graph, Vertices, Counts1).
  443
  444top_sort(Graph, Sorted0, Sorted) :-
  445    vertices_and_zeros(Graph, Vertices, Counts0),
  446    count_edges(Graph, Vertices, Counts0, Counts1),
  447    select_zeros(Counts1, Vertices, Zeros),
  448    top_sort(Zeros, Sorted, Sorted0, Graph, Vertices, Counts1).
  449
  450
  451vertices_and_zeros([], [], []) :- !.
  452vertices_and_zeros([Vertex-_|Graph], [Vertex|Vertices], [0|Zeros]) :-
  453    vertices_and_zeros(Graph, Vertices, Zeros).
  454
  455
  456count_edges([], _, Counts, Counts) :- !.
  457count_edges([_-Neibs|Graph], Vertices, Counts0, Counts2) :-
  458    incr_list(Neibs, Vertices, Counts0, Counts1),
  459    count_edges(Graph, Vertices, Counts1, Counts2).
  460
  461
  462incr_list([], _, Counts, Counts) :- !.
  463incr_list([V1|Neibs], [V2|Vertices], [M|Counts0], [N|Counts1]) :-
  464    V1 == V2,
  465    !,
  466    N is M+1,
  467    incr_list(Neibs, Vertices, Counts0, Counts1).
  468incr_list(Neibs, [_|Vertices], [N|Counts0], [N|Counts1]) :-
  469    incr_list(Neibs, Vertices, Counts0, Counts1).
  470
  471
  472select_zeros([], [], []) :- !.
  473select_zeros([0|Counts], [Vertex|Vertices], [Vertex|Zeros]) :-
  474    !,
  475    select_zeros(Counts, Vertices, Zeros).
  476select_zeros([_|Counts], [_|Vertices], Zeros) :-
  477    select_zeros(Counts, Vertices, Zeros).
  478
  479
  480
  481top_sort([], [], Graph, _, Counts) :-
  482    !,
  483    vertices_and_zeros(Graph, _, Counts).
  484top_sort([Zero|Zeros], [Zero|Sorted], Graph, Vertices, Counts1) :-
  485    graph_memberchk(Zero-Neibs, Graph),
  486    decr_list(Neibs, Vertices, Counts1, Counts2, Zeros, NewZeros),
  487    top_sort(NewZeros, Sorted, Graph, Vertices, Counts2).
  488
  489top_sort([], Sorted0, Sorted0, Graph, _, Counts) :-
  490    !,
  491    vertices_and_zeros(Graph, _, Counts).
  492top_sort([Zero|Zeros], [Zero|Sorted], Sorted0, Graph, Vertices, Counts1) :-
  493    graph_memberchk(Zero-Neibs, Graph),
  494    decr_list(Neibs, Vertices, Counts1, Counts2, Zeros, NewZeros),
  495    top_sort(NewZeros, Sorted, Sorted0, Graph, Vertices, Counts2).
  496
  497graph_memberchk(Element1-Edges, [Element2-Edges2|_]) :-
  498    Element1 == Element2,
  499    !,
  500    Edges = Edges2.
  501graph_memberchk(Element, [_|Rest]) :-
  502    graph_memberchk(Element, Rest).
  503
  504
  505decr_list([], _, Counts, Counts, Zeros, Zeros) :- !.
  506decr_list([V1|Neibs], [V2|Vertices], [1|Counts1], [0|Counts2], Zi, Zo) :-
  507    V1 == V2,
  508    !,
  509    decr_list(Neibs, Vertices, Counts1, Counts2, [V2|Zi], Zo).
  510decr_list([V1|Neibs], [V2|Vertices], [N|Counts1], [M|Counts2], Zi, Zo) :-
  511    V1 == V2,
  512    !,
  513    M is N-1,
  514    decr_list(Neibs, Vertices, Counts1, Counts2, Zi, Zo).
  515decr_list(Neibs, [_|Vertices], [N|Counts1], [N|Counts2], Zi, Zo) :-
  516    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. Example:

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

  531neighbors(Vertex, Graph, Neig) :-
  532    neighbours(Vertex, Graph, Neig).
  533
  534neighbours(V,[V0-Neig|_],Neig) :-
  535    V == V0,
  536    !.
  537neighbours(V,[_|G],Neig) :-
  538    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]
    ).

  560connect_ugraph([], 0, []) :- !.
  561connect_ugraph(Graph, Start, [Start-Vertices|Graph]) :-
  562    vertices(Graph, Vertices),
  563    Vertices = [First|_],
  564    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.

  573before(X, _) :-
  574    var(X),
  575    !,
  576    instantiation_error(X).
  577before(Number, Start) :-
  578    number(Number),
  579    !,
  580    Start is Number - 1.
  581before(_, 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. Example:

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

To be done

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

  600complement(G, NG) :-
  601    vertices(G,Vs),
  602    complement(G,Vs,NG).
  603
  604complement([], _, []).
  605complement([V-Ns|G], Vs, [V-INs|NG]) :-
  606    ord_add_element(Ns,V,Ns1),
  607    ord_subtract(Vs,Ns1,INs),
  608    complement(G, Vs, NG).

 reachable(+Vertex, +UGraph, -Vertices)

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

?- reachable(1,[1-[3,5],2-[4],3-[],4-[5],5-[]],V).
V = [1, 3, 5]

  618reachable(N, G, Rs) :-
  619    reachable([N], G, [N], Rs).
  620
  621reachable([], _, Rs, Rs).
  622reachable([N|Ns], G, Rs0, RsF) :-
  623    neighbours(N, G, Nei),
  624    ord_union(Rs0, Nei, Rs1, D),
  625    append(Ns, D, Nsi),
  626    reachable(Nsi, G, Rs1, RsF)