GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-9b28d7b83c
graph_v2.h
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 tabstop=4
21  */
22 
23 #ifndef _DGL_dglGraph_s_V2_H_
24 #define _DGL_dglGraph_s_V2_H_
25 
26 #ifdef DGL_STATS
27 #include <time.h>
28 #endif
29 
30 /*
31  * Node macros - addresses in a flat node
32  */
33 #define DGL_IN_NODEID_v2 0
34 #define DGL_IN_STATUS_v2 1
35 #define DGL_IN_EDGESET_OFFSET_v2 2
36 #define DGL_IN_ATTR_v2 3
37 #define DGL_IN_SIZE_v2 DGL_IN_ATTR_v2
38 
39 #define DGL_NODE_SIZEOF_v2(nattr) \
40  (sizeof(dglInt32_t) * DGL_IN_SIZE_v2 + (nattr))
41 #define DGL_NODE_WSIZE_v2(nattr) \
42  (DGL_NODE_SIZEOF_v2(nattr) / sizeof(dglInt32_t))
43 #define DGL_NODE_ALLOC_v2(nattr) (malloc(DGL_NODE_SIZEOF_v2(nattr)))
44 
45 #define DGL_NODE_ID_v2(p) ((p)[DGL_IN_NODEID_v2])
46 #define DGL_NODE_STATUS_v2(p) ((p)[DGL_IN_STATUS_v2])
47 #define DGL_NODE_EDGESET_OFFSET_v2(p) ((p)[DGL_IN_EDGESET_OFFSET_v2])
48 #define DGL_NODE_ATTR_PTR_v2(p) ((p) + DGL_IN_ATTR_v2)
49 
50 /*
51  * Edgeset macros - addresses in a flat edge-area
52  */
53 #define DGL_ILA_TOCNT_v2 0
54 #define DGL_ILA_SIZE_v2 1
55 #define DGL_ILA_TOARR_v2 DGL_ILA_SIZE_v2
56 
57 #define DGL_EDGESET_SIZEOF_v2(C, lattr) (sizeof(dglInt32_t) * ((C) + 1))
58 #define DGL_EDGESET_WSIZE_v2(C, lattr) \
59  (DGL_EDGESET_SIZEOF_v2(C, lattr) / sizeof(dglInt32_t))
60 #define DGL_EDGESET_ALLOC_v2(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v2(C, lattr)))
61 #define DGL_EDGESET_REALLOC_v2(P, C, lattr) \
62  (realloc(P, DGL_EDGESET_SIZEOF_v2(C, lattr)))
63 
64 #define DGL_EDGESET_EDGECOUNT_v2(p) ((p)[DGL_ILA_TOCNT_v2])
65 #define DGL_EDGESET_EDGEARRAY_PTR_v2(p) ((p) + DGL_ILA_TOARR_v2)
66 #define DGL_EDGESET_EDGE_PTR_v2(pgrp, p, i) \
67  DGL_EDGEBUFFER_SHIFT_v2(pgrp, *((p) + DGL_ILA_TOARR_v2 + (i)))
68 
69 /*
70  * Edge macros - addresses in a flat edge
71  */
72 #define DGL_IL_HEAD_OFFSET_v2 0
73 #define DGL_IL_TAIL_OFFSET_v2 1
74 #define DGL_IL_STATUS_v2 2
75 #define DGL_IL_COST_v2 3
76 #define DGL_IL_ID_v2 4
77 #define DGL_IL_ATTR_v2 5
78 #define DGL_IL_SIZE_v2 DGL_IL_ATTR_v2
79 
80 #define DGL_EDGE_SIZEOF_v2(lattr) \
81  (sizeof(dglInt32_t) * DGL_IL_SIZE_v2 + (lattr))
82 #define DGL_EDGE_WSIZE_v2(lattr) \
83  (DGL_EDGE_SIZEOF_v2(lattr) / sizeof(dglInt32_t))
84 #define DGL_EDGE_ALLOC_v2(lattr) (malloc(DGL_EDGE_SIZEOF_v2(lattr)))
85 
86 #define DGL_EDGE_HEADNODE_OFFSET_v2(p) ((p)[DGL_IL_HEAD_OFFSET_v2])
87 #define DGL_EDGE_TAILNODE_OFFSET_v2(p) ((p)[DGL_IL_TAIL_OFFSET_v2])
88 #define DGL_EDGE_STATUS_v2(p) ((p)[DGL_IL_STATUS_v2])
89 #define DGL_EDGE_COST_v2(p) ((p)[DGL_IL_COST_v2])
90 #define DGL_EDGE_ID_v2(p) ((p)[DGL_IL_ID_v2])
91 #define DGL_EDGE_ATTR_PTR_v2(p) ((p) + DGL_IL_ATTR_v2)
92 #define DGL_EDGE_HEADNODE_ID_v2(pgrp, pl) \
93  ((pgrp->Flags & 1) \
94  ? DGL_NODE_ID_v2(pgrp->pNodeBuffer + DGL_EDGE_HEADNODE_OFFSET_v2(pl)) \
95  : DGL_EDGE_HEADNODE_OFFSET_v2(pl))
96 #define DGL_EDGE_TAILNODE_ID_v2(pgrp, pl) \
97  ((pgrp->Flags & 1) \
98  ? DGL_NODE_ID_v2(pgrp->pNodeBuffer + DGL_EDGE_TAILNODE_OFFSET_v2(pl)) \
99  : DGL_EDGE_TAILNODE_OFFSET_v2(pl))
100 
101 /*
102  * Scan a node buffer
103  */
104 #define DGL_FOREACH_NODE_v2(pgrp, pn) \
105  for ((pn) = (dglInt32_t *)(pgrp)->pNodeBuffer; \
106  (pgrp)->pNodeBuffer && \
107  (pn) < (dglInt32_t *)((pgrp)->pNodeBuffer + (pgrp)->iNodeBuffer); \
108  (pn) += DGL_NODE_WSIZE_v2((pgrp)->NodeAttrSize))
109 /*
110  * Scan a edgeset
111  */
112 #define DGL_FOREACH_EDGE_v2(pgrp, pla, pl, il) \
113  for ((il) = 0, (pl) = DGL_EDGESET_EDGE_PTR_v2(pgrp, pla, il); \
114  (il) < DGL_EDGESET_EDGECOUNT_v2(pla); \
115  (il)++, (pl) = DGL_EDGESET_EDGE_PTR_v2(pgrp, pla, il))
116 /*
117  * Node Buffer Utilities
118  */
119 #define DGL_NODEBUFFER_SHIFT_v2(pgrp, o) \
120  ((dglInt32_t *)((pgrp)->pNodeBuffer + (o)))
121 #define DGL_NODEBUFFER_OFFSET_v2(pgrp, p) \
122  ((dglInt32_t)((dglByte_t *)p - (dglByte_t *)(pgrp)->pNodeBuffer))
123 
124 /*
125  * Edge Buffer Utilities
126  */
127 #define DGL_EDGEBUFFER_SHIFT_v2(pgrp, o) \
128  ((dglInt32_t *)((pgrp)->pEdgeBuffer + (o)))
129 #define DGL_EDGEBUFFER_OFFSET_v2(pgrp, pl) \
130  ((dglInt32_t)((dglByte_t *)pl - (dglByte_t *)(pgrp)->pEdgeBuffer))
131 
133  dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr,
134  void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags);
135 
138 int dgl_initialize_V2(dglGraph_s *pgraph);
139 int dgl_release_V2(dglGraph_s *pgraph);
140 int dgl_write_V2(dglGraph_s *pgraph, int fd);
141 int dgl_read_V2(dglGraph_s *pgraph, int fd, int version);
142 
144  dglInt32_t nStart);
146 
148  dglInt32_t *pDistance, dglInt32_t nStart,
149  dglInt32_t nDestination, dglSPClip_fn fnClip,
150  void *pvClipArg, dglSPCache_s *pCache);
152  dglInt32_t *pDistance, dglInt32_t nStart,
153  dglInt32_t nDestination, dglSPClip_fn fnClip,
154  void *pvClipArg, dglSPCache_s *pCache);
155 int dgl_dijkstra_V2(dglGraph_s *pgraph, dglSPReport_s **ppReport,
156  dglInt32_t *pDistance, dglInt32_t nStart,
157  dglInt32_t nDestination, dglSPClip_fn fnClip,
158  void *pvClipArg, dglSPCache_s *pCache);
159 
161  dglGraph_s *pgraphOut,
162  dglInt32_t nVertex, void *pvVisited,
163  dglSpanClip_fn fnClip,
164  void *pvClipArg);
166  dglGraph_s *pgraphOut,
167  dglInt32_t nVertex, void *pvVisited,
168  dglSpanClip_fn fnClip,
169  void *pvClipArg);
170 int dgl_depthfirst_spanning_V2(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut,
171  dglInt32_t nVertex, void *pvVisited,
172  dglSpanClip_fn fnClip, void *pvClipArg);
173 
175  dglGraph_s *pgraphOut, dglInt32_t nVertex,
176  dglSpanClip_fn fnClip, void *pvClipArg);
178  dglGraph_s *pgraphOut, dglInt32_t nVertex,
179  dglSpanClip_fn fnClip, void *pvClipArg);
180 int dgl_minimum_spanning_V2(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut,
181  dglInt32_t nVertex, dglSpanClip_fn fnClip,
182  void *pvClipArg);
183 
184 int dgl_add_node_V2(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr,
185  dglInt32_t nFlags);
187  dglInt32_t nEdge);
189  dglInt32_t nEdge);
192 
195 
198 
199 /*
200  * Node Traversing
201  */
207 
208 /*
209  * Edgeset Traversing
210  */
212  dglEdgesetTraverser_s *pTraverser,
213  dglInt32_t *pnEdgeset);
217 
219  dglEdgePrioritizer_s *pEP);
223 
224 #endif
int(* dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *)
Definition: graph.h:179
int(* dglSpanClip_fn)(dglGraph_s *, dglGraph_s *, dglSpanClipInput_s *, dglSpanClipOutput_s *, void *)
Definition: graph.h:185
int dgl_dijkstra_V2(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_v2.c:61
dglInt32_t * dgl_node_t_first_V2(dglNodeTraverser_s *pT)
dglInt32_t * dgl_edge_t_next_V2(dglEdgeTraverser_s *pT)
int dgl_span_minimum_spanning_V2_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
int dgl_edgeset_t_initialize_V2(dglGraph_s *pGraph, dglEdgesetTraverser_s *pTraverser, dglInt32_t *pnEdgeset)
int dgl_write_V2(dglGraph_s *pgraph, int fd)
Definition: graph_v2.c:143
int dgl_dijkstra_V2_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_release_V2(dglGraph_s *pgraph)
Definition: graph_v2.c:123
int dgl_add_edge_V2(dglGraph_s *pgraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr, void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
int dgl_flatten_V2(dglGraph_s *pgraph)
int dgl_node_t_initialize_V2(dglGraph_s *pGraph, dglNodeTraverser_s *pT)
int dgl_edge_t_initialize_V2(dglGraph_s *pGraph, dglEdgeTraverser_s *pTraverser, dglEdgePrioritizer_s *pEP)
int dgl_del_node_inedge_V2(dglGraph_s *pgraph, dglInt32_t nNode, dglInt32_t nEdge)
int dgl_dijkstra_V2_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_del_node_outedge_V2(dglGraph_s *pgraph, dglInt32_t nNode, dglInt32_t nEdge)
int dgl_depthfirst_spanning_V2(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v2.c:76
int dgl_span_minimum_spanning_V2_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
void dgl_sp_cache_release_V2(dglGraph_s *pgraph, dglSPCache_s *pCache)
int dgl_initialize_V2(dglGraph_s *pgraph)
Definition: graph_v2.c:104
int dgl_unflatten_V2(dglGraph_s *pgraph)
dglInt32_t * dgl_getnode_inedgeset_V2(dglGraph_s *pgraph, dglInt32_t *pnode)
void dgl_edgeset_t_release_V2(dglEdgesetTraverser_s *pTraverser)
int dgl_read_V2(dglGraph_s *pgraph, int fd, int version)
Definition: graph_v2.c:238
dglInt32_t * dgl_edgeset_t_first_V2(dglEdgesetTraverser_s *pTraverser)
dglInt32_t * dgl_edge_t_first_V2(dglEdgeTraverser_s *pT)
int dgl_del_edge_V2(dglGraph_s *pgraph, dglInt32_t nId)
dglInt32_t * dgl_edgeset_t_next_V2(dglEdgesetTraverser_s *pTraverser)
int dgl_span_depthfirst_spanning_V2_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
int dgl_del_node_V2(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_sp_cache_initialize_V2(dglGraph_s *pgraph, dglSPCache_s *pCache, dglInt32_t nStart)
void dgl_node_t_release_V2(dglNodeTraverser_s *pT)
dglInt32_t * dgl_get_node_V2(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_add_node_V2(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
dglInt32_t * dgl_get_edge_V2(dglGraph_s *pgraph, dglInt32_t nId)
dglInt32_t * dgl_node_t_find_V2(dglNodeTraverser_s *pT, dglInt32_t nId)
int dgl_span_depthfirst_spanning_V2_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
int dgl_minimum_spanning_V2(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v2.c:90
dglInt32_t * dgl_getnode_outedgeset_V2(dglGraph_s *pgraph, dglInt32_t *pnode)
void dgl_edge_t_release_V2(dglEdgeTraverser_s *pTraverser)
dglInt32_t * dgl_node_t_next_V2(dglNodeTraverser_s *pT)
long dglInt32_t
Definition: type.h:36