GRASS Programmer's Manual 6.4.1(2011)
|
00001 /* 00002 * Copyright (C) 2002 Roberto Micarelli 00003 * 00004 * This program is free software; you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation; either version 2 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program; if not, write to the Free Software 00016 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00017 */ 00018 00019 /* 00020 * best view tabstop=4 00021 */ 00022 00023 #ifndef _DGL_GRAPH_H_ 00024 #define _DGL_GRAPH_H_ 00025 00026 #ifdef DGL_STATS 00027 #include <time.h> 00028 #endif 00029 00030 #include "heap.h" 00031 #include "tree.h" 00032 00033 /* 00034 * Graph State bitmask - returned by dglGet_State() function 00035 */ 00036 #define DGL_GS_FLAT 0x1 /* otherwise is TREE */ 00037 00038 /* 00039 * Graph Family 00040 */ 00041 #define DGL_GF_COMPLETE 0x1 00042 #define DGL_GF_BIPARTITE 0x2 00043 #define DGL_GF_REGULAR 0x4 00044 #define DGL_GF_BOUQUET 0x8 00045 #define DGL_GF_DIPOLE 0x10 00046 #define DGL_GF_PATH 0x20 00047 #define DGL_GF_CYCLE 0x40 00048 00049 /* 00050 * Graph Options 00051 */ 00052 #define DGL_GO_EdgePrioritize_COST 0x10 00053 #define DGL_GO_EdgePrioritize_ATTR 0x20 00054 #define DGL_GO_NodePrioritize_ATTR 0x40 00055 00056 00057 /* 00058 * Node Status bitmask - returned by dglNodeGet_Status() 00059 */ 00060 #define DGL_NS_HEAD 0x1 /* node exists as at least one edge's head (static) */ 00061 #define DGL_NS_TAIL 0x2 /* node exists as at least one edge's tail (static) */ 00062 #define DGL_NS_ALONE 0x4 /* node is a component */ 00063 00064 00065 /* 00066 * Edge Status bitmask - returned by dglEdgeGet_Status() 00067 */ 00068 #define DGL_ES_DIRECTED 0x1 /* force edge to be directed */ 00069 00070 00071 /* 00072 * Endianess Values - returned by dglGet_Endianess() function 00073 */ 00074 #define DGL_ENDIAN_BIG 1 00075 #define DGL_ENDIAN_LITTLE 2 00076 00077 00078 /* 00079 * miscellaneous 00080 */ 00081 /* add-edge/add-node flags */ 00082 #define DGL_STRONGCONNECT 0x1 00083 #define DGL_ALONE 0x2 00084 #define DGL_MERGE_EDGE 0x4 00085 /* */ 00086 00087 00088 00089 /* 00090 * Shortest Path clip definitions 00091 */ 00092 typedef struct _dglSPClipInput 00093 { 00094 dglInt32_t *pnPrevEdge; 00095 dglInt32_t *pnNodeFrom; 00096 dglInt32_t *pnEdge; 00097 dglInt32_t *pnNodeTo; 00098 dglInt32_t nFromDistance; 00099 00100 } dglSPClipInput_s; 00101 00102 typedef struct _dglSPClipOutput 00103 { 00104 dglInt32_t nEdgeCost; 00105 00106 } dglSPClipOutput_s; 00107 00108 00109 /* 00110 * Spanning clip definitions 00111 */ 00112 typedef struct _dglSpanClipInput 00113 { 00114 dglInt32_t *pnNodeFrom; 00115 dglInt32_t *pnEdge; 00116 dglInt32_t *pnNodeTo; 00117 00118 } dglSpanClipInput_s; 00119 00120 typedef struct _dglSpanClipOutput 00121 { 00122 dglInt32_t *pnReserved; 00123 00124 } dglSpanClipOutput_s; 00125 00126 00127 struct dglGraph; 00128 00129 /* 00130 * Node Prioritizer 00131 */ 00132 typedef struct 00133 { 00134 void *pvAVL; 00135 } dglNodePrioritizer_s; 00136 00137 /* 00138 * Edge Prioritizer 00139 */ 00140 typedef struct 00141 { 00142 int cEdge; 00143 int iEdge; 00144 dglTreeEdgePri32_s *pEdgePri32Item; 00145 void *pvAVL; 00146 } dglEdgePrioritizer_s; 00147 00148 00149 /* 00150 * The graph context 00151 */ 00152 typedef struct _dglGraph 00153 { 00154 int iErrno; 00155 00156 dglByte_t Version; 00157 dglByte_t Endian; 00158 dglInt32_t NodeAttrSize; 00159 dglInt32_t EdgeAttrSize; 00160 dglInt32_t aOpaqueSet[16]; 00161 00162 dglInt32_t cNode; 00163 dglInt32_t cHead; 00164 dglInt32_t cTail; 00165 dglInt32_t cAlone; 00166 dglInt32_t cEdge; 00167 dglInt64_t nnCost; 00168 00169 dglInt32_t Flags; 00170 dglInt32_t nFamily; 00171 dglInt32_t nOptions; 00172 00173 void *pNodeTree; 00174 void *pEdgeTree; 00175 dglByte_t *pNodeBuffer; 00176 dglInt32_t iNodeBuffer; 00177 dglByte_t *pEdgeBuffer; 00178 dglInt32_t iEdgeBuffer; 00179 00180 00181 dglEdgePrioritizer_s edgePrioritizer; 00182 dglNodePrioritizer_s nodePrioritizer; 00183 00184 00185 /* so far statistics are only computed by dglAddEdge() */ 00186 #ifdef DGL_STATS 00187 clock_t clkAddEdge; /* cycles spent during the last addedge execution */ 00188 int cAddEdge; /* # of calls to dglAddEdge() */ 00189 clock_t clkNodeTree; /* cycles spent in accessing the node binary tree */ 00190 int cNodeTree; /* # of probes in the node tree */ 00191 #endif 00192 } 00193 dglGraph_s; 00194 00195 /* 00196 * Shortest Path clip function type 00197 */ 00198 typedef int (*dglSPClip_fn) (dglGraph_s *, dglSPClipInput_s *, 00199 dglSPClipOutput_s *, void *); 00200 00201 /* 00202 * Spanning clip function type 00203 */ 00204 typedef int (*dglSpanClip_fn) (dglGraph_s *, dglGraph_s *, 00205 dglSpanClipInput_s *, dglSpanClipOutput_s *, 00206 void *); 00207 00208 /* 00209 * An ARC defined as : from-node, to-node, edge pointer, to-node-distance (from the path starting node) 00210 */ 00211 typedef struct _dglSPArc 00212 { 00213 dglInt32_t nFrom; 00214 dglInt32_t nTo; 00215 dglInt32_t *pnEdge; 00216 dglInt32_t nDistance; 00217 } 00218 dglSPArc_s; 00219 00220 /* 00221 * Shortest Path Report 00222 */ 00223 typedef struct _dglSPReport 00224 { 00225 dglInt32_t nStartNode; 00226 dglInt32_t nDestinationNode; 00227 dglInt32_t nDistance; 00228 dglInt32_t cArc; 00229 dglSPArc_s *pArc; 00230 } 00231 dglSPReport_s; 00232 00233 /* 00234 * Shortest Path Cache 00235 */ 00236 typedef struct 00237 { 00238 dglInt32_t nStartNode; 00239 dglHeap_s NodeHeap; 00240 void *pvVisited; 00241 void *pvPredist; 00242 } 00243 dglSPCache_s; 00244 00245 /* 00246 * Node Traverser 00247 */ 00248 typedef struct 00249 { 00250 dglGraph_s *pGraph; 00251 void *pvAVLT; 00252 dglInt32_t *pnNode; 00253 } dglNodeTraverser_s; 00254 00255 /* 00256 * Edgeset Traverser 00257 */ 00258 typedef struct 00259 { 00260 dglGraph_s *pGraph; 00261 dglInt32_t *pnEdgeset; 00262 void *pvCurrentItem; 00263 int cEdge, iEdge; 00264 } dglEdgesetTraverser_s; 00265 00266 /* 00267 * Edge Traverser 00268 */ 00269 typedef struct 00270 { 00271 dglGraph_s *pGraph; 00272 void *pvAVLT; 00273 dglInt32_t *pnEdge; 00274 dglEdgePrioritizer_s *pEdgePrioritizer; 00275 } dglEdgeTraverser_s; 00276 00277 00278 /* 00279 * Error codes returned by dglError 00280 */ 00281 #define DGL_ERR_BadVersion 1 00282 #define DGL_ERR_BadNodeType 2 00283 #define DGL_ERR_MemoryExhausted 3 00284 #define DGL_ERR_HeapError 4 00285 #define DGL_ERR_UndefinedMethod 5 00286 #define DGL_ERR_Write 6 00287 #define DGL_ERR_Read 7 00288 #define DGL_ERR_NotSupported 8 00289 #define DGL_ERR_UnknownByteOrder 9 00290 #define DGL_ERR_HeadNodeNotFound 10 00291 #define DGL_ERR_TailNodeNotFound 11 00292 #define DGL_ERR_BadEdge 12 00293 #define DGL_ERR_BadOnFlatGraph 13 00294 #define DGL_ERR_BadOnTreeGraph 14 00295 #define DGL_ERR_NodeNotFound 15 00296 #define DGL_ERR_TreeSearchError 16 00297 #define DGL_ERR_UnexpectedNullPointer 17 00298 #define DGL_ERR_VersionNotSupported 18 00299 #define DGL_ERR_EdgeNotFound 19 00300 #define DGL_ERR_NodeAlreadyExist 20 00301 #define DGL_ERR_NodeIsAComponent 21 00302 #define DGL_ERR_EdgeAlreadyExist 22 00303 #define DGL_ERR_BadArgument 23 00304 00305 00306 00307 /* 00308 * graph context management 00309 */ 00310 int dglInitialize(dglGraph_s * pGraph, dglByte_t Version, 00311 dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, 00312 dglInt32_t * pOpaqueSet); 00313 int dglRelease(dglGraph_s * pGraph); 00314 int dglUnflatten(dglGraph_s * pGraph); 00315 int dglFlatten(dglGraph_s * pGraph); 00316 void dglResetStats(dglGraph_s * pgraph); 00317 00318 /* 00319 * node management 00320 */ 00321 dglInt32_t *dglGetNode(dglGraph_s * pGraph, dglInt32_t nNodeId); 00322 int dglAddNode(dglGraph_s * pGraph, 00323 dglInt32_t nNodeId, void *pvNodeAttr, dglInt32_t nFlags); 00324 int dglDelNode(dglGraph_s * pGraph, dglInt32_t nNodeId); 00325 dglInt32_t dglNodeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnNode); 00326 dglInt32_t *dglNodeGet_OutEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode); 00327 dglInt32_t *dglNodeGet_InEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode); 00328 dglInt32_t dglNodeGet_Status(dglGraph_s * pGraph, dglInt32_t * pnNode); 00329 dglInt32_t *dglNodeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode); 00330 void dglNodeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode, 00331 dglInt32_t * pnAttr); 00332 int dglNodeGet_InDegree(dglGraph_s * pGraph, dglInt32_t * pnNode); 00333 int dglNodeGet_OutDegree(dglGraph_s * pGraph, dglInt32_t * pnNode); 00334 int dglNodeGet_Valence(dglGraph_s * pGraph, dglInt32_t * pnNode); 00335 00336 /* 00337 * edge management 00338 */ 00339 dglInt32_t dglEdgesetGet_EdgeCount(dglGraph_s * pGraph, 00340 dglInt32_t * pnOutEdgeset); 00341 00342 dglInt32_t dglEdgeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnEdge); 00343 dglInt32_t dglEdgeGet_Cost(dglGraph_s * pGraph, dglInt32_t * pnEdge); 00344 dglInt32_t *dglEdgeGet_Head(dglGraph_s * pGraph, dglInt32_t * pnEdge); 00345 dglInt32_t *dglEdgeGet_Tail(dglGraph_s * pGraph, dglInt32_t * pnEdge); 00346 dglInt32_t *dglEdgeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnEdge); 00347 int dglEdgeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnAttr, 00348 dglInt32_t * pnEdge); 00349 00350 dglInt32_t *dglGetEdge(dglGraph_s * pGraph, dglInt32_t nEdgeId); 00351 00352 int dglDelEdge(dglGraph_s * pGraph, dglInt32_t nEdgeId); 00353 00354 int dglAddEdge(dglGraph_s * pGraph, 00355 dglInt32_t nHead, 00356 dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge); 00357 00358 int dglAddEdgeX(dglGraph_s * pGraph, 00359 dglInt32_t nHead, 00360 dglInt32_t nTail, 00361 dglInt32_t nCost, 00362 dglInt32_t nEdge, 00363 void *pvFnodeAttr, 00364 void *pvTnodeAttr, void *pvEdgeAttr, dglInt32_t nFlags); 00365 00366 00367 /* 00368 * graph I/O 00369 */ 00370 int dglWrite(dglGraph_s * pGraph, int fd); 00371 int dglRead(dglGraph_s * pGraph, int fd); 00372 00373 typedef struct 00374 { 00375 dglGraph_s *pG; 00376 int nState; 00377 int fSwap; 00378 int cb; 00379 int ib; 00380 unsigned char *pb; 00381 unsigned char ab[118]; /* 118 = graph header size */ 00382 } dglIOContext_s; 00383 00384 int dglIOContextInitialize(dglGraph_s *, dglIOContext_s *); 00385 void dglIOContextRelease(dglIOContext_s *); 00386 00387 /* 00388 * Chunked Write callback function type 00389 */ 00390 typedef int (*dglWriteChunk_fn) (dglGraph_s *, unsigned char *pbChunk, 00391 int cbChunk, void *pvArg); 00392 00393 int dglWriteChunk(dglIOContext_s *, dglWriteChunk_fn, void *pvArg); 00394 int dglReadChunk(dglIOContext_s *, dglByte_t * pbChunk, int cbChunk); 00395 00396 00397 00398 /* 00399 * Algorithms 00400 */ 00401 int dglShortestPath(dglGraph_s * pGraph, 00402 dglSPReport_s ** ppReport, 00403 dglInt32_t nStartNode, 00404 dglInt32_t nDestinationNode, 00405 dglSPClip_fn fnClip, 00406 void *pvClipArg, dglSPCache_s * pCache); 00407 int dglShortestPathGraph(dglGraph_s * pGraph, 00408 dglGraph_s * pGraphOut, 00409 dglInt32_t nStartNode, 00410 dglInt32_t nDestinationNode, 00411 dglSPClip_fn fnClip, 00412 void *pvClipArg, dglSPCache_s * pCache); 00413 int dglShortestDistance(dglGraph_s * pGraph, 00414 dglInt32_t * pnDistance, 00415 dglInt32_t nStartNode, 00416 dglInt32_t nDestinationNode, 00417 dglSPClip_fn fnClip, 00418 void *pvClipArg, dglSPCache_s * pCache); 00419 int dglShortestDistanceGraph(dglGraph_s * pGraph, 00420 dglGraph_s * pGraphOut, 00421 dglInt32_t nStartNode, 00422 dglInt32_t nDestinationNode, 00423 dglSPClip_fn fnClip, 00424 void *pvClipArg, dglSPCache_s * pCache); 00425 00426 int dglInitializeSPCache(dglGraph_s * pgraph, dglSPCache_s * pCache); 00427 void dglReleaseSPCache(dglGraph_s * pgraph, dglSPCache_s * pCache); 00428 void dglFreeSPReport(dglGraph_s * pGraph, dglSPReport_s * pSPReport); 00429 00430 int dglDepthSpanning(dglGraph_s * pgraphInput, 00431 dglGraph_s * pgraphOutput, 00432 dglInt32_t nVertexNode, 00433 dglSpanClip_fn fnClip, void *pvClipArg); 00434 00435 int dglDepthComponents(dglGraph_s * pgraphInput, 00436 dglGraph_s * pgraphComponents, 00437 int cgraphComponents, 00438 dglSpanClip_fn fnClip, void *pvClipArg); 00439 00440 int dglMinimumSpanning(dglGraph_s * pgraphInput, 00441 dglGraph_s * pgraphOutput, 00442 dglInt32_t nVertexNode, 00443 dglSpanClip_fn fnClip, void *pvClipArg); 00444 00445 /* 00446 * error management 00447 */ 00448 int dglErrno(dglGraph_s * pgraph); 00449 char *dglStrerror(dglGraph_s * pgraph); 00450 00451 /* 00452 * graph property hiders 00453 */ 00454 int dglGet_Version(dglGraph_s * pGraph); 00455 void dglSet_Version(dglGraph_s * pGraph, int Version); 00456 int dglGet_Endianess(dglGraph_s * pGraph); 00457 int dglGet_NodeAttrSize(dglGraph_s * pGraph); 00458 int dglGet_EdgeAttrSize(dglGraph_s * pGraph); 00459 int dglGet_NodeCount(dglGraph_s * pGraph); 00460 int dglGet_HeadNodeCount(dglGraph_s * pGraph); 00461 int dglGet_TailNodeCount(dglGraph_s * pGraph); 00462 int dglGet_AloneNodeCount(dglGraph_s * pGraph); 00463 int dglGet_EdgeCount(dglGraph_s * pGraph); 00464 int dglGet_State(dglGraph_s * pGraph); 00465 dglInt32_t *dglGet_Opaque(dglGraph_s * pGraph); 00466 void dglSet_Opaque(dglGraph_s * pGraph, dglInt32_t * pOpaque); 00467 int dglGet_NodeSize(dglGraph_s * pGraph); 00468 int dglGet_EdgeSize(dglGraph_s * pGraph); 00469 dglInt64_t dglGet_Cost(dglGraph_s * pGraph); 00470 void dglSet_Cost(dglGraph_s * pGraph, dglInt64_t nnCost); 00471 dglInt32_t dglGet_Family(dglGraph_s * pGraph); 00472 void dglSet_Family(dglGraph_s * pGraph, dglInt32_t nFamily); 00473 dglInt32_t dglGet_Options(dglGraph_s * pGraph); 00474 void dglSet_Options(dglGraph_s * pGraph, dglInt32_t nOptions); 00475 dglEdgePrioritizer_s *dglGet_EdgePrioritizer(dglGraph_s * pGraph); 00476 dglNodePrioritizer_s *dglGet_NodePrioritizer(dglGraph_s * pGraph); 00477 00478 00479 /* 00480 * node traverser 00481 */ 00482 int dglNode_T_Initialize(dglNodeTraverser_s * pTraverser, 00483 dglGraph_s * pGraph); 00484 void dglNode_T_Release(dglNodeTraverser_s * pTraverser); 00485 dglInt32_t *dglNode_T_First(dglNodeTraverser_s * pTraverser); 00486 dglInt32_t *dglNode_T_Last(dglNodeTraverser_s * pTraverser); 00487 dglInt32_t *dglNode_T_Next(dglNodeTraverser_s * pTraverser); 00488 dglInt32_t *dglNode_T_Prev(dglNodeTraverser_s * pTraverser); 00489 dglInt32_t *dglNode_T_Find(dglNodeTraverser_s * pTraverser, 00490 dglInt32_t nNodeId); 00491 00492 00493 /* 00494 * edgeset traverser 00495 */ 00496 int dglEdgeset_T_Initialize(dglEdgesetTraverser_s * pTraverser, 00497 dglGraph_s * pGraph, dglInt32_t * pnEdgeset); 00498 void dglEdgeset_T_Release(dglEdgesetTraverser_s * pTraverser); 00499 dglInt32_t *dglEdgeset_T_First(dglEdgesetTraverser_s * pTraverser); 00500 dglInt32_t *dglEdgeset_T_Next(dglEdgesetTraverser_s * pTraverser); 00501 00502 00503 /* 00504 * edge traverser 00505 */ 00506 int dglEdge_T_Initialize(dglEdgeTraverser_s * pTraverser, 00507 dglGraph_s * pGraph, 00508 dglEdgePrioritizer_s * pEdgePrioritizer); 00509 void dglEdge_T_Release(dglEdgeTraverser_s * pTraverser); 00510 dglInt32_t *dglEdge_T_First(dglEdgeTraverser_s * pTraverser); 00511 dglInt32_t *dglEdge_T_Next(dglEdgeTraverser_s * pTraverser); 00512 00513 #endif