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_V1_H_
00024 #define _DGL_GRAPH_V1_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_v1 0
00036 #define DGL_IN_STATUS_v1 1
00037 #define DGL_IN_TAIL_OFFSET_v1 2
00038 #define DGL_IN_ATTR_v1 3
00039 #define DGL_IN_SIZE_v1 DGL_IN_ATTR_v1
00040
00041 #define DGL_NODE_SIZEOF_v1( nattr ) (sizeof( dglInt32_t ) * DGL_IN_SIZE_v1 + (nattr) )
00042 #define DGL_NODE_WSIZE_v1( nattr ) (DGL_NODE_SIZEOF_v1( nattr ) / sizeof(dglInt32_t) )
00043 #define DGL_NODE_ALLOC_v1( nattr ) (malloc( DGL_NODE_SIZEOF_v1( nattr ) ) )
00044
00045 #define DGL_NODE_ID_v1(p) ((p)[DGL_IN_NODEID_v1])
00046 #define DGL_NODE_STATUS_v1(p) ((p)[DGL_IN_STATUS_v1])
00047 #define DGL_NODE_EDGESET_OFFSET_v1(p) ((p)[DGL_IN_TAIL_OFFSET_v1])
00048 #define DGL_NODE_ATTR_PTR_v1(p) ((p) + DGL_IN_ATTR_v1)
00049
00050
00051
00052
00053 #define DGL_ILA_TOCNT_v1 0
00054 #define DGL_ILA_SIZE_v1 1
00055 #define DGL_ILA_TOARR_v1 DGL_ILA_SIZE_v1
00056
00057 #define DGL_EDGESET_SIZEOF_v1(C, lattr) (sizeof( dglInt32_t ) * (DGL_ILA_SIZE_v1) + DGL_EDGE_SIZEOF_v1(lattr) * (C))
00058 #define DGL_EDGESET_WSIZE_v1(C, lattr) (DGL_EDGESET_SIZEOF_v1(C, lattr) / sizeof(dglInt32_t))
00059 #define DGL_EDGESET_ALLOC_v1(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v1(C, lattr)))
00060 #define DGL_EDGESET_REALLOC_v1(P, C, lattr) (realloc(P , DGL_EDGESET_SIZEOF_v1(C, lattr)))
00061
00062 #define DGL_EDGESET_EDGECOUNT_v1(p) ((p)[DGL_ILA_TOCNT_v1])
00063 #define DGL_EDGESET_EDGEARRAY_PTR_v1(p) ((p) + DGL_ILA_TOARR_v1)
00064 #define DGL_EDGESET_EDGE_PTR_v1(p,i,C) (((p) + DGL_ILA_TOARR_v1) + (i) * DGL_EDGE_WSIZE_v1(C))
00065
00066
00067
00068
00069 #define DGL_IL_HEAD_OFFSET_v1 0
00070 #define DGL_IL_TAIL_OFFSET_v1 1
00071 #define DGL_IL_COST_v1 2
00072 #define DGL_IL_ID_v1 3
00073 #define DGL_IL_ATTR_v1 4
00074 #define DGL_IL_SIZE_v1 DGL_IL_ATTR_v1
00075
00076 #define DGL_EDGE_SIZEOF_v1( lattr ) (sizeof( dglInt32_t ) * DGL_IL_SIZE_v1 + (lattr))
00077 #define DGL_EDGE_WSIZE_v1( lattr ) (DGL_EDGE_SIZEOF_v1( lattr ) / sizeof( dglInt32_t ))
00078 #define DGL_EDGE_ALLOC_v1( lattr ) (malloc( DGL_EDGE_SIZEOF_v1( lattr ) ))
00079
00080 #define DGL_EDGE_HEADNODE_OFFSET_v1(p) ((p)[DGL_IL_HEAD_OFFSET_v1])
00081 #define DGL_EDGE_TAILNODE_OFFSET_v1(p) ((p)[DGL_IL_TAIL_OFFSET_v1])
00082 #define DGL_EDGE_COST_v1(p) ((p)[DGL_IL_COST_v1])
00083 #define DGL_EDGE_ID_v1(p) ((p)[DGL_IL_ID_v1])
00084 #define DGL_EDGE_ATTR_PTR_v1(p) ((p) + DGL_IL_ATTR_v1)
00085 #define DGL_EDGE_HEADNODE_ID_v1(pgrp,pl) ((pgrp->Flags&1)?\
00086 DGL_NODE_ID_v1(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v1(pl)):\
00087 DGL_EDGE_HEADNODE_OFFSET_v1(pl))
00088 #define DGL_EDGE_TAILNODE_ID_v1(pgrp,pl) ((pgrp->Flags&1)?\
00089 DGL_NODE_ID_v1(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v1(pl)):\
00090 DGL_EDGE_TAILNODE_OFFSET_v1(pl))
00091
00092
00093
00094
00095 #define DGL_FOREACH_NODE_v1(pgrp,pn) for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\
00096 (pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\
00097 (pn)+=DGL_NODE_WSIZE_v1((pgrp)->NodeAttrSize))
00098
00099
00100
00101 #define DGL_FOREACH_EDGE_v1(pgrp,pla,pl) for((pl)=DGL_EDGESET_EDGEARRAY_PTR_v1(pla);\
00102 (pl)<(pla)+DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize)*DGL_EDGESET_EDGECOUNT_v1(pla);\
00103 (pl)+=DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize))
00104
00105
00106
00107 #define DGL_NODEBUFFER_SHIFT_v1(pgrp,o) ((dglInt32_t*)((pgrp)->pNodeBuffer + (o)))
00108 #define DGL_NODEBUFFER_OFFSET_v1(pgrp,p) ((dglInt32_t)p - (dglInt32_t)(pgrp)->pNodeBuffer)
00109
00110
00111
00112
00113 #define DGL_EDGEBUFFER_SHIFT_v1(pgrp,o) ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o)))
00114 #define DGL_EDGEBUFFER_OFFSET_v1(pgrp,pl) ((dglInt32_t)pl - (dglInt32_t)(pgrp)->pEdgeBuffer)
00115
00116
00117
00118
00119 int dgl_add_edge_V1 (
00120 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 ,
00127 void * pvEdgeAttr ,
00128 dglInt32_t nFlags
00129 );
00130
00131 int dgl_unflatten_V1( dglGraph_s * pgraph );
00132 int dgl_flatten_V1( dglGraph_s * pgraph );
00133 int dgl_initialize_V1( dglGraph_s * pgraph );
00134 int dgl_release_V1( dglGraph_s * pgraph );
00135 int dgl_write_V1( dglGraph_s * pgraph , int fd );
00136 int dgl_read_V1( dglGraph_s * pgraph , int fd );
00137
00138
00139 int dgl_sp_cache_initialize_V1( dglGraph_s * pgraph, dglSPCache_s * pCache, dglInt32_t nStart );
00140 void dgl_sp_cache_release_V1( dglGraph_s * pgraph, dglSPCache_s * pCache );
00141
00142 int dgl_dijkstra_V1_TREE (
00143 dglGraph_s * pgraph ,
00144 dglSPReport_s ** ppReport ,
00145 dglInt32_t * pDistance ,
00146 dglInt32_t nStart ,
00147 dglInt32_t nDestination ,
00148 dglSPClip_fn fnClip,
00149 void * pvClipArg,
00150 dglSPCache_s * pCache
00151 );
00152 int dgl_dijkstra_V1_FLAT (
00153 dglGraph_s * pgraph ,
00154 dglSPReport_s ** ppReport ,
00155 dglInt32_t * pDistance ,
00156 dglInt32_t nStart ,
00157 dglInt32_t nDestination ,
00158 dglSPClip_fn fnClip,
00159 void * pvClipArg,
00160 dglSPCache_s * pCache
00161 );
00162 int dgl_dijkstra_V1 (
00163 dglGraph_s * pgraph ,
00164 dglSPReport_s ** ppReport ,
00165 dglInt32_t * pDistance ,
00166 dglInt32_t nStart ,
00167 dglInt32_t nDestination ,
00168 dglSPClip_fn fnClip,
00169 void * pvClipArg,
00170 dglSPCache_s * pCache
00171 );
00172
00173
00174 int dgl_span_depthfirst_spanning_V1_TREE(
00175 dglGraph_s * pgraphIn ,
00176 dglGraph_s * pgraphOut ,
00177 dglInt32_t nVertex ,
00178 void * pvVisited ,
00179 dglSpanClip_fn fnClip ,
00180 void * pvClipArg
00181 );
00182 int dgl_span_depthfirst_spanning_V1_FLAT(
00183 dglGraph_s * pgraphIn ,
00184 dglGraph_s * pgraphOut ,
00185 dglInt32_t nVertex ,
00186 void * pvVisited ,
00187 dglSpanClip_fn fnClip ,
00188 void * pvClipArg
00189 );
00190 int dgl_depthfirst_spanning_V1(
00191 dglGraph_s * pgraphIn ,
00192 dglGraph_s * pgraphOut ,
00193 dglInt32_t nVertex ,
00194 void * pvVisited ,
00195 dglSpanClip_fn fnClip ,
00196 void * pvClipArg
00197 );
00198
00199
00200 int dgl_span_minimum_spanning_V1_TREE(
00201 dglGraph_s * pgraphIn ,
00202 dglGraph_s * pgraphOut ,
00203 dglInt32_t nVertex ,
00204 dglSpanClip_fn fnClip ,
00205 void * pvClipArg
00206 );
00207 int dgl_span_minimum_spanning_V1_FLAT(
00208 dglGraph_s * pgraphIn ,
00209 dglGraph_s * pgraphOut ,
00210 dglInt32_t nVertex ,
00211 dglSpanClip_fn fnClip ,
00212 void * pvClipArg
00213 );
00214 int dgl_minimum_spanning_V1(
00215 dglGraph_s * pgraphIn ,
00216 dglGraph_s * pgraphOut ,
00217 dglInt32_t nVertex ,
00218 dglSpanClip_fn fnClip ,
00219 void * pvClipArg
00220 );
00221
00222
00223 int dgl_add_node_V1(
00224 dglGraph_s * pgraph,
00225 dglInt32_t nId,
00226 void * pvNodeAttr,
00227 dglInt32_t nFlags
00228 );
00229 int dgl_del_node_V1(
00230 dglGraph_s * pgraph,
00231 dglInt32_t nId
00232 );
00233 dglInt32_t * dgl_get_node_V1( dglGraph_s * pgraph , dglInt32_t nId );
00234
00235 dglInt32_t * dgl_get_edge_V1( dglGraph_s * pgraph , dglInt32_t nId );
00236 int dgl_del_edge_V1( dglGraph_s * pgraph , dglInt32_t nId );
00237
00238 dglInt32_t * dgl_getnode_outedgeset_V1( dglGraph_s * pgraph , dglInt32_t * pnode );
00239
00240
00241
00242
00243 int dgl_node_t_initialize_V1( dglGraph_s * pGraph, dglNodeTraverser_s * pT );
00244 void dgl_node_t_release_V1( dglNodeTraverser_s * pT );
00245 dglInt32_t * dgl_node_t_first_V1( dglNodeTraverser_s * pT );
00246 dglInt32_t * dgl_node_t_next_V1( dglNodeTraverser_s * pT );
00247 dglInt32_t * dgl_node_t_find_V1( dglNodeTraverser_s * pT , dglInt32_t nId );
00248
00249
00250
00251
00252
00253 int dgl_edgeset_t_initialize_V1 (
00254 dglGraph_s * pGraph ,
00255 dglEdgesetTraverser_s * pTraverser ,
00256 dglInt32_t * pnEdgeset
00257 );
00258 void dgl_edgeset_t_release_V1 ( dglEdgesetTraverser_s * pTraverser );
00259 dglInt32_t * dgl_edgeset_t_first_V1 ( dglEdgesetTraverser_s * pTraverser );
00260 dglInt32_t * dgl_edgeset_t_next_V1 ( dglEdgesetTraverser_s * pTraverser );
00261
00262
00263 int dgl_edge_t_initialize_V1 ( dglGraph_s * pGraph , dglEdgeTraverser_s * pTraverser , dglEdgePrioritizer_s * pEP );
00264 void dgl_edge_t_release_V1 ( dglEdgeTraverser_s * pTraverser );
00265 dglInt32_t * dgl_edge_t_first_V1 ( dglEdgeTraverser_s * pT );
00266 dglInt32_t * dgl_edge_t_next_V1 ( dglEdgeTraverser_s * pT );
00267
00268
00269
00270
00271 __END_DECLS
00272 #endif