GRASS 8 Programmer's Manual 8.6.0dev(2026)-f6f2c534ea
Loading...
Searching...
No Matches
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
134 void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags);
135
140int dgl_write_V1(dglGraph_s *pgraph, int fd);
141int dgl_read_V1(dglGraph_s *pgraph, int fd);
142
146
159
162 dglInt32_t nVertex, void *pvVisited,
164 void *pvClipArg);
167 dglInt32_t nVertex, void *pvVisited,
169 void *pvClipArg);
171 dglInt32_t nVertex, void *pvVisited,
173
182 void *pvClipArg);
183
188
191
193
194/*
195 * Node Traversing
196 */
202
203/*
204 * Edgeset Traversing
205 */
208 dglInt32_t *pnEdgeset);
212
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)
dglInt32_t * dgl_node_t_first_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_edge_t_first_V1(dglEdgeTraverser_s *pT)
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)
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)
int dgl_read_V1(dglGraph_s *pgraph, int fd)
Definition graph_v1.c:232
dglInt32_t * dgl_node_t_next_V1(dglNodeTraverser_s *pT)
dglInt32_t * dgl_edgeset_t_first_V1(dglEdgesetTraverser_s *pTraverser)
dglInt32_t * dgl_get_node_V1(dglGraph_s *pgraph, dglInt32_t nId)
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_getnode_outedgeset_V1(dglGraph_s *pgraph, dglInt32_t *pnode)
dglInt32_t * dgl_node_t_find_V1(dglNodeTraverser_s *pT, dglInt32_t nId)
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)
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)
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
dglInt32_t * dgl_edge_t_next_V1(dglEdgeTraverser_s *pT)
dglInt32_t * dgl_edgeset_t_next_V1(dglEdgesetTraverser_s *pTraverser)
int dgl_span_minimum_spanning_V1_FLAT(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
dglInt32_t * dgl_get_edge_V1(dglGraph_s *pgraph, dglInt32_t nId)
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