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
00034
00035
00036 #define DGL_GS_FLAT 0x1
00037
00038
00039
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
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
00059
00060 #define DGL_NS_HEAD 0x1
00061 #define DGL_NS_TAIL 0x2
00062 #define DGL_NS_ALONE 0x4
00063
00064
00065
00066
00067
00068 #define DGL_ES_DIRECTED 0x1
00069
00070
00071
00072
00073
00074 #define DGL_ENDIAN_BIG 1
00075 #define DGL_ENDIAN_LITTLE 2
00076
00077
00078
00079
00080
00081
00082 #define DGL_STRONGCONNECT 0x1
00083 #define DGL_ALONE 0x2
00084 #define DGL_MERGE_EDGE 0x4
00085
00086
00087
00088
00089
00090
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
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
00131
00132 typedef struct
00133 {
00134 void *pvAVL;
00135 } dglNodePrioritizer_s;
00136
00137
00138
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
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 *,
00199 dglSPClipOutput_s *, void *);
00200
00201
00202
00203
00204 typedef int (*dglSpanClip_fn) (dglGraph_s *, dglGraph_s *,
00205 dglSpanClipInput_s *, dglSpanClipOutput_s *,
00206 void *);
00207
00208
00209
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
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
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
00247
00248 typedef struct
00249 {
00250 dglGraph_s *pGraph;
00251 void *pvAVLT;
00252 dglInt32_t *pnNode;
00253 } dglNodeTraverser_s;
00254
00255
00256
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
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
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
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
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
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
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];
00382 } dglIOContext_s;
00383
00384 int dglIOContextInitialize(dglGraph_s *, dglIOContext_s *);
00385 void dglIOContextRelease(dglIOContext_s *);
00386
00387
00388
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
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
00447
00448 int dglErrno(dglGraph_s * pgraph);
00449 char *dglStrerror(dglGraph_s * pgraph);
00450
00451
00452
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
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
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
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