1 /* LIBDGL -- a Directed Graph Library implementation 2 * Copyright (C) 2002 Roberto Micarelli 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 19 /* 20 * best view tabstop=4 21 */ 22 23 #ifndef _DGL_dglGraph_s_V2_H_ 24 #define _DGL_dglGraph_s_V2_H_ 25 26 #ifdef DGL_STATS 27 #include <time.h> 28 #endif 29 30 /* 31 * Node macros - addresses in a flat node 32 */ 33 #define DGL_IN_NODEID_v2 0 34 #define DGL_IN_STATUS_v2 1 35 #define DGL_IN_EDGESET_OFFSET_v2 2 36 #define DGL_IN_ATTR_v2 3 37 #define DGL_IN_SIZE_v2 DGL_IN_ATTR_v2 38 39 #define DGL_NODE_SIZEOF_v2( nattr ) (sizeof( dglInt32_t ) * DGL_IN_SIZE_v2 + (nattr) ) 40 #define DGL_NODE_WSIZE_v2( nattr ) (DGL_NODE_SIZEOF_v2( nattr ) / sizeof(dglInt32_t) ) 41 #define DGL_NODE_ALLOC_v2( nattr ) (malloc( DGL_NODE_SIZEOF_v2( nattr ) ) ) 42 43 #define DGL_NODE_ID_v2(p) ((p)[DGL_IN_NODEID_v2]) 44 #define DGL_NODE_STATUS_v2(p) ((p)[DGL_IN_STATUS_v2]) 45 #define DGL_NODE_EDGESET_OFFSET_v2(p) ((p)[DGL_IN_EDGESET_OFFSET_v2]) 46 #define DGL_NODE_ATTR_PTR_v2(p) ((p) + DGL_IN_ATTR_v2) 47 48 /* 49 * Edgeset macros - addresses in a flat edge-area 50 */ 51 #define DGL_ILA_TOCNT_v2 0 52 #define DGL_ILA_SIZE_v2 1 53 #define DGL_ILA_TOARR_v2 DGL_ILA_SIZE_v2 54 55 #define DGL_EDGESET_SIZEOF_v2(C, lattr) (sizeof( dglInt32_t ) * ((C) + 1)) 56 #define DGL_EDGESET_WSIZE_v2(C, lattr) (DGL_EDGESET_SIZEOF_v2(C, lattr) / sizeof(dglInt32_t)) 57 #define DGL_EDGESET_ALLOC_v2(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v2(C, lattr))) 58 #define DGL_EDGESET_REALLOC_v2(P, C, lattr) (realloc(P , DGL_EDGESET_SIZEOF_v2(C, lattr))) 59 60 #define DGL_EDGESET_EDGECOUNT_v2(p) ((p)[DGL_ILA_TOCNT_v2]) 61 #define DGL_EDGESET_EDGEARRAY_PTR_v2(p) ((p) + DGL_ILA_TOARR_v2) 62 #define DGL_EDGESET_EDGE_PTR_v2(pgrp,p,i) DGL_EDGEBUFFER_SHIFT_v2(pgrp,*((p) + DGL_ILA_TOARR_v2 + (i))) 63 64 /* 65 * Edge macros - addresses in a flat edge 66 */ 67 #define DGL_IL_HEAD_OFFSET_v2 0 68 #define DGL_IL_TAIL_OFFSET_v2 1 69 #define DGL_IL_STATUS_v2 2 70 #define DGL_IL_COST_v2 3 71 #define DGL_IL_ID_v2 4 72 #define DGL_IL_ATTR_v2 5 73 #define DGL_IL_SIZE_v2 DGL_IL_ATTR_v2 74 75 #define DGL_EDGE_SIZEOF_v2( lattr ) (sizeof( dglInt32_t ) * DGL_IL_SIZE_v2 + (lattr)) 76 #define DGL_EDGE_WSIZE_v2( lattr ) (DGL_EDGE_SIZEOF_v2( lattr ) / sizeof( dglInt32_t )) 77 #define DGL_EDGE_ALLOC_v2( lattr ) (malloc( DGL_EDGE_SIZEOF_v2( lattr ) )) 78 79 #define DGL_EDGE_HEADNODE_OFFSET_v2(p) ((p)[DGL_IL_HEAD_OFFSET_v2]) 80 #define DGL_EDGE_TAILNODE_OFFSET_v2(p) ((p)[DGL_IL_TAIL_OFFSET_v2]) 81 #define DGL_EDGE_STATUS_v2(p) ((p)[DGL_IL_STATUS_v2]) 82 #define DGL_EDGE_COST_v2(p) ((p)[DGL_IL_COST_v2]) 83 #define DGL_EDGE_ID_v2(p) ((p)[DGL_IL_ID_v2]) 84 #define DGL_EDGE_ATTR_PTR_v2(p) ((p) + DGL_IL_ATTR_v2) 85 #define DGL_EDGE_HEADNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\ 86 DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v2(pl)):\ 87 DGL_EDGE_HEADNODE_OFFSET_v2(pl)) 88 #define DGL_EDGE_TAILNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\ 89 DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v2(pl)):\ 90 DGL_EDGE_TAILNODE_OFFSET_v2(pl)) 91 92 /* 93 * Scan a node buffer 94 */ 95 #define DGL_FOREACH_NODE_v2(pgrp,pn) for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\ 96 (pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\ 97 (pn)+=DGL_NODE_WSIZE_v2((pgrp)->NodeAttrSize)) 98 /* 99 * Scan a edgeset 100 */ 101 #define DGL_FOREACH_EDGE_v2(pgrp,pla,pl,il)\ 102 for((il)=0, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il);\ 103 (il)<DGL_EDGESET_EDGECOUNT_v2(pla);\ 104 (il)++, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il)) 105 /* 106 * Node Buffer Utilities 107 */ 108 #define DGL_NODEBUFFER_SHIFT_v2(pgrp,o) ((dglInt32_t*)((pgrp)->pNodeBuffer + (o))) 109 #define DGL_NODEBUFFER_OFFSET_v2(pgrp,p) ((dglInt32_t)((dglByte_t *)p - (dglByte_t *)(pgrp)->pNodeBuffer)) 110 111 /* 112 * Edge Buffer Utilities 113 */ 114 #define DGL_EDGEBUFFER_SHIFT_v2(pgrp,o) ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o))) 115 #define DGL_EDGEBUFFER_OFFSET_v2(pgrp,pl) ((dglInt32_t)((dglByte_t *)pl - (dglByte_t *)(pgrp)->pEdgeBuffer)) 116 117 118 119 120 int dgl_add_edge_V2(dglGraph_s * pgraph, 121 dglInt32_t nHead, 122 dglInt32_t nTail, 123 dglInt32_t nCost, 124 dglInt32_t nEdge, 125 void *pvHeadAttr, 126 void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags); 127 128 int dgl_unflatten_V2(dglGraph_s * pgraph); 129 int dgl_flatten_V2(dglGraph_s * pgraph); 130 int dgl_initialize_V2(dglGraph_s * pgraph); 131 int dgl_release_V2(dglGraph_s * pgraph); 132 int dgl_write_V2(dglGraph_s * pgraph, int fd); 133 int dgl_read_V2(dglGraph_s * pgraph, int fd, int version); 134 135 136 int dgl_sp_cache_initialize_V2(dglGraph_s * pgraph, dglSPCache_s * pCache, 137 dglInt32_t nStart); 138 void dgl_sp_cache_release_V2(dglGraph_s * pgraph, dglSPCache_s * pCache); 139 140 int dgl_dijkstra_V2_TREE(dglGraph_s * pgraph, 141 dglSPReport_s ** ppReport, 142 dglInt32_t * pDistance, 143 dglInt32_t nStart, 144 dglInt32_t nDestination, 145 dglSPClip_fn fnClip, 146 void *pvClipArg, dglSPCache_s * pCache); 147 int dgl_dijkstra_V2_FLAT(dglGraph_s * pgraph, 148 dglSPReport_s ** ppReport, 149 dglInt32_t * pDistance, 150 dglInt32_t nStart, 151 dglInt32_t nDestination, 152 dglSPClip_fn fnClip, 153 void *pvClipArg, dglSPCache_s * pCache); 154 int dgl_dijkstra_V2(dglGraph_s * pgraph, 155 dglSPReport_s ** ppReport, 156 dglInt32_t * pDistance, 157 dglInt32_t nStart, 158 dglInt32_t nDestination, 159 dglSPClip_fn fnClip, 160 void *pvClipArg, dglSPCache_s * pCache); 161 162 163 int dgl_span_depthfirst_spanning_V2_TREE(dglGraph_s * pgraphIn, 164 dglGraph_s * pgraphOut, 165 dglInt32_t nVertex, 166 void *pvVisited, 167 dglSpanClip_fn fnClip, 168 void *pvClipArg); 169 int dgl_span_depthfirst_spanning_V2_FLAT(dglGraph_s * pgraphIn, 170 dglGraph_s * pgraphOut, 171 dglInt32_t nVertex, 172 void *pvVisited, 173 dglSpanClip_fn fnClip, 174 void *pvClipArg); 175 int dgl_depthfirst_spanning_V2(dglGraph_s * pgraphIn, 176 dglGraph_s * pgraphOut, 177 dglInt32_t nVertex, 178 void *pvVisited, 179 dglSpanClip_fn fnClip, void *pvClipArg); 180 181 182 int dgl_span_minimum_spanning_V2_TREE(dglGraph_s * pgraphIn, 183 dglGraph_s * pgraphOut, 184 dglInt32_t nVertex, 185 dglSpanClip_fn fnClip, void *pvClipArg); 186 int dgl_span_minimum_spanning_V2_FLAT(dglGraph_s * pgraphIn, 187 dglGraph_s * pgraphOut, 188 dglInt32_t nVertex, 189 dglSpanClip_fn fnClip, void *pvClipArg); 190 int dgl_minimum_spanning_V2(dglGraph_s * pgraphIn, 191 dglGraph_s * pgraphOut, 192 dglInt32_t nVertex, 193 dglSpanClip_fn fnClip, void *pvClipArg); 194 195 196 int dgl_add_node_V2(dglGraph_s * pgraph, 197 dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags); 198 int dgl_del_node_outedge_V2(dglGraph_s * pgraph, dglInt32_t nNode, 199 dglInt32_t nEdge); 200 int dgl_del_node_inedge_V2(dglGraph_s * pgraph, dglInt32_t nNode, 201 dglInt32_t nEdge); 202 int dgl_del_node_V2(dglGraph_s * pgraph, dglInt32_t nId); 203 dglInt32_t *dgl_get_node_V2(dglGraph_s * pgraph, dglInt32_t nId); 204 205 dglInt32_t *dgl_get_edge_V2(dglGraph_s * pgraph, dglInt32_t nId); 206 int dgl_del_edge_V2(dglGraph_s * pgraph, dglInt32_t nId); 207 208 dglInt32_t *dgl_getnode_outedgeset_V2(dglGraph_s * pgraph, 209 dglInt32_t * pnode); 210 dglInt32_t *dgl_getnode_inedgeset_V2(dglGraph_s * pgraph, dglInt32_t * pnode); 211 212 /* 213 * Node Traversing 214 */ 215 int dgl_node_t_initialize_V2(dglGraph_s * pGraph, dglNodeTraverser_s * pT); 216 void dgl_node_t_release_V2(dglNodeTraverser_s * pT); 217 dglInt32_t *dgl_node_t_first_V2(dglNodeTraverser_s * pT); 218 dglInt32_t *dgl_node_t_next_V2(dglNodeTraverser_s * pT); 219 dglInt32_t *dgl_node_t_find_V2(dglNodeTraverser_s * pT, dglInt32_t nId); 220 221 222 /* 223 * Edgeset Traversing 224 */ 225 int dgl_edgeset_t_initialize_V2(dglGraph_s * pGraph, 226 dglEdgesetTraverser_s * pTraverser, 227 dglInt32_t * pnEdgeset); 228 void dgl_edgeset_t_release_V2(dglEdgesetTraverser_s * pTraverser); 229 dglInt32_t *dgl_edgeset_t_first_V2(dglEdgesetTraverser_s * pTraverser); 230 dglInt32_t *dgl_edgeset_t_next_V2(dglEdgesetTraverser_s * pTraverser); 231 232 233 int dgl_edge_t_initialize_V2(dglGraph_s * pGraph, 234 dglEdgeTraverser_s * pTraverser, 235 dglEdgePrioritizer_s * pEP); 236 void dgl_edge_t_release_V2(dglEdgeTraverser_s * pTraverser); 237 dglInt32_t *dgl_edge_t_first_V2(dglEdgeTraverser_s * pT); 238 dglInt32_t *dgl_edge_t_next_V2(dglEdgeTraverser_s * pT); 239 240 241 #endif 242