/* LIBDGL -- a Directed Graph Library implementation * Copyright (C) 2002 Roberto Micarelli * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ /* * best view tabstop=4 */ #ifndef _DGL_dglGraph_s_V2_H_ #define _DGL_dglGraph_s_V2_H_ #ifdef DGL_STATS #include #endif /* * Node macros - addresses in a flat node */ #define DGL_IN_NODEID_v2 0 #define DGL_IN_STATUS_v2 1 #define DGL_IN_EDGESET_OFFSET_v2 2 #define DGL_IN_ATTR_v2 3 #define DGL_IN_SIZE_v2 DGL_IN_ATTR_v2 #define DGL_NODE_SIZEOF_v2( nattr ) (sizeof( dglInt32_t ) * DGL_IN_SIZE_v2 + (nattr) ) #define DGL_NODE_WSIZE_v2( nattr ) (DGL_NODE_SIZEOF_v2( nattr ) / sizeof(dglInt32_t) ) #define DGL_NODE_ALLOC_v2( nattr ) (malloc( DGL_NODE_SIZEOF_v2( nattr ) ) ) #define DGL_NODE_ID_v2(p) ((p)[DGL_IN_NODEID_v2]) #define DGL_NODE_STATUS_v2(p) ((p)[DGL_IN_STATUS_v2]) #define DGL_NODE_EDGESET_OFFSET_v2(p) ((p)[DGL_IN_EDGESET_OFFSET_v2]) #define DGL_NODE_ATTR_PTR_v2(p) ((p) + DGL_IN_ATTR_v2) /* * Edgeset macros - addresses in a flat edge-area */ #define DGL_ILA_TOCNT_v2 0 #define DGL_ILA_SIZE_v2 1 #define DGL_ILA_TOARR_v2 DGL_ILA_SIZE_v2 #define DGL_EDGESET_SIZEOF_v2(C, lattr) (sizeof( dglInt32_t ) * ((C) + 1)) #define DGL_EDGESET_WSIZE_v2(C, lattr) (DGL_EDGESET_SIZEOF_v2(C, lattr) / sizeof(dglInt32_t)) #define DGL_EDGESET_ALLOC_v2(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v2(C, lattr))) #define DGL_EDGESET_REALLOC_v2(P, C, lattr) (realloc(P , DGL_EDGESET_SIZEOF_v2(C, lattr))) #define DGL_EDGESET_EDGECOUNT_v2(p) ((p)[DGL_ILA_TOCNT_v2]) #define DGL_EDGESET_EDGEARRAY_PTR_v2(p) ((p) + DGL_ILA_TOARR_v2) #define DGL_EDGESET_EDGE_PTR_v2(pgrp,p,i) DGL_EDGEBUFFER_SHIFT_v2(pgrp,*((p) + DGL_ILA_TOARR_v2 + (i))) /* * Edge macros - addresses in a flat edge */ #define DGL_IL_HEAD_OFFSET_v2 0 #define DGL_IL_TAIL_OFFSET_v2 1 #define DGL_IL_STATUS_v2 2 #define DGL_IL_COST_v2 3 #define DGL_IL_ID_v2 4 #define DGL_IL_ATTR_v2 5 #define DGL_IL_SIZE_v2 DGL_IL_ATTR_v2 #define DGL_EDGE_SIZEOF_v2( lattr ) (sizeof( dglInt32_t ) * DGL_IL_SIZE_v2 + (lattr)) #define DGL_EDGE_WSIZE_v2( lattr ) (DGL_EDGE_SIZEOF_v2( lattr ) / sizeof( dglInt32_t )) #define DGL_EDGE_ALLOC_v2( lattr ) (malloc( DGL_EDGE_SIZEOF_v2( lattr ) )) #define DGL_EDGE_HEADNODE_OFFSET_v2(p) ((p)[DGL_IL_HEAD_OFFSET_v2]) #define DGL_EDGE_TAILNODE_OFFSET_v2(p) ((p)[DGL_IL_TAIL_OFFSET_v2]) #define DGL_EDGE_STATUS_v2(p) ((p)[DGL_IL_STATUS_v2]) #define DGL_EDGE_COST_v2(p) ((p)[DGL_IL_COST_v2]) #define DGL_EDGE_ID_v2(p) ((p)[DGL_IL_ID_v2]) #define DGL_EDGE_ATTR_PTR_v2(p) ((p) + DGL_IL_ATTR_v2) #define DGL_EDGE_HEADNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\ DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v2(pl)):\ DGL_EDGE_HEADNODE_OFFSET_v2(pl)) #define DGL_EDGE_TAILNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\ DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v2(pl)):\ DGL_EDGE_TAILNODE_OFFSET_v2(pl)) /* * Scan a node buffer */ #define DGL_FOREACH_NODE_v2(pgrp,pn) for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\ (pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\ (pn)+=DGL_NODE_WSIZE_v2((pgrp)->NodeAttrSize)) /* * Scan a edgeset */ #define DGL_FOREACH_EDGE_v2(pgrp,pla,pl,il)\ for((il)=0, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il);\ (il)pNodeBuffer + (o))) #define DGL_NODEBUFFER_OFFSET_v2(pgrp,p) ((dglInt32_t)((dglByte_t *)p - (dglByte_t *)(pgrp)->pNodeBuffer)) /* * Edge Buffer Utilities */ #define DGL_EDGEBUFFER_SHIFT_v2(pgrp,o) ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o))) #define DGL_EDGEBUFFER_OFFSET_v2(pgrp,pl) ((dglInt32_t)((dglByte_t *)pl - (dglByte_t *)(pgrp)->pEdgeBuffer)) int dgl_add_edge_V2(dglGraph_s * pgraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr, void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags); int dgl_unflatten_V2(dglGraph_s * pgraph); int dgl_flatten_V2(dglGraph_s * pgraph); int dgl_initialize_V2(dglGraph_s * pgraph); int dgl_release_V2(dglGraph_s * pgraph); int dgl_write_V2(dglGraph_s * pgraph, int fd); int dgl_read_V2(dglGraph_s * pgraph, int fd, int version); int dgl_sp_cache_initialize_V2(dglGraph_s * pgraph, dglSPCache_s * pCache, dglInt32_t nStart); void dgl_sp_cache_release_V2(dglGraph_s * pgraph, dglSPCache_s * pCache); int dgl_dijkstra_V2_TREE(dglGraph_s * pgraph, dglSPReport_s ** ppReport, dglInt32_t * pDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s * pCache); int dgl_dijkstra_V2_FLAT(dglGraph_s * pgraph, dglSPReport_s ** ppReport, dglInt32_t * pDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s * pCache); int dgl_dijkstra_V2(dglGraph_s * pgraph, dglSPReport_s ** ppReport, dglInt32_t * pDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s * pCache); int dgl_span_depthfirst_spanning_V2_TREE(dglGraph_s * pgraphIn, dglGraph_s * pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg); int dgl_span_depthfirst_spanning_V2_FLAT(dglGraph_s * pgraphIn, dglGraph_s * pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg); int dgl_depthfirst_spanning_V2(dglGraph_s * pgraphIn, dglGraph_s * pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg); int dgl_span_minimum_spanning_V2_TREE(dglGraph_s * pgraphIn, dglGraph_s * pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg); int dgl_span_minimum_spanning_V2_FLAT(dglGraph_s * pgraphIn, dglGraph_s * pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg); int dgl_minimum_spanning_V2(dglGraph_s * pgraphIn, dglGraph_s * pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg); int dgl_add_node_V2(dglGraph_s * pgraph, dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags); int dgl_del_node_outedge_V2(dglGraph_s * pgraph, dglInt32_t nNode, dglInt32_t nEdge); int dgl_del_node_inedge_V2(dglGraph_s * pgraph, dglInt32_t nNode, dglInt32_t nEdge); int dgl_del_node_V2(dglGraph_s * pgraph, dglInt32_t nId); dglInt32_t *dgl_get_node_V2(dglGraph_s * pgraph, dglInt32_t nId); dglInt32_t *dgl_get_edge_V2(dglGraph_s * pgraph, dglInt32_t nId); int dgl_del_edge_V2(dglGraph_s * pgraph, dglInt32_t nId); dglInt32_t *dgl_getnode_outedgeset_V2(dglGraph_s * pgraph, dglInt32_t * pnode); dglInt32_t *dgl_getnode_inedgeset_V2(dglGraph_s * pgraph, dglInt32_t * pnode); /* * Node Traversing */ int dgl_node_t_initialize_V2(dglGraph_s * pGraph, dglNodeTraverser_s * pT); void dgl_node_t_release_V2(dglNodeTraverser_s * pT); dglInt32_t *dgl_node_t_first_V2(dglNodeTraverser_s * pT); dglInt32_t *dgl_node_t_next_V2(dglNodeTraverser_s * pT); dglInt32_t *dgl_node_t_find_V2(dglNodeTraverser_s * pT, dglInt32_t nId); /* * Edgeset Traversing */ int dgl_edgeset_t_initialize_V2(dglGraph_s * pGraph, dglEdgesetTraverser_s * pTraverser, dglInt32_t * pnEdgeset); void dgl_edgeset_t_release_V2(dglEdgesetTraverser_s * pTraverser); dglInt32_t *dgl_edgeset_t_first_V2(dglEdgesetTraverser_s * pTraverser); dglInt32_t *dgl_edgeset_t_next_V2(dglEdgesetTraverser_s * pTraverser); int dgl_edge_t_initialize_V2(dglGraph_s * pGraph, dglEdgeTraverser_s * pTraverser, dglEdgePrioritizer_s * pEP); void dgl_edge_t_release_V2(dglEdgeTraverser_s * pTraverser); dglInt32_t *dgl_edge_t_first_V2(dglEdgeTraverser_s * pT); dglInt32_t *dgl_edge_t_next_V2(dglEdgeTraverser_s * pT); #endif