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
453
454
455
456
457
|
/*
data structures and stuff for the planarity algorithm
Paulette Lieby, Brendan McKay
October 2001
*/
#ifndef _PLANARITY_H_
#define _PLANARITY_H_
/* The following line must be uncommented for compiling into Magma. */
/* #define PLANAR_IN_MAGMA */
#ifdef PLANAR_IN_MAGMA
#include "defs.h"
#include "system.h" /* includes <stdio.h> <signal.h> "system_math.h"
<setjmp.h> <ctype.h> and more
*/
#else
/* not PLANAR_IN_MAGMA */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#undef FALSE
#undef TRUE
#define FALSE 0
#define TRUE 1
#define NP NULL
#define ASSERT(x) assert(x)
#define DIE() exit(0)
#define mem_malloc malloc
#define mem_realloc realloc
#define mem_free free
#include "naututil.h"
#ifdef CPUDEFS
CPUDEFS
#endif
#define time_current_user() CPUTIME
#endif /* not PLANAR_IN_MAGMA */
#include "nauty.h"
/*
max number of edges (and directed edges) for the embed_graph
data structure:
1 more than for a (possibly) planar graph to allow search for obstructions
1. if the graph is planar the embedding cannot possibly contain
more than 3*n - 6 edges (including the short cut edges)
2. if the graph is non planar, when retrieving and marking the
obstruction, we introduce EXACTLY one edge crossing
*/
#define MAXE(n) ((n) > 1 ? 3*(n) - 5 : 0)
#define MAXDE(n) (6*(n) - 10)
#define NIL (-1)
#define CUTV (-2) /* obviously used in diff. circ. than NILSIGN */
#define NILSIGN (-2)
#define CCLOCKW 1
#define CLOCKW -1
#define TE 1
#define BE 2
#define SCE 3
/*
various "marks" for various purposes, ONLY for the t_ver_edge str
note: do NOT use a mark in {0,..,n} since those values are
used either while initialising or in the walkup procedure
*/
#define MARK_EMBED(n) ((n)+1)
#define MARK_EXT_FACE(n) ((n)+2)
#define MARK_EXT_FACE_L(n) ((n)+3)
#define MARK_EXT_FACE_R(n) ((n)+4)
#define MARK_X_Y_PATH(n) ((n)+5)
#define MARK_MINORS(n) ((n)+6)
#define MIN_EMBED_MARK 0 /* ONLY for the t_embed_sparse_rep str */
typedef enum
{
MINOR_A,
MINOR_B,
MINOR_C,
MINOR_D,
MINOR_E,
MINOR_E1,
MINOR_E2,
MINOR_E3,
MINOR_E4,
MINOR_E5,
NBR_MINORS
} minor;
/*
a basic doubly linked circular list storing
vertices/edges from the "big" 2*n + 2(3*n-5) array of vertices/edges
only used internally in the planarity tester: especially
where ordering of the vertices is important
*/
typedef struct dlcl {
int info;
/*
info is:
- position in "big" array
*/
int in_adjl; /* if relevant, the pos in the adjl. list
of this edge
*/
int twin_in_adjl; /* if relevant, the pos in the adjl. list
of the twin of this edge
*/
int mult; /* if relevant, #occurences if this edge
(when graph is not simple
*/
struct dlcl * right;
struct dlcl * left;
} t_dlcl;
/*
a common structure for both (virtual) vertex & edge
*/
typedef struct ver_edge {
/* vertex data */
int label;
int DFS_parent;
int least_ancestor;
int lowpoint;
t_dlcl * separated_DFS_child_list;
t_dlcl * rep_in_parent_list;
t_dlcl * pertinent_bicomp_list;
int adjacent_to;
int visited;
/* edge data */
int neighbour;
int in_adjl;
int twin_in_adjl;
int mult;
int type;
int sign;
/* link the lot in a doubly linked circular list */
/* links indicate positions in the array of vertices/edges */
int link[2];
} t_ver_edge;
/*
data structure for the merge queue
*/
typedef struct merge_queue {
int start, end;
int *b;
} t_merge_queue;
/*
data structure for the sparse graph representation:
the array of vertices
*/
typedef struct ver_sparse_rep {
int first_edge; /* can be index into an adj. list
or an embedding */
} t_ver_sparse_rep;
/*
data structure for the sparse graph representation:
a record in the adjacency list
*/
typedef struct adjl_sparse_rep {
int end_vertex;
int next; /* next in list as an index in the adj. list */
} t_adjl_sparse_rep;
/*
data structure for the sparse graph representation:
a record in the embedding
*/
typedef struct embed_sparse_rep {
int in_adjl;/* index of edge in adj. list */
int next; /* next edge in embedding */
int prev; /* previous edge in embedding */
int inv; /* inverse edge */
int mark; /* a spot for marking */
} t_embed_sparse_rep;
/*
data structure for the sparse graph representation:
a record an individual edge
*/
typedef struct edge_sparse_rep {
int ends[2];
} t_edge_sparse_rep;
/*
data structure for the sparse graph representation:
a record for a component
*/
typedef struct comp_sparse_rep {
int nbr_v; /* nbr of vertices */
int *v; /* the actual vertices */
} t_comp_sparse_rep;
typedef struct graph_sparse_rep {
t_ver_sparse_rep *V;
int n;
t_adjl_sparse_rep *A;
int size_A;
int pos_A;
int nbr_e; /* ALWAYS # directed edges */
} t_graph_sparse_rep;
#ifdef __cplusplus
extern "C" {
#endif
/*
* embed_graph_protos.h
*/
/* aproto: file embed_graph/sparseg_adjl_pred.c */
extern boolean sparseg_adjl_dir_edge_exists (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int);
extern boolean sparseg_adjl_u_adj_v (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int);
extern boolean sparseg_adjl_sub (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, t_ver_sparse_rep *, int, t_adjl_sparse_rep *);
extern boolean sparseg_adjl_eq (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, t_ver_sparse_rep *, int, t_adjl_sparse_rep *);
/* aproto: endfile */
/* aproto: file embed_graph/VES_misc.c */
extern boolean embedg_VES_is_vertex (int, int);
extern boolean embedg_VES_is_virtual_vertex (int, int);
extern boolean embedg_VES_is_edge (int, int);
extern boolean embedg_VES_is_tree_edge (t_ver_edge *, int, int);
extern boolean embedg_VES_is_back_edge (t_ver_edge *, int, int);
extern boolean embedg_VES_is_short_cut_edge (t_ver_edge *, int, int);
extern void embedg_VES_print_vertex (int, int);
extern void embedg_VES_print_virtual_vertex (t_ver_edge *, int, int);
extern void embedg_VES_print_any_vertex (t_ver_edge *, int, int);
extern void embedg_VES_print_any_rec (t_ver_edge *, int, int);
extern void embedg_VES_print_edge (t_ver_edge *, int, int);
extern void embedg_VES_print_flipped_edges (t_ver_edge *, int, int);
extern int embedg_VES_get_edge_from_ver (t_ver_edge *, int, int);
extern int embedg_VES_get_ver_from_edge (t_ver_edge *, int, int);
extern int embedg_VES_get_twin_edge (t_ver_edge *, int, int);
extern int embedg_VES_get_ver_from_virtual (t_ver_edge *, int, int);
extern int embedg_VES_get_ver (t_ver_edge *, int, int);
extern int embedg_VES_get_next_in_dlcl (t_ver_edge *, int, int, int);
extern void embedg_VES_walk_bicomp (t_ver_edge *, int, int, int);
extern void embedg_VES_print_adj_list (t_ver_edge *, int, int, boolean);
extern boolean embedg_VES_is_adj_list_consistent (t_ver_edge *, int, int);
extern boolean embedg_VES_are_adj_lists_consistent (t_ver_edge *, int);
extern void embedg_VES_remove_edge (t_ver_edge *, int, int);
extern void embedg_VES_set_orientation (t_ver_edge *, int, int *);
/* aproto: endfile */
/* aproto: file embed_graph/embed_edge.c */
extern void embedg_VES_embed_edge (t_ver_edge *, int, int *, int, int, int, int, int);
extern void embedg_VES_add_edge (t_ver_edge *, int, int *, int, int, boolean, int);
/* aproto: endfile */
/* aproto: file embed_graph/embedg_misc.c */
extern void embedg_VES_delete (t_ver_edge *, int);
extern void embedg_VES_print (t_ver_edge *, int);
extern void embedg_VES_print_bigcomps (t_ver_edge *, int);
/* aproto: endfile */
/* aproto: file embed_graph/ext_face_walk.c */
extern void embedg_VES_get_succ_on_ext_face (t_ver_edge *, int, int, int, boolean, int, int *, int *);
extern void embedg_VES_get_succ_active_on_ext_face (t_ver_edge *, int, int, int, int, boolean, int, int *, int *);
extern void embedg_VES_get_succ_ext_active_on_ext_face (t_ver_edge *, int, int, int, int, boolean, int, int *, int *);
extern void embedg_VES_get_succ_pertinent_on_ext_face (t_ver_edge *, int, int, int, int, boolean, int, int *, int *);
/* aproto: endfile */
/* aproto: file embed_graph/isolator.c */
extern int embedg_iso_get_c_of_v (t_ver_edge *, int, int, int);
extern boolean embedg_iso_is_minor_A (t_ver_edge *, int, int *, int, int, int *);
extern void embedg_iso_get_x_y_w (t_ver_edge *, int, int, int, int, int, int, int, int *, int *, int *);
extern boolean embedg_iso_is_minor_B (t_ver_edge *, int, int *, int, int, int *, int *, int *);
extern void embedg_iso_get_highest_x_y_path (t_ver_edge *, int, int, int, int, int, int, int, int, int, int **, int **, int *, int *, boolean *, boolean *, boolean *);
/* aproto: endfile */
/* aproto: file embed_graph/mark_kur.c */
extern boolean embedg_VES_is_ext_face_marked (t_ver_edge *, int, int, int);
extern void embedg_mark_minor_A (t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int, int);
extern void embedg_mark_minor_B (t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int, int, int, int);
extern void embedg_mark_minor_C (t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int, int, int, int, int *, int *, int, boolean, boolean);
extern void embedg_mark_minor_D (t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int, int, int, int, int *, int *, int, int);
extern minor embedg_mark_minor_E (t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int, int, int, int, int *, int *, int);
/* aproto: endfile */
/* aproto: file embed_graph/merge_bicomps.c */
extern void embedg_VES_merge_simple_bicomps (t_ver_edge *, int, int, int, int, int);
extern void embedg_VES_merge_pertinent_bicomps (t_ver_edge *, int, int, int, int, int);
/* aproto: endfile */
/* aproto: file embed_graph/merge_queue_misc.c */
extern t_merge_queue embedg_merge_queue_new (int);
extern void embedg_merge_queue_delete (t_merge_queue);
extern boolean embedg_merge_queue_empty (t_merge_queue);
extern void embedg_merge_queue_print (t_merge_queue);
extern void embedg_merge_queue_append (t_merge_queue *, t_ver_edge *, int, int, int, int, int);
extern void embedg_merge_queue_append_vertex (t_merge_queue *, t_ver_edge *, int, int, int);
extern void embedg_merge_queue_append_virtual_vertex (t_merge_queue *, t_ver_edge *, int, int, int);
extern void embedg_merge_queue_get (t_merge_queue *, int *, int *, int *, int *);
extern void embedg_merge_queue_prune (t_merge_queue *, int *, int *, int *, int *);
/* aproto: endfile */
/* aproto: file embed_graph/obstruction.c */
extern void embedg_obstruction (t_ver_sparse_rep *, t_adjl_sparse_rep *, t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int, t_ver_sparse_rep **, t_adjl_sparse_rep **, int *);
extern minor embedg_mark_obstruction (t_dlcl **, t_dlcl **, t_ver_edge *, int, int *, int, int);
/* aproto: endfile */
/* aproto: file embed_graph/post_dfs_preproc.c */
extern t_dlcl *sparseg_order_wrt_lowpoint (int, int *, int *, t_dlcl *);
extern int *sparseg_find_least_ancestor (int, t_dlcl **);
extern int *sparseg_find_dfs_parent (int, t_dlcl **);
/* aproto: endfile */
/* aproto: file embed_graph/proper_face_walk.c */
extern boolean embedg_VES_get_succ_on_proper_face_with_avoidance (t_ver_edge *, int, int, int, int, boolean, int, int *, int *, int *);
extern void embedg_VES_get_succ_on_proper_face (t_ver_edge *, int, int, int, int, int, int *, int *, int *);
extern void embedg_VES_walk_proper_face (t_ver_edge *, int, int, int, boolean, int);
/* aproto: endfile */
/* aproto: file embed_graph/vertex_activity.c */
extern boolean embedg_VES_is_ver_pertinent (t_ver_edge *, int, int, int);
extern boolean embedg_VES_is_ver_ext_active (t_ver_edge *, int, int, int);
extern boolean embedg_VES_is_ver_int_active (t_ver_edge *, int, int, int);
extern boolean embedg_VES_is_ver_inactive (t_ver_edge *, int, int, int);
/* aproto: endfile */
/* aproto: file embed_graph/walkdown.c */
extern t_merge_queue embedg_walkdown (t_ver_edge *, int, int *, int);
/* aproto: endfile */
/* aproto: file embed_graph/sparseg_dlcl_misc.c */
extern void sparseg_dlcl_delete (t_dlcl **, int);
extern void sparseg_dlcl_print (t_dlcl **, int);
extern boolean sparseg_dlcl_is_adjacent (t_dlcl **, int, int, int, t_dlcl **);
extern void sparseg_dlcl_append_to_neigh_list (t_dlcl **, int, int, int, int);
extern void sparseg_dlcl_to_sparseg (t_dlcl **, int, int, t_ver_sparse_rep **, t_adjl_sparse_rep **);
extern boolean sparseg_dlcl_sub (t_dlcl **, int, t_dlcl **, int);
/* aproto: endfile */
/* aproto: file embed_graph/walkup.c */
extern void embedg_walkup (t_ver_edge *, int, int, t_dlcl *);
/* aproto: endfile */
/* aproto: file embed_graph/dfs_preprocessing.c */
extern void sparseg_adjl_dfs_preprocessing (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int *, int **, int **, int **, t_dlcl ***, t_dlcl ***, int **, int **, t_dlcl ***);
/* aproto: endfile */
/* aproto: file embed_graph/planar_by_edge_addition.c */
extern boolean sparseg_adjl_is_planar (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int *, t_dlcl ***, t_dlcl ***, t_dlcl ***, t_ver_edge **, int *, int *, int *);
/* aproto: endfile */
/* aproto: file embed_graph/recover.c */
extern void embedg_recover_embedding (t_ver_sparse_rep *, t_adjl_sparse_rep *, t_ver_edge *, int, int, t_dlcl **, t_ver_sparse_rep **, t_embed_sparse_rep **);
extern void embedg_recov_embed_walk_proper_face (int, int, t_adjl_sparse_rep *, t_embed_sparse_rep *, boolean, int);
extern boolean embedg_check_recov_embedding (int, int, int, t_ver_sparse_rep *, t_adjl_sparse_rep *, t_embed_sparse_rep *);
extern t_dlcl **embedg_recover_obstruction (t_ver_edge *, int, minor, int *);
extern boolean embedg_check_recov_obs (t_dlcl **, int, minor);
/* aproto: endfile */
/* aproto: file embed_graph/planar_alg_init.c */
extern t_ver_edge *embedg_planar_alg_init (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int *, int *, t_dlcl ***, t_dlcl ***, t_dlcl ***);
/* aproto: endfile */
/* aproto: file embed_graph/dlcl_misc.c */
extern t_dlcl *embedg_dlcl_rec_new (int);
extern void embedg_dlcl_rec_print (t_dlcl *);
extern void embedg_dlcl_print (t_dlcl *);
extern t_dlcl *embedg_dlcl_rec_append (t_dlcl *, t_dlcl *);
extern t_dlcl *embedg_dlcl_rec_prepend (t_dlcl *, t_dlcl *);
extern t_dlcl *embedg_dlcl_cat (t_dlcl *, t_dlcl *);
extern t_dlcl *embedg_dlcl_find (t_dlcl *, int);
extern t_dlcl *embedg_dlcl_find_with_NIL_twin_in_adjl (t_dlcl *, int);
extern t_dlcl *embedg_dlcl_delete_first (t_dlcl *);
extern t_dlcl *embedg_dlcl_delete_rec (t_dlcl *, t_dlcl *);
extern boolean embedg_dlcl_is_empty (t_dlcl *);
extern t_dlcl *embedg_dlcl_list_next (t_dlcl *);
extern t_dlcl *embedg_dlcl_list_prev (t_dlcl *);
extern t_dlcl *embedg_dlcl_list_last (t_dlcl *);
extern void embedg_dlcl_delete (t_dlcl *);
extern t_dlcl *embedg_dlcl_copy (t_dlcl *);
extern int embedg_dlcl_length (t_dlcl *);
/* aproto: endfile */
/* aproto: file embed_graph/sparseg_adjl.c */
extern boolean sparseg_adjl_plan_and_iso (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int *, t_ver_sparse_rep **, t_adjl_sparse_rep **, t_embed_sparse_rep **, int *);
extern int *sparseg_adjl_footprint (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int);
extern void sparseg_adjl_print (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, boolean);
extern void sparseg_adjl_embed_print (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, t_embed_sparse_rep *, boolean);
extern graph *sparseg_adjl_to_nauty_graph (t_ver_sparse_rep *, int, t_adjl_sparse_rep *);
extern t_edge_sparse_rep *sparseg_adjl_edges (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, boolean);
/* aproto: endfile */
/* aproto: file embed_graph/embedding.c */
extern void embedg_embedding (t_ver_sparse_rep *, t_adjl_sparse_rep *, t_ver_edge *, int, int, int, int, t_dlcl **, t_ver_sparse_rep **, t_embed_sparse_rep **);
extern void embedg_remove_SCE (t_ver_edge *, int, int);
extern int *embedg_vertices_orientation (t_ver_edge *, int);
extern int embedg_merge_remaining_virtual (t_ver_edge *, int);
extern int embedg_nbr_faces (t_ver_edge *, int, int, int *, int *);
extern boolean embedg_is_embed_valid (t_ver_edge *, int, int, int, int *, int *);
/* aproto: endfile */
/* aproto: file embed_graph/sparseg_adjl_modify.c */
extern boolean sparseg_adjl_add_edge (t_ver_sparse_rep *, int, t_adjl_sparse_rep **, int *, int *, int, int, boolean);
extern boolean sparseg_adjl_add_edge_no_extend (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int *, int, int, boolean);
extern boolean sparseg_adjl_add_dir_edge (t_ver_sparse_rep *, int, t_adjl_sparse_rep **, int *, int *, int, int, boolean);
extern boolean sparseg_adjl_add_dir_edge_no_extend (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int *, int, int, boolean);
extern boolean sparseg_adjl_remove_edge_no_red (t_ver_sparse_rep *, t_adjl_sparse_rep *, int, int);
extern boolean sparseg_adjl_remove_dir_edge_no_red (t_ver_sparse_rep *, t_adjl_sparse_rep *, int, int);
extern int sparseg_adjl_remove_all_dir_edge_no_red (t_ver_sparse_rep *, t_adjl_sparse_rep *, int, int);
extern void sparseg_adjl_add_vertices (t_ver_sparse_rep **, int, int);
extern void sparseg_adjl_add_vertices_no_extend (t_ver_sparse_rep *, int, int);
extern void sparseg_adjl_remove_vertex (t_ver_sparse_rep **, int, t_adjl_sparse_rep *, int, int, int *);
extern void sparseg_adjl_remove_vertex_no_red (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int *);
extern void sparseg_adjl_relabel_vertex (t_adjl_sparse_rep *, int, int);
/* aproto: endfile */
/* aproto: file embed_graph/sparseg_adjl_misc.c */
extern void sparseg_adjl_assign_V (t_ver_sparse_rep *, t_ver_sparse_rep *, int);
extern t_ver_sparse_rep *sparseg_adjl_dup_V (t_ver_sparse_rep *, int);
extern void sparseg_adjl_assign_A (t_adjl_sparse_rep *, t_adjl_sparse_rep *, int);
extern t_adjl_sparse_rep *sparseg_adjl_dup_A (t_adjl_sparse_rep *, int);
extern void sparseg_embed_assign_E (t_embed_sparse_rep *, t_embed_sparse_rep *, int);
extern t_embed_sparse_rep *sparseg_embed_dup_E (t_embed_sparse_rep *, int);
extern void sparseg_adjl_underlying_undir (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, t_ver_sparse_rep **, t_adjl_sparse_rep **, int *, int *);
extern void sparseg_adjl_edge_union (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, t_ver_sparse_rep *, t_adjl_sparse_rep *, boolean, t_ver_sparse_rep **, t_adjl_sparse_rep **, int *, int *);
extern void sparseg_adjl_add_edges (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int *, t_ver_sparse_rep *, t_adjl_sparse_rep *, boolean, int *);
/* aproto: endfile */
/* aproto: file embed_graph/degree.c */
extern int *sparseg_adjl_degree_seq (t_ver_sparse_rep *, int, t_adjl_sparse_rep *);
/* aproto: endfile */
/* aproto: file embed_graph/neighbours.c */
extern void sparseg_adjl_vertex_out_neighbours (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int **, int *);
extern void sparseg_adjl_vertex_in_neighbours (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int **, int *);
/* aproto: endfile */
/* aproto: file embed_graph/misc.c */
extern void sparseg_comp_delete (t_comp_sparse_rep *, int);
extern void sparseg_comp_print (t_comp_sparse_rep *, int);
/* aproto: endfile */
/* aproto: file embed_graph/dfs_things.c */
extern void sparseg_adjl_dfs_things (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, boolean, int *, t_ver_sparse_rep **, t_adjl_sparse_rep **, int *, int **, int **, int **, int **, int **, int *, int **, int *, t_comp_sparse_rep **);
extern void sparseg_adjl_dfs_add_vertex_to_comp (t_comp_sparse_rep **, int *, int);
extern void sparseg_adjl_dfs_create_new_comp (t_comp_sparse_rep **, int *);
extern void sparseg_adjl_from_comps_to_sparseg_adjl (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, t_comp_sparse_rep *, int, t_graph_sparse_rep **);
extern void sparseg_adjl_from_start_comp_to_sparseg_adjl (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int *, t_graph_sparse_rep **);
/* aproto: endfile */
/* aproto: file embed_graph/dfs_for_digraph.c */
extern void sparseg_adjl_dfs_digraph (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, int, int, t_ver_sparse_rep **, t_adjl_sparse_rep **, int *, int **, int **, int **, int **, int **, int *, t_comp_sparse_rep **);
/* aproto: endfile */
/* aproto: file embed_graph/bfs.c */
extern void sparseg_adjl_bfs (t_ver_sparse_rep *, int, t_adjl_sparse_rep *, boolean, int, t_ver_sparse_rep **, t_adjl_sparse_rep **, int *);
/* aproto: endfile */
/* aproto: file embed_graph/faces.c */
extern void sparseg_adjl_walk_proper_face (int, t_adjl_sparse_rep *, t_embed_sparse_rep *, int, boolean, int, int *, t_edge_sparse_rep *);
extern void sparseg_adjl_get_face_edges (int, t_adjl_sparse_rep *, int, t_embed_sparse_rep *, int, t_edge_sparse_rep **, int *, boolean, int);
/* aproto: endfile */
#ifdef __cplusplus
}
#endif
#endif /* _PLANARITY_H_ */
|
