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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
|
// Copyright (C) 2007 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#undef DLIB_GRAPH_UTILs_ABSTRACT_
#ifdef DLIB_GRAPH_UTILs_ABSTRACT_
#include "../directed_graph.h"
#include "../algs.h"
namespace dlib
{
// ----------------------------------------------------------------------------------------
template <
typename T
>
typename T::edge_type& edge(
T& g,
unsigned long i,
unsigned long j
);
/*!
requires
- T is an implementation of graph/graph_kernel_abstract.h
- g.has_edge(i,j)
ensures
- returns a reference to the edge data for the edge connecting nodes i and j
(i.e. returns g.node(i).edge(x) such that g.node(i).neighbor(x).index() == j)
!*/
template <
typename T
>
typename const T::edge_type& edge(
const T& g,
unsigned long i,
unsigned long j
);
/*!
requires
- T is an implementation of graph/graph_kernel_abstract.h
- g.has_edge(i,j)
ensures
- returns a const reference to the edge data for the edge connecting nodes i and j
(i.e. returns g.node(i).edge(x) such that g.node(i).neighbor(x).index() == j)
!*/
// ----------------------------------------------------------------------------------------
template <
typename T
>
typename T::edge_type& edge(
T& g,
unsigned long parent_idx,
unsigned long child_idx
);
/*!
requires
- T is an implementation of directed_graph/directed_graph_kernel_abstract.h
- g.has_edge(parent_idx,child_idx)
ensures
- returns a reference to the edge data for the directed edge connecting parent
node g.node(parent_idx) to child node g.node(child_idx).
!*/
template <
typename T
>
typename const T::edge_type& edge(
const T& g,
unsigned long parent_idx,
unsigned long child_idx
);
/*!
requires
- T is an implementation of directed_graph/directed_graph_kernel_abstract.h
- g.has_edge(parent_idx,child_idx)
ensures
- returns a const reference to the edge data for the directed edge connecting
parent node g.node(parent_idx) to child node g.node(child_idx).
!*/
// ----------------------------------------------------------------------------------------
template <
typename T
>
bool graph_has_symmetric_edges (
const T& graph
);
/*!
requires
- T is an implementation of directed_graph/directed_graph_kernel_abstract.h
ensures
- if (All nodes have either 0 edges between them or 2 edges between them.
That is, if there is an edge pointing from node A to node B then there is
also an edge from B to A) then
- returns true
- else
- returns false
!*/
// ----------------------------------------------------------------------------------------
template <
typename T
>
bool graph_contains_directed_cycle (
const T& graph
);
/*!
requires
- T is an implementation of directed_graph/directed_graph_kernel_abstract.h
ensures
- if (there is a directed cycle in the given graph) then
- returns true
- else
- returns false
!*/
// ----------------------------------------------------------------------------------------
template <
typename T
>
bool graph_contains_undirected_cycle (
const T& graph
);
/*!
requires
- T is an implementation of directed_graph/directed_graph_kernel_abstract.h or
T is an implementation of graph/graph_kernel_abstract.h
ensures
- if (there is an undirected cycle in the given graph) then
- returns true
- else
- returns false
!*/
// ----------------------------------------------------------------------------------------
template <
typename T
>
bool graph_contains_length_one_cycle (
const T& graph
);
/*!
requires
- T is an implementation of directed_graph/directed_graph_kernel_abstract.h or
T is an implementation of graph/graph_kernel_abstract.h
ensures
- if (it is the case that graph.has_edge(i,i) == true for some i) then
- returns true
- else
- returns false
!*/
// ----------------------------------------------------------------------------------------
template <
typename src_type,
typename dest_type
>
void copy_graph_structure (
const src_type& src,
dest_type& dest
);
/*!
requires
- src_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
src_type is an implementation of graph/graph_kernel_abstract.h
- dest_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
dest_type is an implementation of graph/graph_kernel_abstract.h
- dest_type is not a directed_graph when src_type is a graph
ensures
- this function copies the graph structure from src into dest
- #dest.number_of_nodes() == src.number_of_nodes()
- for all valid i: #dest.node(i).item has an initial value for its type
- for all valid i and j:
- if (src.has_edge(i,j) == true) then
- #dest.has_edge(i,j) == true
!*/
// ----------------------------------------------------------------------------------------
template <
typename src_type,
typename dest_type
>
void copy_graph (
const src_type& src,
dest_type& dest
);
/*!
requires
- src_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
src_type is an implementation of graph/graph_kernel_abstract.h
- dest_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
dest_type is an implementation of graph/graph_kernel_abstract.h
- src_type and dest_type are both the same kind of graph. That is, they
are either both directed or both undirected.
- the node and edge data in the graphs are copyable via operator=().
ensures
- #dest is a complete duplicate of src.
!*/
// ----------------------------------------------------------------------------------------
template <
typename directed_graph_type,
typename graph_type
>
void create_moral_graph (
const directed_graph_type& g,
graph_type& moral_graph
);
/*!
requires
- directed_graph_type is an implementation of directed_graph/directed_graph_kernel_abstract.h
- graph_type is an implementation of graph/graph_kernel_abstract.h
- graph_contains_directed_cycle(g) == false
ensures
- #moral_graph == the moralized version of the directed graph g
- #moral_graph.number_of_nodes() == g.number_of_nodes()
- for all valid i and j:
- if (g.has_edge(i,j) == true) then
- #moral_graph.has_edge(i,j) == true
(i.e. all the edges that are in g are also in moral_graph)
- for all valid i:
- for all pairs p1 and p2 such that p1 != p2 and g.node(p1) and g.node(p2) are both
parents of node g.node(i):
- #moral_graph.has_edge(p1,p2) == true
(i.e. all the parents of a node are connected in the moral graph)
!*/
// ----------------------------------------------------------------------------------------
template <
typename T,
typename S
>
void find_connected_nodes (
const T& n,
S& visited
);
/*!
requires
- T is a node_type from an implementation of directed_graph/directed_graph_kernel_abstract.h or
T is a node_type from an implementation of graph/graph_kernel_abstract.h
- S is an implementation of set/set_kernel_abstract.h
ensures
- let G be the graph that contains node n
- #visited.is_member(n.index()) == true
- for all i such that there is an undirected path from n to G.node(i):
- #visited.is_member(i) == true
- for all i such that visited.is_member(i):
- #visited.is_member(i) == true
(i.e. this function doesn't remove anything from visited. So if
it contains stuff when you call this function then it will still
contain those things once the function ends)
!*/
// ----------------------------------------------------------------------------------------
template <
typename T
>
bool graph_is_connected (
const T& g
);
/*!
requires
- T is an implementation of directed_graph/directed_graph_kernel_abstract.h or
T is an implementation of graph/graph_kernel_abstract.h
ensures
- every node in g has an undirected path to every other node in g.
I.e. g is a connected graph
!*/
// ----------------------------------------------------------------------------------------
template <
typename graph_type,
typename sets_of_int
>
bool is_clique (
const graph_type& g,
const sets_of_int& clique
);
/*!
requires
- graph_type is an implementation of graph/graph_kernel_abstract.h
- sets_of_int is an implementation of set/set_kernel_abstract.h
and it contains unsigned long objects.
- graph_contains_length_one_cycle(g) == false
- for all x such that clique.is_member(x):
- x < g.number_of_nodes()
ensures
- if (it is true that for all i and j such that clique.is_member(i) and
clique.is_member(j) then g.has_edge(i,j) == true) then
- returns true
- else
- returns false
- if (clique.size() == 0) then
- returns true
(this is just a special case of the above condition)
- else
- returns false
!*/
// ----------------------------------------------------------------------------------------
template <
typename graph_type,
typename sets_of_int
>
bool is_maximal_clique (
const graph_type& g,
const sets_of_int& clique
);
/*!
requires
- graph_type is an implementation of graph/graph_kernel_abstract.h
- sets_of_int is an implementation of set/set_kernel_abstract.h
and it contains unsigned long objects.
- graph_contains_length_one_cycle(g) == false
- for all x such that clique.is_member(x):
- x < g.number_of_nodes()
- is_clique(g,clique) == true
ensures
- if (there is no x such that clique.is_member(x) == false
and g.has_edge(i,x) for all i such that cliques.is_member(i)) then
- returns true
- else
- returns false
- if (clique.size() == 0) then
- returns true
(this is just a special case of the above condition)
- else
- returns false
!*/
// ----------------------------------------------------------------------------------------
template <
typename graph_type,
typename set_of_sets_of_int
>
void triangulate_graph_and_find_cliques (
graph_type& g,
set_of_sets_of_int& cliques
);
/*!
requires
- graph_type is an implementation of graph/graph_kernel_abstract.h
- set_of_sets_of_int is an implementation of set/set_kernel_abstract.h
and it contains another set object which is comparable by operator< and
itself contains unsigned long objects.
(e.g. set<set<unsigned long>::compare_1a>::kernel_1a)
- graph_contains_length_one_cycle(g) == false
- graph_is_connected(g) == true
ensures
- #g.number_of_nodes() == g.number_of_nodes()
- all this function does to g is add edges to it until g becomes a
chordal graph where a chordal graph is a graph where each cycle
in the graph of 4 or more nodes has an edge joining two nodes
that are not adjacent in the cycle.
- #cliques.size() == the number of maximal cliques in the graph #g
- for all valid sets S such that #cliques.is_member(S):
- for all valid integers i and j such that S.is_member(i) == true
and S.is_member(j) == true and i != j:
- #g.has_edge(i,j) == true
!*/
// ----------------------------------------------------------------------------------------
template <
typename graph_type,
typename join_tree_type
>
bool is_join_tree (
const graph_type& g,
const join_tree_type& join_tree
);
/*!
requires
- graph_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
graph_type is an implementation of graph/graph_kernel_abstract.h
- join_tree_type is an implementation of graph/graph_kernel_abstract.h
- join_tree_type::type is an implementation of set/set_compare_abstract.h and
this set type contains unsigned long objects.
- join_tree_type::edge_type is an implementation of set/set_compare_abstract.h and
this set type contains unsigned long objects.
- graph_contains_length_one_cycle(g) == false
- graph_is_connected(g) == true
ensures
- if (join_tree is a valid join tree of graph g. That is, join_tree is a
tree decomposition of g) then
- returns true
- else
- returns false
- a join tree of graph g is defined as follows:
- graph_contains_undirected_cycle(join_tree) == false
- graph_is_connected(join_tree) == true
- for all valid i:
- join_tree.node(i).item == a non-empty set containing node indexes
from g. That is, this set contains all the nodes from g that are
in this cluster in the join tree
- for all valid i and j such that i and j are both < join_tree.number_of_nodes()
- let X be the set of numbers that is contained in both join_tree.node(i).item
and join_tree.node(j).item
- It is the case that all nodes on the unique path between join_tree.node(i)
and join_tree.node(j) contain the numbers from X in their sets.
- edge(join_tree,i,j) == a set containing the intersection of
join_tree.node(i).item and join_tree.node(j).item
- the node index for every node in g appears in some node in join_tree at
least once.
!*/
// ----------------------------------------------------------------------------------------
template <
typename graph_type,
typename join_tree_type
>
void create_join_tree (
const graph_type& g,
join_tree_type& join_tree
);
/*!
requires
- graph_type is an implementation of graph/graph_kernel_abstract.h
- join_tree_type is an implementation of graph/graph_kernel_abstract.h
- join_tree_type::type is an implementation of set/set_compare_abstract.h and
this set type contains unsigned long objects.
- join_tree_type::edge_type is an implementation of set/set_compare_abstract.h and
this set type contains unsigned long objects.
- graph_contains_length_one_cycle(g) == false
- graph_is_connected(g) == true
ensures
- #is_join_tree(g, join_tree) == true
!*/
// ----------------------------------------------------------------------------------------
}
#endif // DLIB_GRAPH_UTILs_ABSTRACT_
|
