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