graph_v1.h

Go to the documentation of this file.
00001 /* LIBDGL -- a Directed Graph Library implementation
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_V1_H_
00024 #define _DGL_GRAPH_V1_H_
00025 
00026 #ifdef DGL_STATS
00027 #include <time.h>
00028 #endif
00029 
00030 __BEGIN_DECLS
00031 
00032 /*
00033  * Node macros - addresses in a flat node
00034  */
00035 #define DGL_IN_NODEID_v1                0
00036 #define DGL_IN_STATUS_v1                1
00037 #define DGL_IN_TAIL_OFFSET_v1   2
00038 #define DGL_IN_ATTR_v1                  3
00039 #define DGL_IN_SIZE_v1                  DGL_IN_ATTR_v1
00040 
00041 #define DGL_NODE_SIZEOF_v1( nattr  )    (sizeof( dglInt32_t ) * DGL_IN_SIZE_v1 + (nattr) )
00042 #define DGL_NODE_WSIZE_v1( nattr )              (DGL_NODE_SIZEOF_v1( nattr ) / sizeof(dglInt32_t) )
00043 #define DGL_NODE_ALLOC_v1( nattr )      (malloc( DGL_NODE_SIZEOF_v1( nattr ) ) )
00044 
00045 #define DGL_NODE_ID_v1(p)                               ((p)[DGL_IN_NODEID_v1])
00046 #define DGL_NODE_STATUS_v1(p)                   ((p)[DGL_IN_STATUS_v1])
00047 #define DGL_NODE_EDGESET_OFFSET_v1(p)   ((p)[DGL_IN_TAIL_OFFSET_v1])
00048 #define DGL_NODE_ATTR_PTR_v1(p)                 ((p) + DGL_IN_ATTR_v1)
00049 
00050 /*
00051  * Edgeset macros - addresses in a flat edge-area
00052  */
00053 #define DGL_ILA_TOCNT_v1        0
00054 #define DGL_ILA_SIZE_v1         1
00055 #define DGL_ILA_TOARR_v1        DGL_ILA_SIZE_v1
00056 
00057 #define DGL_EDGESET_SIZEOF_v1(C, lattr)         (sizeof( dglInt32_t ) * (DGL_ILA_SIZE_v1) + DGL_EDGE_SIZEOF_v1(lattr) * (C))
00058 #define DGL_EDGESET_WSIZE_v1(C, lattr)          (DGL_EDGESET_SIZEOF_v1(C, lattr) / sizeof(dglInt32_t))
00059 #define DGL_EDGESET_ALLOC_v1(C, lattr)          (malloc(DGL_EDGESET_SIZEOF_v1(C, lattr)))
00060 #define DGL_EDGESET_REALLOC_v1(P, C, lattr)     (realloc(P , DGL_EDGESET_SIZEOF_v1(C, lattr)))
00061 
00062 #define DGL_EDGESET_EDGECOUNT_v1(p)                     ((p)[DGL_ILA_TOCNT_v1])
00063 #define DGL_EDGESET_EDGEARRAY_PTR_v1(p)         ((p) + DGL_ILA_TOARR_v1)
00064 #define DGL_EDGESET_EDGE_PTR_v1(p,i,C)          (((p) + DGL_ILA_TOARR_v1) + (i) * DGL_EDGE_WSIZE_v1(C))
00065 
00066 /*
00067  * Edge macros - addresses in a flat edge
00068  */
00069 #define DGL_IL_HEAD_OFFSET_v1   0
00070 #define DGL_IL_TAIL_OFFSET_v1   1
00071 #define DGL_IL_COST_v1                  2
00072 #define DGL_IL_ID_v1                    3
00073 #define DGL_IL_ATTR_v1                  4
00074 #define DGL_IL_SIZE_v1                  DGL_IL_ATTR_v1
00075 
00076 #define DGL_EDGE_SIZEOF_v1( lattr )     (sizeof( dglInt32_t ) * DGL_IL_SIZE_v1 + (lattr))
00077 #define DGL_EDGE_WSIZE_v1( lattr )              (DGL_EDGE_SIZEOF_v1( lattr ) / sizeof( dglInt32_t ))
00078 #define DGL_EDGE_ALLOC_v1( lattr )      (malloc( DGL_EDGE_SIZEOF_v1( lattr ) ))
00079 
00080 #define DGL_EDGE_HEADNODE_OFFSET_v1(p)          ((p)[DGL_IL_HEAD_OFFSET_v1])
00081 #define DGL_EDGE_TAILNODE_OFFSET_v1(p)          ((p)[DGL_IL_TAIL_OFFSET_v1])
00082 #define DGL_EDGE_COST_v1(p)                                     ((p)[DGL_IL_COST_v1])
00083 #define DGL_EDGE_ID_v1(p)                                       ((p)[DGL_IL_ID_v1])
00084 #define DGL_EDGE_ATTR_PTR_v1(p)                         ((p) + DGL_IL_ATTR_v1)
00085 #define DGL_EDGE_HEADNODE_ID_v1(pgrp,pl)        ((pgrp->Flags&1)?\
00086                                                                                                 DGL_NODE_ID_v1(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v1(pl)):\
00087                                                                                                 DGL_EDGE_HEADNODE_OFFSET_v1(pl))
00088 #define DGL_EDGE_TAILNODE_ID_v1(pgrp,pl)        ((pgrp->Flags&1)?\
00089                                                                                                 DGL_NODE_ID_v1(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v1(pl)):\
00090                                                                                                 DGL_EDGE_TAILNODE_OFFSET_v1(pl))
00091 
00092 /*
00093  * Scan a node buffer
00094  */
00095 #define DGL_FOREACH_NODE_v1(pgrp,pn)    for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\
00096                                                                                         (pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\
00097                                                                                         (pn)+=DGL_NODE_WSIZE_v1((pgrp)->NodeAttrSize))
00098 /*
00099  * Scan a edgeset
00100  */
00101 #define DGL_FOREACH_EDGE_v1(pgrp,pla,pl)        for((pl)=DGL_EDGESET_EDGEARRAY_PTR_v1(pla);\
00102                                                                                                 (pl)<(pla)+DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize)*DGL_EDGESET_EDGECOUNT_v1(pla);\
00103                                                                                                 (pl)+=DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize))
00104 /*
00105  * Node Buffer Utilities
00106  */
00107 #define DGL_NODEBUFFER_SHIFT_v1(pgrp,o)         ((dglInt32_t*)((pgrp)->pNodeBuffer + (o)))
00108 #define DGL_NODEBUFFER_OFFSET_v1(pgrp,p)        ((dglInt32_t)p - (dglInt32_t)(pgrp)->pNodeBuffer)
00109 
00110 /*
00111  * Edge Buffer Utilities
00112  */
00113 #define DGL_EDGEBUFFER_SHIFT_v1(pgrp,o)         ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o)))
00114 #define DGL_EDGEBUFFER_OFFSET_v1(pgrp,pl)       ((dglInt32_t)pl - (dglInt32_t)(pgrp)->pEdgeBuffer)
00115 
00116 
00117 
00118 
00119 int dgl_add_edge_V1 (
00120                         dglGraph_s *    pgraph ,
00121                         dglInt32_t              nHead,
00122                         dglInt32_t              nTail,
00123                         dglInt32_t              nCost,
00124                         dglInt32_t              nEdge,
00125                         void * pvHeadAttr ,     
00126                         void * pvTailAttr ,     
00127                         void * pvEdgeAttr ,
00128                         dglInt32_t              nFlags
00129                         );
00130 
00131 int dgl_unflatten_V1( dglGraph_s * pgraph );
00132 int dgl_flatten_V1( dglGraph_s * pgraph );
00133 int dgl_initialize_V1( dglGraph_s * pgraph );
00134 int dgl_release_V1( dglGraph_s * pgraph );
00135 int dgl_write_V1( dglGraph_s * pgraph , int fd );
00136 int dgl_read_V1( dglGraph_s * pgraph , int fd );
00137 
00138 
00139 int dgl_sp_cache_initialize_V1( dglGraph_s * pgraph, dglSPCache_s * pCache, dglInt32_t nStart );
00140 void dgl_sp_cache_release_V1( dglGraph_s * pgraph, dglSPCache_s * pCache );
00141 
00142 int dgl_dijkstra_V1_TREE        (
00143                                                 dglGraph_s *            pgraph ,
00144                                                 dglSPReport_s **        ppReport ,
00145                                                 dglInt32_t *                    pDistance ,
00146                                                 dglInt32_t                      nStart ,
00147                                                 dglInt32_t                      nDestination ,
00148                                                 dglSPClip_fn            fnClip,
00149                                                 void *                          pvClipArg,
00150                                                 dglSPCache_s *  pCache
00151                                                 );
00152 int dgl_dijkstra_V1_FLAT        (
00153                                                 dglGraph_s *            pgraph ,
00154                                                 dglSPReport_s **        ppReport ,
00155                                                 dglInt32_t *                    pDistance ,
00156                                                 dglInt32_t                      nStart ,
00157                                                 dglInt32_t                      nDestination ,
00158                                                 dglSPClip_fn            fnClip,
00159                                                 void *                          pvClipArg,
00160                                                 dglSPCache_s *  pCache
00161                                                 );
00162 int dgl_dijkstra_V1     (
00163                                                 dglGraph_s *            pgraph ,
00164                                                 dglSPReport_s **        ppReport ,
00165                                                 dglInt32_t *                    pDistance ,
00166                                                 dglInt32_t                      nStart ,
00167                                                 dglInt32_t                      nDestination ,
00168                                                 dglSPClip_fn            fnClip,
00169                                                 void *                          pvClipArg,
00170                                                 dglSPCache_s *  pCache
00171                                                 );
00172 
00173 
00174 int dgl_span_depthfirst_spanning_V1_TREE(
00175                                                 dglGraph_s * pgraphIn ,
00176                                                 dglGraph_s * pgraphOut ,
00177                                                 dglInt32_t nVertex ,
00178                                                 void * pvVisited ,
00179                                                 dglSpanClip_fn  fnClip ,
00180                                                 void *                          pvClipArg
00181                                                 );
00182 int dgl_span_depthfirst_spanning_V1_FLAT(
00183                                                 dglGraph_s * pgraphIn ,
00184                                                 dglGraph_s * pgraphOut ,
00185                                                 dglInt32_t nVertex ,
00186                                                 void * pvVisited ,
00187                                                 dglSpanClip_fn  fnClip ,
00188                                                 void *                          pvClipArg
00189                                                 );
00190 int dgl_depthfirst_spanning_V1(
00191                                                 dglGraph_s * pgraphIn ,
00192                                                 dglGraph_s * pgraphOut ,
00193                                                 dglInt32_t nVertex ,
00194                                                 void * pvVisited ,
00195                                                 dglSpanClip_fn  fnClip ,
00196                                                 void *                          pvClipArg
00197                                                 );
00198 
00199 
00200 int dgl_span_minimum_spanning_V1_TREE(
00201                                                 dglGraph_s * pgraphIn ,
00202                                                 dglGraph_s * pgraphOut ,
00203                                                 dglInt32_t nVertex ,
00204                                                 dglSpanClip_fn  fnClip ,
00205                                                 void *                          pvClipArg
00206                                                 );
00207 int dgl_span_minimum_spanning_V1_FLAT(
00208                                                 dglGraph_s * pgraphIn ,
00209                                                 dglGraph_s * pgraphOut ,
00210                                                 dglInt32_t nVertex ,
00211                                                 dglSpanClip_fn  fnClip ,
00212                                                 void *                          pvClipArg
00213                                                 );
00214 int dgl_minimum_spanning_V1(
00215                                                 dglGraph_s * pgraphIn ,
00216                                                 dglGraph_s * pgraphOut ,
00217                                                 dglInt32_t nVertex ,
00218                                                 dglSpanClip_fn  fnClip ,
00219                                                 void *                          pvClipArg
00220                                                 );
00221 
00222 
00223 int dgl_add_node_V1(
00224                                                 dglGraph_s *  pgraph,
00225                                                 dglInt32_t       nId,
00226                                                 void *                  pvNodeAttr,     
00227                                                 dglInt32_t              nFlags
00228                                         );
00229 int dgl_del_node_V1(
00230                                                 dglGraph_s *  pgraph,
00231                                                 dglInt32_t       nId
00232                                         );
00233 dglInt32_t * dgl_get_node_V1( dglGraph_s * pgraph , dglInt32_t nId );
00234 
00235 dglInt32_t * dgl_get_edge_V1( dglGraph_s * pgraph , dglInt32_t nId );
00236 int dgl_del_edge_V1( dglGraph_s * pgraph , dglInt32_t nId );
00237 
00238 dglInt32_t * dgl_getnode_outedgeset_V1( dglGraph_s * pgraph , dglInt32_t * pnode );
00239 
00240 /*
00241  * Node Traversing
00242  */
00243 int                     dgl_node_t_initialize_V1( dglGraph_s * pGraph, dglNodeTraverser_s * pT );
00244 void            dgl_node_t_release_V1( dglNodeTraverser_s * pT );
00245 dglInt32_t * dgl_node_t_first_V1( dglNodeTraverser_s * pT );
00246 dglInt32_t * dgl_node_t_next_V1( dglNodeTraverser_s * pT );
00247 dglInt32_t * dgl_node_t_find_V1( dglNodeTraverser_s * pT , dglInt32_t nId );
00248 
00249 
00250 /*
00251  * Edgeset Traversing
00252  */
00253 int                     dgl_edgeset_t_initialize_V1     (
00254                                                                                 dglGraph_s * pGraph ,
00255                                                                                 dglEdgesetTraverser_s * pTraverser ,
00256                                                                                 dglInt32_t * pnEdgeset
00257                                                                                 );
00258 void            dgl_edgeset_t_release_V1        ( dglEdgesetTraverser_s * pTraverser );
00259 dglInt32_t *    dgl_edgeset_t_first_V1  ( dglEdgesetTraverser_s * pTraverser );
00260 dglInt32_t *    dgl_edgeset_t_next_V1   ( dglEdgesetTraverser_s * pTraverser );
00261 
00262 
00263 int             dgl_edge_t_initialize_V1        ( dglGraph_s * pGraph , dglEdgeTraverser_s * pTraverser , dglEdgePrioritizer_s * pEP );
00264 void            dgl_edge_t_release_V1           ( dglEdgeTraverser_s * pTraverser );
00265 dglInt32_t * dgl_edge_t_first_V1                ( dglEdgeTraverser_s * pT );
00266 dglInt32_t * dgl_edge_t_next_V1         ( dglEdgeTraverser_s * pT );
00267 
00268 
00269 
00270 
00271 __END_DECLS
00272 #endif

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