graph.h

Go to the documentation of this file.
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

Generated on Sat Oct 24 03:25:20 2009 for GRASS Programmer's Manual by  doxygen 1.6.1