VIA - Volumetric Image Analysis
|
00001 /* 00002 * $Id: VGraph.h 726 2004-03-08 13:12:45Z lohmann $ 00003 * 00004 * Definitions associated with Graph: their representation in files and 00005 * in memory, and operations that can be performed with them. 00006 */ 00007 00008 #ifndef V_VGraph_h 00009 #define V_VGraph_h 1 00010 00011 /* 00012 * Copyright 1993, 1994 University of British Columbia 00013 * 00014 * Permission to use, copy, modify, distribute, and sell this software and its 00015 * documentation for any purpose is hereby granted without fee, provided that 00016 * the above copyright notice appears in all copies and that both that 00017 * copyright notice and this permission notice appear in supporting 00018 * documentation. UBC makes no representations about the suitability of this 00019 * software for any purpose. It is provided "as is" without express or 00020 * implied warranty. 00021 * 00022 * Author: David Lowe, UBC Laboratory for Computational Intelligence 00023 */ 00024 00025 /* From the Vista library: */ 00026 #include "viaio/Vlib.h" 00027 #include "viaio/file.h" 00028 00029 /* For portability: */ 00030 #include <X11/Xfuncproto.h> 00031 00032 #ifdef __cplusplus 00033 extern "C" { 00034 #endif 00035 00036 00037 /* Structures for representing Graph in memory. 00038 * ------------------------------------------- 00039 * 00040 * A Graph is stored as a table of node records. Nodes are connected by an 00041 * adjancency list. The actual data of a node is stored in an opaque field 00042 * of the node; the size of this field is given in the Graph structure. 00043 * Thus, the representation of the node data is unknown to this structure. 00044 */ 00045 00046 typedef struct V_GraphRec { 00047 int nnodes; /* number of nodes */ 00048 int nfields; /* size of fields in a node�s private area */ 00049 VRepnKind node_repn; /* data representation in a node */ 00050 VAttrList attributes; /* list of other attributes */ 00051 struct VNodestruct **table; /* node table of Graph */ 00052 int size; /* number of places in table */ 00053 int lastUsed; /* last entry used in table */ 00054 int iter; /* iteration counter in sequential access */ 00055 int useWeights; /* TRUE iff weights are used */ 00056 } VGraphRec, *VGraph; 00057 00058 typedef struct VNodebaseStruct { 00059 unsigned int hops: 31; /* numbor of hops in this node */ 00060 unsigned int visited: 1; /* true iff seen before */ 00061 VFloat weight; /* weight of this node */ 00062 struct VAdjstruct *head; 00063 } VNodeBaseRec, *VNodeBase; 00064 00065 typedef struct VNodestruct { 00066 VNodeBaseRec base; 00067 char data[1]; /* private data area of node starts here */ 00068 } VNodeRec, *VNode; 00069 00070 typedef struct VAdjstruct { 00071 unsigned int id; /* node reference */ 00072 VFloat weight; /* weight of this node */ 00073 struct VAdjstruct *next; /* list of adjacent nodes */ 00074 } VAdjRec, *VAdjacency; 00075 00076 /* 00077 * Attributes used to represent Graph 00078 * ---------------------------------- 00079 */ 00080 00081 /* Attribute type names: */ 00082 #define VGraphAttr "Graph" 00083 #define VNGraphNodesAttr "nnodes" 00084 #define VNNodeFieldsAttr "nfields" 00085 #define VNNodeWeightsAttr "useWeights" 00086 00087 00088 /* 00089 * Macros for accessing Graph attributes in memory. 00090 * ----------------------------------------------- 00091 */ 00092 00093 #define VGraphNNodes(graph) (graph->nnodes) 00094 00095 #define VGraphNFields(graph) (graph->nfields) 00096 00097 #define VGraphNSize(graph) (graph->size) 00098 00099 #define VGraphAttrList(graph) (graph->attributes) 00100 00101 #define VGraphGetNode(graph, nid) (graph->table[nid-1]) 00102 00103 #define VGraphNodeIsFree(graph, nid) (graph->table[nid-1] == 0) 00104 00105 #define VNodeRepn(graph) (graph->node_repn) 00106 00107 #define VNodeSize(graph) \ 00108 (sizeof(VNodeBaseRec) + (graph->nfields * VRepnPrecision(graph->node_repn)) / 8) 00109 00110 #define VNodeTestVisit(node) (((VNodeBase)node)->visited == TRUE) 00111 00112 #define VNodeSetVisit(node) (((VNodeBase)node)->visited = TRUE) 00113 00114 #define VNodeClearVisit(node) (((VNodeBase)node)->visited = FALSE) 00115 00116 /* 00117 * Declarations of library routines. 00118 */ 00119 00120 /* From Graph.c: */ 00121 00122 extern VGraph VCreateGraph ( 00123 #if NeedFunctionPrototypes 00124 int /* nnodes */, 00125 int /* nfields */, 00126 VRepnKind /* node_repn */, 00127 int /* save weights */ 00128 #endif 00129 ); 00130 00131 extern VGraph VCopyGraph ( 00132 #if NeedFunctionPrototypes 00133 VGraph /* Graph */ 00134 #endif 00135 ); 00136 00137 extern void VDestroyGraph ( 00138 #if NeedFunctionPrototypes 00139 VGraph /* Graph */ 00140 #endif 00141 ); 00142 00143 extern int VReadGraphs ( 00144 #if NeedFunctionPrototypes 00145 FILE * /* file */, 00146 VAttrList * /* attributes */, 00147 VGraph ** /* graphs */ 00148 #endif 00149 ); 00150 00151 extern VBoolean VWriteGraphs ( 00152 #if NeedFunctionPrototypes 00153 FILE * /* file */, 00154 VAttrList /* attributes */, 00155 int /* ngraphs */, 00156 VGraph * /* graphs */ 00157 #endif 00158 ); 00159 00160 extern int VGraphLookupNode ( 00161 #if NeedFunctionPrototypes 00162 VGraph /* graph */, 00163 VNode /* node */ 00164 #endif 00165 ); 00166 00167 extern int VGraphAddNode ( 00168 #if NeedFunctionPrototypes 00169 VGraph /* graph */, 00170 VNode /* node */ 00171 #endif 00172 ); 00173 00174 extern int VGraphAddNodeAt ( 00175 #if NeedFunctionPrototypes 00176 VGraph /* graph */, 00177 VNode /* node */, 00178 int /* position */ 00179 #endif 00180 ); 00181 00182 extern int VGraphLinkNodes ( 00183 #if NeedFunctionPrototypes 00184 VGraph /* graph */, 00185 int /* a */, 00186 int /* b */ 00187 #endif 00188 ); 00189 00190 extern int VGraphUnlinkNodes ( 00191 #if NeedFunctionPrototypes 00192 VGraph /* graph */, 00193 int /* a */, 00194 int /* b */ 00195 #endif 00196 ); 00197 00198 extern VPointer VGraphFirstNode ( 00199 #if NeedFunctionPrototypes 00200 VGraph /* graph */ 00201 #endif 00202 ); 00203 00204 extern VPointer VGraphNextNode ( 00205 #if NeedFunctionPrototypes 00206 VGraph /* graph */ 00207 #endif 00208 ); 00209 00210 extern void VGraphClearVisit ( 00211 #if NeedFunctionPrototypes 00212 VGraph /* graph */ 00213 #endif 00214 ); 00215 00216 extern int VGraphResizeFields ( 00217 #if NeedFunctionPrototypes 00218 VGraph /* graph */, 00219 int /* nfields */ 00220 #endif 00221 ); 00222 00223 extern int VGraphNCycles ( 00224 #if NeedFunctionPrototypes 00225 VGraph /* graph */ 00226 #endif 00227 ); 00228 00229 extern void VGraphToggleNodesFrom ( 00230 #if NeedFunctionPrototypes 00231 VGraph /* graph */, 00232 int /* i */ 00233 #endif 00234 ); 00235 00236 extern void VDestroyNode ( 00237 #if NeedFunctionPrototypes 00238 VGraph /* graph */, 00239 int /* i */ 00240 #endif 00241 ); 00242 00243 extern void VGraphDestroyNodesFrom ( 00244 #if NeedFunctionPrototypes 00245 VGraph /* graph */, 00246 int /* i */ 00247 #endif 00248 ); 00249 00250 extern void VGraphClearHops ( 00251 #if NeedFunctionPrototypes 00252 VGraph /* graph */ 00253 #endif 00254 ); 00255 00256 #ifdef __cplusplus 00257 } 00258 #endif 00259 00260 #endif /* V_VGraph_h */