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 __BEGIN_DECLS
00034 
00035 /*
00036  * Graph State bitmask - returned by dglGet_State() function
00037  */
00038 #define DGL_GS_FLAT                     0x1             /* otherwise is TREE */
00039 
00040 /*
00041  * Graph Family
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  * Graph Options
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  * Node Status bitmask - returned by dglNodeGet_Status()
00061  */
00062 #define DGL_NS_HEAD                     0x1             /* node exists as at least one edge's head (static) */
00063 #define DGL_NS_TAIL                     0x2             /* node exists as at least one edge's tail (static) */
00064 #define DGL_NS_ALONE            0x4             /* node is a component */
00065 
00066 
00067 /*
00068  * Edge Status bitmask - returned by dglEdgeGet_Status()
00069  */
00070 #define DGL_ES_DIRECTED         0x1             /* force edge to be directed */
00071 
00072 
00073 /*
00074  * Endianess Values - returned by dglGet_Endianess() function
00075  */
00076 #define DGL_ENDIAN_BIG          1
00077 #define DGL_ENDIAN_LITTLE       2
00078 
00079 
00080 /*
00081  * miscellaneous
00082  */
00083 /* add-edge/add-node flags */
00084 #define DGL_STRONGCONNECT       0x1
00085 #define DGL_ALONE                       0x2
00086 #define DGL_MERGE_EDGE          0x4
00087 /* */
00088 
00089 
00090 
00091 /*
00092  * Shortest Path clip definitions
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  * Spanning clip definitions
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  * Node Prioritizer
00133  */
00134 typedef struct {
00135         void * pvAVL;
00136 } dglNodePrioritizer_s;
00137 
00138 /*
00139  * Edge Prioritizer
00140  */
00141 typedef struct {
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 *, dglSPClipOutput_s *, void *);
00199 
00200 /*
00201  * Spanning clip function type
00202  */
00203 typedef int (*dglSpanClip_fn)(dglGraph_s *, dglGraph_s *, dglSpanClipInput_s *, dglSpanClipOutput_s *, void *);
00204 
00205 /*
00206  * An ARC defined as : from-node, to-node, edge pointer, to-node-distance (from the path starting node)
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  * Shortest Path Report
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  * Shortest Path Cache
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  * Node Traverser
00243  */
00244 typedef struct {
00245         dglGraph_s *            pGraph;
00246         void *                          pvAVLT;
00247         dglInt32_t *            pnNode;
00248 } dglNodeTraverser_s;
00249 
00250 /*
00251  * Edgeset Traverser
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  * Edge Traverser
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  * Error codes returned by dglError
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  * graph context management
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  * node management
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  * edge management
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  * graph I/O
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]; /* 118 = graph header size */
00390 } dglIOContext_s;
00391 
00392 int dglIOContextInitialize(dglGraph_s *, dglIOContext_s *);
00393 void dglIOContextRelease(dglIOContext_s *);
00394 
00395 /*
00396  * Chunked Write callback function type
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  * Algorithms
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  * error management
00475  */
00476 int    dglErrno( dglGraph_s * pgraph );
00477 char * dglStrerror( dglGraph_s * pgraph );
00478 
00479 /*
00480  * graph property hiders
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  * node traverser
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  * edgeset traverser
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  * edge traverser
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

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5