1/* struct::graph - critcl - layer 1 declarations
2 * (a) Data structures.
3 */
4
5#ifndef _DS_H
6#define _DS_H 1
7
8#include "tcl.h"
9
10/*
11 * The data structures for a graph are mainly double-linked lists, combined
12 * with hash maps.
13 *
14 * We have a single structure per interpreter, -> GG.  This structure holds
15 * the counter and string buffer for the generation of automatic graph names.
16 *
17 * We have one structure per graph, -> G. It holds a single hash map for the
18 * attributes, and two hash maps with associated lists for nodes and arcs. The
19 * maps are for retrieval by name, the lists when searches by various features
20 * are done. Beyond we have the counters and string buffer for the generation
21 * of automatic arc- and node-names. As the information for nodes and arcs are
22 * identical they are pulled together in their own common structure -> GCC.
23 *
24 * The basic information of both nodes and arcs themselves is the same as
25 * well, name and attributes, and the graph owning them. Pulled together in a
26 * common structure, -> GC. This also holds the prev/next linkage for the per
27 * graph lists starting in GCC. The node/arc structures are pseudo-derived
28 * from this structure.
29 *
30 * Each node manages two lists of arcs, incoming and outgoing ones. The list
31 * elements are -> GL structures, also called the interlinks, as they weld
32 * nodes and arcs together. Neither node nor arcs refer directly to each
33 * other, but go through these interlinks. The indirection allows the
34 * insertion, movement and removal of arcs without having to perform complex
35 * updates in the node and arc structures. Like shifting array elements, with
36 * O(n^2) effort. The list anchors are -> GLA structures, keeping track of the
37 * list length as well.
38 *
39 * Arcs manage their source/target directly, by refering to the relevant
40 * interlink structures.
41 */
42
43/*
44 * Forward declarations of references to graphs, nodes, and arcs.
45 */
46
47typedef struct GL* GLPtr; /* node/arc interlink */
48typedef struct GC* GCPtr; /* node/arc common */
49typedef struct GN* GNPtr; /* node */
50typedef struct GA* GAPtr; /* arc */
51typedef struct G*  GPtr;  /* graph */
52typedef struct GG* GGPtr; /* Per-interp (global) */
53
54/*
55 * Chains of arcs, structure for interlinkage between nodes and arcs.
56 * Operations API & Impl. -> gl.[ch]
57 */
58
59typedef struct GL {
60    GNPtr n;    /* Node the interlink belongs to */
61    GAPtr a;    /* Arc the  interlink belongs to */
62    GLPtr prev; /* Previous interlink in chain */
63    GLPtr next; /* Next     interlink in chain */
64} GL;
65
66/*
67 * Data common to nodes and arcs
68 */
69
70typedef struct GC {
71    /* Identity / handle */
72    /* Internal rep should be of type */
73    /* 'tcllib::struct::graph/critcl::{node,arc}'. */
74    /* See below. */
75
76    Tcl_Obj*	   name;
77    Tcl_HashEntry* he;
78
79    /* Node / Arc attributes */
80
81    Tcl_HashTable* attr; /* NULL if the entity has no attributes */
82
83    /* Basic linkage of node/arc to its graph */
84
85    GPtr  graph; /* Graph the node/arc belongs to */
86    GCPtr next;  /* Double linked list of all */
87    GCPtr prev;  /* nodes/arc. See GGC for the head */
88} GC;
89
90/*
91 * Interlink chains, anchor structure
92 */
93
94typedef struct GLA {
95    GL* first; /* First interlink */
96    int n;     /* Number of interlinks */
97} GLA;
98
99/*
100 * Node structure.
101 */
102
103typedef struct GN {
104    GC base; /* Basics, common information */
105
106    /* Node navigation. Incoming/Outgoing arcs, via interlink chains. */
107
108    GLA in;
109    GLA out;
110} GN;
111
112/*
113 * Arc structure.
114 */
115
116typedef struct GA {
117    GC base; /* Basics, common information */
118
119    /* Arc navigation. Start/End node. Indirect specification through an
120     * interlink.
121     */
122
123    GL* start; /* Interlink to node where arc begins */
124    GL* end;   /* Interlink to node where arc ends */
125
126    Tcl_Obj* weight; /* If not NULL the weight of the arc */
127} GA;
128
129/*
130 * Helper structure for the lists and maps of nodes/arcs.
131 */
132
133typedef struct GCC {
134    Tcl_HashTable* map;   /* Mapping names -> structure */
135    GC*            first; /* Start of entity list */
136    int            n;     /* Length of the list */
137} GCC;
138
139/*
140 * Graph structure.
141 */
142
143typedef struct G {
144    Tcl_Command    cmd;   /* Token of the object command for * the graph */
145    GCC            nodes; /* All nodes */
146    GCC            arcs;  /* All arcs */
147    Tcl_HashTable* attr;  /* Graph attributes. NULL if the graph has none */
148
149    /* Generation of node and arc handles. Graph local storage, makes the code
150     * thread oblivious.
151     */
152
153    char handle [50];
154    int  ncounter;	/* Counter used by the generator of node names */
155    int  acounter;	/* Counter used by the generator of arc names */
156} G;
157
158/*
159 * 'Global' management. One structure per interpreter.
160 */
161
162typedef struct GG {
163    long int counter;  /* Graph id generator */
164    char     buf [50]; /* Buffer for handle construction */
165} GG;
166
167
168typedef GC* (GN_GET_GC) (G* g, Tcl_Obj* x, Tcl_Interp* interp, Tcl_Obj* graph);
169
170#endif /* _DS_H */
171
172/*
173 * Local Variables:
174 * mode: c
175 * c-basic-offset: 4
176 * fill-column: 78
177 * End:
178 */
179