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