VIA - Volumetric Image Analysis
VGraph.h
1 /*
2  * $Id: VGraph.h 726 2004-03-08 13:12:45Z lohmann $
3  *
4  * Definitions associated with Graph: their representation in files and
5  * in memory, and operations that can be performed with them.
6  */
7 
8 #ifndef V_VGraph_h
9 #define V_VGraph_h 1
10 
11 /*
12  * Copyright 1993, 1994 University of British Columbia
13  *
14  * Permission to use, copy, modify, distribute, and sell this software and its
15  * documentation for any purpose is hereby granted without fee, provided that
16  * the above copyright notice appears in all copies and that both that
17  * copyright notice and this permission notice appear in supporting
18  * documentation. UBC makes no representations about the suitability of this
19  * software for any purpose. It is provided "as is" without express or
20  * implied warranty.
21  *
22  * Author: David Lowe, UBC Laboratory for Computational Intelligence
23  */
24 
25 /* From the Vista library: */
26 #include "viaio/Vlib.h"
27 #include "viaio/file.h"
28 
29 /* For portability: */
30 #include <X11/Xfuncproto.h>
31 
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35 
36 
37 /* Structures for representing Graph in memory.
38  * -------------------------------------------
39  *
40  * A Graph is stored as a table of node records. Nodes are connected by an
41  * adjancency list. The actual data of a node is stored in an opaque field
42  * of the node; the size of this field is given in the Graph structure.
43  * Thus, the representation of the node data is unknown to this structure.
44  */
45 
46 typedef struct V_GraphRec {
47  int nnodes; /* number of nodes */
48  int nfields; /* size of fields in a node�s private area */
49  VRepnKind node_repn; /* data representation in a node */
50  VAttrList attributes; /* list of other attributes */
51  struct VNodestruct **table; /* node table of Graph */
52  int size; /* number of places in table */
53  int lastUsed; /* last entry used in table */
54  int iter; /* iteration counter in sequential access */
55  int useWeights; /* TRUE iff weights are used */
56 } VGraphRec, *VGraph;
57 
58 typedef struct VNodebaseStruct {
59  unsigned int hops: 31; /* numbor of hops in this node */
60  unsigned int visited: 1; /* true iff seen before */
61  VFloat weight; /* weight of this node */
62  struct VAdjstruct *head;
63 } VNodeBaseRec, *VNodeBase;
64 
65 typedef struct VNodestruct {
66  VNodeBaseRec base;
67  char data[1]; /* private data area of node starts here */
68 } VNodeRec, *VNode;
69 
70 typedef struct VAdjstruct {
71  unsigned int id; /* node reference */
72  VFloat weight; /* weight of this node */
73  struct VAdjstruct *next; /* list of adjacent nodes */
74 } VAdjRec, *VAdjacency;
75 
76 /*
77  * Attributes used to represent Graph
78  * ----------------------------------
79  */
80 
81 /* Attribute type names: */
82 #define VGraphAttr "Graph"
83 #define VNGraphNodesAttr "nnodes"
84 #define VNNodeFieldsAttr "nfields"
85 #define VNNodeWeightsAttr "useWeights"
86 
87 
88 /*
89  * Macros for accessing Graph attributes in memory.
90  * -----------------------------------------------
91  */
92 
93 #define VGraphNNodes(graph) (graph->nnodes)
94 
95 #define VGraphNFields(graph) (graph->nfields)
96 
97 #define VGraphNSize(graph) (graph->size)
98 
99 #define VGraphAttrList(graph) (graph->attributes)
100 
101 #define VGraphGetNode(graph, nid) (graph->table[nid-1])
102 
103 #define VGraphNodeIsFree(graph, nid) (graph->table[nid-1] == 0)
104 
105 #define VNodeRepn(graph) (graph->node_repn)
106 
107 #define VNodeSize(graph) \
108  (sizeof(VNodeBaseRec) + (graph->nfields * VRepnPrecision(graph->node_repn)) / 8)
109 
110 #define VNodeTestVisit(node) (((VNodeBase)node)->visited == TRUE)
111 
112 #define VNodeSetVisit(node) (((VNodeBase)node)->visited = TRUE)
113 
114 #define VNodeClearVisit(node) (((VNodeBase)node)->visited = FALSE)
115 
116 /*
117  * Declarations of library routines.
118  */
119 
120 /* From Graph.c: */
121 
122 extern VGraph VCreateGraph (
123 #if NeedFunctionPrototypes
124  int /* nnodes */,
125  int /* nfields */,
126  VRepnKind /* node_repn */,
127  int /* save weights */
128 #endif
129 );
130 
131 extern VGraph VCopyGraph (
132 #if NeedFunctionPrototypes
133  VGraph /* Graph */
134 #endif
135 );
136 
137 extern void VDestroyGraph (
138 #if NeedFunctionPrototypes
139  VGraph /* Graph */
140 #endif
141 );
142 
143 extern int VReadGraphs (
144 #if NeedFunctionPrototypes
145  FILE * /* file */,
146  VAttrList * /* attributes */,
147  VGraph ** /* graphs */
148 #endif
149 );
150 
151 extern VBoolean VWriteGraphs (
152 #if NeedFunctionPrototypes
153  FILE * /* file */,
154  VAttrList /* attributes */,
155  int /* ngraphs */,
156  VGraph * /* graphs */
157 #endif
158 );
159 
160 extern int VGraphLookupNode (
161 #if NeedFunctionPrototypes
162  VGraph /* graph */,
163  VNode /* node */
164 #endif
165 );
166 
167 extern int VGraphAddNode (
168 #if NeedFunctionPrototypes
169  VGraph /* graph */,
170  VNode /* node */
171 #endif
172 );
173 
174 extern int VGraphAddNodeAt (
175 #if NeedFunctionPrototypes
176  VGraph /* graph */,
177  VNode /* node */,
178  int /* position */
179 #endif
180 );
181 
182 extern int VGraphLinkNodes (
183 #if NeedFunctionPrototypes
184  VGraph /* graph */,
185  int /* a */,
186  int /* b */
187 #endif
188 );
189 
190 extern int VGraphUnlinkNodes (
191 #if NeedFunctionPrototypes
192  VGraph /* graph */,
193  int /* a */,
194  int /* b */
195 #endif
196 );
197 
198 extern VPointer VGraphFirstNode (
199 #if NeedFunctionPrototypes
200  VGraph /* graph */
201 #endif
202 );
203 
204 extern VPointer VGraphNextNode (
205 #if NeedFunctionPrototypes
206  VGraph /* graph */
207 #endif
208 );
209 
210 extern void VGraphClearVisit (
211 #if NeedFunctionPrototypes
212  VGraph /* graph */
213 #endif
214 );
215 
216 extern int VGraphResizeFields (
217 #if NeedFunctionPrototypes
218  VGraph /* graph */,
219  int /* nfields */
220 #endif
221 );
222 
223 extern int VGraphNCycles (
224 #if NeedFunctionPrototypes
225  VGraph /* graph */
226 #endif
227 );
228 
229 extern void VGraphToggleNodesFrom (
230 #if NeedFunctionPrototypes
231  VGraph /* graph */,
232  int /* i */
233 #endif
234 );
235 
236 extern void VDestroyNode (
237 #if NeedFunctionPrototypes
238  VGraph /* graph */,
239  int /* i */
240 #endif
241 );
242 
243 extern void VGraphDestroyNodesFrom (
244 #if NeedFunctionPrototypes
245  VGraph /* graph */,
246  int /* i */
247 #endif
248 );
249 
250 extern void VGraphClearHops (
251 #if NeedFunctionPrototypes
252  VGraph /* graph */
253 #endif
254 );
255 
256 #ifdef __cplusplus
257 }
258 #endif
259 
260 #endif /* V_VGraph_h */