GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
graph_v1.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_V1_H_
24 #define _DGL_dglGraph_s_V1_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_v1 0
34 #define DGL_IN_STATUS_v1 1
35 #define DGL_IN_TAIL_OFFSET_v1 2
36 #define DGL_IN_ATTR_v1 3
37 #define DGL_IN_SIZE_v1 DGL_IN_ATTR_v1
38 
39 #define DGL_NODE_SIZEOF_v1( nattr ) (sizeof( dglInt32_t ) * DGL_IN_SIZE_v1 + (nattr) )
40 #define DGL_NODE_WSIZE_v1( nattr ) (DGL_NODE_SIZEOF_v1( nattr ) / sizeof(dglInt32_t) )
41 #define DGL_NODE_ALLOC_v1( nattr ) (malloc( DGL_NODE_SIZEOF_v1( nattr ) ) )
42 
43 #define DGL_NODE_ID_v1(p) ((p)[DGL_IN_NODEID_v1])
44 #define DGL_NODE_STATUS_v1(p) ((p)[DGL_IN_STATUS_v1])
45 #define DGL_NODE_EDGESET_OFFSET_v1(p) ((p)[DGL_IN_TAIL_OFFSET_v1])
46 #define DGL_NODE_ATTR_PTR_v1(p) ((p) + DGL_IN_ATTR_v1)
47 
48 /*
49  * Edgeset macros - addresses in a flat edge-area
50  */
51 #define DGL_ILA_TOCNT_v1 0
52 #define DGL_ILA_SIZE_v1 1
53 #define DGL_ILA_TOARR_v1 DGL_ILA_SIZE_v1
54 
55 #define DGL_EDGESET_SIZEOF_v1(C, lattr) (sizeof( dglInt32_t ) * (DGL_ILA_SIZE_v1) + DGL_EDGE_SIZEOF_v1(lattr) * (C))
56 #define DGL_EDGESET_WSIZE_v1(C, lattr) (DGL_EDGESET_SIZEOF_v1(C, lattr) / sizeof(dglInt32_t))
57 #define DGL_EDGESET_ALLOC_v1(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v1(C, lattr)))
58 #define DGL_EDGESET_REALLOC_v1(P, C, lattr) (realloc(P , DGL_EDGESET_SIZEOF_v1(C, lattr)))
59 
60 #define DGL_EDGESET_EDGECOUNT_v1(p) ((p)[DGL_ILA_TOCNT_v1])
61 #define DGL_EDGESET_EDGEARRAY_PTR_v1(p) ((p) + DGL_ILA_TOARR_v1)
62 #define DGL_EDGESET_EDGE_PTR_v1(p,i,C) (((p) + DGL_ILA_TOARR_v1) + (i) * DGL_EDGE_WSIZE_v1(C))
63 
64 /*
65  * Edge macros - addresses in a flat edge
66  */
67 #define DGL_IL_HEAD_OFFSET_v1 0
68 #define DGL_IL_TAIL_OFFSET_v1 1
69 #define DGL_IL_COST_v1 2
70 #define DGL_IL_ID_v1 3
71 #define DGL_IL_ATTR_v1 4
72 #define DGL_IL_SIZE_v1 DGL_IL_ATTR_v1
73 
74 #define DGL_EDGE_SIZEOF_v1( lattr ) (sizeof( dglInt32_t ) * DGL_IL_SIZE_v1 + (lattr))
75 #define DGL_EDGE_WSIZE_v1( lattr ) (DGL_EDGE_SIZEOF_v1( lattr ) / sizeof( dglInt32_t ))
76 #define DGL_EDGE_ALLOC_v1( lattr ) (malloc( DGL_EDGE_SIZEOF_v1( lattr ) ))
77 
78 #define DGL_EDGE_HEADNODE_OFFSET_v1(p) ((p)[DGL_IL_HEAD_OFFSET_v1])
79 #define DGL_EDGE_TAILNODE_OFFSET_v1(p) ((p)[DGL_IL_TAIL_OFFSET_v1])
80 #define DGL_EDGE_COST_v1(p) ((p)[DGL_IL_COST_v1])
81 #define DGL_EDGE_ID_v1(p) ((p)[DGL_IL_ID_v1])
82 #define DGL_EDGE_ATTR_PTR_v1(p) ((p) + DGL_IL_ATTR_v1)
83 #define DGL_EDGE_HEADNODE_ID_v1(pgrp,pl) ((pgrp->Flags&1)?\
84  DGL_NODE_ID_v1(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v1(pl)):\
85  DGL_EDGE_HEADNODE_OFFSET_v1(pl))
86 #define DGL_EDGE_TAILNODE_ID_v1(pgrp,pl) ((pgrp->Flags&1)?\
87  DGL_NODE_ID_v1(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v1(pl)):\
88  DGL_EDGE_TAILNODE_OFFSET_v1(pl))
89 
90 /*
91  * Scan a node buffer
92  */
93 #define DGL_FOREACH_NODE_v1(pgrp,pn) for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\
94  (pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\
95  (pn)+=DGL_NODE_WSIZE_v1((pgrp)->NodeAttrSize))
96 /*
97  * Scan a edgeset
98  */
99 #define DGL_FOREACH_EDGE_v1(pgrp,pla,pl) for((pl)=DGL_EDGESET_EDGEARRAY_PTR_v1(pla);\
100  (pl)<(pla)+DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize)*DGL_EDGESET_EDGECOUNT_v1(pla);\
101  (pl)+=DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize))
102 /*
103  * Node Buffer Utilities
104  */
105 #define DGL_NODEBUFFER_SHIFT_v1(pgrp,o) ((dglInt32_t*)((pgrp)->pNodeBuffer + (o)))
106 #define DGL_NODEBUFFER_OFFSET_v1(pgrp,p) ((dglInt32_t)((dglByte_t *)p - (dglByte_t *)(pgrp)->pNodeBuffer))
107 
108 /*
109  * Edge Buffer Utilities
110  */
111 #define DGL_EDGEBUFFER_SHIFT_v1(pgrp,o) ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o)))
112 #define DGL_EDGEBUFFER_OFFSET_v1(pgrp,pl) ((dglInt32_t)((dglByte_t *)pl - (dglByte_t *)(pgrp)->pEdgeBuffer))
113 
114 
115 
116 
117 int dgl_add_edge_V1(dglGraph_s * pgraph,
118  dglInt32_t nHead,
119  dglInt32_t nTail,
120  dglInt32_t nCost,
121  dglInt32_t nEdge,
122  void *pvHeadAttr,
123  void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags);
124 
125 int dgl_unflatten_V1(dglGraph_s * pgraph);
126 int dgl_flatten_V1(dglGraph_s * pgraph);
127 int dgl_initialize_V1(dglGraph_s * pgraph);
128 int dgl_release_V1(dglGraph_s * pgraph);
129 int dgl_write_V1(dglGraph_s * pgraph, int fd);
130 int dgl_read_V1(dglGraph_s * pgraph, int fd);
131 
132 
133 int dgl_sp_cache_initialize_V1(dglGraph_s * pgraph, dglSPCache_s * pCache,
134  dglInt32_t nStart);
135 void dgl_sp_cache_release_V1(dglGraph_s * pgraph, dglSPCache_s * pCache);
136 
137 int dgl_dijkstra_V1_TREE(dglGraph_s * pgraph,
138  dglSPReport_s ** ppReport,
139  dglInt32_t * pDistance,
140  dglInt32_t nStart,
141  dglInt32_t nDestination,
142  dglSPClip_fn fnClip,
143  void *pvClipArg, dglSPCache_s * pCache);
144 int dgl_dijkstra_V1_FLAT(dglGraph_s * pgraph,
145  dglSPReport_s ** ppReport,
146  dglInt32_t * pDistance,
147  dglInt32_t nStart,
148  dglInt32_t nDestination,
149  dglSPClip_fn fnClip,
150  void *pvClipArg, dglSPCache_s * pCache);
151 int dgl_dijkstra_V1(dglGraph_s * pgraph,
152  dglSPReport_s ** ppReport,
153  dglInt32_t * pDistance,
154  dglInt32_t nStart,
155  dglInt32_t nDestination,
156  dglSPClip_fn fnClip,
157  void *pvClipArg, dglSPCache_s * pCache);
158 
159 
161  dglGraph_s * pgraphOut,
162  dglInt32_t nVertex,
163  void *pvVisited,
164  dglSpanClip_fn fnClip,
165  void *pvClipArg);
167  dglGraph_s * pgraphOut,
168  dglInt32_t nVertex,
169  void *pvVisited,
170  dglSpanClip_fn fnClip,
171  void *pvClipArg);
173  dglGraph_s * pgraphOut,
174  dglInt32_t nVertex,
175  void *pvVisited,
176  dglSpanClip_fn fnClip, void *pvClipArg);
177 
178 
180  dglGraph_s * pgraphOut,
181  dglInt32_t nVertex,
182  dglSpanClip_fn fnClip, void *pvClipArg);
184  dglGraph_s * pgraphOut,
185  dglInt32_t nVertex,
186  dglSpanClip_fn fnClip, void *pvClipArg);
187 int dgl_minimum_spanning_V1(dglGraph_s * pgraphIn,
188  dglGraph_s * pgraphOut,
189  dglInt32_t nVertex,
190  dglSpanClip_fn fnClip, void *pvClipArg);
191 
192 
193 int dgl_add_node_V1(dglGraph_s * pgraph,
194  dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags);
195 int dgl_del_node_V1(dglGraph_s * pgraph, dglInt32_t nId);
197 
199 int dgl_del_edge_V1(dglGraph_s * pgraph, dglInt32_t nId);
200 
202  dglInt32_t * pnode);
203 
204 /*
205  * Node Traversing
206  */
212 
213 
214 /*
215  * Edgeset Traversing
216  */
218  dglEdgesetTraverser_s * pTraverser,
219  dglInt32_t * pnEdgeset);
223 
224 
226  dglEdgeTraverser_s * pTraverser,
227  dglEdgePrioritizer_s * pEP);
228 void dgl_edge_t_release_V1(dglEdgeTraverser_s * pTraverser);
231 
232 
233 
234 
235 #endif
int dgl_span_minimum_spanning_V1_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
void dgl_sp_cache_release_V1(dglGraph_s *pgraph, dglSPCache_s *pCache)
int dgl_span_minimum_spanning_V1_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
int dgl_del_node_V1(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_write_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:154
int dgl_node_t_initialize_V1(dglGraph_s *pGraph, dglNodeTraverser_s *pT)
dglInt32_t * dgl_get_edge_V1(dglGraph_s *pgraph, dglInt32_t nId)
int(* dglSpanClip_fn)(dglGraph_s *, dglGraph_s *, dglSpanClipInput_s *, dglSpanClipOutput_s *, void *)
Definition: graph.h:204
dglInt32_t * dgl_edge_t_first_V1(dglEdgeTraverser_s *pT)
int dgl_edgeset_t_initialize_V1(dglGraph_s *pGraph, dglEdgesetTraverser_s *pTraverser, dglInt32_t *pnEdgeset)
int dgl_add_edge_V1(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_depthfirst_spanning_V1(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v1.c:86
int dgl_sp_cache_initialize_V1(dglGraph_s *pgraph, dglSPCache_s *pCache, dglInt32_t nStart)
dglInt32_t * dgl_edgeset_t_next_V1(dglEdgesetTraverser_s *pTraverser)
int dgl_read_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:250
void dgl_node_t_release_V1(dglNodeTraverser_s *pT)
int dgl_release_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:133
void dgl_edge_t_release_V1(dglEdgeTraverser_s *pTraverser)
int dgl_edge_t_initialize_V1(dglGraph_s *pGraph, dglEdgeTraverser_s *pTraverser, dglEdgePrioritizer_s *pEP)
dglInt32_t * dgl_get_node_V1(dglGraph_s *pgraph, dglInt32_t nId)
long dglInt32_t
Definition: type.h:37
int dgl_del_edge_V1(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_dijkstra_V1_TREE(dglGraph_s *pgraph, dglSPReport_s **ppReport, dglInt32_t *pDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
dglInt32_t * dgl_node_t_first_V1(dglNodeTraverser_s *pT)
int dgl_add_node_V1(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
int dgl_minimum_spanning_V1(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v1.c:104
int dgl_dijkstra_V1_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_unflatten_V1(dglGraph_s *pgraph)
int(* dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *)
Definition: graph.h:198
dglInt32_t * dgl_node_t_find_V1(dglNodeTraverser_s *pT, dglInt32_t nId)
int dgl_flatten_V1(dglGraph_s *pgraph)
dglInt32_t * dgl_getnode_outedgeset_V1(dglGraph_s *pgraph, dglInt32_t *pnode)
int dgl_dijkstra_V1(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_v1.c:67
dglInt32_t * dgl_edgeset_t_first_V1(dglEdgesetTraverser_s *pTraverser)
dglInt32_t * dgl_node_t_next_V1(dglNodeTraverser_s *pT)
int dgl_span_depthfirst_spanning_V1_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
dglInt32_t * dgl_edge_t_next_V1(dglEdgeTraverser_s *pT)
int dgl_initialize_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:120
void dgl_edgeset_t_release_V1(dglEdgesetTraverser_s *pTraverser)
int dgl_span_depthfirst_spanning_V1_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)