GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-f0497c5f6c
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 #include "type.h"
32 #include "tree.h"
33 #include "graph.h"
34 #include "graph_v1.h"
35 #include "helpers.h"
36 
37 /* Template expansion
38  */
39 #include "v1-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 "v1-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 "v1-defs.h"
57 #include "sp-template.c"
58 #include "span-template.c"
59 #undef DGL_DEFINE_FLAT_PROCS
60 
61 int dgl_dijkstra_V1(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_V1_FLAT(pgraph, ppReport, pDistance, nStart,
68  nDestination, fnClip, pvClipArg, pCache);
69  }
70  else {
71  return dgl_dijkstra_V1_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_V1(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_V1_FLAT(pgraphIn, pgraphOut, nVertex,
96  fnClip, pvClipArg);
97  }
98  else {
99  return dgl_span_minimum_spanning_V1_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  pgraph->pEdgeTree = NULL;
114  return 0;
115 }
116 
118 {
119  pgraph->iErrno = 0;
120 
121  if (pgraph->pNodeTree)
123  if (pgraph->pEdgeTree)
125  if (pgraph->pNodeBuffer)
126  free(pgraph->pNodeBuffer);
127  if (pgraph->pEdgeBuffer)
128  free(pgraph->pEdgeBuffer);
129  if (pgraph->edgePrioritizer.pvAVL)
131  if (pgraph->nodePrioritizer.pvAVL)
133 
134  return 0;
135 }
136 
137 int dgl_write_V1(dglGraph_s *pgraph, int fd)
138 {
139  long nret, cnt, tot;
140 
141  pgraph->iErrno = 0;
142 
143  if (write(fd, &pgraph->Version, 1) != 1) {
144  pgraph->iErrno = DGL_ERR_Write;
145  return -pgraph->iErrno;
146  }
147 
148  if (write(fd, &pgraph->Endian, 1) != 1) {
149  pgraph->iErrno = DGL_ERR_Write;
150  return -pgraph->iErrno;
151  }
152 
153  if (write(fd, &pgraph->NodeAttrSize, sizeof(dglInt32_t)) !=
154  sizeof(dglInt32_t)) {
155  pgraph->iErrno = DGL_ERR_Write;
156  return -pgraph->iErrno;
157  }
158 
159  if (write(fd, &pgraph->EdgeAttrSize, sizeof(dglInt32_t)) !=
160  sizeof(dglInt32_t)) {
161  pgraph->iErrno = DGL_ERR_Write;
162  return -pgraph->iErrno;
163  }
164 
165  for (cnt = 0; cnt < 16; cnt++) {
166  if (write(fd, &pgraph->aOpaqueSet[cnt], sizeof(dglInt32_t)) !=
167  sizeof(dglInt32_t)) {
168  pgraph->iErrno = DGL_ERR_Write;
169  return -pgraph->iErrno;
170  }
171  }
172 
173  if (write(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
174  pgraph->iErrno = DGL_ERR_Write;
175  return -pgraph->iErrno;
176  }
177 
178  if (write(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
179  pgraph->iErrno = DGL_ERR_Write;
180  return -pgraph->iErrno;
181  }
182 
183  if (write(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
184  pgraph->iErrno = DGL_ERR_Write;
185  return -pgraph->iErrno;
186  }
187 
188  if (write(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
189  pgraph->iErrno = DGL_ERR_Write;
190  return -pgraph->iErrno;
191  }
192 
193  if (write(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
194  pgraph->iErrno = DGL_ERR_Write;
195  return -pgraph->iErrno;
196  }
197 
198  if (write(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
199  pgraph->iErrno = DGL_ERR_Write;
200  return -pgraph->iErrno;
201  }
202 
203  if (write(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
204  sizeof(dglInt32_t)) {
205  pgraph->iErrno = DGL_ERR_Write;
206  return -pgraph->iErrno;
207  }
208 
209  if (write(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
210  sizeof(dglInt32_t)) {
211  pgraph->iErrno = DGL_ERR_Write;
212  return -pgraph->iErrno;
213  }
214 
215  for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
216  if ((nret = write(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
217  pgraph->iErrno = DGL_ERR_Write;
218  return -pgraph->iErrno;
219  }
220  }
221 
222  for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
223  if ((nret = write(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
224  pgraph->iErrno = DGL_ERR_Write;
225  return -pgraph->iErrno;
226  }
227  }
228 
229  return 0;
230 }
231 
232 int dgl_read_V1(dglGraph_s *pgraph, int fd)
233 {
234  long nret, cnt, tot;
235  dglByte_t Endian;
236  dglInt32_t NodeAttrSize, EdgeAttrSize;
237  int i, cn, fSwap;
238  dglInt32_t *pn;
239 
240  if (read(fd, &Endian, 1) != 1) {
241  pgraph->iErrno = DGL_ERR_Read;
242  return -pgraph->iErrno;
243  }
244 
245  fSwap = 0;
246 #ifdef DGL_ENDIAN_BIG
247  if (Endian == DGL_ENDIAN_LITTLE)
248  fSwap = 1;
249 #else
250  if (Endian == DGL_ENDIAN_BIG)
251  fSwap = 1;
252 #endif
253 
254  if (read(fd, &NodeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
255  pgraph->iErrno = DGL_ERR_Read;
256  return -pgraph->iErrno;
257  }
258  if (fSwap)
259  dgl_swapInt32Bytes(&NodeAttrSize);
260 
261  if (read(fd, &EdgeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
262  pgraph->iErrno = DGL_ERR_Read;
263  return -pgraph->iErrno;
264  }
265  if (fSwap)
266  dgl_swapInt32Bytes(&EdgeAttrSize);
267 
268  if ((nret = dglInitialize(pgraph, 1, NodeAttrSize, EdgeAttrSize, NULL)) <
269  0) {
270  return nret;
271  }
272 
273  for (cnt = 0; cnt < 16; cnt++) {
274  if ((nret = read(fd, &pgraph->aOpaqueSet[cnt], sizeof(dglInt32_t))) !=
275  sizeof(dglInt32_t)) {
276  pgraph->iErrno = DGL_ERR_Read;
277  return -pgraph->iErrno;
278  }
279  if (fSwap)
280  dgl_swapInt32Bytes(&pgraph->aOpaqueSet[cnt]);
281  }
282 
283  if (read(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
284  pgraph->iErrno = DGL_ERR_Read;
285  return -pgraph->iErrno;
286  }
287  if (fSwap)
288  dgl_swapInt64Bytes(&pgraph->nnCost);
289 
290  if (read(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
291  pgraph->iErrno = DGL_ERR_Read;
292  return -pgraph->iErrno;
293  }
294  if (fSwap)
295  dgl_swapInt32Bytes(&pgraph->cNode);
296 
297  if (read(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
298  pgraph->iErrno = DGL_ERR_Read;
299  return -pgraph->iErrno;
300  }
301  if (fSwap)
302  dgl_swapInt32Bytes(&pgraph->cHead);
303 
304  if (read(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
305  pgraph->iErrno = DGL_ERR_Read;
306  return -pgraph->iErrno;
307  }
308  if (fSwap)
309  dgl_swapInt32Bytes(&pgraph->cTail);
310 
311  if (read(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
312  pgraph->iErrno = DGL_ERR_Read;
313  return -pgraph->iErrno;
314  }
315  if (fSwap)
316  dgl_swapInt32Bytes(&pgraph->cAlone);
317 
318  if (read(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
319  pgraph->iErrno = DGL_ERR_Read;
320  return -pgraph->iErrno;
321  }
322  if (fSwap)
323  dgl_swapInt32Bytes(&pgraph->cEdge);
324 
325  if (read(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
326  sizeof(dglInt32_t)) {
327  pgraph->iErrno = DGL_ERR_Read;
328  return -pgraph->iErrno;
329  }
330  if (fSwap)
332 
333  if (read(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
334  sizeof(dglInt32_t)) {
335  pgraph->iErrno = DGL_ERR_Read;
336  return -pgraph->iErrno;
337  }
338  if (fSwap)
340 
341  if ((pgraph->pNodeBuffer = malloc(pgraph->iNodeBuffer)) == NULL) {
343  return -pgraph->iErrno;
344  }
345 
346  if ((pgraph->pEdgeBuffer = malloc(pgraph->iEdgeBuffer)) == NULL) {
347  free(pgraph->pNodeBuffer);
349  return -pgraph->iErrno;
350  }
351 
352  for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
353  if ((nret = read(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
354  free(pgraph->pNodeBuffer);
355  free(pgraph->pEdgeBuffer);
356  pgraph->iErrno = DGL_ERR_Read;
357  return -pgraph->iErrno;
358  }
359  }
360  if (fSwap) {
361  pn = (dglInt32_t *)pgraph->pNodeBuffer;
362  cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
363  for (i = 0; i < cn; i++) {
364  dgl_swapInt32Bytes(&pn[i]);
365  }
366  }
367 
368  for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
369  if ((nret = read(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
370  free(pgraph->pNodeBuffer);
371  free(pgraph->pEdgeBuffer);
372  pgraph->iErrno = DGL_ERR_Read;
373  return -pgraph->iErrno;
374  }
375  }
376  if (fSwap) {
377  pn = (dglInt32_t *)pgraph->pEdgeBuffer;
378  cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
379  for (i = 0; i < cn; i++) {
380  dgl_swapInt32Bytes(&pn[i]);
381  }
382  }
383 
384  pgraph->Flags |= 0x1; /* flat-state */
385  return 0;
386 }
#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_initialize_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:104
int dgl_write_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:137
int dgl_read_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:232
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:76
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:61
int dgl_minimum_spanning_V1(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v1.c:90
int dgl_release_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:117
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 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)
int dgl_span_depthfirst_spanning_V1_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
int dgl_span_depthfirst_spanning_V1_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
int dgl_span_minimum_spanning_V1_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
int dgl_span_minimum_spanning_V1_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, 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
void dglTreeNodeCancel(void *pvNode, void *pvParam UNUSED)
Definition: tree.c:45
int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB, void *pvParam UNUSED)
Definition: tree.c:54
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)