GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-6da4f45b8e
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) \
40  (sizeof(dglInt32_t) * DGL_IN_SIZE_v1 + (nattr))
41 #define DGL_NODE_WSIZE_v1(nattr) \
42  (DGL_NODE_SIZEOF_v1(nattr) / sizeof(dglInt32_t))
43 #define DGL_NODE_ALLOC_v1(nattr) (malloc(DGL_NODE_SIZEOF_v1(nattr)))
44 
45 #define DGL_NODE_ID_v1(p) ((p)[DGL_IN_NODEID_v1])
46 #define DGL_NODE_STATUS_v1(p) ((p)[DGL_IN_STATUS_v1])
47 #define DGL_NODE_EDGESET_OFFSET_v1(p) ((p)[DGL_IN_TAIL_OFFSET_v1])
48 #define DGL_NODE_ATTR_PTR_v1(p) ((p) + DGL_IN_ATTR_v1)
49 
50 /*
51  * Edgeset macros - addresses in a flat edge-area
52  */
53 #define DGL_ILA_TOCNT_v1 0
54 #define DGL_ILA_SIZE_v1 1
55 #define DGL_ILA_TOARR_v1 DGL_ILA_SIZE_v1
56 
57 #define DGL_EDGESET_SIZEOF_v1(C, lattr) \
58  (sizeof(dglInt32_t) * (DGL_ILA_SIZE_v1) + DGL_EDGE_SIZEOF_v1(lattr) * (C))
59 #define DGL_EDGESET_WSIZE_v1(C, lattr) \
60  (DGL_EDGESET_SIZEOF_v1(C, lattr) / sizeof(dglInt32_t))
61 #define DGL_EDGESET_ALLOC_v1(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v1(C, lattr)))
62 #define DGL_EDGESET_REALLOC_v1(P, C, lattr) \
63  (realloc(P, DGL_EDGESET_SIZEOF_v1(C, lattr)))
64 
65 #define DGL_EDGESET_EDGECOUNT_v1(p) ((p)[DGL_ILA_TOCNT_v1])
66 #define DGL_EDGESET_EDGEARRAY_PTR_v1(p) ((p) + DGL_ILA_TOARR_v1)
67 #define DGL_EDGESET_EDGE_PTR_v1(p, i, C) \
68  (((p) + DGL_ILA_TOARR_v1) + (i)*DGL_EDGE_WSIZE_v1(C))
69 
70 /*
71  * Edge macros - addresses in a flat edge
72  */
73 #define DGL_IL_HEAD_OFFSET_v1 0
74 #define DGL_IL_TAIL_OFFSET_v1 1
75 #define DGL_IL_COST_v1 2
76 #define DGL_IL_ID_v1 3
77 #define DGL_IL_ATTR_v1 4
78 #define DGL_IL_SIZE_v1 DGL_IL_ATTR_v1
79 
80 #define DGL_EDGE_SIZEOF_v1(lattr) \
81  (sizeof(dglInt32_t) * DGL_IL_SIZE_v1 + (lattr))
82 #define DGL_EDGE_WSIZE_v1(lattr) \
83  (DGL_EDGE_SIZEOF_v1(lattr) / sizeof(dglInt32_t))
84 #define DGL_EDGE_ALLOC_v1(lattr) (malloc(DGL_EDGE_SIZEOF_v1(lattr)))
85 
86 #define DGL_EDGE_HEADNODE_OFFSET_v1(p) ((p)[DGL_IL_HEAD_OFFSET_v1])
87 #define DGL_EDGE_TAILNODE_OFFSET_v1(p) ((p)[DGL_IL_TAIL_OFFSET_v1])
88 #define DGL_EDGE_COST_v1(p) ((p)[DGL_IL_COST_v1])
89 #define DGL_EDGE_ID_v1(p) ((p)[DGL_IL_ID_v1])
90 #define DGL_EDGE_ATTR_PTR_v1(p) ((p) + DGL_IL_ATTR_v1)
91 #define DGL_EDGE_HEADNODE_ID_v1(pgrp, pl) \
92  ((pgrp->Flags & 1) \
93  ? DGL_NODE_ID_v1(pgrp->pNodeBuffer + DGL_EDGE_HEADNODE_OFFSET_v1(pl)) \
94  : DGL_EDGE_HEADNODE_OFFSET_v1(pl))
95 #define DGL_EDGE_TAILNODE_ID_v1(pgrp, pl) \
96  ((pgrp->Flags & 1) \
97  ? DGL_NODE_ID_v1(pgrp->pNodeBuffer + DGL_EDGE_TAILNODE_OFFSET_v1(pl)) \
98  : DGL_EDGE_TAILNODE_OFFSET_v1(pl))
99 
100 /*
101  * Scan a node buffer
102  */
103 #define DGL_FOREACH_NODE_v1(pgrp, pn) \
104  for ((pn) = (dglInt32_t *)(pgrp)->pNodeBuffer; \
105  (pgrp)->pNodeBuffer && \
106  (pn) < (dglInt32_t *)((pgrp)->pNodeBuffer + (pgrp)->iNodeBuffer); \
107  (pn) += DGL_NODE_WSIZE_v1((pgrp)->NodeAttrSize))
108 /*
109  * Scan a edgeset
110  */
111 #define DGL_FOREACH_EDGE_v1(pgrp, pla, pl) \
112  for ((pl) = DGL_EDGESET_EDGEARRAY_PTR_v1(pla); \
113  (pl) < (pla) + DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize) * \
114  DGL_EDGESET_EDGECOUNT_v1(pla); \
115  (pl) += DGL_EDGE_WSIZE_v1((pgrp)->EdgeAttrSize))
116 /*
117  * Node Buffer Utilities
118  */
119 #define DGL_NODEBUFFER_SHIFT_v1(pgrp, o) \
120  ((dglInt32_t *)((pgrp)->pNodeBuffer + (o)))
121 #define DGL_NODEBUFFER_OFFSET_v1(pgrp, p) \
122  ((dglInt32_t)((dglByte_t *)p - (dglByte_t *)(pgrp)->pNodeBuffer))
123 
124 /*
125  * Edge Buffer Utilities
126  */
127 #define DGL_EDGEBUFFER_SHIFT_v1(pgrp, o) \
128  ((dglInt32_t *)((pgrp)->pEdgeBuffer + (o)))
129 #define DGL_EDGEBUFFER_OFFSET_v1(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_V1(dglGraph_s *pgraph);
139 int dgl_release_V1(dglGraph_s *pgraph);
140 int dgl_write_V1(dglGraph_s *pgraph, int fd);
141 int dgl_read_V1(dglGraph_s *pgraph, int fd);
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_V1(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_V1(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_V1(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut,
181  dglInt32_t nVertex, dglSpanClip_fn fnClip,
182  void *pvClipArg);
183 
184 int dgl_add_node_V1(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr,
185  dglInt32_t nFlags);
188 
191 
193 
194 /*
195  * Node Traversing
196  */
202 
203 /*
204  * Edgeset Traversing
205  */
207  dglEdgesetTraverser_s *pTraverser,
208  dglInt32_t *pnEdgeset);
212 
214  dglEdgePrioritizer_s *pEP);
218 
219 #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
void dgl_node_t_release_V1(dglNodeTraverser_s *pT)
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)
dglInt32_t * dgl_edgeset_t_next_V1(dglEdgesetTraverser_s *pTraverser)
int dgl_initialize_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:104
int dgl_add_node_V1(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
int dgl_write_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:137
int dgl_unflatten_V1(dglGraph_s *pgraph)
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)
dglInt32_t * dgl_node_t_find_V1(dglNodeTraverser_s *pT, dglInt32_t nId)
int dgl_span_depthfirst_spanning_V1_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
int dgl_edgeset_t_initialize_V1(dglGraph_s *pGraph, dglEdgesetTraverser_s *pTraverser, dglInt32_t *pnEdgeset)
void dgl_sp_cache_release_V1(dglGraph_s *pgraph, dglSPCache_s *pCache)
dglInt32_t * dgl_get_edge_V1(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_read_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:232
dglInt32_t * dgl_edge_t_first_V1(dglEdgeTraverser_s *pT)
dglInt32_t * dgl_get_node_V1(dglGraph_s *pgraph, dglInt32_t nId)
dglInt32_t * dgl_node_t_next_V1(dglNodeTraverser_s *pT)
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:76
dglInt32_t * dgl_edgeset_t_first_V1(dglEdgesetTraverser_s *pTraverser)
int dgl_node_t_initialize_V1(dglGraph_s *pGraph, dglNodeTraverser_s *pT)
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:61
int dgl_sp_cache_initialize_V1(dglGraph_s *pgraph, dglSPCache_s *pCache, dglInt32_t nStart)
int dgl_span_depthfirst_spanning_V1_FLAT(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_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_flatten_V1(dglGraph_s *pgraph)
void dgl_edgeset_t_release_V1(dglEdgesetTraverser_s *pTraverser)
dglInt32_t * dgl_getnode_outedgeset_V1(dglGraph_s *pgraph, dglInt32_t *pnode)
int dgl_edge_t_initialize_V1(dglGraph_s *pGraph, dglEdgeTraverser_s *pTraverser, dglEdgePrioritizer_s *pEP)
int dgl_minimum_spanning_V1(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v1.c:90
int dgl_span_minimum_spanning_V1_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
int dgl_del_edge_V1(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_del_node_V1(dglGraph_s *pgraph, dglInt32_t nId)
void dgl_edge_t_release_V1(dglEdgeTraverser_s *pTraverser)
int dgl_release_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:117
int dgl_span_minimum_spanning_V1_TREE(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
long dglInt32_t
Definition: type.h:36