GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
graph_v1.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_v1.h"
36 #include "helpers.h"
37 
38 
39 /* Template expansion
40  */
41 #include "v1-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 "v1-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 "v1-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_V1_FLAT(pgraph, ppReport, pDistance, nStart,
77  nDestination, fnClip, pvClipArg, pCache);
78  }
79  else {
80  return dgl_dijkstra_V1_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_V1_FLAT(pgraphIn, pgraphOut,
94  nVertex, pvVisited,
95  fnClip, pvClipArg);
96  }
97  else {
98  return dgl_span_depthfirst_spanning_V1_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_V1_FLAT(pgraphIn, pgraphOut, nVertex,
111  fnClip, pvClipArg);
112  }
113  else {
114  return dgl_span_minimum_spanning_V1_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  pgraph->pEdgeTree = NULL;
130  return 0;
131 }
132 
134 {
135  pgraph->iErrno = 0;
136 
137  if (pgraph->pNodeTree)
139  if (pgraph->pEdgeTree)
141  if (pgraph->pNodeBuffer)
142  free(pgraph->pNodeBuffer);
143  if (pgraph->pEdgeBuffer)
144  free(pgraph->pEdgeBuffer);
145  if (pgraph->edgePrioritizer.pvAVL)
147  if (pgraph->nodePrioritizer.pvAVL)
149 
150  return 0;
151 }
152 
153 
154 int dgl_write_V1(dglGraph_s * pgraph, int fd)
155 {
156  long nret, cnt, tot;
157 
158  pgraph->iErrno = 0;
159 
160  if (write(fd, &pgraph->Version, 1) != 1) {
161  pgraph->iErrno = DGL_ERR_Write;
162  return -pgraph->iErrno;
163  }
164 
165  if (write(fd, &pgraph->Endian, 1) != 1) {
166  pgraph->iErrno = DGL_ERR_Write;
167  return -pgraph->iErrno;
168  }
169 
170  if (write(fd, &pgraph->NodeAttrSize, sizeof(dglInt32_t)) !=
171  sizeof(dglInt32_t)) {
172  pgraph->iErrno = DGL_ERR_Write;
173  return -pgraph->iErrno;
174  }
175 
176  if (write(fd, &pgraph->EdgeAttrSize, sizeof(dglInt32_t)) !=
177  sizeof(dglInt32_t)) {
178  pgraph->iErrno = DGL_ERR_Write;
179  return -pgraph->iErrno;
180  }
181 
182  for (cnt = 0; cnt < 16; cnt++) {
183  if (write(fd, &pgraph->aOpaqueSet[cnt], sizeof(dglInt32_t)) !=
184  sizeof(dglInt32_t)) {
185  pgraph->iErrno = DGL_ERR_Write;
186  return -pgraph->iErrno;
187  }
188  }
189 
190  if (write(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
191  pgraph->iErrno = DGL_ERR_Write;
192  return -pgraph->iErrno;
193  }
194 
195  if (write(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
196  pgraph->iErrno = DGL_ERR_Write;
197  return -pgraph->iErrno;
198  }
199 
200  if (write(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
201  pgraph->iErrno = DGL_ERR_Write;
202  return -pgraph->iErrno;
203  }
204 
205  if (write(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
206  pgraph->iErrno = DGL_ERR_Write;
207  return -pgraph->iErrno;
208  }
209 
210  if (write(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
211  pgraph->iErrno = DGL_ERR_Write;
212  return -pgraph->iErrno;
213  }
214 
215  if (write(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
216  pgraph->iErrno = DGL_ERR_Write;
217  return -pgraph->iErrno;
218  }
219 
220  if (write(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
221  sizeof(dglInt32_t)) {
222  pgraph->iErrno = DGL_ERR_Write;
223  return -pgraph->iErrno;
224  }
225 
226  if (write(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
227  sizeof(dglInt32_t)) {
228  pgraph->iErrno = DGL_ERR_Write;
229  return -pgraph->iErrno;
230  }
231 
232  for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
233  if ((nret = write(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
234  pgraph->iErrno = DGL_ERR_Write;
235  return -pgraph->iErrno;
236  }
237  }
238 
239  for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
240  if ((nret = write(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
241  pgraph->iErrno = DGL_ERR_Write;
242  return -pgraph->iErrno;
243  }
244  }
245 
246  return 0;
247 }
248 
249 
250 int dgl_read_V1(dglGraph_s * pgraph, int fd)
251 {
252  long nret, cnt, tot;
253  dglByte_t Endian;
254  dglInt32_t NodeAttrSize, EdgeAttrSize;
255  int i, cn, fSwap;
256  dglInt32_t *pn;
257 
258  if (read(fd, &Endian, 1) != 1) {
259  pgraph->iErrno = DGL_ERR_Read;
260  return -pgraph->iErrno;
261  }
262 
263  fSwap = 0;
264 #ifdef DGL_ENDIAN_BIG
265  if (Endian == DGL_ENDIAN_LITTLE)
266  fSwap = 1;
267 #else
268  if (Endian == DGL_ENDIAN_BIG)
269  fSwap = 1;
270 #endif
271 
272  if (read(fd, &NodeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
273  pgraph->iErrno = DGL_ERR_Read;
274  return -pgraph->iErrno;
275  }
276  if (fSwap)
277  dgl_swapInt32Bytes(&NodeAttrSize);
278 
279  if (read(fd, &EdgeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
280  pgraph->iErrno = DGL_ERR_Read;
281  return -pgraph->iErrno;
282  }
283  if (fSwap)
284  dgl_swapInt32Bytes(&EdgeAttrSize);
285 
286  if ((nret =
287  dglInitialize(pgraph, 1, NodeAttrSize, EdgeAttrSize, NULL)) < 0) {
288  return nret;
289  }
290 
291  for (cnt = 0; cnt < 16; cnt++) {
292  if ((nret =
293  read(fd, &pgraph->aOpaqueSet[cnt],
294  sizeof(dglInt32_t))) != sizeof(dglInt32_t)) {
295  pgraph->iErrno = DGL_ERR_Read;
296  return -pgraph->iErrno;
297  }
298  if (fSwap)
299  dgl_swapInt32Bytes(&pgraph->aOpaqueSet[cnt]);
300  }
301 
302  if (read(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
303  pgraph->iErrno = DGL_ERR_Read;
304  return -pgraph->iErrno;
305  }
306  if (fSwap)
307  dgl_swapInt64Bytes(&pgraph->nnCost);
308 
309  if (read(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
310  pgraph->iErrno = DGL_ERR_Read;
311  return -pgraph->iErrno;
312  }
313  if (fSwap)
314  dgl_swapInt32Bytes(&pgraph->cNode);
315 
316  if (read(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
317  pgraph->iErrno = DGL_ERR_Read;
318  return -pgraph->iErrno;
319  }
320  if (fSwap)
321  dgl_swapInt32Bytes(&pgraph->cHead);
322 
323  if (read(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
324  pgraph->iErrno = DGL_ERR_Read;
325  return -pgraph->iErrno;
326  }
327  if (fSwap)
328  dgl_swapInt32Bytes(&pgraph->cTail);
329 
330  if (read(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
331  pgraph->iErrno = DGL_ERR_Read;
332  return -pgraph->iErrno;
333  }
334  if (fSwap)
335  dgl_swapInt32Bytes(&pgraph->cAlone);
336 
337  if (read(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
338  pgraph->iErrno = DGL_ERR_Read;
339  return -pgraph->iErrno;
340  }
341  if (fSwap)
342  dgl_swapInt32Bytes(&pgraph->cEdge);
343 
344  if (read(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
345  sizeof(dglInt32_t)) {
346  pgraph->iErrno = DGL_ERR_Read;
347  return -pgraph->iErrno;
348  }
349  if (fSwap)
351 
352  if (read(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
353  sizeof(dglInt32_t)) {
354  pgraph->iErrno = DGL_ERR_Read;
355  return -pgraph->iErrno;
356  }
357  if (fSwap)
359 
360  if ((pgraph->pNodeBuffer = malloc(pgraph->iNodeBuffer)) == NULL) {
362  return -pgraph->iErrno;
363  }
364 
365  if ((pgraph->pEdgeBuffer = malloc(pgraph->iEdgeBuffer)) == NULL) {
366  free(pgraph->pNodeBuffer);
368  return -pgraph->iErrno;
369  }
370 
371  for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
372  if ((nret = read(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
373  free(pgraph->pNodeBuffer);
374  free(pgraph->pEdgeBuffer);
375  pgraph->iErrno = DGL_ERR_Read;
376  return -pgraph->iErrno;
377  }
378  }
379  if (fSwap) {
380  pn = (dglInt32_t *) pgraph->pNodeBuffer;
381  cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
382  for (i = 0; i < cn; i++) {
383  dgl_swapInt32Bytes(&pn[i]);
384  }
385  }
386 
387  for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
388  if ((nret = read(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
389  free(pgraph->pNodeBuffer);
390  free(pgraph->pEdgeBuffer);
391  pgraph->iErrno = DGL_ERR_Read;
392  return -pgraph->iErrno;
393  }
394  }
395  if (fSwap) {
396  pn = (dglInt32_t *) pgraph->pEdgeBuffer;
397  cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
398  for (i = 0; i < cn; i++) {
399  dgl_swapInt32Bytes(&pn[i]);
400  }
401  }
402 
403  pgraph->Flags |= 0x1; /* flat-state */
404  return 0;
405 }
dglInt32_t cEdge
Definition: graph.h:166
dglInt64_t nnCost
Definition: graph.h:167
int dgl_span_minimum_spanning_V1_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
dglInt32_t Flags
Definition: graph.h:169
dglEdgePrioritizer_s edgePrioritizer
Definition: graph.h:181
#define DGL_ERR_Write
Definition: graph.h:286
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_span_minimum_spanning_V1_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
dglInt32_t NodeAttrSize
Definition: graph.h:158
dglInt32_t iEdgeBuffer
Definition: graph.h:178
int dgl_initialize_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:120
dglNodePrioritizer_s nodePrioritizer
Definition: graph.h:182
int dgl_release_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:133
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 dgl_dijkstra_V1(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_v1.c:67
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)
int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB, void *pvParam)
Definition: tree.c:53
#define DGL_ERR_Read
Definition: graph.h:287
int iErrno
Definition: graph.h:154
#define DGL_GS_FLAT
Definition: graph.h:36
int dgl_minimum_spanning_V1(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v1.c:104
dglInt32_t aOpaqueSet[16]
Definition: graph.h:160
dglInt32_t cTail
Definition: graph.h:164
#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
void * dglTreeGetAllocator()
Definition: tree.c:422
void * pEdgeTree
Definition: graph.h:174
#define DGL_ENDIAN_LITTLE
Definition: graph.h:75
int dgl_dijkstra_V1_TREE(dglGraph_s *pgraph, dglSPReport_s **ppReport, dglInt32_t *pDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
dglInt32_t cAlone
Definition: graph.h:165
dglInt32_t cHead
Definition: graph.h:163
int dgl_dijkstra_V1_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
void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam)
Definition: tree.c:312
int dgl_depthfirst_spanning_V1(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v1.c:86
dglByte_t Version
Definition: graph.h:156
int dgl_read_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:250
dglInt32_t EdgeAttrSize
Definition: graph.h:159
int dgl_span_depthfirst_spanning_V1_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
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
int dgl_write_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:154
int dgl_span_depthfirst_spanning_V1_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)