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
|
/* struct::graph - critcl - layer 1 declarations
* (a) Data structures.
*/
#ifndef _DS_H
#define _DS_H 1
#include "tcl.h"
/*
* The data structures for a graph are mainly double-linked lists, combined
* with hash maps.
*
* We have a single structure per interpreter, -> GG. This structure holds
* the counter and string buffer for the generation of automatic graph names.
*
* We have one structure per graph, -> G. It holds a single hash map for the
* attributes, and two hash maps with associated lists for nodes and arcs. The
* maps are for retrieval by name, the lists when searches by various features
* are done. Beyond we have the counters and string buffer for the generation
* of automatic arc- and node-names. As the information for nodes and arcs are
* identical they are pulled together in their own common structure -> GCC.
*
* The basic information of both nodes and arcs themselves is the same as
* well, name and attributes, and the graph owning them. Pulled together in a
* common structure, -> GC. This also holds the prev/next linkage for the per
* graph lists starting in GCC. The node/arc structures are pseudo-derived
* from this structure.
*
* Each node manages two lists of arcs, incoming and outgoing ones. The list
* elements are -> GL structures, also called the interlinks, as they weld
* nodes and arcs together. Neither node nor arcs refer directly to each
* other, but go through these interlinks. The indirection allows the
* insertion, movement and removal of arcs without having to perform complex
* updates in the node and arc structures. Like shifting array elements, with
* O(n^2) effort. The list anchors are -> GLA structures, keeping track of the
* list length as well.
*
* Arcs manage their source/target directly, by refering to the relevant
* interlink structures.
*/
/*
* Forward declarations of references to graphs, nodes, and arcs.
*/
typedef struct GL* GLPtr; /* node/arc interlink */
typedef struct GC* GCPtr; /* node/arc common */
typedef struct GN* GNPtr; /* node */
typedef struct GA* GAPtr; /* arc */
typedef struct G* GPtr; /* graph */
typedef struct GG* GGPtr; /* Per-interp (global) */
/*
* Chains of arcs, structure for interlinkage between nodes and arcs.
* Operations API & Impl. -> gl.[ch]
*/
typedef struct GL {
GNPtr n; /* Node the interlink belongs to */
GAPtr a; /* Arc the interlink belongs to */
GLPtr prev; /* Previous interlink in chain */
GLPtr next; /* Next interlink in chain */
} GL;
/*
* Data common to nodes and arcs
*/
typedef struct GC {
/* Identity / handle */
/* Internal rep should be of type */
/* 'tcllib::struct::graph/critcl::{node,arc}'. */
/* See below. */
Tcl_Obj* name;
Tcl_HashEntry* he;
/* Node / Arc attributes */
Tcl_HashTable* attr; /* NULL if the entity has no attributes */
/* Basic linkage of node/arc to its graph */
GPtr graph; /* Graph the node/arc belongs to */
GCPtr next; /* Double linked list of all */
GCPtr prev; /* nodes/arc. See GGC for the head */
} GC;
/*
* Interlink chains, anchor structure
*/
typedef struct GLA {
GL* first; /* First interlink */
int n; /* Number of interlinks */
} GLA;
/*
* Node structure.
*/
typedef struct GN {
GC base; /* Basics, common information */
/* Node navigation. Incoming/Outgoing arcs, via interlink chains. */
GLA in;
GLA out;
} GN;
/*
* Arc structure.
*/
typedef struct GA {
GC base; /* Basics, common information */
/* Arc navigation. Start/End node. Indirect specification through an
* interlink.
*/
GL* start; /* Interlink to node where arc begins */
GL* end; /* Interlink to node where arc ends */
Tcl_Obj* weight; /* If not NULL the weight of the arc */
} GA;
/*
* Helper structure for the lists and maps of nodes/arcs.
*/
typedef struct GCC {
Tcl_HashTable* map; /* Mapping names -> structure */
GC* first; /* Start of entity list */
int n; /* Length of the list */
} GCC;
/*
* Graph structure.
*/
typedef struct G {
Tcl_Command cmd; /* Token of the object command for * the graph */
GCC nodes; /* All nodes */
GCC arcs; /* All arcs */
Tcl_HashTable* attr; /* Graph attributes. NULL if the graph has none */
/* Generation of node and arc handles. Graph local storage, makes the code
* thread oblivious.
*/
char handle [50];
int ncounter; /* Counter used by the generator of node names */
int acounter; /* Counter used by the generator of arc names */
} G;
/*
* 'Global' management. One structure per interpreter.
*/
typedef struct GG {
long int counter; /* Graph id generator */
char buf [50]; /* Buffer for handle construction */
} GG;
typedef GC* (GN_GET_GC) (G* g, Tcl_Obj* x, Tcl_Interp* interp, Tcl_Obj* graph);
#endif /* _DS_H */
/*
* Local Variables:
* mode: c
* c-basic-offset: 4
* fill-column: 78
* End:
*/
|
