1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
\libdoc{ugraphs}{Unweighted Graphs}
\label{sec:lib:ugraphs}
\makebox[\linewidth]{\hfill Authors: \emph{Richard O'Keefe \& Vitor Santos Costa}}
\begin{quote}{\it
Implementation and documentation are copied from YAP 5.0.1. The
\pllib{ugraph} library is based on code originally written by Richard
O'Keefe. The code was then extended to be compatible with the SICStus
Prolog ugraphs library. Code and documentation have been cleaned and
style has been changed to be more in line with the rest of SWI-Prolog.}
{\it
The ugraphs library was originally released in the public domain.
The YAP version is covered by the Perl Artistic license, version 2.0.
This code is dual-licensed under the modified GPL as used for all
SWI-Prolog libraries or the Perl Artistic license, version 2.0.
}
\end{quote}
The routines assume directed graphs; undirected graphs may be
implemented by using two edges.
Originally graphs were represented in two formats. The SICStus library
and this version of \pllib{ugraphs.pl} only use the
\jargon{S-representation}. The S-representation of a graph is a list of
(vertex-neighbors) pairs, where the pairs are in standard order (as
produced by keysort) and the neighbors of each vertex are also in
standard order (as produced by sort). This form is convenient for many
calculations. Each vertex appears in the S-representation, even if it
has no neighbors.
\begin{description}
\predicate{vertices_edges_to_ugraph}{3}{+Vertices, +Edges, -Graph}
Given a graph with a set of \arg{Vertices} and a set of \arg{Edges},
\arg{Graph} must unify with the corresponding S-representation. Note
that vertices without edges will appear in \arg{Vertices} but not in
\arg{Edges}. Moreover, it is sufficient for a vertex to appear in
\arg{Edges}.
\begin{code}
?- vertices_edges_to_ugraph([],[1-3,2-4,4-5,1-5], L).
L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[]]
\end{code}
In this case all vertices are defined implicitly. The next example shows
three unconnected vertices:
\begin{code}
?- 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-[]] ?
\end{code}
\predicate{vertices}{2}{+Graph, -Vertices}
Unify \arg{Vertices} with all vertices appearing in \arg{Graph}. Example:
\begin{code}
?- vertices([1-[3,5],2-[4],3-[],4-[5],5-[]], L).
L = [1, 2, 3, 4, 5]
\end{code}
\predicate{edges}{2}{+Graph, -Edges}
Unify \arg{Edges} with all edges appearing in \arg{Graph}. Example:
\begin{code}
?- edges([1-[3,5],2-[4],3-[],4-[5],5-[]], L).
L = [1-3, 1-5, 2-4, 4-5]
\end{code}
\predicate{add_vertices}{3}{+Graph, +Vertices, -NewGraph}
Unify \arg{NewGraph} with a new graph obtained by adding the list of
\arg{Vertices} to \arg{Graph}. Example:
\begin{code}
?- add_vertices([1-[3,5],2-[]], [0,1,2,9], NG).
NG = [0-[], 1-[3,5], 2-[], 9-[]]
\end{code}
\predicate{del_vertices}{3}{+Graph, +Vertices, -NewGraph}
Unify \arg{NewGraph} with a new graph obtained by deleting the list of
\arg{Vertices} and all edges that start from or go to a vertex in
\arg{Vertices} from \arg{Graph}. Example:
\begin{code}
?- del_vertices([2,1],
[1-[3,5],2-[4],3-[],4-[5],
5-[],6-[],7-[2,6],8-[]],
NL).
NL = [3-[],4-[5],5-[],6-[],7-[6],8-[]]
\end{code}
\predicate{add_edges}{3}{+Graph, +Edges, -NewGraph}
Unify \arg{NewGraph} with a new graph obtained by adding the list of
\arg{Edges} to \arg{Graph}. Example:
\begin{code}
?- 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-[]]
\end{code}
\predicate{del_edges}{3}{+Graph, +Edges, -NewGraph}
Unify \arg{NewGraph} with a new graph obtained by removing the list of
\arg{Edges} from \arg{Graph}. Notice that no vertices are deleted. Example:
\begin{code}
?- 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-[]]
\end{code}
\predicate{transpose_ugraph}{2}{+Graph, -NewGraph}
Unify \arg{NewGraph} with a new graph obtained from \arg{Graph} by
replacing all edges of the form V1-V2 by edges of the form V2-V1. The
cost is $O(|V|^2)$. Notice that an undirected graph is its own transpose.
Example:
\begin{code}
?- transpose_ugraph([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-[]]
\end{code}
\predicate{neighbours}{3}{+Vertex, +Graph, -Vertices}
Unify \arg{Vertices} with the list of neighbours of vertex \arg{Vertex}
in \arg{Graph}. Example:
\begin{code}
?- neighbours(4,[1-[3,5],2-[4],3-[],
4-[1,2,7,5],5-[],6-[],7-[],8-[]], NL).
NL = [1,2,7,5]
\end{code}
\predicate{neighbors}{3}{+Vertex, +Graph, -Vertices}
American version of neighbours/3.
\predicate{complement}{2}{+Graph, -NewGraph}
Unify \arg{NewGraph} with the graph complementary to \arg{Graph}. Example:
\begin{code}
?- 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]]
\end{code}
\predicate{compose}{3}{+LeftGraph, +RightGraph, -NewGraph}
Compose \arg{NewGraph} by connecting the \jargon{drains} of \arg{LeftGraph} to
the \jargon{sources} of \arg{RightGraph}. Example:
\begin{code}
?- compose([1-[2],2-[3]],[2-[4],3-[1,2,4]],L).
L = [1-[4], 2-[1,2,4], 3-[]]
\end{code}
\predicate{ugraph_union}{3}{+Graph1, +Graph2, -NewGraph}
\arg{NewGraph} is the union of \arg{Graph1} and \arg{Graph2}. Example:
\begin{code}
?- ugraph_union([1-[2],2-[3]],[2-[4],3-[1,2,4]],L).
L = [1-[2], 2-[3,4], 3-[1,2,4]]
\end{code}
\predicate{top_sort}{2}{+Graph, -Sort}
Generate the set of nodes \arg{Sort} as a topological sorting of
\arg{Graph}, if one is possible. 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:
\begin{code}
?- top_sort([1-[2], 2-[3], 3-[]], L).
L = [1, 2, 3]
\end{code}
\predicate{top_sort}{3}{+Graph, -Sort0, -Sort}
Generate the difference list Sort-Sort0 as a topological sorting of
\arg{Graph}, if one is possible.
\predicate{transitive_closure}{2}{+Graph, -Closure}
Generate the graph Closure as the transitive closure of
\arg{Graph}. Example:
\begin{code}
?- transitive_closure([1-[2,3],2-[4,5],4-[6]],L).
L = [1-[2,3,4,5,6], 2-[4,5,6], 4-[6]]
\end{code}
\predicate{reachable}{3}{+Vertex, +Graph, -Vertices}
Unify \arg{Vertices} with the set of all vertices in \arg{Graph} that are
reachable from \arg{Vertex}. Example:
\begin{code}
?- reachable(1,[1-[3,5],2-[4],3-[],4-[5],5-[]],V).
V = [1, 3, 5]
\end{code}
\end{description}
|
