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_V1_H_ 24 #define _DGL_dglGraph_s_V1_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_v1 0 34 #define DGL_IN_STATUS_v1 1 35 #define DGL_IN_TAIL_OFFSET_v1 2 36 #define DGL_IN_ATTR_v1 3 37 #define DGL_IN_SIZE_v1 DGL_IN_ATTR_v1 38 39 #define DGL_NODE_SIZEOF_v1( nattr ) (sizeof( dglInt32_t ) * DGL_IN_SIZE_v1 + (nattr) ) 40 #define DGL_NODE_WSIZE_v1( nattr ) (DGL_NODE_SIZEOF_v1( nattr ) / sizeof(dglInt32_t) ) 41 #define DGL_NODE_ALLOC_v1( nattr ) (malloc( DGL_NODE_SIZEOF_v1( nattr ) ) ) 42 43 #define DGL_NODE_ID_v1(p) ((p)[DGL_IN_NODEID_v1]) 44 #define DGL_NODE_STATUS_v1(p) ((p)[DGL_IN_STATUS_v1]) 45 #define DGL_NODE_EDGESET_OFFSET_v1(p) ((p)[DGL_IN_TAIL_OFFSET_v1]) 46 #define DGL_NODE_ATTR_PTR_v1(p) ((p) + DGL_IN_ATTR_v1) 47 48 /* 49 * Edgeset macros - addresses in a flat edge-area 50 */ 51 #define DGL_ILA_TOCNT_v1 0 52 #define DGL_ILA_SIZE_v1 1 53 #define DGL_ILA_TOARR_v1 DGL_ILA_SIZE_v1 54 55 #define DGL_EDGESET_SIZEOF_v1(C, lattr) (sizeof( dglInt32_t ) * (DGL_ILA_SIZE_v1) + DGL_EDGE_SIZEOF_v1(lattr) * (C)) 56 #define DGL_EDGESET_WSIZE_v1(C, lattr) (DGL_EDGESET_SIZEOF_v1(C, lattr) / sizeof(dglInt32_t)) 57 #define DGL_EDGESET_ALLOC_v1(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v1(C, lattr))) 58 #define DGL_EDGESET_REALLOC_v1(P, C, lattr) (realloc(P , DGL_EDGESET_SIZEOF_v1(C, lattr))) 59 60 #define DGL_EDGESET_EDGECOUNT_v1(p) ((p)[DGL_ILA_TOCNT_v1]) 61 #define DGL_EDGESET_EDGEARRAY_PTR_v1(p) ((p) + DGL_ILA_TOARR_v1) 62 #define DGL_EDGESET_EDGE_PTR_v1(p,i,C) (((p) + DGL_ILA_TOARR_v1) + (i) * DGL_EDGE_WSIZE_v1(C)) 63 64 /* 65 * Edge macros - addresses in a flat edge 66 */ 67 #define DGL_IL_HEAD_OFFSET_v1 0 68 #define DGL_IL_TAIL_OFFSET_v1 1 69 #define DGL_IL_COST_v1 2 70 #define DGL_IL_ID_v1 3 71 #define DGL_IL_ATTR_v1 4 72 #define DGL_IL_SIZE_v1 DGL_IL_ATTR_v1 73 74 #define DGL_EDGE_SIZEOF_v1( lattr ) (sizeof( dglInt32_t ) * DGL_IL_SIZE_v1 + (lattr)) 75 #define DGL_EDGE_WSIZE_v1( lattr ) (DGL_EDGE_SIZEOF_v1( lattr ) / sizeof( dglInt32_t )) 76 #define DGL_EDGE_ALLOC_v1( lattr ) (malloc( DGL_EDGE_SIZEOF_v1( lattr ) )) 77 78 #define DGL_EDGE_HEADNODE_OFFSET_v1(p) ((p)[DGL_IL_HEAD_OFFSET_v1]) 79 #define DGL_EDGE_TAILNODE_OFFSET_v1(p) ((p)[DGL_IL_TAIL_OFFSET_v1]) 80 #define DGL_EDGE_COST_v1(p) ((p)[DGL_IL_COST_v1]) 81 #define DGL_EDGE_ID_v1(p) ((p)[DGL_IL_ID_v1]) 82 #define DGL_EDGE_ATTR_PTR_v1(p) ((p) + DGL_IL_ATTR_v1) 83 #define DGL_EDGE_HEADNODE_ID_v1(pgrp,pl) ((pgrp->Flags&1)?\ 84 DGL_NODE_ID_v1(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v1(pl)):\ 85 DGL_EDGE_HEADNODE_OFFSET_v1(pl)) 86 #define DGL_EDGE_TAILNODE_ID_v1(pgrp,pl) ((pgrp->Flags&1)?\ 87 DGL_NODE_ID_v1(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v1(pl)):\ 88 DGL_EDGE_TAILNODE_OFFSET_v1(pl)) 89 90 /* 91 * Scan a node buffer 92 */ 93 #define DGL_FOREACH_NODE_v1(pgrp,pn) for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\ 94 (pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\ 95 (pn)+=DGL_NODE_WSIZE_v1((pgrp)->NodeAttrSize)) 96 /* 97 * Scan a edgeset 98 */ 99 #define DGL_FOREACH_EDGE_v1(pgrp,pla,pl) for((pl)=DGL_EDGESET_EDGEARRAY_PTR_v1(pla);\ 100 (pl)<(pla)+DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize)*DGL_EDGESET_EDGECOUNT_v1(pla);\ 101 (pl)+=DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize)) 102 /* 103 * Node Buffer Utilities 104 */ 105 #define DGL_NODEBUFFER_SHIFT_v1(pgrp,o) ((dglInt32_t*)((pgrp)->pNodeBuffer + (o))) 106 #define DGL_NODEBUFFER_OFFSET_v1(pgrp,p) ((dglInt32_t)((dglByte_t *)p - (dglByte_t *)(pgrp)->pNodeBuffer)) 107 108 /* 109 * Edge Buffer Utilities 110 */ 111 #define DGL_EDGEBUFFER_SHIFT_v1(pgrp,o) ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o))) 112 #define DGL_EDGEBUFFER_OFFSET_v1(pgrp,pl) ((dglInt32_t)((dglByte_t *)pl - (dglByte_t *)(pgrp)->pEdgeBuffer)) 113 114 115 116 117 int dgl_add_edge_V1(dglGraph_s * pgraph, 118 dglInt32_t nHead, 119 dglInt32_t nTail, 120 dglInt32_t nCost, 121 dglInt32_t nEdge, 122 void *pvHeadAttr, 123 void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags); 124 125 int dgl_unflatten_V1(dglGraph_s * pgraph); 126 int dgl_flatten_V1(dglGraph_s * pgraph); 127 int dgl_initialize_V1(dglGraph_s * pgraph); 128 int dgl_release_V1(dglGraph_s * pgraph); 129 int dgl_write_V1(dglGraph_s * pgraph, int fd); 130 int dgl_read_V1(dglGraph_s * pgraph, int fd); 131 132 133 int dgl_sp_cache_initialize_V1(dglGraph_s * pgraph, dglSPCache_s * pCache, 134 dglInt32_t nStart); 135 void dgl_sp_cache_release_V1(dglGraph_s * pgraph, dglSPCache_s * pCache); 136 137 int dgl_dijkstra_V1_TREE(dglGraph_s * pgraph, 138 dglSPReport_s ** ppReport, 139 dglInt32_t * pDistance, 140 dglInt32_t nStart, 141 dglInt32_t nDestination, 142 dglSPClip_fn fnClip, 143 void *pvClipArg, dglSPCache_s * pCache); 144 int dgl_dijkstra_V1_FLAT(dglGraph_s * pgraph, 145 dglSPReport_s ** ppReport, 146 dglInt32_t * pDistance, 147 dglInt32_t nStart, 148 dglInt32_t nDestination, 149 dglSPClip_fn fnClip, 150 void *pvClipArg, dglSPCache_s * pCache); 151 int dgl_dijkstra_V1(dglGraph_s * pgraph, 152 dglSPReport_s ** ppReport, 153 dglInt32_t * pDistance, 154 dglInt32_t nStart, 155 dglInt32_t nDestination, 156 dglSPClip_fn fnClip, 157 void *pvClipArg, dglSPCache_s * pCache); 158 159 160 int dgl_span_depthfirst_spanning_V1_TREE(dglGraph_s * pgraphIn, 161 dglGraph_s * pgraphOut, 162 dglInt32_t nVertex, 163 void *pvVisited, 164 dglSpanClip_fn fnClip, 165 void *pvClipArg); 166 int dgl_span_depthfirst_spanning_V1_FLAT(dglGraph_s * pgraphIn, 167 dglGraph_s * pgraphOut, 168 dglInt32_t nVertex, 169 void *pvVisited, 170 dglSpanClip_fn fnClip, 171 void *pvClipArg); 172 int dgl_depthfirst_spanning_V1(dglGraph_s * pgraphIn, 173 dglGraph_s * pgraphOut, 174 dglInt32_t nVertex, 175 void *pvVisited, 176 dglSpanClip_fn fnClip, void *pvClipArg); 177 178 179 int dgl_span_minimum_spanning_V1_TREE(dglGraph_s * pgraphIn, 180 dglGraph_s * pgraphOut, 181 dglInt32_t nVertex, 182 dglSpanClip_fn fnClip, void *pvClipArg); 183 int dgl_span_minimum_spanning_V1_FLAT(dglGraph_s * pgraphIn, 184 dglGraph_s * pgraphOut, 185 dglInt32_t nVertex, 186 dglSpanClip_fn fnClip, void *pvClipArg); 187 int dgl_minimum_spanning_V1(dglGraph_s * pgraphIn, 188 dglGraph_s * pgraphOut, 189 dglInt32_t nVertex, 190 dglSpanClip_fn fnClip, void *pvClipArg); 191 192 193 int dgl_add_node_V1(dglGraph_s * pgraph, 194 dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags); 195 int dgl_del_node_V1(dglGraph_s * pgraph, dglInt32_t nId); 196 dglInt32_t *dgl_get_node_V1(dglGraph_s * pgraph, dglInt32_t nId); 197 198 dglInt32_t *dgl_get_edge_V1(dglGraph_s * pgraph, dglInt32_t nId); 199 int dgl_del_edge_V1(dglGraph_s * pgraph, dglInt32_t nId); 200 201 dglInt32_t *dgl_getnode_outedgeset_V1(dglGraph_s * pgraph, 202 dglInt32_t * pnode); 203 204 /* 205 * Node Traversing 206 */ 207 int dgl_node_t_initialize_V1(dglGraph_s * pGraph, dglNodeTraverser_s * pT); 208 void dgl_node_t_release_V1(dglNodeTraverser_s * pT); 209 dglInt32_t *dgl_node_t_first_V1(dglNodeTraverser_s * pT); 210 dglInt32_t *dgl_node_t_next_V1(dglNodeTraverser_s * pT); 211 dglInt32_t *dgl_node_t_find_V1(dglNodeTraverser_s * pT, dglInt32_t nId); 212 213 214 /* 215 * Edgeset Traversing 216 */ 217 int dgl_edgeset_t_initialize_V1(dglGraph_s * pGraph, 218 dglEdgesetTraverser_s * pTraverser, 219 dglInt32_t * pnEdgeset); 220 void dgl_edgeset_t_release_V1(dglEdgesetTraverser_s * pTraverser); 221 dglInt32_t *dgl_edgeset_t_first_V1(dglEdgesetTraverser_s * pTraverser); 222 dglInt32_t *dgl_edgeset_t_next_V1(dglEdgesetTraverser_s * pTraverser); 223 224 225 int dgl_edge_t_initialize_V1(dglGraph_s * pGraph, 226 dglEdgeTraverser_s * pTraverser, 227 dglEdgePrioritizer_s * pEP); 228 void dgl_edge_t_release_V1(dglEdgeTraverser_s * pTraverser); 229 dglInt32_t *dgl_edge_t_first_V1(dglEdgeTraverser_s * pT); 230 dglInt32_t *dgl_edge_t_next_V1(dglEdgeTraverser_s * pT); 231 232 233 234 235 #endif 236