GRASS Programmer's Manual
6.4.1(2011)
|
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