00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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
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
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
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
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
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
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
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
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
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