GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
span-template.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 /*
24  * Build the depth-first spanning tree of 'pgraphIn' into 'pgraphOut'
25  * - pgraphOut must have been previously initialized by the caller and is returned in TREE state
26  * - I prefer using a iterative approach with a stack for 'waiting edges' instead of recursion: it's
27  * cheaper to stack 8 bytes for each edge than the whole function stack
28  * - The visited network is passed by the caller because this function can be used for two purposes:
29  * 1. generate a single spanning tree (dglDepthSpanning)
30  * 2. part of a loop for generating connected-components of the graph (dglDepthComponents)
31  */
33  dglGraph_s * pgraphOut,
34  dglInt32_t nVertex,
35  void *pvVisited,
36  dglSpanClip_fn fnClip, void *pvClipArg)
37 {
38  struct _stackItem
39  {
40  dglInt32_t *pnHead;
41  dglInt32_t *pnEdge;
42  int iWay;
43  };
44 
45  struct _stackItem stackItem;
46  struct _stackItem *pStackItem;
47 
48  dglInt32_t *pHead;
49  dglInt32_t *pTail;
50  dglInt32_t *pEdgeset;
51  dglInt32_t *pEdge;
52  long istack = 0;
53  unsigned char *pstack = NULL;
54  int nret;
55  dglSpanClipInput_s clipInput;
56  dglTreeNode_s findVisited;
58 
59 
60  if ((pHead = dglGetNode(pgraphIn, nVertex)) == NULL) {
61  pgraphIn->iErrno = DGL_ERR_HeadNodeNotFound;
62  goto dfs_error;
63  }
64 
65  /*
66  * the simplest case is when vertex node is alone or has no outgoing edges, the result
67  * of the spanning is a graph having only one node
68  */
69  if (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE ||
70  (!(DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) &&
71  DGL_NODE_STATUS(pHead) & DGL_NS_TAIL)) {
72  nret =
73  DGL_ADD_NODE_FUNC(pgraphOut, DGL_NODE_ID(pHead),
74  DGL_NODE_ATTR_PTR(pHead), 0);
75  if (nret < 0) {
76  goto dfs_error;
77  }
78  return 0;
79  }
80 
81  if ((DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) || pgraphIn->Version == 3) {
82 
83  pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
84 
85  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
86  goto dfs_error;
87  }
88  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
89  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
90  ) {
91  stackItem.pnHead = pHead;
92  stackItem.pnEdge = pEdge;
93  stackItem.iWay = 0;
94  if ((pstack =
95  dgl_mempush(pstack, &istack, sizeof(stackItem),
96  &stackItem)) == NULL) {
97  pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
98  goto dfs_error;
99  }
100  }
102 
103  if (pgraphIn->Version == 3) {
104  pEdgeset = _DGL_INEDGESET(pgraphIn, pHead);
105 
106  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
107  goto dfs_error;
108  }
109  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
110  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
111  ) {
112  if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
113  continue;
114  stackItem.pnHead = pHead;
115  stackItem.pnEdge = pEdge;
116  stackItem.iWay = 1;
117  if ((pstack =
118  dgl_mempush(pstack, &istack, sizeof(stackItem),
119  &stackItem)) == NULL) {
120  pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
121  goto dfs_error;
122  }
123  }
125  }
126 
127  if (dglTreeNodeAdd(pvVisited, DGL_NODE_ID(pHead)) == NULL) {
128  pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
129  goto dfs_error;
130  }
131  }
132 
133  while ((pStackItem =
134  (struct _stackItem *)dgl_mempop(pstack, &istack,
135  sizeof(stackItem))) != NULL) {
136  pHead = pStackItem->pnHead;
137  pEdge = pStackItem->pnEdge;
138 
139  if (pStackItem->iWay == 0)
140  pTail = _DGL_EDGE_TAILNODE(pgraphIn, pEdge);
141  else
142  pTail = _DGL_EDGE_HEADNODE(pgraphIn, pEdge);
143 
144  findVisited.nKey = DGL_NODE_ID(pTail);
145  if (avl_find(pvVisited, &findVisited)) { /* already visited */
146  continue;
147  }
148 
149  if (fnClip) {
150  clipInput.pnNodeFrom = pHead;
151  clipInput.pnEdge = pEdge;
152  clipInput.pnNodeTo = pTail;
153  if (fnClip(pgraphIn, pgraphOut, &clipInput, NULL, pvClipArg))
154  continue;
155  }
156 
157  if (dglTreeNodeAdd(pvVisited, DGL_NODE_ID(pTail)) == NULL) {
158  pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
159  goto dfs_error;
160  }
161 
162  /* add this edge */
163  nret = DGL_ADD_EDGE_FUNC(pgraphOut,
164  DGL_NODE_ID(pHead),
165  DGL_NODE_ID(pTail),
166  DGL_EDGE_COST(pEdge),
167  DGL_EDGE_ID(pEdge),
168  DGL_NODE_ATTR_PTR(pHead),
169  DGL_NODE_ATTR_PTR(pTail),
170  DGL_EDGE_ATTR_PTR(pEdge), 0);
171 
172  if (nret < 0) {
173  goto dfs_error;
174  }
175 
176  if ((DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) || pgraphIn->Version == 3) {
177 
178  pEdgeset = _DGL_OUTEDGESET(pgraphIn, pTail);
179  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
180  goto dfs_error;
181  }
182  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
183  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
184  ) {
185  stackItem.pnHead = pTail;
186  stackItem.pnEdge = pEdge;
187  stackItem.iWay = 0;
188  if ((pstack =
189  dgl_mempush(pstack, &istack, sizeof(stackItem),
190  &stackItem)) == NULL) {
191  pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
192  goto dfs_error;
193  }
194  }
196 
197  if (pgraphIn->Version == 3) {
198  pEdgeset = _DGL_INEDGESET(pgraphIn, pTail);
199  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) <
200  0) {
201  goto dfs_error;
202  }
203  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
204  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
205  ) {
206  if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
207  continue;
208  stackItem.pnHead = pTail;
209  stackItem.pnEdge = pEdge;
210  stackItem.iWay = 1;
211  if ((pstack =
212  dgl_mempush(pstack, &istack, sizeof(stackItem),
213  &stackItem)) == NULL) {
214  pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
215  goto dfs_error;
216  }
217  }
219  }
220  }
221  }
222 
223  if (pstack)
224  free(pstack);
225  return 0;
226 
227  dfs_error:
228  if (pstack)
229  free(pstack);
230  return -pgraphIn->iErrno;
231 }
232 
233 /*
234  * Use a edge prioritized, tree growing scheme (aka Prim algorithm) in order to
235  * be appliable to both undirected graphs (minimum spanning tree - MST) and
236  * digraphs (minimum arborescense tree - MAT)
237  * The vertex argument is ignored in MST (when algorithm is applied to a
238  * version 3 undirected graph).
239  */
241  dglGraph_s * pgraphOut,
242  dglInt32_t nVertex,
243  dglSpanClip_fn fnClip, void *pvClipArg)
244 {
245  dglInt32_t *pHead, *pTail, *pEdgeset, *pEdge;
246  dglHeap_s FrontEdgeHeap;
247  dglHeapData_u HeapData;
248  dglHeapNode_s HeapItem;
249  dglTreeNode_s *pPredistItem, findItem;
251  int nret;
252 
253  dglHeapInit(&FrontEdgeHeap);
254 
255  if (pgraphIn->Version == 3) { /* undirected: pick up the first node */
257 
258  DGL_NODE_T_INITIALIZE_FUNC(pgraphIn, &pT);
259  pHead = DGL_NODE_T_FIRST_FUNC(&pT);
261  }
262  else { /* directed: pick up the arborescense origin */
263  pHead = DGL_GET_NODE_FUNC(pgraphIn, nVertex);
264  }
265 
266  if (pHead == NULL) {
267  pgraphIn->iErrno = DGL_ERR_HeadNodeNotFound;
268  goto mst_error;
269  }
270 
271  if (DGL_NODE_STATUS(pHead) & DGL_NS_HEAD ||
272  DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) {
273 
274  if ((DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) ||
275  (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) ||
276  pgraphIn->Version == 3) {
278  (pgraphOut, DGL_NODE_ID(pHead), DGL_NODE_ATTR_PTR(pHead),
279  0) < 0) {
280  goto mst_error;
281  }
282 
283  if (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) {
284  dglHeapFree(&FrontEdgeHeap, NULL);
285  return 0;
286  }
287 
288  pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
289  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
290  goto mst_error;
291  }
292  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
293  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
294  ) {
295  HeapData.pv = pEdge;
296  if (dglHeapInsertMin
297  (&FrontEdgeHeap, DGL_EDGE_COST(pEdge), 0, HeapData) < 0) {
298  pgraphIn->iErrno = DGL_ERR_HeapError;
299  goto mst_error;
300  }
301  }
303  if (pgraphIn->Version == 3) {
304  pEdgeset = _DGL_INEDGESET(pgraphIn, pHead);
305  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) <
306  0) {
307  goto mst_error;
308  }
309  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
310  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
311  ) {
312  if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
313  continue;
314  HeapData.pv = pEdge;
315  if (dglHeapInsertMin
316  (&FrontEdgeHeap, DGL_EDGE_COST(pEdge), 1,
317  HeapData) < 0) {
318  pgraphIn->iErrno = DGL_ERR_HeapError;
319  goto mst_error;
320  }
321  }
323  }
324  }
325  }
326  else {
327  pgraphIn->iErrno = DGL_ERR_BadEdge;
328  goto mst_error;
329  }
330 
331  while (dglHeapExtractMin(&FrontEdgeHeap, &HeapItem) == 1) {
332  pEdge = HeapItem.value.pv;
333 
334  if (HeapItem.flags == 0) {
335  if ((pHead = _DGL_EDGE_HEADNODE(pgraphIn, pEdge)) == NULL) {
337  goto mst_error;
338  }
339  if ((pTail = _DGL_EDGE_TAILNODE(pgraphIn, pEdge)) == NULL) {
341  goto mst_error;
342  }
343  }
344  else if (pgraphIn->Version == 3) {
345  if ((pTail = _DGL_EDGE_HEADNODE(pgraphIn, pEdge)) == NULL) {
347  goto mst_error;
348  }
349  if ((pHead = _DGL_EDGE_TAILNODE(pgraphIn, pEdge)) == NULL) {
351  goto mst_error;
352  }
353  }
354  else
355  continue;
356 
357  findItem.nKey = DGL_NODE_ID(pTail);
358 
359  if ((pPredistItem =
360  avl_find(pgraphOut->pNodeTree, &findItem)) != NULL) {
361  continue;
362  }
363 
364  nret = DGL_ADD_EDGE_FUNC(pgraphOut,
365  DGL_NODE_ID(pHead),
366  DGL_NODE_ID(pTail),
367  DGL_EDGE_COST(pEdge),
368  DGL_EDGE_ID(pEdge),
369  DGL_NODE_ATTR_PTR(pHead),
370  DGL_NODE_ATTR_PTR(pTail),
371  DGL_EDGE_ATTR_PTR(pEdge), 0);
372 
373  if (nret < 0) {
374  goto mst_error;
375  }
376 
377  pHead = pTail;
378 
379  if ((DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) || pgraphIn->Version == 3) {
380  pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
381  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
382  goto mst_error;
383  }
384  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
385  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
386  ) {
387  HeapData.pv = pEdge;
388  if (dglHeapInsertMin
389  (&FrontEdgeHeap, DGL_EDGE_COST(pEdge), 0, HeapData) < 0) {
390  pgraphIn->iErrno = DGL_ERR_HeapError;
391  goto mst_error;
392  }
393  }
394  if (pgraphIn->Version == 3) {
396  pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
397  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) <
398  0) {
399  goto mst_error;
400  }
401  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
402  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
403  ) {
404  if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
405  continue;
406  HeapData.pv = pEdge;
407  if (dglHeapInsertMin
408  (&FrontEdgeHeap, DGL_EDGE_COST(pEdge), 1,
409  HeapData) < 0) {
410  pgraphIn->iErrno = DGL_ERR_HeapError;
411  goto mst_error;
412  }
413  }
415  }
416  }
417  }
418  dglHeapFree(&FrontEdgeHeap, NULL);
419  return 0;
420 
421  mst_error:
422  dglHeapFree(&FrontEdgeHeap, NULL);
423  return -pgraphIn->iErrno;
424 }
#define DGL_NS_HEAD
Definition: graph.h:60
#define DGL_NODE_ATTR_PTR
Definition: v1-defs.h:127
int DGL_EDGESET_T_INITIALIZE_FUNC(dglGraph_s *pGraph, dglEdgesetTraverser_s *pT, dglInt32_t *pnEdgeset)
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
int DGL_ADD_EDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr, void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
#define DGL_EDGE_COST
Definition: v1-defs.h:136
#define avl_find
Definition: tree.h:38
dglHeapData_u value
Definition: heap.h:39
void dglHeapFree(dglHeap_s *pheap, dglHeapCancelItem_fn pfnCancelItem)
Definition: heap.c:37
void * pNodeTree
Definition: graph.h:173
Definition: heap.h:44
long nKey
Definition: tree.h:63
#define DGL_NODE_STATUS
Definition: v1-defs.h:125
#define DGL_EDGE_ID
Definition: v1-defs.h:137
void dglHeapInit(dglHeap_s *pheap)
Definition: heap.c:29
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
dglInt32_t * pnEdge
Definition: graph.h:115
dglTreeNode_s * dglTreeNodeAdd(void *pavl, dglInt32_t nKey)
Definition: tree.c:65
#define DGL_ERR_HeadNodeNotFound
Definition: graph.h:290
int iErrno
Definition: graph.h:154
#define DGL_EDGE_STATUS(p)
Definition: v1-defs.h:135
dglInt32_t * pnNodeFrom
Definition: graph.h:114
#define DGL_ERR_HeapError
Definition: graph.h:284
dglInt32_t * DGL_GET_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nodeid)
int DGL_SPAN_MINIMUM_SPANNING_FUNC(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
#define DGL_NODE_ID
Definition: v1-defs.h:126
#define DGL_ERR_MemoryExhausted
Definition: graph.h:283
long dglInt32_t
Definition: type.h:37
int DGL_NODE_T_INITIALIZE_FUNC(dglGraph_s *pGraph, dglNodeTraverser_s *pT)
int DGL_SPAN_DEPTHFIRST_SPANNING_FUNC(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: span-template.c:32
unsigned char * dgl_mempop(unsigned char *pstack, long *istack, long size)
Definition: helpers.c:48
dglInt32_t * pnNodeTo
Definition: graph.h:116
unsigned char * dgl_mempush(unsigned char *pstack, long *istack, long size, void *pv)
Definition: helpers.c:35
#define DGL_NS_TAIL
Definition: graph.h:61
#define DGL_EDGE_ATTR_PTR
Definition: v1-defs.h:138
#define DGL_ES_DIRECTED
Definition: graph.h:68
dglInt32_t * DGL_EDGESET_T_NEXT_FUNC(dglEdgesetTraverser_s *pT)
unsigned char flags
Definition: heap.h:40
dglInt32_t * DGL_EDGESET_T_FIRST_FUNC(dglEdgesetTraverser_s *pT)
void DGL_NODE_T_RELEASE_FUNC(dglNodeTraverser_s *pT)
dglByte_t Version
Definition: graph.h:156
#define DGL_ERR_BadEdge
Definition: graph.h:292
void * pv
Definition: heap.h:27
#define DGL_ERR_UnexpectedNullPointer
Definition: graph.h:297
#define DGL_NS_ALONE
Definition: graph.h:62
int dglHeapInsertMin(dglHeap_s *pheap, long key, unsigned char flags, dglHeapData_u value)
Definition: heap.c:52
int dglHeapExtractMin(dglHeap_s *pheap, dglHeapNode_s *pnoderet)
Definition: heap.c:79
dglInt32_t * DGL_NODE_T_FIRST_FUNC(dglNodeTraverser_s *pT)
int DGL_ADD_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
void DGL_EDGESET_T_RELEASE_FUNC(dglEdgesetTraverser_s *pT)