1 /* 2 * Copyright (C) 2002 Roberto Micarelli 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 19 /* 20 * best view tabstop=4 21 */ 22 23 #ifndef _DGL_dglGraph_s_H_ 24 #define _DGL_dglGraph_s_H_ 25 26 #ifdef DGL_STATS 27 #include <time.h> 28 #endif 29 30 #include "heap.h" 31 #include "tree.h" 32 33 /* 34 * Graph State bitmask - returned by dglGet_State() function 35 */ 36 #define DGL_GS_FLAT 0x1 /* otherwise is TREE */ 37 38 /* 39 * Graph Family 40 */ 41 #define DGL_GF_COMPLETE 0x1 42 #define DGL_GF_BIPARTITE 0x2 43 #define DGL_GF_REGULAR 0x4 44 #define DGL_GF_BOUQUET 0x8 45 #define DGL_GF_DIPOLE 0x10 46 #define DGL_GF_PATH 0x20 47 #define DGL_GF_CYCLE 0x40 48 49 /* 50 * Graph Options 51 */ 52 #define DGL_GO_EdgePrioritize_COST 0x10 53 #define DGL_GO_EdgePrioritize_ATTR 0x20 54 #define DGL_GO_NodePrioritize_ATTR 0x40 55 56 57 /* 58 * Node Status bitmask - returned by dglNodeGet_Status() 59 */ 60 #define DGL_NS_HEAD 0x1 /* node exists as at least one edge's head (static) */ 61 #define DGL_NS_TAIL 0x2 /* node exists as at least one edge's tail (static) */ 62 #define DGL_NS_ALONE 0x4 /* node is a component */ 63 64 65 /* 66 * Edge Status bitmask - returned by dglEdgeGet_Status() 67 */ 68 #define DGL_ES_DIRECTED 0x1 /* force edge to be directed */ 69 70 71 /* 72 * Endianess Values - returned by dglGet_Endianess() function 73 */ 74 #define DGL_ENDIAN_BIG 1 75 #define DGL_ENDIAN_LITTLE 2 76 77 78 /* 79 * miscellaneous 80 */ 81 /* add-edge/add-node flags */ 82 #define DGL_STRONGCONNECT 0x1 83 #define DGL_ALONE 0x2 84 #define DGL_MERGE_EDGE 0x4 85 /* */ 86 87 88 89 /* 90 * Shortest Path clip definitions 91 */ 92 typedef struct _dglSPClipInput 93 { 94 dglInt32_t *pnPrevEdge; 95 dglInt32_t *pnNodeFrom; 96 dglInt32_t *pnEdge; 97 dglInt32_t *pnNodeTo; 98 dglInt32_t nFromDistance; 99 100 } dglSPClipInput_s; 101 102 typedef struct _dglSPClipOutput 103 { 104 dglInt32_t nEdgeCost; 105 106 } dglSPClipOutput_s; 107 108 109 /* 110 * Spanning clip definitions 111 */ 112 typedef struct _dglSpanClipInput 113 { 114 dglInt32_t *pnNodeFrom; 115 dglInt32_t *pnEdge; 116 dglInt32_t *pnNodeTo; 117 118 } dglSpanClipInput_s; 119 120 typedef struct _dglSpanClipOutput 121 { 122 dglInt32_t *pnReserved; 123 124 } dglSpanClipOutput_s; 125 126 127 struct dglGraph; 128 129 /* 130 * Node Prioritizer 131 */ 132 typedef struct 133 { 134 void *pvAVL; 135 } dglNodePrioritizer_s; 136 137 /* 138 * Edge Prioritizer 139 */ 140 typedef struct 141 { 142 int cEdge; 143 int iEdge; 144 dglTreeEdgePri32_s *pEdgePri32Item; 145 void *pvAVL; 146 } dglEdgePrioritizer_s; 147 148 149 /* 150 * The graph context 151 */ 152 typedef struct _dglGraph 153 { 154 int iErrno; 155 156 dglByte_t Version; 157 dglByte_t Endian; 158 dglInt32_t NodeAttrSize; 159 dglInt32_t EdgeAttrSize; 160 dglInt32_t aOpaqueSet[16]; 161 162 dglInt32_t cNode; 163 dglInt32_t cHead; 164 dglInt32_t cTail; 165 dglInt32_t cAlone; 166 dglInt32_t cEdge; 167 dglInt64_t nnCost; 168 169 dglInt32_t Flags; 170 dglInt32_t nFamily; 171 dglInt32_t nOptions; 172 173 void *pNodeTree; 174 void *pEdgeTree; 175 dglByte_t *pNodeBuffer; 176 dglInt32_t iNodeBuffer; 177 dglByte_t *pEdgeBuffer; 178 dglInt32_t iEdgeBuffer; 179 180 181 dglEdgePrioritizer_s edgePrioritizer; 182 dglNodePrioritizer_s nodePrioritizer; 183 184 185 /* so far statistics are only computed by dglAddEdge() */ 186 #ifdef DGL_STATS 187 clock_t clkAddEdge; /* cycles spent during the last addedge execution */ 188 int cAddEdge; /* # of calls to dglAddEdge() */ 189 clock_t clkNodeTree; /* cycles spent in accessing the node binary tree */ 190 int cNodeTree; /* # of probes in the node tree */ 191 #endif 192 } 193 dglGraph_s; 194 195 /* 196 * Shortest Path clip function type 197 */ 198 typedef int (*dglSPClip_fn) (dglGraph_s *, dglSPClipInput_s *, 199 dglSPClipOutput_s *, void *); 200 201 /* 202 * Spanning clip function type 203 */ 204 typedef int (*dglSpanClip_fn) (dglGraph_s *, dglGraph_s *, 205 dglSpanClipInput_s *, dglSpanClipOutput_s *, 206 void *); 207 208 /* 209 * An ARC defined as : from-node, to-node, edge pointer, to-node-distance (from the path starting node) 210 */ 211 typedef struct _dglSPArc 212 { 213 dglInt32_t nFrom; 214 dglInt32_t nTo; 215 dglInt32_t *pnEdge; 216 dglInt32_t nDistance; 217 } 218 dglSPArc_s; 219 220 /* 221 * Shortest Path Report 222 */ 223 typedef struct _dglSPReport 224 { 225 dglInt32_t nStartNode; 226 dglInt32_t nDestinationNode; 227 dglInt32_t nDistance; 228 dglInt32_t cArc; 229 dglSPArc_s *pArc; 230 } 231 dglSPReport_s; 232 233 /* 234 * Shortest Path Cache 235 */ 236 typedef struct 237 { 238 dglInt32_t nStartNode; 239 dglHeap_s NodeHeap; 240 void *pvVisited; 241 void *pvPredist; 242 } 243 dglSPCache_s; 244 245 /* 246 * Node Traverser 247 */ 248 typedef struct 249 { 250 dglGraph_s *pGraph; 251 void *pvAVLT; 252 dglInt32_t *pnNode; 253 } dglNodeTraverser_s; 254 255 /* 256 * Edgeset Traverser 257 */ 258 typedef struct 259 { 260 dglGraph_s *pGraph; 261 dglInt32_t *pnEdgeset; 262 void *pvCurrentItem; 263 int cEdge, iEdge; 264 } dglEdgesetTraverser_s; 265 266 /* 267 * Edge Traverser 268 */ 269 typedef struct 270 { 271 dglGraph_s *pGraph; 272 void *pvAVLT; 273 dglInt32_t *pnEdge; 274 dglEdgePrioritizer_s *pEdgePrioritizer; 275 } dglEdgeTraverser_s; 276 277 278 /* 279 * Error codes returned by dglError 280 */ 281 #define DGL_ERR_BadVersion 1 282 #define DGL_ERR_BadNodeType 2 283 #define DGL_ERR_MemoryExhausted 3 284 #define DGL_ERR_HeapError 4 285 #define DGL_ERR_UndefinedMethod 5 286 #define DGL_ERR_Write 6 287 #define DGL_ERR_Read 7 288 #define DGL_ERR_NotSupported 8 289 #define DGL_ERR_UnknownByteOrder 9 290 #define DGL_ERR_HeadNodeNotFound 10 291 #define DGL_ERR_TailNodeNotFound 11 292 #define DGL_ERR_BadEdge 12 293 #define DGL_ERR_BadOnFlatGraph 13 294 #define DGL_ERR_BadOnTreeGraph 14 295 #define DGL_ERR_NodeNotFound 15 296 #define DGL_ERR_TreeSearchError 16 297 #define DGL_ERR_UnexpectedNullPointer 17 298 #define DGL_ERR_VersionNotSupported 18 299 #define DGL_ERR_EdgeNotFound 19 300 #define DGL_ERR_NodeAlreadyExist 20 301 #define DGL_ERR_NodeIsAComponent 21 302 #define DGL_ERR_EdgeAlreadyExist 22 303 #define DGL_ERR_BadArgument 23 304 305 306 307 /* 308 * graph context management 309 */ 310 int dglInitialize(dglGraph_s * pGraph, dglByte_t Version, 311 dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, 312 dglInt32_t * pOpaqueSet); 313 int dglRelease(dglGraph_s * pGraph); 314 int dglUnflatten(dglGraph_s * pGraph); 315 int dglFlatten(dglGraph_s * pGraph); 316 void dglResetStats(dglGraph_s * pgraph); 317 318 /* 319 * node management 320 */ 321 dglInt32_t *dglGetNode(dglGraph_s * pGraph, dglInt32_t nNodeId); 322 int dglAddNode(dglGraph_s * pGraph, 323 dglInt32_t nNodeId, void *pvNodeAttr, dglInt32_t nFlags); 324 int dglDelNode(dglGraph_s * pGraph, dglInt32_t nNodeId); 325 dglInt32_t dglNodeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnNode); 326 dglInt32_t *dglNodeGet_OutEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode); 327 dglInt32_t *dglNodeGet_InEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode); 328 dglInt32_t dglNodeGet_Status(dglGraph_s * pGraph, dglInt32_t * pnNode); 329 dglInt32_t *dglNodeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode); 330 void dglNodeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode, 331 dglInt32_t * pnAttr); 332 int dglNodeGet_InDegree(dglGraph_s * pGraph, dglInt32_t * pnNode); 333 int dglNodeGet_OutDegree(dglGraph_s * pGraph, dglInt32_t * pnNode); 334 int dglNodeGet_Valence(dglGraph_s * pGraph, dglInt32_t * pnNode); 335 336 /* 337 * edge management 338 */ 339 dglInt32_t dglEdgesetGet_EdgeCount(dglGraph_s * pGraph, 340 dglInt32_t * pnOutEdgeset); 341 342 dglInt32_t dglEdgeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnEdge); 343 dglInt32_t dglEdgeGet_Cost(dglGraph_s * pGraph, dglInt32_t * pnEdge); 344 dglInt32_t *dglEdgeGet_Head(dglGraph_s * pGraph, dglInt32_t * pnEdge); 345 dglInt32_t *dglEdgeGet_Tail(dglGraph_s * pGraph, dglInt32_t * pnEdge); 346 dglInt32_t *dglEdgeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnEdge); 347 int dglEdgeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnAttr, 348 dglInt32_t * pnEdge); 349 350 dglInt32_t *dglGetEdge(dglGraph_s * pGraph, dglInt32_t nEdgeId); 351 352 int dglDelEdge(dglGraph_s * pGraph, dglInt32_t nEdgeId); 353 354 int dglAddEdge(dglGraph_s * pGraph, 355 dglInt32_t nHead, 356 dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge); 357 358 int dglAddEdgeX(dglGraph_s * pGraph, 359 dglInt32_t nHead, 360 dglInt32_t nTail, 361 dglInt32_t nCost, 362 dglInt32_t nEdge, 363 void *pvFnodeAttr, 364 void *pvTnodeAttr, void *pvEdgeAttr, dglInt32_t nFlags); 365 366 367 /* 368 * graph I/O 369 */ 370 int dglWrite(dglGraph_s * pGraph, int fd); 371 int dglRead(dglGraph_s * pGraph, int fd); 372 373 typedef struct 374 { 375 dglGraph_s *pG; 376 int nState; 377 int fSwap; 378 int cb; 379 int ib; 380 unsigned char *pb; 381 unsigned char ab[118]; /* 118 = graph header size */ 382 } dglIOContext_s; 383 384 int dglIOContextInitialize(dglGraph_s *, dglIOContext_s *); 385 void dglIOContextRelease(dglIOContext_s *); 386 387 /* 388 * Chunked Write callback function type 389 */ 390 typedef int (*dglWriteChunk_fn) (dglGraph_s *, unsigned char *pbChunk, 391 int cbChunk, void *pvArg); 392 393 int dglWriteChunk(dglIOContext_s *, dglWriteChunk_fn, void *pvArg); 394 int dglReadChunk(dglIOContext_s *, dglByte_t * pbChunk, int cbChunk); 395 396 397 398 /* 399 * Algorithms 400 */ 401 int dglShortestPath(dglGraph_s * pGraph, 402 dglSPReport_s ** ppReport, 403 dglInt32_t nStartNode, 404 dglInt32_t nDestinationNode, 405 dglSPClip_fn fnClip, 406 void *pvClipArg, dglSPCache_s * pCache); 407 int dglShortestPathGraph(dglGraph_s * pGraph, 408 dglGraph_s * pGraphOut, 409 dglInt32_t nStartNode, 410 dglInt32_t nDestinationNode, 411 dglSPClip_fn fnClip, 412 void *pvClipArg, dglSPCache_s * pCache); 413 int dglShortestDistance(dglGraph_s * pGraph, 414 dglInt32_t * pnDistance, 415 dglInt32_t nStartNode, 416 dglInt32_t nDestinationNode, 417 dglSPClip_fn fnClip, 418 void *pvClipArg, dglSPCache_s * pCache); 419 int dglShortestDistanceGraph(dglGraph_s * pGraph, 420 dglGraph_s * pGraphOut, 421 dglInt32_t nStartNode, 422 dglInt32_t nDestinationNode, 423 dglSPClip_fn fnClip, 424 void *pvClipArg, dglSPCache_s * pCache); 425 426 int dglInitializeSPCache(dglGraph_s * pgraph, dglSPCache_s * pCache); 427 void dglReleaseSPCache(dglGraph_s * pgraph, dglSPCache_s * pCache); 428 void dglFreeSPReport(dglGraph_s * pGraph, dglSPReport_s * pSPReport); 429 430 int dglDepthSpanning(dglGraph_s * pgraphInput, 431 dglGraph_s * pgraphOutput, 432 dglInt32_t nVertexNode, 433 dglSpanClip_fn fnClip, void *pvClipArg); 434 435 int dglDepthComponents(dglGraph_s * pgraphInput, 436 dglGraph_s * pgraphComponents, 437 int cgraphComponents, 438 dglSpanClip_fn fnClip, void *pvClipArg); 439 440 int dglMinimumSpanning(dglGraph_s * pgraphInput, 441 dglGraph_s * pgraphOutput, 442 dglInt32_t nVertexNode, 443 dglSpanClip_fn fnClip, void *pvClipArg); 444 445 /* 446 * error management 447 */ 448 int dglErrno(dglGraph_s * pgraph); 449 char *dglStrerror(dglGraph_s * pgraph); 450 451 /* 452 * graph property hiders 453 */ 454 int dglGet_Version(dglGraph_s * pGraph); 455 void dglSet_Version(dglGraph_s * pGraph, int Version); 456 int dglGet_Endianess(dglGraph_s * pGraph); 457 int dglGet_NodeAttrSize(dglGraph_s * pGraph); 458 int dglGet_EdgeAttrSize(dglGraph_s * pGraph); 459 int dglGet_NodeCount(dglGraph_s * pGraph); 460 int dglGet_HeadNodeCount(dglGraph_s * pGraph); 461 int dglGet_TailNodeCount(dglGraph_s * pGraph); 462 int dglGet_AloneNodeCount(dglGraph_s * pGraph); 463 int dglGet_EdgeCount(dglGraph_s * pGraph); 464 int dglGet_State(dglGraph_s * pGraph); 465 dglInt32_t *dglGet_Opaque(dglGraph_s * pGraph); 466 void dglSet_Opaque(dglGraph_s * pGraph, dglInt32_t * pOpaque); 467 int dglGet_NodeSize(dglGraph_s * pGraph); 468 int dglGet_EdgeSize(dglGraph_s * pGraph); 469 dglInt64_t dglGet_Cost(dglGraph_s * pGraph); 470 void dglSet_Cost(dglGraph_s * pGraph, dglInt64_t nnCost); 471 dglInt32_t dglGet_Family(dglGraph_s * pGraph); 472 void dglSet_Family(dglGraph_s * pGraph, dglInt32_t nFamily); 473 dglInt32_t dglGet_Options(dglGraph_s * pGraph); 474 void dglSet_Options(dglGraph_s * pGraph, dglInt32_t nOptions); 475 dglEdgePrioritizer_s *dglGet_EdgePrioritizer(dglGraph_s * pGraph); 476 dglNodePrioritizer_s *dglGet_NodePrioritizer(dglGraph_s * pGraph); 477 478 479 /* 480 * node traverser 481 */ 482 int dglNode_T_Initialize(dglNodeTraverser_s * pTraverser, 483 dglGraph_s * pGraph); 484 void dglNode_T_Release(dglNodeTraverser_s * pTraverser); 485 dglInt32_t *dglNode_T_First(dglNodeTraverser_s * pTraverser); 486 dglInt32_t *dglNode_T_Last(dglNodeTraverser_s * pTraverser); 487 dglInt32_t *dglNode_T_Next(dglNodeTraverser_s * pTraverser); 488 dglInt32_t *dglNode_T_Prev(dglNodeTraverser_s * pTraverser); 489 dglInt32_t *dglNode_T_Find(dglNodeTraverser_s * pTraverser, 490 dglInt32_t nNodeId); 491 492 493 /* 494 * edgeset traverser 495 */ 496 int dglEdgeset_T_Initialize(dglEdgesetTraverser_s * pTraverser, 497 dglGraph_s * pGraph, dglInt32_t * pnEdgeset); 498 void dglEdgeset_T_Release(dglEdgesetTraverser_s * pTraverser); 499 dglInt32_t *dglEdgeset_T_First(dglEdgesetTraverser_s * pTraverser); 500 dglInt32_t *dglEdgeset_T_Next(dglEdgesetTraverser_s * pTraverser); 501 502 503 /* 504 * edge traverser 505 */ 506 int dglEdge_T_Initialize(dglEdgeTraverser_s * pTraverser, 507 dglGraph_s * pGraph, 508 dglEdgePrioritizer_s * pEdgePrioritizer); 509 void dglEdge_T_Release(dglEdgeTraverser_s * pTraverser); 510 dglInt32_t *dglEdge_T_First(dglEdgeTraverser_s * pTraverser); 511 dglInt32_t *dglEdge_T_Next(dglEdgeTraverser_s * pTraverser); 512 513 #endif 514