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 47 typedef struct GL* GLPtr; /* node/arc interlink */ 48 typedef struct GC* GCPtr; /* node/arc common */ 49 typedef struct GN* GNPtr; /* node */ 50 typedef struct GA* GAPtr; /* arc */ 51 typedef struct G* GPtr; /* graph */ 52 typedef 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 59 typedef 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 70 typedef 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 94 typedef struct GLA { 95 GL* first; /* First interlink */ 96 int n; /* Number of interlinks */ 97 } GLA; 98 99 /* 100 * Node structure. 101 */ 102 103 typedef 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 116 typedef 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 133 typedef 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 143 typedef 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 162 typedef struct GG { 163 size_t counter; /* Graph id generator */ 164 char buf [50]; /* Buffer for handle construction */ 165 } GG; 166 167 168 typedef 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