GRASS GIS 7 Programmer's Manual  7.5.svn(2017)-r71793
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
graph_v2.h
Go to the documentation of this file.
1 /* LIBDGL -- a Directed Graph Library implementation
2  * Copyright (C) 2002 Roberto Micarelli
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17  */
18 
19 /*
20  * best view tabstop=4
21  */
22 
23 #ifndef _DGL_dglGraph_s_V2_H_
24 #define _DGL_dglGraph_s_V2_H_
25 
26 #ifdef DGL_STATS
27 #include <time.h>
28 #endif
29 
30 /*
31  * Node macros - addresses in a flat node
32  */
33 #define DGL_IN_NODEID_v2 0
34 #define DGL_IN_STATUS_v2 1
35 #define DGL_IN_EDGESET_OFFSET_v2 2
36 #define DGL_IN_ATTR_v2 3
37 #define DGL_IN_SIZE_v2 DGL_IN_ATTR_v2
38 
39 #define DGL_NODE_SIZEOF_v2( nattr ) (sizeof( dglInt32_t ) * DGL_IN_SIZE_v2 + (nattr) )
40 #define DGL_NODE_WSIZE_v2( nattr ) (DGL_NODE_SIZEOF_v2( nattr ) / sizeof(dglInt32_t) )
41 #define DGL_NODE_ALLOC_v2( nattr ) (malloc( DGL_NODE_SIZEOF_v2( nattr ) ) )
42 
43 #define DGL_NODE_ID_v2(p) ((p)[DGL_IN_NODEID_v2])
44 #define DGL_NODE_STATUS_v2(p) ((p)[DGL_IN_STATUS_v2])
45 #define DGL_NODE_EDGESET_OFFSET_v2(p) ((p)[DGL_IN_EDGESET_OFFSET_v2])
46 #define DGL_NODE_ATTR_PTR_v2(p) ((p) + DGL_IN_ATTR_v2)
47 
48 /*
49  * Edgeset macros - addresses in a flat edge-area
50  */
51 #define DGL_ILA_TOCNT_v2 0
52 #define DGL_ILA_SIZE_v2 1
53 #define DGL_ILA_TOARR_v2 DGL_ILA_SIZE_v2
54 
55 #define DGL_EDGESET_SIZEOF_v2(C, lattr) (sizeof( dglInt32_t ) * ((C) + 1))
56 #define DGL_EDGESET_WSIZE_v2(C, lattr) (DGL_EDGESET_SIZEOF_v2(C, lattr) / sizeof(dglInt32_t))
57 #define DGL_EDGESET_ALLOC_v2(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v2(C, lattr)))
58 #define DGL_EDGESET_REALLOC_v2(P, C, lattr) (realloc(P , DGL_EDGESET_SIZEOF_v2(C, lattr)))
59 
60 #define DGL_EDGESET_EDGECOUNT_v2(p) ((p)[DGL_ILA_TOCNT_v2])
61 #define DGL_EDGESET_EDGEARRAY_PTR_v2(p) ((p) + DGL_ILA_TOARR_v2)
62 #define DGL_EDGESET_EDGE_PTR_v2(pgrp,p,i) DGL_EDGEBUFFER_SHIFT_v2(pgrp,*((p) + DGL_ILA_TOARR_v2 + (i)))
63 
64 /*
65  * Edge macros - addresses in a flat edge
66  */
67 #define DGL_IL_HEAD_OFFSET_v2 0
68 #define DGL_IL_TAIL_OFFSET_v2 1
69 #define DGL_IL_STATUS_v2 2
70 #define DGL_IL_COST_v2 3
71 #define DGL_IL_ID_v2 4
72 #define DGL_IL_ATTR_v2 5
73 #define DGL_IL_SIZE_v2 DGL_IL_ATTR_v2
74 
75 #define DGL_EDGE_SIZEOF_v2( lattr ) (sizeof( dglInt32_t ) * DGL_IL_SIZE_v2 + (lattr))
76 #define DGL_EDGE_WSIZE_v2( lattr ) (DGL_EDGE_SIZEOF_v2( lattr ) / sizeof( dglInt32_t ))
77 #define DGL_EDGE_ALLOC_v2( lattr ) (malloc( DGL_EDGE_SIZEOF_v2( lattr ) ))
78 
79 #define DGL_EDGE_HEADNODE_OFFSET_v2(p) ((p)[DGL_IL_HEAD_OFFSET_v2])
80 #define DGL_EDGE_TAILNODE_OFFSET_v2(p) ((p)[DGL_IL_TAIL_OFFSET_v2])
81 #define DGL_EDGE_STATUS_v2(p) ((p)[DGL_IL_STATUS_v2])
82 #define DGL_EDGE_COST_v2(p) ((p)[DGL_IL_COST_v2])
83 #define DGL_EDGE_ID_v2(p) ((p)[DGL_IL_ID_v2])
84 #define DGL_EDGE_ATTR_PTR_v2(p) ((p) + DGL_IL_ATTR_v2)
85 #define DGL_EDGE_HEADNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\
86  DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v2(pl)):\
87  DGL_EDGE_HEADNODE_OFFSET_v2(pl))
88 #define DGL_EDGE_TAILNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\
89  DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v2(pl)):\
90  DGL_EDGE_TAILNODE_OFFSET_v2(pl))
91 
92 /*
93  * Scan a node buffer
94  */
95 #define DGL_FOREACH_NODE_v2(pgrp,pn) for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\
96  (pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\
97  (pn)+=DGL_NODE_WSIZE_v2((pgrp)->NodeAttrSize))
98 /*
99  * Scan a edgeset
100  */
101 #define DGL_FOREACH_EDGE_v2(pgrp,pla,pl,il)\
102  for((il)=0, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il);\
103  (il)<DGL_EDGESET_EDGECOUNT_v2(pla);\
104  (il)++, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il))
105 /*
106  * Node Buffer Utilities
107  */
108 #define DGL_NODEBUFFER_SHIFT_v2(pgrp,o) ((dglInt32_t*)((pgrp)->pNodeBuffer + (o)))
109 #define DGL_NODEBUFFER_OFFSET_v2(pgrp,p) ((dglInt32_t)((dglByte_t *)p - (dglByte_t *)(pgrp)->pNodeBuffer))
110 
111 /*
112  * Edge Buffer Utilities
113  */
114 #define DGL_EDGEBUFFER_SHIFT_v2(pgrp,o) ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o)))
115 #define DGL_EDGEBUFFER_OFFSET_v2(pgrp,pl) ((dglInt32_t)((dglByte_t *)pl - (dglByte_t *)(pgrp)->pEdgeBuffer))
116 
117 
118 
119 
120 int dgl_add_edge_V2(dglGraph_s * pgraph,
121  dglInt32_t nHead,
122  dglInt32_t nTail,
123  dglInt32_t nCost,
124  dglInt32_t nEdge,
125  void *pvHeadAttr,
126  void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags);
127 
128 int dgl_unflatten_V2(dglGraph_s * pgraph);
129 int dgl_flatten_V2(dglGraph_s * pgraph);
130 int dgl_initialize_V2(dglGraph_s * pgraph);
131 int dgl_release_V2(dglGraph_s * pgraph);
132 int dgl_write_V2(dglGraph_s * pgraph, int fd);
133 int dgl_read_V2(dglGraph_s * pgraph, int fd, int version);
134 
135 
136 int dgl_sp_cache_initialize_V2(dglGraph_s * pgraph, dglSPCache_s * pCache,
137  dglInt32_t nStart);
138 void dgl_sp_cache_release_V2(dglGraph_s * pgraph, dglSPCache_s * pCache);
139 
140 int dgl_dijkstra_V2_TREE(dglGraph_s * pgraph,
141  dglSPReport_s ** ppReport,
142  dglInt32_t * pDistance,
143  dglInt32_t nStart,
144  dglInt32_t nDestination,
145  dglSPClip_fn fnClip,
146  void *pvClipArg, dglSPCache_s * pCache);
147 int dgl_dijkstra_V2_FLAT(dglGraph_s * pgraph,
148  dglSPReport_s ** ppReport,
149  dglInt32_t * pDistance,
150  dglInt32_t nStart,
151  dglInt32_t nDestination,
152  dglSPClip_fn fnClip,
153  void *pvClipArg, dglSPCache_s * pCache);
154 int dgl_dijkstra_V2(dglGraph_s * pgraph,
155  dglSPReport_s ** ppReport,
156  dglInt32_t * pDistance,
157  dglInt32_t nStart,
158  dglInt32_t nDestination,
159  dglSPClip_fn fnClip,
160  void *pvClipArg, dglSPCache_s * pCache);
161 
162 
164  dglGraph_s * pgraphOut,
165  dglInt32_t nVertex,
166  void *pvVisited,
167  dglSpanClip_fn fnClip,
168  void *pvClipArg);
170  dglGraph_s * pgraphOut,
171  dglInt32_t nVertex,
172  void *pvVisited,
173  dglSpanClip_fn fnClip,
174  void *pvClipArg);
176  dglGraph_s * pgraphOut,
177  dglInt32_t nVertex,
178  void *pvVisited,
179  dglSpanClip_fn fnClip, void *pvClipArg);
180 
181 
183  dglGraph_s * pgraphOut,
184  dglInt32_t nVertex,
185  dglSpanClip_fn fnClip, void *pvClipArg);
187  dglGraph_s * pgraphOut,
188  dglInt32_t nVertex,
189  dglSpanClip_fn fnClip, void *pvClipArg);
190 int dgl_minimum_spanning_V2(dglGraph_s * pgraphIn,
191  dglGraph_s * pgraphOut,
192  dglInt32_t nVertex,
193  dglSpanClip_fn fnClip, void *pvClipArg);
194 
195 
196 int dgl_add_node_V2(dglGraph_s * pgraph,
197  dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags);
198 int dgl_del_node_outedge_V2(dglGraph_s * pgraph, dglInt32_t nNode,
199  dglInt32_t nEdge);
200 int dgl_del_node_inedge_V2(dglGraph_s * pgraph, dglInt32_t nNode,
201  dglInt32_t nEdge);
202 int dgl_del_node_V2(dglGraph_s * pgraph, dglInt32_t nId);
204 
206 int dgl_del_edge_V2(dglGraph_s * pgraph, dglInt32_t nId);
207 
209  dglInt32_t * pnode);
211 
212 /*
213  * Node Traversing
214  */
220 
221 
222 /*
223  * Edgeset Traversing
224  */
226  dglEdgesetTraverser_s * pTraverser,
227  dglInt32_t * pnEdgeset);
231 
232 
234  dglEdgeTraverser_s * pTraverser,
235  dglEdgePrioritizer_s * pEP);
236 void dgl_edge_t_release_V2(dglEdgeTraverser_s * pTraverser);
239 
240 
241 #endif
int dgl_del_node_outedge_V2(dglGraph_s *pgraph, dglInt32_t nNode, dglInt32_t nEdge)
dglInt32_t * dgl_node_t_next_V2(dglNodeTraverser_s *pT)
void dgl_node_t_release_V2(dglNodeTraverser_s *pT)
int dgl_span_minimum_spanning_V2_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
dglInt32_t * dgl_get_node_V2(dglGraph_s *pgraph, dglInt32_t nId)
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)
Definition: graph_v2.c:67
int dgl_release_V2(dglGraph_s *pgraph)
Definition: graph_v2.c:139
int dgl_read_V2(dglGraph_s *pgraph, int fd, int version)
Definition: graph_v2.c:256
int dgl_span_depthfirst_spanning_V2_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
dglInt32_t * dgl_getnode_outedgeset_V2(dglGraph_s *pgraph, dglInt32_t *pnode)
void dgl_edge_t_release_V2(dglEdgeTraverser_s *pTraverser)
dglInt32_t * dgl_edge_t_next_V2(dglEdgeTraverser_s *pT)
int dgl_del_node_V2(dglGraph_s *pgraph, dglInt32_t nId)
void dgl_sp_cache_release_V2(dglGraph_s *pgraph, dglSPCache_s *pCache)
dglInt32_t * dgl_node_t_find_V2(dglNodeTraverser_s *pT, dglInt32_t nId)
int dgl_sp_cache_initialize_V2(dglGraph_s *pgraph, dglSPCache_s *pCache, dglInt32_t nStart)
int dgl_node_t_initialize_V2(dglGraph_s *pGraph, dglNodeTraverser_s *pT)
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)
fd
Definition: d/range.c:69
dglInt32_t * dgl_get_edge_V2(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_write_V2(dglGraph_s *pgraph, int fd)
Definition: graph_v2.c:160
dglInt32_t * dgl_getnode_inedgeset_V2(dglGraph_s *pgraph, dglInt32_t *pnode)
int dgl_depthfirst_spanning_V2(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v2.c:86
int dgl_del_edge_V2(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_add_node_V2(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
void dgl_edgeset_t_release_V2(dglEdgesetTraverser_s *pTraverser)
long dglInt32_t
Definition: type.h:37
int dgl_flatten_V2(dglGraph_s *pgraph)
int dgl_minimum_spanning_V2(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v2.c:104
int dgl_unflatten_V2(dglGraph_s *pgraph)
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_initialize_V2(dglGraph_s *pgraph)
Definition: graph_v2.c:120
int dgl_del_node_inedge_V2(dglGraph_s *pgraph, dglInt32_t nNode, dglInt32_t nEdge)
int dgl_edgeset_t_initialize_V2(dglGraph_s *pGraph, dglEdgesetTraverser_s *pTraverser, dglInt32_t *pnEdgeset)
dglInt32_t * dgl_edgeset_t_next_V2(dglEdgesetTraverser_s *pTraverser)
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_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_edge_t_initialize_V2(dglGraph_s *pGraph, dglEdgeTraverser_s *pTraverser, dglEdgePrioritizer_s *pEP)
int dgl_span_minimum_spanning_V2_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
dglInt32_t * dgl_edge_t_first_V2(dglEdgeTraverser_s *pT)
int(* dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *)
Definition: graph.h:198
int(* dglSpanClip_fn)(dglGraph_s *, dglGraph_s *, dglSpanClipInput_s *, dglSpanClipOutput_s *, void *)
Definition: graph.h:204
dglInt32_t * dgl_node_t_first_V2(dglNodeTraverser_s *pT)
dglInt32_t * dgl_edgeset_t_first_V2(dglEdgesetTraverser_s *pTraverser)