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 __BEGIN_DECLS
00031
00032
00033
00034
00035 #define DGL_IN_NODEID_v2 0
00036 #define DGL_IN_STATUS_v2 1
00037 #define DGL_IN_EDGESET_OFFSET_v2 2
00038 #define DGL_IN_ATTR_v2 3
00039 #define DGL_IN_SIZE_v2 DGL_IN_ATTR_v2
00040
00041 #define DGL_NODE_SIZEOF_v2( nattr ) (sizeof( dglInt32_t ) * DGL_IN_SIZE_v2 + (nattr) )
00042 #define DGL_NODE_WSIZE_v2( nattr ) (DGL_NODE_SIZEOF_v2( nattr ) / sizeof(dglInt32_t) )
00043 #define DGL_NODE_ALLOC_v2( nattr ) (malloc( DGL_NODE_SIZEOF_v2( nattr ) ) )
00044
00045 #define DGL_NODE_ID_v2(p) ((p)[DGL_IN_NODEID_v2])
00046 #define DGL_NODE_STATUS_v2(p) ((p)[DGL_IN_STATUS_v2])
00047 #define DGL_NODE_EDGESET_OFFSET_v2(p) ((p)[DGL_IN_EDGESET_OFFSET_v2])
00048 #define DGL_NODE_ATTR_PTR_v2(p) ((p) + DGL_IN_ATTR_v2)
00049
00050
00051
00052
00053 #define DGL_ILA_TOCNT_v2 0
00054 #define DGL_ILA_SIZE_v2 1
00055 #define DGL_ILA_TOARR_v2 DGL_ILA_SIZE_v2
00056
00057 #define DGL_EDGESET_SIZEOF_v2(C, lattr) (sizeof( dglInt32_t ) * ((C) + 1))
00058 #define DGL_EDGESET_WSIZE_v2(C, lattr) (DGL_EDGESET_SIZEOF_v2(C, lattr) / sizeof(dglInt32_t))
00059 #define DGL_EDGESET_ALLOC_v2(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v2(C, lattr)))
00060 #define DGL_EDGESET_REALLOC_v2(P, C, lattr) (realloc(P , DGL_EDGESET_SIZEOF_v2(C, lattr)))
00061
00062 #define DGL_EDGESET_EDGECOUNT_v2(p) ((p)[DGL_ILA_TOCNT_v2])
00063 #define DGL_EDGESET_EDGEARRAY_PTR_v2(p) ((p) + DGL_ILA_TOARR_v2)
00064 #define DGL_EDGESET_EDGE_PTR_v2(pgrp,p,i) DGL_EDGEBUFFER_SHIFT_v2(pgrp,*((p) + DGL_ILA_TOARR_v2 + (i)))
00065
00066
00067
00068
00069 #define DGL_IL_HEAD_OFFSET_v2 0
00070 #define DGL_IL_TAIL_OFFSET_v2 1
00071 #define DGL_IL_STATUS_v2 2
00072 #define DGL_IL_COST_v2 3
00073 #define DGL_IL_ID_v2 4
00074 #define DGL_IL_ATTR_v2 5
00075 #define DGL_IL_SIZE_v2 DGL_IL_ATTR_v2
00076
00077 #define DGL_EDGE_SIZEOF_v2( lattr ) (sizeof( dglInt32_t ) * DGL_IL_SIZE_v2 + (lattr))
00078 #define DGL_EDGE_WSIZE_v2( lattr ) (DGL_EDGE_SIZEOF_v2( lattr ) / sizeof( dglInt32_t ))
00079 #define DGL_EDGE_ALLOC_v2( lattr ) (malloc( DGL_EDGE_SIZEOF_v2( lattr ) ))
00080
00081 #define DGL_EDGE_HEADNODE_OFFSET_v2(p) ((p)[DGL_IL_HEAD_OFFSET_v2])
00082 #define DGL_EDGE_TAILNODE_OFFSET_v2(p) ((p)[DGL_IL_TAIL_OFFSET_v2])
00083 #define DGL_EDGE_STATUS_v2(p) ((p)[DGL_IL_STATUS_v2])
00084 #define DGL_EDGE_COST_v2(p) ((p)[DGL_IL_COST_v2])
00085 #define DGL_EDGE_ID_v2(p) ((p)[DGL_IL_ID_v2])
00086 #define DGL_EDGE_ATTR_PTR_v2(p) ((p) + DGL_IL_ATTR_v2)
00087 #define DGL_EDGE_HEADNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\
00088 DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v2(pl)):\
00089 DGL_EDGE_HEADNODE_OFFSET_v2(pl))
00090 #define DGL_EDGE_TAILNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\
00091 DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v2(pl)):\
00092 DGL_EDGE_TAILNODE_OFFSET_v2(pl))
00093
00094
00095
00096
00097 #define DGL_FOREACH_NODE_v2(pgrp,pn) for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\
00098 (pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\
00099 (pn)+=DGL_NODE_WSIZE_v2((pgrp)->NodeAttrSize))
00100
00101
00102
00103 #define DGL_FOREACH_EDGE_v2(pgrp,pla,pl,il)\
00104 for((il)=0, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il);\
00105 (il)<DGL_EDGESET_EDGECOUNT_v2(pla);\
00106 (il)++, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il))
00107
00108
00109
00110 #define DGL_NODEBUFFER_SHIFT_v2(pgrp,o) ((dglInt32_t*)((pgrp)->pNodeBuffer + (o)))
00111 #define DGL_NODEBUFFER_OFFSET_v2(pgrp,p) ((dglInt32_t)p - (dglInt32_t)(pgrp)->pNodeBuffer)
00112
00113
00114
00115
00116 #define DGL_EDGEBUFFER_SHIFT_v2(pgrp,o) ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o)))
00117 #define DGL_EDGEBUFFER_OFFSET_v2(pgrp,pl) ((dglInt32_t)pl - (dglInt32_t)(pgrp)->pEdgeBuffer)
00118
00119
00120
00121
00122 int dgl_add_edge_V2 (
00123 dglGraph_s * pgraph ,
00124 dglInt32_t nHead,
00125 dglInt32_t nTail,
00126 dglInt32_t nCost,
00127 dglInt32_t nEdge,
00128 void * pvHeadAttr ,
00129 void * pvTailAttr ,
00130 void * pvEdgeAttr ,
00131 dglInt32_t nFlags
00132 );
00133
00134 int dgl_unflatten_V2( dglGraph_s * pgraph );
00135 int dgl_flatten_V2( dglGraph_s * pgraph );
00136 int dgl_initialize_V2( dglGraph_s * pgraph );
00137 int dgl_release_V2( dglGraph_s * pgraph );
00138 int dgl_write_V2( dglGraph_s * pgraph , int fd );
00139 int dgl_read_V2( dglGraph_s * pgraph , int fd , int version );
00140
00141
00142 int dgl_sp_cache_initialize_V2( dglGraph_s * pgraph, dglSPCache_s * pCache, dglInt32_t nStart );
00143 void dgl_sp_cache_release_V2( dglGraph_s * pgraph, dglSPCache_s * pCache );
00144
00145 int dgl_dijkstra_V2_TREE (
00146 dglGraph_s * pgraph ,
00147 dglSPReport_s ** ppReport ,
00148 dglInt32_t * pDistance ,
00149 dglInt32_t nStart ,
00150 dglInt32_t nDestination ,
00151 dglSPClip_fn fnClip,
00152 void * pvClipArg,
00153 dglSPCache_s * pCache
00154 );
00155 int dgl_dijkstra_V2_FLAT (
00156 dglGraph_s * pgraph ,
00157 dglSPReport_s ** ppReport ,
00158 dglInt32_t * pDistance ,
00159 dglInt32_t nStart ,
00160 dglInt32_t nDestination ,
00161 dglSPClip_fn fnClip,
00162 void * pvClipArg,
00163 dglSPCache_s * pCache
00164 );
00165 int dgl_dijkstra_V2 (
00166 dglGraph_s * pgraph ,
00167 dglSPReport_s ** ppReport ,
00168 dglInt32_t * pDistance ,
00169 dglInt32_t nStart ,
00170 dglInt32_t nDestination ,
00171 dglSPClip_fn fnClip,
00172 void * pvClipArg,
00173 dglSPCache_s * pCache
00174 );
00175
00176
00177 int dgl_span_depthfirst_spanning_V2_TREE(
00178 dglGraph_s * pgraphIn ,
00179 dglGraph_s * pgraphOut ,
00180 dglInt32_t nVertex ,
00181 void * pvVisited ,
00182 dglSpanClip_fn fnClip ,
00183 void * pvClipArg
00184 );
00185 int dgl_span_depthfirst_spanning_V2_FLAT(
00186 dglGraph_s * pgraphIn ,
00187 dglGraph_s * pgraphOut ,
00188 dglInt32_t nVertex ,
00189 void * pvVisited ,
00190 dglSpanClip_fn fnClip ,
00191 void * pvClipArg
00192 );
00193 int dgl_depthfirst_spanning_V2(
00194 dglGraph_s * pgraphIn ,
00195 dglGraph_s * pgraphOut ,
00196 dglInt32_t nVertex ,
00197 void * pvVisited ,
00198 dglSpanClip_fn fnClip ,
00199 void * pvClipArg
00200 );
00201
00202
00203 int dgl_span_minimum_spanning_V2_TREE(
00204 dglGraph_s * pgraphIn ,
00205 dglGraph_s * pgraphOut ,
00206 dglInt32_t nVertex ,
00207 dglSpanClip_fn fnClip ,
00208 void * pvClipArg
00209 );
00210 int dgl_span_minimum_spanning_V2_FLAT(
00211 dglGraph_s * pgraphIn ,
00212 dglGraph_s * pgraphOut ,
00213 dglInt32_t nVertex ,
00214 dglSpanClip_fn fnClip ,
00215 void * pvClipArg
00216 );
00217 int dgl_minimum_spanning_V2(
00218 dglGraph_s * pgraphIn ,
00219 dglGraph_s * pgraphOut ,
00220 dglInt32_t nVertex ,
00221 dglSpanClip_fn fnClip ,
00222 void * pvClipArg
00223 );
00224
00225
00226 int dgl_add_node_V2(
00227 dglGraph_s * pgraph,
00228 dglInt32_t nId,
00229 void * pvNodeAttr,
00230 dglInt32_t nFlags
00231 );
00232 int dgl_del_node_outedge_V2(dglGraph_s * pgraph, dglInt32_t nNode, dglInt32_t nEdge);
00233 int dgl_del_node_inedge_V2(dglGraph_s * pgraph, dglInt32_t nNode, dglInt32_t nEdge);
00234 int dgl_del_node_V2(
00235 dglGraph_s * pgraph,
00236 dglInt32_t nId
00237 );
00238 dglInt32_t * dgl_get_node_V2( dglGraph_s * pgraph , dglInt32_t nId );
00239
00240 dglInt32_t * dgl_get_edge_V2( dglGraph_s * pgraph , dglInt32_t nId );
00241 int dgl_del_edge_V2( dglGraph_s * pgraph , dglInt32_t nId );
00242
00243 dglInt32_t * dgl_getnode_outedgeset_V2( dglGraph_s * pgraph , dglInt32_t * pnode );
00244 dglInt32_t * dgl_getnode_inedgeset_V2( dglGraph_s * pgraph , dglInt32_t * pnode );
00245
00246
00247
00248
00249 int dgl_node_t_initialize_V2( dglGraph_s * pGraph, dglNodeTraverser_s * pT );
00250 void dgl_node_t_release_V2( dglNodeTraverser_s * pT );
00251 dglInt32_t * dgl_node_t_first_V2( dglNodeTraverser_s * pT );
00252 dglInt32_t * dgl_node_t_next_V2( dglNodeTraverser_s * pT );
00253 dglInt32_t * dgl_node_t_find_V2( dglNodeTraverser_s * pT , dglInt32_t nId );
00254
00255
00256
00257
00258
00259 int dgl_edgeset_t_initialize_V2 (
00260 dglGraph_s * pGraph ,
00261 dglEdgesetTraverser_s * pTraverser ,
00262 dglInt32_t * pnEdgeset
00263 );
00264 void dgl_edgeset_t_release_V2 ( dglEdgesetTraverser_s * pTraverser );
00265 dglInt32_t * dgl_edgeset_t_first_V2 ( dglEdgesetTraverser_s * pTraverser );
00266 dglInt32_t * dgl_edgeset_t_next_V2 ( dglEdgesetTraverser_s * pTraverser );
00267
00268
00269 int dgl_edge_t_initialize_V2 ( dglGraph_s * pGraph , dglEdgeTraverser_s * pTraverser , dglEdgePrioritizer_s * pEP );
00270 void dgl_edge_t_release_V2 ( dglEdgeTraverser_s * pTraverser );
00271 dglInt32_t * dgl_edge_t_first_V2 ( dglEdgeTraverser_s * pT );
00272 dglInt32_t * dgl_edge_t_next_V2 ( dglEdgeTraverser_s * pT );
00273
00274
00275
00276
00277 __END_DECLS
00278 #endif