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