GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-1d42e580e2
edgemgmt-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  * Add edge can be performed on TREE state graph. If the state is FLAT
27  * return BadOnFlatGraph error.
28  */
30  dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr,
31  void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
32 {
33  dglInt32_t *pHead;
34  dglInt32_t *pTail;
35  dglInt32_t *pEdgeset;
36  dglInt32_t *pEdge;
37  DGL_T_NODEITEM_TYPE *pHeadNodeItem;
38  DGL_T_NODEITEM_TYPE *pTailNodeItem;
39 
40 #if defined(_DGL_V2)
41  dglInt32_t *pinEdgeset;
42  dglTreeEdge_s *pEdgeItem;
43  /* dglTreeEdge_s findEdge; */
44 #endif
45 
46  if (pgraph->Flags & DGL_GS_FLAT) {
48  return -pgraph->iErrno;
49  }
50 
51 #ifdef DGL_STATS
52  {
53  clock_t clk = clock();
54 #endif
55 
56  if ((pHeadNodeItem = DGL_T_NODEITEM_Add(pgraph->pNodeTree, nHead)) ==
57  NULL ||
58  (pTailNodeItem = DGL_T_NODEITEM_Add(pgraph->pNodeTree, nTail)) ==
59  NULL) {
61  return -pgraph->iErrno;
62  }
63 
64 #ifdef DGL_STATS
65  pgraph->clkNodeTree += clock() - clk;
66  pgraph->cNodeTree++;
67  pgraph->cNodeTree++;
68  }
69 #endif
70 
71  if (DGL_T_NODEITEM_NodePTR(pHeadNodeItem) == NULL) {
72  if ((pHead = DGL_NODE_ALLOC(pgraph->NodeAttrSize)) == NULL) {
74  return -1;
75  }
76  DGL_NODE_STATUS(pHead) = 0;
77  DGL_T_NODEITEM_Set_NodePTR(pHeadNodeItem, pHead);
78  pgraph->cNode++;
79  pgraph->cHead++;
80  }
81  else {
82  pHead = DGL_T_NODEITEM_NodePTR(pHeadNodeItem);
83  if (!(DGL_NODE_STATUS(pHead) & DGL_NS_HEAD))
84  pgraph->cHead++;
85  }
86 
87  if (DGL_T_NODEITEM_NodePTR(pTailNodeItem) == NULL) {
88  if ((pTail = DGL_NODE_ALLOC(pgraph->NodeAttrSize)) == NULL) {
90  return -pgraph->iErrno;
91  }
92  DGL_NODE_STATUS(pTail) = 0;
93  DGL_T_NODEITEM_Set_NodePTR(pTailNodeItem, pTail);
94  pgraph->cNode++;
95  pgraph->cTail++;
96  }
97  else {
98  pTail = DGL_T_NODEITEM_NodePTR(pTailNodeItem);
99  if (!(DGL_NODE_STATUS(pTail) & DGL_NS_TAIL))
100  pgraph->cTail++;
101  }
102 
103  DGL_NODE_STATUS(pHead) |= DGL_NS_HEAD;
104  DGL_NODE_STATUS(pTail) |= DGL_NS_TAIL;
105 
106  if (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) {
107  DGL_NODE_STATUS(pHead) &= ~DGL_NS_ALONE;
108  pgraph->cAlone--;
109  }
110 
111  if (DGL_NODE_STATUS(pTail) & DGL_NS_ALONE) {
112  DGL_NODE_STATUS(pTail) &= ~DGL_NS_ALONE;
113  pgraph->cAlone--;
114  }
115 
116  DGL_NODE_ID(pHead) = nHead;
117  DGL_NODE_ID(pTail) = nTail;
118 
119  DGL_NODE_EDGESET_OFFSET(pHead) = -1;
120  DGL_NODE_EDGESET_OFFSET(pTail) = -1;
121 
122  if (pvHeadAttr && pgraph->NodeAttrSize) {
123  memcpy(DGL_NODE_ATTR_PTR(pHead), pvHeadAttr, pgraph->NodeAttrSize);
124  }
125 
126  if (pvTailAttr && pgraph->NodeAttrSize) {
127  memcpy(DGL_NODE_ATTR_PTR(pTail), pvTailAttr, pgraph->NodeAttrSize);
128  }
129 
130  /*
131  if ( DGL_T_NODEITEM_OutEdgesetPTR(pTailNodeItem) == NULL )
132  {
133  pEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize );
134  if ( pEdgeset == NULL ) {
135  pgraph->iErrno = DGL_ERR_MemoryExhausted;
136  return -pgraph->iErrno;
137  }
138  DGL_EDGESET_EDGECOUNT(pEdgeset) = 0;
139  DGL_T_NODEITEM_Set_OutEdgesetPTR(pTailNodeItem,pEdgeset);
140  }
141  */
142 
143  if ((pEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pHeadNodeItem)) == NULL) {
144  pEdgeset = DGL_EDGESET_ALLOC(1, pgraph->EdgeAttrSize);
145  if (pEdgeset == NULL) {
147  return -pgraph->iErrno;
148  }
149  DGL_EDGESET_EDGECOUNT(pEdgeset) = 0;
150  DGL_T_NODEITEM_Set_OutEdgesetPTR(pHeadNodeItem, pEdgeset);
151  }
152  else {
153  pEdgeset =
154  DGL_EDGESET_REALLOC(pEdgeset, DGL_EDGESET_EDGECOUNT(pEdgeset) + 1,
155  pgraph->EdgeAttrSize);
156 
157  if (pEdgeset == NULL) {
159  return -pgraph->iErrno;
160  }
161  DGL_T_NODEITEM_Set_OutEdgesetPTR(pHeadNodeItem, pEdgeset);
162  }
163 
164 #if defined(_DGL_V2)
165  /*
166  if ( DGL_T_NODEITEM_InEdgesetPTR(pHeadNodeItem) == NULL )
167  {
168  pinEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize );
169  if ( pinEdgeset == NULL ) {
170  pgraph->iErrno = DGL_ERR_MemoryExhausted;
171  return -pgraph->iErrno;
172  }
173  DGL_EDGESET_EDGECOUNT(pinEdgeset) = 0;
174  DGL_T_NODEITEM_Set_InEdgesetPTR(pHeadNodeItem,pinEdgeset);
175  }
176  */
177 
178  if ((pinEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pTailNodeItem)) == NULL) {
179  pinEdgeset = DGL_EDGESET_ALLOC(1, pgraph->EdgeAttrSize);
180  if (pinEdgeset == NULL) {
182  return -pgraph->iErrno;
183  }
184  DGL_EDGESET_EDGECOUNT(pinEdgeset) = 0;
185  DGL_T_NODEITEM_Set_InEdgesetPTR(pTailNodeItem, pinEdgeset);
186  }
187  else {
188  pinEdgeset = DGL_EDGESET_REALLOC(pinEdgeset,
189  DGL_EDGESET_EDGECOUNT(pinEdgeset) + 1,
190  pgraph->EdgeAttrSize);
191 
192  if (pinEdgeset == NULL) {
194  return -pgraph->iErrno;
195  }
196  DGL_T_NODEITEM_Set_InEdgesetPTR(pTailNodeItem, pinEdgeset);
197  }
198 
199  /*
200  * Set the edge-tree
201  */
202  /* findEdge.nKey = nEdge; */
203 
204  if ((pEdgeItem = dglTreeEdgeAdd(pgraph->pEdgeTree, nEdge)) == NULL) {
206  return -pgraph->iErrno;
207  }
208  if (pEdgeItem->pv) {
210  return -pgraph->iErrno;
211  }
212  if ((pEdgeItem->pv = DGL_EDGE_ALLOC(pgraph->EdgeAttrSize)) == NULL) {
214  return -pgraph->iErrno;
215  }
216 
217  /*
218  * assign edge id
219  */
220  pEdgeset[DGL_EDGESET_EDGECOUNT(pEdgeset) + 1] = nEdge;
221  pinEdgeset[DGL_EDGESET_EDGECOUNT(pinEdgeset) + 1] = nEdge;
222  ++DGL_EDGESET_EDGECOUNT(pEdgeset);
223  ++DGL_EDGESET_EDGECOUNT(pinEdgeset);
224 
225  /*
226  printf( "add edge: node %ld(%ld,%ld) -> %ld(%ld,%ld)\n",
227  DGL_NODE_ID(pHead), DGL_EDGESET_EDGECOUNT(pEdgeset),0,
228  DGL_NODE_ID(pTail), 0,DGL_EDGESET_EDGECOUNT(pinEdgeset));
229  */
230 
231  pEdge = pEdgeItem->pv;
232 #endif
233 
234 #if defined(_DGL_V1)
235  pEdge = DGL_EDGESET_EDGE_PTR(pEdgeset, DGL_EDGESET_EDGECOUNT(pEdgeset),
236  pgraph->EdgeAttrSize);
237  DGL_EDGESET_EDGECOUNT(pEdgeset)++;
238 #endif
239 
240  DGL_EDGE_HEADNODE_OFFSET(pEdge) =
241  nHead; /* will be an offset after flattening */
242  DGL_EDGE_TAILNODE_OFFSET(pEdge) =
243  nTail; /* will be an offset after flattening */
244  DGL_EDGE_COST(pEdge) = nCost;
245  DGL_EDGE_ID(pEdge) = nEdge;
246 
247 #if !defined(_DGL_V1)
248  if (nFlags & DGL_ES_DIRECTED)
250  else
251  DGL_EDGE_STATUS(pEdge) = 0;
252 #endif
253 
254  pgraph->cEdge++;
255  pgraph->nnCost += (dglInt64_t)nCost;
256 
257  if (pvEdgeAttr && pgraph->EdgeAttrSize) {
258  memcpy(DGL_EDGE_ATTR_PTR(pEdge), pvEdgeAttr, pgraph->EdgeAttrSize);
259  }
260 
261  /*
262  * If requested add a cost-weighted entry into the edge prioritizer
263  */
264 #if !defined(_DGL_V1)
265  if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
266  if (dgl_edge_prioritizer_add(pgraph, DGL_EDGE_ID(pEdge),
267  DGL_EDGE_COST(pEdge)) < 0) {
268  return -pgraph->iErrno;
269  }
270  }
271 #endif
272 
273  if (nFlags & DGL_STRONGCONNECT) {
274  return DGL_ADD_EDGE_FUNC(pgraph, nTail, nHead, nCost, nEdge, pvHeadAttr,
275  pvTailAttr, pvEdgeAttr,
276  nFlags & ~DGL_STRONGCONNECT);
277  }
278 
279  return 0;
280 }
281 
283 {
284 #if defined(_DGL_V1)
285  pgraph->iErrno = DGL_ERR_NotSupported;
286  return -pgraph->iErrno;
287 #else
288  dglTreeEdge_s *pEdgeItem, findEdgeItem;
289  dglInt32_t *pEdge;
290 
291  if (pgraph->Flags & DGL_GS_FLAT) {
292  pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
293  return -pgraph->iErrno;
294  }
295 
296  if (pgraph->pEdgeTree == NULL) {
298  return -pgraph->iErrno;
299  }
300 
301  findEdgeItem.nKey = nEdge;
302  if ((pEdgeItem = avl_find(pgraph->pEdgeTree, &findEdgeItem)) == NULL) {
303  pgraph->iErrno = DGL_ERR_EdgeNotFound;
304  return -pgraph->iErrno;
305  }
306 
307  pEdge = pEdgeItem->pv;
308 
310  DGL_EDGE_ID(pEdge)) < 0) {
311  return -pgraph->iErrno;
312  }
313 
315  DGL_EDGE_ID(pEdge)) < 0) {
316  return -pgraph->iErrno;
317  }
318 
319  /* prioritizer sync
320  */
321  if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
322  if (dgl_edge_prioritizer_del(pgraph, DGL_EDGE_ID(pEdge),
323  DGL_EDGE_COST(pEdge)) < 0) {
324  return -pgraph->iErrno;
325  }
326  }
327  /*
328  */
329  pgraph->cEdge--;
330  pgraph->nnCost -= (dglInt64_t)DGL_EDGE_COST(pEdge);
331 
332  avl_delete(pgraph->pEdgeTree, pEdgeItem);
333  dglTreeEdgeCancel(pEdgeItem, NULL);
334  return 0;
335 #endif
336 }
337 
339 {
340 #if defined(_DGL_V1)
341  pgraph->iErrno = DGL_ERR_NotSupported;
342  return NULL;
343 #else
344  register dglInt32_t top; /* top of table */
345  register dglInt32_t pos; /* current position to compare */
346  register dglInt32_t bot; /* bottom of table */
347  register dglInt32_t *pref;
348  register int cwords; /* size of a edge in words of 32 bit */
349  register dglTreeEdge_s *ptreeEdge;
350  dglTreeEdge_s findEdge;
351  dglInt32_t id;
352 
353  pgraph->iErrno = 0;
354  if (pgraph->Flags & DGL_GS_FLAT) {
355  cwords = DGL_EDGE_WSIZE(pgraph->EdgeAttrSize);
356  /*bot = pgraph->iEdgeBuffer / DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize);
357  */
358  bot = pgraph->cEdge;
359  top = 0;
360  pos = 0;
361  pref = (dglInt32_t *)pgraph->pEdgeBuffer;
362 
363  /* perform a binary search
364  */
365  while (top != bot) {
366  pos = top + (bot - top) / 2;
367  id = DGL_EDGE_ID(&pref[pos * cwords]);
368  if (id == nEdge) {
369  break;
370  }
371  else if (nEdge < id) {
372  bot = pos;
373  }
374  else if (nEdge > id) {
375  top = pos + 1;
376  }
377  }
378  if (top == bot) {
379  return NULL;
380  }
381  return &pref[pos * cwords];
382  }
383  else {
384  findEdge.nKey = nEdge;
385  ptreeEdge = avl_find(pgraph->pEdgeTree, &findEdge);
386  if (ptreeEdge && ptreeEdge->pv) {
387  return ptreeEdge->pv;
388  }
389  return NULL;
390  }
391 #endif
392 }
#define NULL
Definition: ccmath.h:32
int DGL_DEL_EDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nEdge UNUSED)
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)
dglInt32_t * DGL_GET_EDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nEdge UNUSED)
#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_GO_EdgePrioritize_COST
Definition: graph.h:52
#define DGL_ERR_MemoryExhausted
Definition: graph.h:254
#define DGL_ERR_BadOnFlatGraph
Definition: graph.h:264
#define DGL_NS_HEAD
Definition: graph.h:59
#define DGL_ERR_EdgeAlreadyExist
Definition: graph.h:273
#define DGL_ERR_NotSupported
Definition: graph.h:259
#define DGL_GS_FLAT
Definition: graph.h:36
#define DGL_STRONGCONNECT
Definition: graph.h:78
#define DGL_ERR_UnexpectedNullPointer
Definition: graph.h:268
#define DGL_ERR_EdgeNotFound
Definition: graph.h:270
#define DGL_ES_DIRECTED
Definition: graph.h:66
int dgl_edge_prioritizer_del(dglGraph_s *pG, dglInt32_t nId, dglInt32_t nPriId)
Definition: helpers.c:91
int dgl_edge_prioritizer_add(dglGraph_s *pG, dglInt32_t nId, dglInt32_t nPriId)
Definition: helpers.c:132
int DGL_DEL_NODE_INEDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nNode, dglInt32_t nEdge)
int DGL_DEL_NODE_OUTEDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nNode, dglInt32_t nEdge)
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
dglInt32_t nOptions
Definition: graph.h:155
dglInt32_t EdgeAttrSize
Definition: graph.h:143
dglInt32_t cAlone
Definition: graph.h:149
dglInt32_t cHead
Definition: graph.h:147
int iErrno
Definition: graph.h:138
dglInt32_t cNode
Definition: graph.h:146
void * pNodeTree
Definition: graph.h:157
void * pEdgeTree
Definition: graph.h:158
dglInt32_t Flags
Definition: graph.h:153
dglInt64_t nnCost
Definition: graph.h:151
dglInt32_t nKey
Definition: tree.h:90
void * pv
Definition: tree.h:91
dglTreeEdge_s * dglTreeEdgeAdd(void *pavl, dglInt32_t nKey)
Definition: tree.c:171
void dglTreeEdgeCancel(void *pvEdge, void *pvParam UNUSED)
Definition: tree.c:152
#define avl_find
Definition: tree.h:38
#define avl_delete
Definition: tree.h:37
long long dglInt64_t
Definition: type.h:37
long dglInt32_t
Definition: type.h:36
#define DGL_EDGESET_EDGE_PTR
Definition: v1-defs.h:149
#define DGL_T_NODEITEM_InEdgesetPTR(p)
Definition: v1-defs.h:173
#define DGL_T_NODEITEM_TYPE
Definition: v1-defs.h:168
#define DGL_NODE_STATUS
Definition: v1-defs.h:126
#define DGL_T_NODEITEM_Add
Definition: v1-defs.h:177
#define DGL_EDGESET_ALLOC
Definition: v1-defs.h:150
#define DGL_NODE_ID
Definition: v1-defs.h:127
#define DGL_EDGE_WSIZE
Definition: v1-defs.h:135
#define DGL_NODE_EDGESET_OFFSET
Definition: v1-defs.h:129
#define DGL_NODE_ALLOC
Definition: v1-defs.h:123
#define DGL_T_NODEITEM_Set_InEdgesetPTR(p, ptr)
Definition: v1-defs.h:174
#define DGL_T_NODEITEM_OutEdgesetPTR(p)
Definition: v1-defs.h:171
#define DGL_T_NODEITEM_Set_NodePTR(p, ptr)
Definition: v1-defs.h:170
#define DGL_EDGE_ALLOC
Definition: v1-defs.h:133
#define DGL_EDGE_TAILNODE_OFFSET
Definition: v1-defs.h:141
#define DGL_EDGESET_EDGECOUNT
Definition: v1-defs.h:148
#define DGL_EDGE_ATTR_PTR
Definition: v1-defs.h:139
#define DGL_T_NODEITEM_Set_OutEdgesetPTR(p, ptr)
Definition: v1-defs.h:172
#define DGL_EDGE_STATUS(p)
Definition: v1-defs.h:136
#define DGL_T_NODEITEM_NodePTR(p)
Definition: v1-defs.h:169
#define DGL_NODE_ATTR_PTR
Definition: v1-defs.h:128
#define DGL_EDGE_ID
Definition: v1-defs.h:138
#define DGL_EDGE_HEADNODE_OFFSET
Definition: v1-defs.h:140
#define DGL_EDGESET_REALLOC
Definition: v1-defs.h:151
#define DGL_EDGE_COST
Definition: v1-defs.h:137