GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
graph_v2.c
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 with tabstop=4
21  */
22 
23 #include <stdio.h>
24 #include <string.h>
25 #include <sys/types.h>
26 #include <sys/stat.h>
27 #include <unistd.h>
28 #include <stdlib.h>
29 #include <errno.h>
30 
31 
32 #include "type.h"
33 #include "tree.h"
34 #include "graph.h"
35 #include "graph_v2.h"
36 #include "helpers.h"
37 
38 
39 /* Template expansion
40  */
41 #include "v2-defs.h"
42 #include "sp-template.c"
43 #include "nodemgmt-template.c"
44 #include "edgemgmt-template.c"
45 #include "misc-template.c"
46 
47 
48 /* algorithms for TREE state
49  */
50 #define DGL_DEFINE_TREE_PROCS 1
51 #include "v2-defs.h"
52 #include "sp-template.c"
53 #include "span-template.c"
54 #undef DGL_DEFINE_TREE_PROCS
55 
56 
57 /* algorithms for FLAT state
58  */
59 #define DGL_DEFINE_FLAT_PROCS 1
60 #include "v2-defs.h"
61 #include "sp-template.c"
62 #include "span-template.c"
63 #undef DGL_DEFINE_FLAT_PROCS
64 
65 
66 
68  dglSPReport_s ** ppReport,
69  dglInt32_t * pDistance,
70  dglInt32_t nStart,
71  dglInt32_t nDestination,
72  dglSPClip_fn fnClip,
73  void *pvClipArg, dglSPCache_s * pCache)
74 {
75  if (pgraph->Flags & DGL_GS_FLAT) {
76  return dgl_dijkstra_V2_FLAT(pgraph, ppReport, pDistance, nStart,
77  nDestination, fnClip, pvClipArg, pCache);
78  }
79  else {
80  return dgl_dijkstra_V2_TREE(pgraph, ppReport, pDistance, nStart,
81  nDestination, fnClip, pvClipArg, pCache);
82  }
83 }
84 
85 
87  dglGraph_s * pgraphOut,
88  dglInt32_t nVertex,
89  void *pvVisited,
90  dglSpanClip_fn fnClip, void *pvClipArg)
91 {
92  if (pgraphIn->Flags & DGL_GS_FLAT) {
93  return dgl_span_depthfirst_spanning_V2_FLAT(pgraphIn, pgraphOut,
94  nVertex, pvVisited,
95  fnClip, pvClipArg);
96  }
97  else {
98  return dgl_span_depthfirst_spanning_V2_TREE(pgraphIn, pgraphOut,
99  nVertex, pvVisited,
100  fnClip, pvClipArg);
101  }
102 }
103 
105  dglGraph_s * pgraphOut,
106  dglInt32_t nVertex,
107  dglSpanClip_fn fnClip, void *pvClipArg)
108 {
109  if (pgraphIn->Flags & DGL_GS_FLAT) {
110  return dgl_span_minimum_spanning_V2_FLAT(pgraphIn, pgraphOut, nVertex,
111  fnClip, pvClipArg);
112  }
113  else {
114  return dgl_span_minimum_spanning_V2_TREE(pgraphIn, pgraphOut, nVertex,
115  fnClip, pvClipArg);
116  }
117 }
118 
119 
121 {
122  if (pgraph->pNodeTree == NULL)
123  pgraph->pNodeTree =
125  if (pgraph->pNodeTree == NULL) {
127  return -pgraph->iErrno;
128  }
129  if (pgraph->pEdgeTree == NULL)
130  pgraph->pEdgeTree =
132  if (pgraph->pEdgeTree == NULL) {
134  return -pgraph->iErrno;
135  }
136  return 0;
137 }
138 
140 {
141  pgraph->iErrno = 0;
142 
143  if (pgraph->pNodeTree)
145  if (pgraph->pEdgeTree)
147  if (pgraph->pNodeBuffer)
148  free(pgraph->pNodeBuffer);
149  if (pgraph->pEdgeBuffer)
150  free(pgraph->pEdgeBuffer);
151  if (pgraph->edgePrioritizer.pvAVL)
153  if (pgraph->nodePrioritizer.pvAVL)
155 
156  return 0;
157 }
158 
159 
160 int dgl_write_V2(dglGraph_s * pgraph, int fd)
161 {
162  long nret, cnt, tot;
163 
164  pgraph->iErrno = 0;
165 
166  if (write(fd, &pgraph->Version, 1) != 1) {
167  pgraph->iErrno = DGL_ERR_Write;
168  return -pgraph->iErrno;
169  }
170 
171  if (write(fd, &pgraph->Endian, 1) != 1) {
172  pgraph->iErrno = DGL_ERR_Write;
173  return -pgraph->iErrno;
174  }
175 
176  if (write(fd, &pgraph->NodeAttrSize, sizeof(dglInt32_t)) !=
177  sizeof(dglInt32_t)) {
178  pgraph->iErrno = DGL_ERR_Write;
179  return -pgraph->iErrno;
180  }
181 
182  if (write(fd, &pgraph->EdgeAttrSize, sizeof(dglInt32_t)) !=
183  sizeof(dglInt32_t)) {
184  pgraph->iErrno = DGL_ERR_Write;
185  return -pgraph->iErrno;
186  }
187 
188  for (cnt = 0; cnt < 16; cnt++) {
189  if (write(fd, &pgraph->aOpaqueSet[cnt], sizeof(dglInt32_t)) !=
190  sizeof(dglInt32_t)) {
191  pgraph->iErrno = DGL_ERR_Write;
192  return -pgraph->iErrno;
193  }
194  }
195 
196  if (write(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
197  pgraph->iErrno = DGL_ERR_Write;
198  return -pgraph->iErrno;
199  }
200 
201  if (write(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
202  pgraph->iErrno = DGL_ERR_Write;
203  return -pgraph->iErrno;
204  }
205 
206  if (write(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
207  pgraph->iErrno = DGL_ERR_Write;
208  return -pgraph->iErrno;
209  }
210 
211  if (write(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
212  pgraph->iErrno = DGL_ERR_Write;
213  return -pgraph->iErrno;
214  }
215 
216  if (write(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
217  pgraph->iErrno = DGL_ERR_Write;
218  return -pgraph->iErrno;
219  }
220 
221  if (write(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
222  pgraph->iErrno = DGL_ERR_Write;
223  return -pgraph->iErrno;
224  }
225 
226  if (write(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
227  sizeof(dglInt32_t)) {
228  pgraph->iErrno = DGL_ERR_Write;
229  return -pgraph->iErrno;
230  }
231 
232  if (write(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
233  sizeof(dglInt32_t)) {
234  pgraph->iErrno = DGL_ERR_Write;
235  return -pgraph->iErrno;
236  }
237 
238  for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
239  if ((nret = write(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
240  pgraph->iErrno = DGL_ERR_Write;
241  return -pgraph->iErrno;
242  }
243  }
244 
245  for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
246  if ((nret = write(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
247  pgraph->iErrno = DGL_ERR_Write;
248  return -pgraph->iErrno;
249  }
250  }
251 
252  return 0;
253 }
254 
255 
256 int dgl_read_V2(dglGraph_s * pgraph, int fd, int version)
257 {
258  long nret, cnt, tot;
259  dglByte_t Endian;
260  dglInt32_t NodeAttrSize, EdgeAttrSize;
261  int i, cn, fSwap;
262  dglInt32_t *pn;
263 
264  if (read(fd, &Endian, 1) != 1) {
265  pgraph->iErrno = DGL_ERR_Read;
266  return -pgraph->iErrno;
267  }
268 
269  fSwap = 0;
270 #ifdef DGL_ENDIAN_BIG
271  if (Endian == DGL_ENDIAN_LITTLE)
272  fSwap = 1;
273 #else
274  if (Endian == DGL_ENDIAN_BIG)
275  fSwap = 1;
276 #endif
277 
278  if (read(fd, &NodeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
279  pgraph->iErrno = DGL_ERR_Read;
280  return -pgraph->iErrno;
281  }
282  if (fSwap)
283  dgl_swapInt32Bytes(&NodeAttrSize);
284 
285  if (read(fd, &EdgeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
286  pgraph->iErrno = DGL_ERR_Read;
287  return -pgraph->iErrno;
288  }
289  if (fSwap)
290  dgl_swapInt32Bytes(&EdgeAttrSize);
291 
292  if ((nret =
293  dglInitialize(pgraph, version, NodeAttrSize, EdgeAttrSize,
294  NULL)) < 0) {
295  return nret;
296  }
297 
298  for (cnt = 0; cnt < 16; cnt++) {
299  if ((nret =
300  read(fd, &pgraph->aOpaqueSet[cnt],
301  sizeof(dglInt32_t))) != sizeof(dglInt32_t)) {
302  pgraph->iErrno = DGL_ERR_Read;
303  return -pgraph->iErrno;
304  }
305  if (fSwap)
306  dgl_swapInt32Bytes(&pgraph->aOpaqueSet[cnt]);
307  }
308 
309  if (read(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
310  pgraph->iErrno = DGL_ERR_Read;
311  return -pgraph->iErrno;
312  }
313  if (fSwap)
314  dgl_swapInt64Bytes(&pgraph->nnCost);
315 
316  if (read(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
317  pgraph->iErrno = DGL_ERR_Read;
318  return -pgraph->iErrno;
319  }
320  if (fSwap)
321  dgl_swapInt32Bytes(&pgraph->cNode);
322 
323  if (read(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
324  pgraph->iErrno = DGL_ERR_Read;
325  return -pgraph->iErrno;
326  }
327  if (fSwap)
328  dgl_swapInt32Bytes(&pgraph->cHead);
329 
330  if (read(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
331  pgraph->iErrno = DGL_ERR_Read;
332  return -pgraph->iErrno;
333  }
334  if (fSwap)
335  dgl_swapInt32Bytes(&pgraph->cTail);
336 
337  if (read(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
338  pgraph->iErrno = DGL_ERR_Read;
339  return -pgraph->iErrno;
340  }
341  if (fSwap)
342  dgl_swapInt32Bytes(&pgraph->cAlone);
343 
344  if (read(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
345  pgraph->iErrno = DGL_ERR_Read;
346  return -pgraph->iErrno;
347  }
348  if (fSwap)
349  dgl_swapInt32Bytes(&pgraph->cEdge);
350 
351  if (read(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
352  sizeof(dglInt32_t)) {
353  pgraph->iErrno = DGL_ERR_Read;
354  return -pgraph->iErrno;
355  }
356  if (fSwap)
358 
359  if (read(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
360  sizeof(dglInt32_t)) {
361  pgraph->iErrno = DGL_ERR_Read;
362  return -pgraph->iErrno;
363  }
364  if (fSwap)
366 
367  if ((pgraph->pNodeBuffer = malloc(pgraph->iNodeBuffer)) == NULL) {
369  return -pgraph->iErrno;
370  }
371 
372  if ((pgraph->pEdgeBuffer = malloc(pgraph->iEdgeBuffer)) == NULL) {
373  free(pgraph->pNodeBuffer);
375  return -pgraph->iErrno;
376  }
377 
378  for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
379  if ((nret = read(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
380  free(pgraph->pNodeBuffer);
381  free(pgraph->pEdgeBuffer);
382  pgraph->iErrno = DGL_ERR_Read;
383  return -pgraph->iErrno;
384  }
385  }
386  if (fSwap) {
387  pn = (dglInt32_t *) pgraph->pNodeBuffer;
388  cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
389  for (i = 0; i < cn; i++) {
390  dgl_swapInt32Bytes(&pn[i]);
391  }
392  }
393 
394  for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
395  if ((nret = read(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
396  free(pgraph->pNodeBuffer);
397  free(pgraph->pEdgeBuffer);
398  pgraph->iErrno = DGL_ERR_Read;
399  return -pgraph->iErrno;
400  }
401  }
402  if (fSwap) {
403  pn = (dglInt32_t *) pgraph->pEdgeBuffer;
404  cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
405  for (i = 0; i < cn; i++) {
406  dgl_swapInt32Bytes(&pn[i]);
407  }
408  }
409 
410  pgraph->Flags |= 0x1; /* flat-state */
411  return 0;
412 }
int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB, void *pvParam)
Definition: tree.c:162
dglInt32_t cEdge
Definition: graph.h:166
dglInt64_t nnCost
Definition: graph.h:167
dglInt32_t Flags
Definition: graph.h:169
int dgl_span_minimum_spanning_V2_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
dglEdgePrioritizer_s edgePrioritizer
Definition: graph.h:181
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
#define DGL_ERR_Write
Definition: graph.h:286
int dgl_release_V2(dglGraph_s *pgraph)
Definition: graph_v2.c:139
void dglTreeNodeCancel(void *pvNode, void *pvParam)
Definition: tree.c:44
unsigned char dglByte_t
Definition: type.h:36
void dglTreeEdgeCancel(void *pvEdge, void *pvParam)
Definition: tree.c:155
#define avl_destroy
Definition: tree.h:33
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 NodeAttrSize
Definition: graph.h:158
dglInt32_t iEdgeBuffer
Definition: graph.h:178
dglNodePrioritizer_s nodePrioritizer
Definition: graph.h:182
void * pNodeTree
Definition: graph.h:173
void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam)
Definition: tree.c:364
void dgl_swapInt64Bytes(dglInt64_t *pn)
Definition: helpers.c:68
int(* dglSpanClip_fn)(dglGraph_s *, dglGraph_s *, dglSpanClipInput_s *, dglSpanClipOutput_s *, void *)
Definition: graph.h:204
void free(void *)
#define NULL
Definition: ccmath.h:32
#define DGL_ENDIAN_BIG
Definition: graph.h:74
int dglInitialize(dglGraph_s *pGraph, dglByte_t Version, dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, dglInt32_t *pOpaqueSet)
dglInt32_t cNode
Definition: graph.h:162
void * malloc(YYSIZE_T)
#define DGL_ERR_Read
Definition: graph.h:287
int dgl_write_V2(dglGraph_s *pgraph, int fd)
Definition: graph_v2.c:160
int iErrno
Definition: graph.h:154
#define DGL_GS_FLAT
Definition: graph.h:36
dglInt32_t aOpaqueSet[16]
Definition: graph.h:160
int dglTreeNode2Compare(const void *pvNode2A, const void *pvNode2B, void *pvParam)
Definition: tree.c:109
dglInt32_t cTail
Definition: graph.h:164
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
#define avl_create
Definition: tree.h:31
void dgl_swapInt32Bytes(dglInt32_t *pn)
Definition: helpers.c:55
#define DGL_ERR_MemoryExhausted
Definition: graph.h:283
long long dglInt64_t
Definition: type.h:38
long dglInt32_t
Definition: type.h:37
int dgl_minimum_spanning_V2(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v2.c:104
void * dglTreeGetAllocator()
Definition: tree.c:422
void * pEdgeTree
Definition: graph.h:174
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
#define DGL_ENDIAN_LITTLE
Definition: graph.h:75
dglInt32_t cAlone
Definition: graph.h:165
dglInt32_t cHead
Definition: graph.h:163
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(* dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *)
Definition: graph.h:198
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)
void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam)
Definition: tree.c:312
int dgl_span_minimum_spanning_V2_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
dglByte_t Version
Definition: graph.h:156
dglInt32_t EdgeAttrSize
Definition: graph.h:159
dglByte_t Endian
Definition: graph.h:157
dglInt32_t iNodeBuffer
Definition: graph.h:176
dglByte_t * pEdgeBuffer
Definition: graph.h:177
dglByte_t * pNodeBuffer
Definition: graph.h:175