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