PublicShow sourceugraphs.pl -- Graph manipulation library

The S-representation of a graph is a list of (vertex-neighbours) pairs, where the pairs are in standard order (as produced by keysort) and the neighbours of each vertex are also in standard order (as produced by sort). This form is convenient for many calculations.

A new UGraph from raw data can be created using vertices_edges_to_ugraph/3.

Adapted to support some of the functionality of the SICStus ugraphs library by Vitor Santos Costa.

Ported from YAP 5.0.1 to SWI-Prolog by Jan Wielemaker.

author
- R.A.O'Keefe
- Vitor Santos Costa
- Jan Wielemaker
license
- GPL+SWI-exception or Artistic 2.0
Source 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.
Source 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-[]]
Source 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.
Source ugraph_union(+Set1, +Set2, ?Union)
Is true when Union is the union of Set1 and Set2. This code is a copy of set union
Source 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.
Source 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.
Source compose(G1, G2, Composition)
Calculates the composition of two S-form graphs, which need not have the same set of vertices.
Source top_sort(+Graph, -Sorted) is semidet
Source 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.

Source neighbors(+Vertex, +Graph, -Neigbours) is det
Source neighbours(+Vertex, +Graph, -Neigbours) is det
Neigbours is a sorted list of the neighbours of Vertex in Graph.
Source top_sort(+Graph, -Sorted) is semidet
Source 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.

Source neighbors(+Vertex, +Graph, -Neigbours) is det
Source neighbours(+Vertex, +Graph, -Neigbours) is det
Neigbours is a sorted list of the neighbours of Vertex in Graph.

Undocumented predicates

The following predicates are exported, but not or incorrectly documented.

Source transitive_closure(Arg1, Arg2)
Source reachable(Arg1, Arg2, Arg3)
Source del_edges(Arg1, Arg2, Arg3)
Source complement(Arg1, Arg2)
Source add_edges(Arg1, Arg2, Arg3)
Source add_vertices(Arg1, Arg2, Arg3)