graph_v2.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_V2_H_
00024 #define _DGL_GRAPH_V2_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_v2                                        0
00036 #define DGL_IN_STATUS_v2                                        1
00037 #define DGL_IN_EDGESET_OFFSET_v2                        2
00038 #define DGL_IN_ATTR_v2                                  3
00039 #define DGL_IN_SIZE_v2                                  DGL_IN_ATTR_v2
00040 
00041 #define DGL_NODE_SIZEOF_v2( nattr  )            (sizeof( dglInt32_t ) * DGL_IN_SIZE_v2 + (nattr) )
00042 #define DGL_NODE_WSIZE_v2( nattr )              (DGL_NODE_SIZEOF_v2( nattr ) / sizeof(dglInt32_t) )
00043 #define DGL_NODE_ALLOC_v2( nattr )              (malloc( DGL_NODE_SIZEOF_v2( nattr ) ) )
00044 
00045 #define DGL_NODE_ID_v2(p)                                       ((p)[DGL_IN_NODEID_v2])
00046 #define DGL_NODE_STATUS_v2(p)                           ((p)[DGL_IN_STATUS_v2])
00047 #define DGL_NODE_EDGESET_OFFSET_v2(p)           ((p)[DGL_IN_EDGESET_OFFSET_v2])
00048 #define DGL_NODE_ATTR_PTR_v2(p)                         ((p) + DGL_IN_ATTR_v2)
00049 
00050 /*
00051  * Edgeset macros - addresses in a flat edge-area
00052  */
00053 #define DGL_ILA_TOCNT_v2                                                0
00054 #define DGL_ILA_SIZE_v2                                         1
00055 #define DGL_ILA_TOARR_v2                                                DGL_ILA_SIZE_v2
00056 
00057 #define DGL_EDGESET_SIZEOF_v2(C, lattr)         (sizeof( dglInt32_t ) * ((C) + 1))
00058 #define DGL_EDGESET_WSIZE_v2(C, lattr)          (DGL_EDGESET_SIZEOF_v2(C, lattr) / sizeof(dglInt32_t))
00059 #define DGL_EDGESET_ALLOC_v2(C, lattr)          (malloc(DGL_EDGESET_SIZEOF_v2(C, lattr)))
00060 #define DGL_EDGESET_REALLOC_v2(P, C, lattr)     (realloc(P , DGL_EDGESET_SIZEOF_v2(C, lattr)))
00061 
00062 #define DGL_EDGESET_EDGECOUNT_v2(p)                     ((p)[DGL_ILA_TOCNT_v2])
00063 #define DGL_EDGESET_EDGEARRAY_PTR_v2(p)         ((p) + DGL_ILA_TOARR_v2)
00064 #define DGL_EDGESET_EDGE_PTR_v2(pgrp,p,i)       DGL_EDGEBUFFER_SHIFT_v2(pgrp,*((p) + DGL_ILA_TOARR_v2 + (i)))
00065 
00066 /*
00067  * Edge macros - addresses in a flat edge
00068  */
00069 #define DGL_IL_HEAD_OFFSET_v2                                   0
00070 #define DGL_IL_TAIL_OFFSET_v2                                   1
00071 #define DGL_IL_STATUS_v2                                                2
00072 #define DGL_IL_COST_v2                                          3
00073 #define DGL_IL_ID_v2                                                    4
00074 #define DGL_IL_ATTR_v2                                          5
00075 #define DGL_IL_SIZE_v2                                          DGL_IL_ATTR_v2
00076 
00077 #define DGL_EDGE_SIZEOF_v2( lattr )                     (sizeof( dglInt32_t ) * DGL_IL_SIZE_v2 + (lattr))
00078 #define DGL_EDGE_WSIZE_v2( lattr )                      (DGL_EDGE_SIZEOF_v2( lattr ) / sizeof( dglInt32_t ))
00079 #define DGL_EDGE_ALLOC_v2( lattr )                      (malloc( DGL_EDGE_SIZEOF_v2( lattr ) ))
00080 
00081 #define DGL_EDGE_HEADNODE_OFFSET_v2(p)          ((p)[DGL_IL_HEAD_OFFSET_v2])
00082 #define DGL_EDGE_TAILNODE_OFFSET_v2(p)          ((p)[DGL_IL_TAIL_OFFSET_v2])
00083 #define DGL_EDGE_STATUS_v2(p)                                   ((p)[DGL_IL_STATUS_v2])
00084 #define DGL_EDGE_COST_v2(p)                                     ((p)[DGL_IL_COST_v2])
00085 #define DGL_EDGE_ID_v2(p)                                               ((p)[DGL_IL_ID_v2])
00086 #define DGL_EDGE_ATTR_PTR_v2(p)                         ((p) + DGL_IL_ATTR_v2)
00087 #define DGL_EDGE_HEADNODE_ID_v2(pgrp,pl)                ((pgrp->Flags&1)?\
00088                                                                                                 DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v2(pl)):\
00089                                                                                                 DGL_EDGE_HEADNODE_OFFSET_v2(pl))
00090 #define DGL_EDGE_TAILNODE_ID_v2(pgrp,pl)                ((pgrp->Flags&1)?\
00091                                                                                                 DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v2(pl)):\
00092                                                                                                 DGL_EDGE_TAILNODE_OFFSET_v2(pl))
00093 
00094 /*
00095  * Scan a node buffer
00096  */
00097 #define DGL_FOREACH_NODE_v2(pgrp,pn)                    for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\
00098                                                                                                 (pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\
00099                                                                                                 (pn)+=DGL_NODE_WSIZE_v2((pgrp)->NodeAttrSize))
00100 /*
00101  * Scan a edgeset
00102  */
00103 #define DGL_FOREACH_EDGE_v2(pgrp,pla,pl,il)\
00104                 for((il)=0, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il);\
00105                         (il)<DGL_EDGESET_EDGECOUNT_v2(pla);\
00106                         (il)++, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il))
00107 /*
00108  * Node Buffer Utilities
00109  */
00110 #define DGL_NODEBUFFER_SHIFT_v2(pgrp,o)         ((dglInt32_t*)((pgrp)->pNodeBuffer + (o)))
00111 #define DGL_NODEBUFFER_OFFSET_v2(pgrp,p)                ((dglInt32_t)p - (dglInt32_t)(pgrp)->pNodeBuffer)
00112 
00113 /*
00114  * Edge Buffer Utilities
00115  */
00116 #define DGL_EDGEBUFFER_SHIFT_v2(pgrp,o)         ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o)))
00117 #define DGL_EDGEBUFFER_OFFSET_v2(pgrp,pl)               ((dglInt32_t)pl - (dglInt32_t)(pgrp)->pEdgeBuffer)
00118 
00119 
00120 
00121 
00122 int dgl_add_edge_V2 (
00123                         dglGraph_s *    pgraph ,
00124                         dglInt32_t              nHead,
00125                         dglInt32_t              nTail,
00126                         dglInt32_t              nCost,
00127                         dglInt32_t              nEdge,
00128                         void * pvHeadAttr ,     
00129                         void * pvTailAttr ,     
00130                         void * pvEdgeAttr ,
00131                         dglInt32_t              nFlags
00132                         );
00133 
00134 int dgl_unflatten_V2( dglGraph_s * pgraph );
00135 int dgl_flatten_V2( dglGraph_s * pgraph );
00136 int dgl_initialize_V2( dglGraph_s * pgraph );
00137 int dgl_release_V2( dglGraph_s * pgraph );
00138 int dgl_write_V2( dglGraph_s * pgraph , int fd );
00139 int dgl_read_V2( dglGraph_s * pgraph , int fd , int version );
00140 
00141 
00142 int dgl_sp_cache_initialize_V2( dglGraph_s * pgraph, dglSPCache_s * pCache, dglInt32_t nStart );
00143 void dgl_sp_cache_release_V2( dglGraph_s * pgraph, dglSPCache_s * pCache );
00144 
00145 int dgl_dijkstra_V2_TREE        (
00146                                                 dglGraph_s *            pgraph ,
00147                                                 dglSPReport_s **        ppReport ,
00148                                                 dglInt32_t *                    pDistance ,
00149                                                 dglInt32_t                      nStart ,
00150                                                 dglInt32_t                      nDestination ,
00151                                                 dglSPClip_fn            fnClip,
00152                                                 void *                          pvClipArg,
00153                                                 dglSPCache_s *  pCache
00154                                                 );
00155 int dgl_dijkstra_V2_FLAT        (
00156                                                 dglGraph_s *            pgraph ,
00157                                                 dglSPReport_s **        ppReport ,
00158                                                 dglInt32_t *                    pDistance ,
00159                                                 dglInt32_t                      nStart ,
00160                                                 dglInt32_t                      nDestination ,
00161                                                 dglSPClip_fn            fnClip,
00162                                                 void *                          pvClipArg,
00163                                                 dglSPCache_s *  pCache
00164                                                 );
00165 int dgl_dijkstra_V2     (
00166                                                 dglGraph_s *            pgraph ,
00167                                                 dglSPReport_s **        ppReport ,
00168                                                 dglInt32_t *                    pDistance ,
00169                                                 dglInt32_t                      nStart ,
00170                                                 dglInt32_t                      nDestination ,
00171                                                 dglSPClip_fn            fnClip,
00172                                                 void *                          pvClipArg,
00173                                                 dglSPCache_s *  pCache
00174                                                 );
00175 
00176 
00177 int dgl_span_depthfirst_spanning_V2_TREE(
00178                                                 dglGraph_s * pgraphIn ,
00179                                                 dglGraph_s * pgraphOut ,
00180                                                 dglInt32_t nVertex ,
00181                                                 void * pvVisited ,
00182                                                 dglSpanClip_fn  fnClip ,
00183                                                 void *                          pvClipArg
00184                                                 );
00185 int dgl_span_depthfirst_spanning_V2_FLAT(
00186                                                 dglGraph_s * pgraphIn ,
00187                                                 dglGraph_s * pgraphOut ,
00188                                                 dglInt32_t nVertex ,
00189                                                 void * pvVisited ,
00190                                                 dglSpanClip_fn  fnClip ,
00191                                                 void *                          pvClipArg
00192                                                 );
00193 int dgl_depthfirst_spanning_V2(
00194                                                 dglGraph_s * pgraphIn ,
00195                                                 dglGraph_s * pgraphOut ,
00196                                                 dglInt32_t nVertex ,
00197                                                 void * pvVisited ,
00198                                                 dglSpanClip_fn  fnClip ,
00199                                                 void *                          pvClipArg
00200                                                 );
00201 
00202 
00203 int dgl_span_minimum_spanning_V2_TREE(
00204                                                 dglGraph_s * pgraphIn ,
00205                                                 dglGraph_s * pgraphOut ,
00206                                                 dglInt32_t nVertex ,
00207                                                 dglSpanClip_fn  fnClip ,
00208                                                 void *                          pvClipArg
00209                                                 );
00210 int dgl_span_minimum_spanning_V2_FLAT(
00211                                                 dglGraph_s * pgraphIn ,
00212                                                 dglGraph_s * pgraphOut ,
00213                                                 dglInt32_t nVertex ,
00214                                                 dglSpanClip_fn  fnClip ,
00215                                                 void *                          pvClipArg
00216                                                 );
00217 int dgl_minimum_spanning_V2(
00218                                                 dglGraph_s * pgraphIn ,
00219                                                 dglGraph_s * pgraphOut ,
00220                                                 dglInt32_t nVertex ,
00221                                                 dglSpanClip_fn  fnClip ,
00222                                                 void *                          pvClipArg
00223                                                 );
00224 
00225 
00226 int dgl_add_node_V2(
00227                                                 dglGraph_s *  pgraph,
00228                                                 dglInt32_t       nId,
00229                                                 void *                  pvNodeAttr,     
00230                                                 dglInt32_t              nFlags
00231                                         );
00232 int dgl_del_node_outedge_V2(dglGraph_s * pgraph, dglInt32_t nNode, dglInt32_t nEdge);
00233 int dgl_del_node_inedge_V2(dglGraph_s * pgraph, dglInt32_t nNode, dglInt32_t nEdge);
00234 int dgl_del_node_V2(
00235                                                 dglGraph_s *  pgraph,
00236                                                 dglInt32_t       nId
00237                                         );
00238 dglInt32_t * dgl_get_node_V2( dglGraph_s * pgraph , dglInt32_t nId );
00239 
00240 dglInt32_t * dgl_get_edge_V2( dglGraph_s * pgraph , dglInt32_t nId );
00241 int dgl_del_edge_V2( dglGraph_s * pgraph , dglInt32_t nId );
00242 
00243 dglInt32_t * dgl_getnode_outedgeset_V2( dglGraph_s * pgraph , dglInt32_t * pnode );
00244 dglInt32_t * dgl_getnode_inedgeset_V2( dglGraph_s * pgraph , dglInt32_t * pnode );
00245 
00246 /*
00247  * Node Traversing
00248  */
00249 int                     dgl_node_t_initialize_V2( dglGraph_s * pGraph, dglNodeTraverser_s * pT );
00250 void            dgl_node_t_release_V2( dglNodeTraverser_s * pT );
00251 dglInt32_t * dgl_node_t_first_V2( dglNodeTraverser_s * pT );
00252 dglInt32_t * dgl_node_t_next_V2( dglNodeTraverser_s * pT );
00253 dglInt32_t * dgl_node_t_find_V2( dglNodeTraverser_s * pT , dglInt32_t nId );
00254 
00255 
00256 /*
00257  * Edgeset Traversing
00258  */
00259 int                     dgl_edgeset_t_initialize_V2     (
00260                                                                                 dglGraph_s * pGraph ,
00261                                                                                 dglEdgesetTraverser_s * pTraverser ,
00262                                                                                 dglInt32_t * pnEdgeset
00263                                                                                 );
00264 void            dgl_edgeset_t_release_V2        ( dglEdgesetTraverser_s * pTraverser );
00265 dglInt32_t *    dgl_edgeset_t_first_V2  ( dglEdgesetTraverser_s * pTraverser );
00266 dglInt32_t *    dgl_edgeset_t_next_V2   ( dglEdgesetTraverser_s * pTraverser );
00267 
00268 
00269 int             dgl_edge_t_initialize_V2        ( dglGraph_s * pGraph , dglEdgeTraverser_s * pTraverser , dglEdgePrioritizer_s * pEP );
00270 void            dgl_edge_t_release_V2           ( dglEdgeTraverser_s * pTraverser );
00271 dglInt32_t * dgl_edge_t_first_V2                ( dglEdgeTraverser_s * pT );
00272 dglInt32_t * dgl_edge_t_next_V2         ( dglEdgeTraverser_s * pT );
00273 
00274 
00275 
00276 
00277 __END_DECLS
00278 #endif

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