GRASS Programmer's Manual
6.4.3(2013)-r
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Properties
Macros
Pages
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_GRAPH_V1_H_
24
#define _DGL_GRAPH_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)p - (dglInt32_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)pl - (dglInt32_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
160
int
dgl_span_depthfirst_spanning_V1_TREE
(
dglGraph_s
* pgraphIn,
161
dglGraph_s
* pgraphOut,
162
dglInt32_t
nVertex,
163
void
*pvVisited,
164
dglSpanClip_fn
fnClip,
165
void
*pvClipArg);
166
int
dgl_span_depthfirst_spanning_V1_FLAT
(
dglGraph_s
* pgraphIn,
167
dglGraph_s
* pgraphOut,
168
dglInt32_t
nVertex,
169
void
*pvVisited,
170
dglSpanClip_fn
fnClip,
171
void
*pvClipArg);
172
int
dgl_depthfirst_spanning_V1
(
dglGraph_s
* pgraphIn,
173
dglGraph_s
* pgraphOut,
174
dglInt32_t
nVertex,
175
void
*pvVisited,
176
dglSpanClip_fn
fnClip,
void
*pvClipArg);
177
178
179
int
dgl_span_minimum_spanning_V1_TREE
(
dglGraph_s
* pgraphIn,
180
dglGraph_s
* pgraphOut,
181
dglInt32_t
nVertex,
182
dglSpanClip_fn
fnClip,
void
*pvClipArg);
183
int
dgl_span_minimum_spanning_V1_FLAT
(
dglGraph_s
* pgraphIn,
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);
196
dglInt32_t
*
dgl_get_node_V1
(
dglGraph_s
* pgraph,
dglInt32_t
nId);
197
198
dglInt32_t
*
dgl_get_edge_V1
(
dglGraph_s
* pgraph,
dglInt32_t
nId);
199
int
dgl_del_edge_V1
(
dglGraph_s
* pgraph,
dglInt32_t
nId);
200
201
dglInt32_t
*
dgl_getnode_outedgeset_V1
(
dglGraph_s
* pgraph,
202
dglInt32_t
* pnode);
203
204
/*
205
* Node Traversing
206
*/
207
int
dgl_node_t_initialize_V1
(
dglGraph_s
* pGraph,
dglNodeTraverser_s
* pT);
208
void
dgl_node_t_release_V1
(
dglNodeTraverser_s
* pT);
209
dglInt32_t
*
dgl_node_t_first_V1
(
dglNodeTraverser_s
* pT);
210
dglInt32_t
*
dgl_node_t_next_V1
(
dglNodeTraverser_s
* pT);
211
dglInt32_t
*
dgl_node_t_find_V1
(
dglNodeTraverser_s
* pT,
dglInt32_t
nId);
212
213
214
/*
215
* Edgeset Traversing
216
*/
217
int
dgl_edgeset_t_initialize_V1
(
dglGraph_s
* pGraph,
218
dglEdgesetTraverser_s
* pTraverser,
219
dglInt32_t
* pnEdgeset);
220
void
dgl_edgeset_t_release_V1
(
dglEdgesetTraverser_s
* pTraverser);
221
dglInt32_t
*
dgl_edgeset_t_first_V1
(
dglEdgesetTraverser_s
* pTraverser);
222
dglInt32_t
*
dgl_edgeset_t_next_V1
(
dglEdgesetTraverser_s
* pTraverser);
223
224
225
int
dgl_edge_t_initialize_V1
(
dglGraph_s
* pGraph,
226
dglEdgeTraverser_s
* pTraverser,
227
dglEdgePrioritizer_s
* pEP);
228
void
dgl_edge_t_release_V1
(
dglEdgeTraverser_s
* pTraverser);
229
dglInt32_t
*
dgl_edge_t_first_V1
(
dglEdgeTraverser_s
* pT);
230
dglInt32_t
*
dgl_edge_t_next_V1
(
dglEdgeTraverser_s
* pT);
231
232
233
234
235
#endif
lib
vector
dglib
graph_v1.h
Generated on Sat Oct 5 2013 12:11:08 for GRASS Programmer's Manual by
1.8.4