00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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 __BEGIN_DECLS
00034
00035
00036
00037
00038 #define DGL_GS_FLAT 0x1
00039
00040
00041
00042
00043 #define DGL_GF_COMPLETE 0x1
00044 #define DGL_GF_BIPARTITE 0x2
00045 #define DGL_GF_REGULAR 0x4
00046 #define DGL_GF_BOUQUET 0x8
00047 #define DGL_GF_DIPOLE 0x10
00048 #define DGL_GF_PATH 0x20
00049 #define DGL_GF_CYCLE 0x40
00050
00051
00052
00053
00054 #define DGL_GO_EdgePrioritize_COST 0x10
00055 #define DGL_GO_EdgePrioritize_ATTR 0x20
00056 #define DGL_GO_NodePrioritize_ATTR 0x40
00057
00058
00059
00060
00061
00062 #define DGL_NS_HEAD 0x1
00063 #define DGL_NS_TAIL 0x2
00064 #define DGL_NS_ALONE 0x4
00065
00066
00067
00068
00069
00070 #define DGL_ES_DIRECTED 0x1
00071
00072
00073
00074
00075
00076 #define DGL_ENDIAN_BIG 1
00077 #define DGL_ENDIAN_LITTLE 2
00078
00079
00080
00081
00082
00083
00084 #define DGL_STRONGCONNECT 0x1
00085 #define DGL_ALONE 0x2
00086 #define DGL_MERGE_EDGE 0x4
00087
00088
00089
00090
00091
00092
00093
00094 typedef struct _dglSPClipInput
00095 {
00096 dglInt32_t * pnPrevEdge;
00097 dglInt32_t * pnNodeFrom;
00098 dglInt32_t * pnEdge;
00099 dglInt32_t * pnNodeTo;
00100 dglInt32_t nFromDistance;
00101
00102 } dglSPClipInput_s;
00103
00104 typedef struct _dglSPClipOutput
00105 {
00106 dglInt32_t nEdgeCost;
00107
00108 } dglSPClipOutput_s;
00109
00110
00111
00112
00113
00114 typedef struct _dglSpanClipInput
00115 {
00116 dglInt32_t * pnNodeFrom;
00117 dglInt32_t * pnEdge;
00118 dglInt32_t * pnNodeTo;
00119
00120 } dglSpanClipInput_s;
00121
00122 typedef struct _dglSpanClipOutput
00123 {
00124 dglInt32_t * pnReserved;
00125
00126 } dglSpanClipOutput_s;
00127
00128
00129 struct dglGraph;
00130
00131
00132
00133
00134 typedef struct {
00135 void * pvAVL;
00136 } dglNodePrioritizer_s;
00137
00138
00139
00140
00141 typedef struct {
00142 int cEdge;
00143 int iEdge;
00144 dglTreeEdgePri32_s * pEdgePri32Item;
00145 void * pvAVL;
00146 } dglEdgePrioritizer_s;
00147
00148
00149
00150
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
00186 #ifdef DGL_STATS
00187 clock_t clkAddEdge;
00188 int cAddEdge;
00189 clock_t clkNodeTree;
00190 int cNodeTree;
00191 #endif
00192 }
00193 dglGraph_s;
00194
00195
00196
00197
00198 typedef int (*dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *);
00199
00200
00201
00202
00203 typedef int (*dglSpanClip_fn)(dglGraph_s *, dglGraph_s *, dglSpanClipInput_s *, dglSpanClipOutput_s *, void *);
00204
00205
00206
00207
00208 typedef struct _dglSPArc
00209 {
00210 dglInt32_t nFrom;
00211 dglInt32_t nTo;
00212 dglInt32_t * pnEdge;
00213 dglInt32_t nDistance;
00214 }
00215 dglSPArc_s;
00216
00217
00218
00219
00220 typedef struct _dglSPReport
00221 {
00222 dglInt32_t nStartNode;
00223 dglInt32_t nDestinationNode;
00224 dglInt32_t nDistance;
00225 dglInt32_t cArc;
00226 dglSPArc_s * pArc;
00227 }
00228 dglSPReport_s;
00229
00230
00231
00232
00233 typedef struct {
00234 dglInt32_t nStartNode;
00235 dglHeap_s NodeHeap;
00236 void * pvVisited;
00237 void * pvPredist;
00238 }
00239 dglSPCache_s;
00240
00241
00242
00243
00244 typedef struct {
00245 dglGraph_s * pGraph;
00246 void * pvAVLT;
00247 dglInt32_t * pnNode;
00248 } dglNodeTraverser_s;
00249
00250
00251
00252
00253 typedef struct {
00254 dglGraph_s * pGraph;
00255 dglInt32_t * pnEdgeset;
00256 void * pvCurrentItem;
00257 int cEdge, iEdge;
00258 } dglEdgesetTraverser_s;
00259
00260
00261
00262
00263 typedef struct {
00264 dglGraph_s * pGraph;
00265 void * pvAVLT;
00266 dglInt32_t * pnEdge;
00267 dglEdgePrioritizer_s * pEdgePrioritizer;
00268 } dglEdgeTraverser_s;
00269
00270
00271
00272
00273
00274 #define DGL_ERR_BadVersion 1
00275 #define DGL_ERR_BadNodeType 2
00276 #define DGL_ERR_MemoryExhausted 3
00277 #define DGL_ERR_HeapError 4
00278 #define DGL_ERR_UndefinedMethod 5
00279 #define DGL_ERR_Write 6
00280 #define DGL_ERR_Read 7
00281 #define DGL_ERR_NotSupported 8
00282 #define DGL_ERR_UnknownByteOrder 9
00283 #define DGL_ERR_HeadNodeNotFound 10
00284 #define DGL_ERR_TailNodeNotFound 11
00285 #define DGL_ERR_BadEdge 12
00286 #define DGL_ERR_BadOnFlatGraph 13
00287 #define DGL_ERR_BadOnTreeGraph 14
00288 #define DGL_ERR_NodeNotFound 15
00289 #define DGL_ERR_TreeSearchError 16
00290 #define DGL_ERR_UnexpectedNullPointer 17
00291 #define DGL_ERR_VersionNotSupported 18
00292 #define DGL_ERR_EdgeNotFound 19
00293 #define DGL_ERR_NodeAlreadyExist 20
00294 #define DGL_ERR_NodeIsAComponent 21
00295 #define DGL_ERR_EdgeAlreadyExist 22
00296 #define DGL_ERR_BadArgument 23
00297
00298
00299
00300
00301
00302
00303 int dglInitialize(dglGraph_s * pGraph, dglByte_t Version, dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, dglInt32_t * pOpaqueSet);
00304 int dglRelease( dglGraph_s * pGraph );
00305 int dglUnflatten( dglGraph_s * pGraph );
00306 int dglFlatten( dglGraph_s * pGraph );
00307 void dglResetStats( dglGraph_s * pgraph );
00308
00309
00310
00311
00312 dglInt32_t * dglGetNode(dglGraph_s * pGraph , dglInt32_t nNodeId);
00313 int dglAddNode(
00314 dglGraph_s * pGraph ,
00315 dglInt32_t nNodeId ,
00316 void * pvNodeAttr ,
00317 dglInt32_t nFlags
00318 );
00319 int dglDelNode(
00320 dglGraph_s * pGraph ,
00321 dglInt32_t nNodeId
00322 );
00323 dglInt32_t dglNodeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnNode);
00324 dglInt32_t * dglNodeGet_OutEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode);
00325 dglInt32_t * dglNodeGet_InEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode);
00326 dglInt32_t dglNodeGet_Status(dglGraph_s * pGraph, dglInt32_t * pnNode);
00327 dglInt32_t * dglNodeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode);
00328 void dglNodeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode, dglInt32_t * pnAttr);
00329 int dglNodeGet_InDegree(dglGraph_s * pGraph, dglInt32_t * pnNode);
00330 int dglNodeGet_OutDegree(dglGraph_s * pGraph, dglInt32_t * pnNode);
00331 int dglNodeGet_Valence(dglGraph_s * pGraph, dglInt32_t * pnNode);
00332
00333
00334
00335
00336 dglInt32_t dglEdgesetGet_EdgeCount(dglGraph_s * pGraph, dglInt32_t * pnOutEdgeset);
00337
00338 dglInt32_t dglEdgeGet_Id(dglGraph_s * pGraph , dglInt32_t * pnEdge );
00339 dglInt32_t dglEdgeGet_Cost(dglGraph_s * pGraph , dglInt32_t * pnEdge );
00340 dglInt32_t * dglEdgeGet_Head(dglGraph_s * pGraph , dglInt32_t * pnEdge );
00341 dglInt32_t * dglEdgeGet_Tail(dglGraph_s * pGraph , dglInt32_t * pnEdge );
00342 dglInt32_t * dglEdgeGet_Attr(dglGraph_s * pGraph , dglInt32_t * pnEdge );
00343 int dglEdgeSet_Attr(dglGraph_s * pGraph , dglInt32_t * pnAttr , dglInt32_t * pnEdge );
00344
00345 dglInt32_t * dglGetEdge(
00346 dglGraph_s * pGraph ,
00347 dglInt32_t nEdgeId
00348 );
00349
00350 int dglDelEdge(
00351 dglGraph_s * pGraph ,
00352 dglInt32_t nEdgeId
00353 );
00354
00355 int dglAddEdge(
00356 dglGraph_s * pGraph ,
00357 dglInt32_t nHead ,
00358 dglInt32_t nTail ,
00359 dglInt32_t nCost ,
00360 dglInt32_t nEdge
00361 );
00362
00363 int dglAddEdgeX(
00364 dglGraph_s * pGraph ,
00365 dglInt32_t nHead ,
00366 dglInt32_t nTail ,
00367 dglInt32_t nCost ,
00368 dglInt32_t nEdge ,
00369 void * pvFnodeAttr ,
00370 void * pvTnodeAttr ,
00371 void * pvEdgeAttr ,
00372 dglInt32_t nFlags
00373 );
00374
00375
00376
00377
00378
00379 int dglWrite( dglGraph_s * pGraph, int fd );
00380 int dglRead( dglGraph_s * pGraph, int fd );
00381
00382 typedef struct {
00383 dglGraph_s * pG;
00384 int nState;
00385 int fSwap;
00386 int cb;
00387 int ib;
00388 unsigned char * pb;
00389 unsigned char ab[118];
00390 } dglIOContext_s;
00391
00392 int dglIOContextInitialize(dglGraph_s *, dglIOContext_s *);
00393 void dglIOContextRelease(dglIOContext_s *);
00394
00395
00396
00397
00398 typedef int (*dglWriteChunk_fn)( dglGraph_s *, unsigned char * pbChunk, int cbChunk, void * pvArg );
00399
00400 int dglWriteChunk(dglIOContext_s *, dglWriteChunk_fn, void * pvArg);
00401 int dglReadChunk(dglIOContext_s *, dglByte_t * pbChunk, int cbChunk);
00402
00403
00404
00405
00406
00407
00408 int dglShortestPath(
00409 dglGraph_s * pGraph,
00410 dglSPReport_s ** ppReport,
00411 dglInt32_t nStartNode,
00412 dglInt32_t nDestinationNode,
00413 dglSPClip_fn fnClip,
00414 void * pvClipArg,
00415 dglSPCache_s * pCache
00416 );
00417 int dglShortestPathGraph(
00418 dglGraph_s * pGraph,
00419 dglGraph_s * pGraphOut,
00420 dglInt32_t nStartNode,
00421 dglInt32_t nDestinationNode,
00422 dglSPClip_fn fnClip,
00423 void * pvClipArg,
00424 dglSPCache_s * pCache
00425 );
00426 int dglShortestDistance(
00427 dglGraph_s * pGraph,
00428 dglInt32_t * pnDistance,
00429 dglInt32_t nStartNode,
00430 dglInt32_t nDestinationNode,
00431 dglSPClip_fn fnClip,
00432 void * pvClipArg,
00433 dglSPCache_s * pCache
00434 );
00435 int dglShortestDistanceGraph(
00436 dglGraph_s * pGraph,
00437 dglGraph_s * pGraphOut,
00438 dglInt32_t nStartNode,
00439 dglInt32_t nDestinationNode,
00440 dglSPClip_fn fnClip,
00441 void * pvClipArg,
00442 dglSPCache_s * pCache
00443 );
00444
00445 int dglInitializeSPCache( dglGraph_s * pgraph, dglSPCache_s * pCache );
00446 void dglReleaseSPCache ( dglGraph_s * pgraph, dglSPCache_s * pCache );
00447 void dglFreeSPReport ( dglGraph_s * pGraph , dglSPReport_s * pSPReport );
00448
00449 int dglDepthSpanning(
00450 dglGraph_s * pgraphInput,
00451 dglGraph_s * pgraphOutput,
00452 dglInt32_t nVertexNode,
00453 dglSpanClip_fn fnClip,
00454 void * pvClipArg
00455 );
00456
00457 int dglDepthComponents(
00458 dglGraph_s * pgraphInput,
00459 dglGraph_s * pgraphComponents,
00460 int cgraphComponents,
00461 dglSpanClip_fn fnClip,
00462 void * pvClipArg
00463 );
00464
00465 int dglMinimumSpanning(
00466 dglGraph_s * pgraphInput,
00467 dglGraph_s * pgraphOutput,
00468 dglInt32_t nVertexNode,
00469 dglSpanClip_fn fnClip,
00470 void * pvClipArg
00471 );
00472
00473
00474
00475
00476 int dglErrno( dglGraph_s * pgraph );
00477 char * dglStrerror( dglGraph_s * pgraph );
00478
00479
00480
00481
00482 int dglGet_Version (dglGraph_s * pGraph);
00483 void dglSet_Version (dglGraph_s * pGraph, int Version);
00484 int dglGet_Endianess (dglGraph_s * pGraph);
00485 int dglGet_NodeAttrSize (dglGraph_s * pGraph);
00486 int dglGet_EdgeAttrSize (dglGraph_s * pGraph);
00487 int dglGet_NodeCount (dglGraph_s * pGraph);
00488 int dglGet_HeadNodeCount(dglGraph_s * pGraph);
00489 int dglGet_TailNodeCount(dglGraph_s * pGraph);
00490 int dglGet_AloneNodeCount(dglGraph_s * pGraph);
00491 int dglGet_EdgeCount (dglGraph_s * pGraph);
00492 int dglGet_State (dglGraph_s * pGraph);
00493 dglInt32_t * dglGet_Opaque (dglGraph_s * pGraph);
00494 void dglSet_Opaque (dglGraph_s * pGraph, dglInt32_t * pOpaque);
00495 int dglGet_NodeSize (dglGraph_s * pGraph);
00496 int dglGet_EdgeSize (dglGraph_s * pGraph);
00497 dglInt64_t dglGet_Cost (dglGraph_s * pGraph);
00498 void dglSet_Cost (dglGraph_s * pGraph, dglInt64_t nnCost);
00499 dglInt32_t dglGet_Family (dglGraph_s * pGraph);
00500 void dglSet_Family (dglGraph_s * pGraph, dglInt32_t nFamily);
00501 dglInt32_t dglGet_Options (dglGraph_s * pGraph);
00502 void dglSet_Options (dglGraph_s * pGraph, dglInt32_t nOptions);
00503 dglEdgePrioritizer_s * dglGet_EdgePrioritizer(dglGraph_s * pGraph);
00504 dglNodePrioritizer_s * dglGet_NodePrioritizer(dglGraph_s * pGraph);
00505
00506
00507
00508
00509
00510 int dglNode_T_Initialize( dglNodeTraverser_s * pTraverser , dglGraph_s * pGraph );
00511 void dglNode_T_Release ( dglNodeTraverser_s * pTraverser );
00512 dglInt32_t *dglNode_T_First ( dglNodeTraverser_s * pTraverser );
00513 dglInt32_t *dglNode_T_Last ( dglNodeTraverser_s * pTraverser );
00514 dglInt32_t *dglNode_T_Next ( dglNodeTraverser_s * pTraverser );
00515 dglInt32_t *dglNode_T_Prev ( dglNodeTraverser_s * pTraverser );
00516 dglInt32_t *dglNode_T_Find ( dglNodeTraverser_s * pTraverser , dglInt32_t nNodeId );
00517
00518
00519
00520
00521
00522 int dglEdgeset_T_Initialize (
00523 dglEdgesetTraverser_s * pTraverser ,
00524 dglGraph_s * pGraph ,
00525 dglInt32_t * pnEdgeset
00526 );
00527 void dglEdgeset_T_Release ( dglEdgesetTraverser_s * pTraverser );
00528 dglInt32_t *dglEdgeset_T_First ( dglEdgesetTraverser_s * pTraverser );
00529 dglInt32_t *dglEdgeset_T_Next ( dglEdgesetTraverser_s * pTraverser );
00530
00531
00532
00533
00534
00535 int dglEdge_T_Initialize (
00536 dglEdgeTraverser_s * pTraverser ,
00537 dglGraph_s * pGraph ,
00538 dglEdgePrioritizer_s * pEdgePrioritizer
00539 );
00540 void dglEdge_T_Release ( dglEdgeTraverser_s * pTraverser );
00541 dglInt32_t *dglEdge_T_First ( dglEdgeTraverser_s * pTraverser );
00542 dglInt32_t *dglEdge_T_Next ( dglEdgeTraverser_s * pTraverser );
00543
00544 __END_DECLS
00545 #endif