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