GRASS Programmer's Manual
6.4.2(2012)
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Pages
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_GRAPH_V2_H_
24
#define _DGL_GRAPH_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 ) (sizeof( dglInt32_t ) * DGL_IN_SIZE_v2 + (nattr) )
40
#define DGL_NODE_WSIZE_v2( nattr ) (DGL_NODE_SIZEOF_v2( nattr ) / sizeof(dglInt32_t) )
41
#define DGL_NODE_ALLOC_v2( nattr ) (malloc( DGL_NODE_SIZEOF_v2( nattr ) ) )
42
43
#define DGL_NODE_ID_v2(p) ((p)[DGL_IN_NODEID_v2])
44
#define DGL_NODE_STATUS_v2(p) ((p)[DGL_IN_STATUS_v2])
45
#define DGL_NODE_EDGESET_OFFSET_v2(p) ((p)[DGL_IN_EDGESET_OFFSET_v2])
46
#define DGL_NODE_ATTR_PTR_v2(p) ((p) + DGL_IN_ATTR_v2)
47
48
/*
49
* Edgeset macros - addresses in a flat edge-area
50
*/
51
#define DGL_ILA_TOCNT_v2 0
52
#define DGL_ILA_SIZE_v2 1
53
#define DGL_ILA_TOARR_v2 DGL_ILA_SIZE_v2
54
55
#define DGL_EDGESET_SIZEOF_v2(C, lattr) (sizeof( dglInt32_t ) * ((C) + 1))
56
#define DGL_EDGESET_WSIZE_v2(C, lattr) (DGL_EDGESET_SIZEOF_v2(C, lattr) / sizeof(dglInt32_t))
57
#define DGL_EDGESET_ALLOC_v2(C, lattr) (malloc(DGL_EDGESET_SIZEOF_v2(C, lattr)))
58
#define DGL_EDGESET_REALLOC_v2(P, C, lattr) (realloc(P , DGL_EDGESET_SIZEOF_v2(C, lattr)))
59
60
#define DGL_EDGESET_EDGECOUNT_v2(p) ((p)[DGL_ILA_TOCNT_v2])
61
#define DGL_EDGESET_EDGEARRAY_PTR_v2(p) ((p) + DGL_ILA_TOARR_v2)
62
#define DGL_EDGESET_EDGE_PTR_v2(pgrp,p,i) DGL_EDGEBUFFER_SHIFT_v2(pgrp,*((p) + DGL_ILA_TOARR_v2 + (i)))
63
64
/*
65
* Edge macros - addresses in a flat edge
66
*/
67
#define DGL_IL_HEAD_OFFSET_v2 0
68
#define DGL_IL_TAIL_OFFSET_v2 1
69
#define DGL_IL_STATUS_v2 2
70
#define DGL_IL_COST_v2 3
71
#define DGL_IL_ID_v2 4
72
#define DGL_IL_ATTR_v2 5
73
#define DGL_IL_SIZE_v2 DGL_IL_ATTR_v2
74
75
#define DGL_EDGE_SIZEOF_v2( lattr ) (sizeof( dglInt32_t ) * DGL_IL_SIZE_v2 + (lattr))
76
#define DGL_EDGE_WSIZE_v2( lattr ) (DGL_EDGE_SIZEOF_v2( lattr ) / sizeof( dglInt32_t ))
77
#define DGL_EDGE_ALLOC_v2( lattr ) (malloc( DGL_EDGE_SIZEOF_v2( lattr ) ))
78
79
#define DGL_EDGE_HEADNODE_OFFSET_v2(p) ((p)[DGL_IL_HEAD_OFFSET_v2])
80
#define DGL_EDGE_TAILNODE_OFFSET_v2(p) ((p)[DGL_IL_TAIL_OFFSET_v2])
81
#define DGL_EDGE_STATUS_v2(p) ((p)[DGL_IL_STATUS_v2])
82
#define DGL_EDGE_COST_v2(p) ((p)[DGL_IL_COST_v2])
83
#define DGL_EDGE_ID_v2(p) ((p)[DGL_IL_ID_v2])
84
#define DGL_EDGE_ATTR_PTR_v2(p) ((p) + DGL_IL_ATTR_v2)
85
#define DGL_EDGE_HEADNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\
86
DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_HEADNODE_OFFSET_v2(pl)):\
87
DGL_EDGE_HEADNODE_OFFSET_v2(pl))
88
#define DGL_EDGE_TAILNODE_ID_v2(pgrp,pl) ((pgrp->Flags&1)?\
89
DGL_NODE_ID_v2(pgrp->pNodeBuffer+DGL_EDGE_TAILNODE_OFFSET_v2(pl)):\
90
DGL_EDGE_TAILNODE_OFFSET_v2(pl))
91
92
/*
93
* Scan a node buffer
94
*/
95
#define DGL_FOREACH_NODE_v2(pgrp,pn) for((pn)=(dglInt32_t*)(pgrp)->pNodeBuffer;\
96
(pgrp)->pNodeBuffer && (pn)<(dglInt32_t*)((pgrp)->pNodeBuffer+(pgrp)->iNodeBuffer);\
97
(pn)+=DGL_NODE_WSIZE_v2((pgrp)->NodeAttrSize))
98
/*
99
* Scan a edgeset
100
*/
101
#define DGL_FOREACH_EDGE_v2(pgrp,pla,pl,il)\
102
for((il)=0, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il);\
103
(il)<DGL_EDGESET_EDGECOUNT_v2(pla);\
104
(il)++, (pl)=DGL_EDGESET_EDGE_PTR_v2(pgrp,pla,il))
105
/*
106
* Node Buffer Utilities
107
*/
108
#define DGL_NODEBUFFER_SHIFT_v2(pgrp,o) ((dglInt32_t*)((pgrp)->pNodeBuffer + (o)))
109
#define DGL_NODEBUFFER_OFFSET_v2(pgrp,p) ((dglInt32_t)p - (dglInt32_t)(pgrp)->pNodeBuffer)
110
111
/*
112
* Edge Buffer Utilities
113
*/
114
#define DGL_EDGEBUFFER_SHIFT_v2(pgrp,o) ((dglInt32_t*)((pgrp)->pEdgeBuffer + (o)))
115
#define DGL_EDGEBUFFER_OFFSET_v2(pgrp,pl) ((dglInt32_t)pl - (dglInt32_t)(pgrp)->pEdgeBuffer)
116
117
118
119
120
int
dgl_add_edge_V2
(
dglGraph_s
* pgraph,
121
dglInt32_t
nHead,
122
dglInt32_t
nTail,
123
dglInt32_t
nCost,
124
dglInt32_t
nEdge,
125
void
*pvHeadAttr,
126
void
*pvTailAttr,
void
*pvEdgeAttr,
dglInt32_t
nFlags);
127
128
int
dgl_unflatten_V2
(
dglGraph_s
* pgraph);
129
int
dgl_flatten_V2
(
dglGraph_s
* pgraph);
130
int
dgl_initialize_V2
(
dglGraph_s
* pgraph);
131
int
dgl_release_V2
(
dglGraph_s
* pgraph);
132
int
dgl_write_V2
(
dglGraph_s
* pgraph,
int
fd);
133
int
dgl_read_V2
(
dglGraph_s
* pgraph,
int
fd,
int
version
);
134
135
136
int
dgl_sp_cache_initialize_V2
(
dglGraph_s
* pgraph,
dglSPCache_s
* pCache,
137
dglInt32_t
nStart);
138
void
dgl_sp_cache_release_V2
(
dglGraph_s
* pgraph,
dglSPCache_s
* pCache);
139
140
int
dgl_dijkstra_V2_TREE
(
dglGraph_s
* pgraph,
141
dglSPReport_s
** ppReport,
142
dglInt32_t
* pDistance,
143
dglInt32_t
nStart,
144
dglInt32_t
nDestination,
145
dglSPClip_fn
fnClip,
146
void
*pvClipArg,
dglSPCache_s
* pCache);
147
int
dgl_dijkstra_V2_FLAT
(
dglGraph_s
* pgraph,
148
dglSPReport_s
** ppReport,
149
dglInt32_t
* pDistance,
150
dglInt32_t
nStart,
151
dglInt32_t
nDestination,
152
dglSPClip_fn
fnClip,
153
void
*pvClipArg,
dglSPCache_s
* pCache);
154
int
dgl_dijkstra_V2
(
dglGraph_s
* pgraph,
155
dglSPReport_s
** ppReport,
156
dglInt32_t
* pDistance,
157
dglInt32_t
nStart,
158
dglInt32_t
nDestination,
159
dglSPClip_fn
fnClip,
160
void
*pvClipArg,
dglSPCache_s
* pCache);
161
162
163
int
dgl_span_depthfirst_spanning_V2_TREE
(
dglGraph_s
* pgraphIn,
164
dglGraph_s
* pgraphOut,
165
dglInt32_t
nVertex,
166
void
*pvVisited,
167
dglSpanClip_fn
fnClip,
168
void
*pvClipArg);
169
int
dgl_span_depthfirst_spanning_V2_FLAT
(
dglGraph_s
* pgraphIn,
170
dglGraph_s
* pgraphOut,
171
dglInt32_t
nVertex,
172
void
*pvVisited,
173
dglSpanClip_fn
fnClip,
174
void
*pvClipArg);
175
int
dgl_depthfirst_spanning_V2
(
dglGraph_s
* pgraphIn,
176
dglGraph_s
* pgraphOut,
177
dglInt32_t
nVertex,
178
void
*pvVisited,
179
dglSpanClip_fn
fnClip,
void
*pvClipArg);
180
181
182
int
dgl_span_minimum_spanning_V2_TREE
(
dglGraph_s
* pgraphIn,
183
dglGraph_s
* pgraphOut,
184
dglInt32_t
nVertex,
185
dglSpanClip_fn
fnClip,
void
*pvClipArg);
186
int
dgl_span_minimum_spanning_V2_FLAT
(
dglGraph_s
* pgraphIn,
187
dglGraph_s
* pgraphOut,
188
dglInt32_t
nVertex,
189
dglSpanClip_fn
fnClip,
void
*pvClipArg);
190
int
dgl_minimum_spanning_V2
(
dglGraph_s
* pgraphIn,
191
dglGraph_s
* pgraphOut,
192
dglInt32_t
nVertex,
193
dglSpanClip_fn
fnClip,
void
*pvClipArg);
194
195
196
int
dgl_add_node_V2
(
dglGraph_s
* pgraph,
197
dglInt32_t
nId,
void
*pvNodeAttr,
dglInt32_t
nFlags);
198
int
dgl_del_node_outedge_V2
(
dglGraph_s
* pgraph,
dglInt32_t
nNode,
199
dglInt32_t
nEdge);
200
int
dgl_del_node_inedge_V2
(
dglGraph_s
* pgraph,
dglInt32_t
nNode,
201
dglInt32_t
nEdge);
202
int
dgl_del_node_V2
(
dglGraph_s
* pgraph,
dglInt32_t
nId);
203
dglInt32_t
*
dgl_get_node_V2
(
dglGraph_s
* pgraph,
dglInt32_t
nId);
204
205
dglInt32_t
*
dgl_get_edge_V2
(
dglGraph_s
* pgraph,
dglInt32_t
nId);
206
int
dgl_del_edge_V2
(
dglGraph_s
* pgraph,
dglInt32_t
nId);
207
208
dglInt32_t
*
dgl_getnode_outedgeset_V2
(
dglGraph_s
* pgraph,
209
dglInt32_t
* pnode);
210
dglInt32_t
*
dgl_getnode_inedgeset_V2
(
dglGraph_s
* pgraph,
dglInt32_t
* pnode);
211
212
/*
213
* Node Traversing
214
*/
215
int
dgl_node_t_initialize_V2
(
dglGraph_s
* pGraph,
dglNodeTraverser_s
* pT);
216
void
dgl_node_t_release_V2
(
dglNodeTraverser_s
* pT);
217
dglInt32_t
*
dgl_node_t_first_V2
(
dglNodeTraverser_s
* pT);
218
dglInt32_t
*
dgl_node_t_next_V2
(
dglNodeTraverser_s
* pT);
219
dglInt32_t
*
dgl_node_t_find_V2
(
dglNodeTraverser_s
* pT,
dglInt32_t
nId);
220
221
222
/*
223
* Edgeset Traversing
224
*/
225
int
dgl_edgeset_t_initialize_V2
(
dglGraph_s
* pGraph,
226
dglEdgesetTraverser_s
* pTraverser,
227
dglInt32_t
* pnEdgeset);
228
void
dgl_edgeset_t_release_V2
(
dglEdgesetTraverser_s
* pTraverser);
229
dglInt32_t
*
dgl_edgeset_t_first_V2
(
dglEdgesetTraverser_s
* pTraverser);
230
dglInt32_t
*
dgl_edgeset_t_next_V2
(
dglEdgesetTraverser_s
* pTraverser);
231
232
233
int
dgl_edge_t_initialize_V2
(
dglGraph_s
* pGraph,
234
dglEdgeTraverser_s
* pTraverser,
235
dglEdgePrioritizer_s
* pEP);
236
void
dgl_edge_t_release_V2
(
dglEdgeTraverser_s
* pTraverser);
237
dglInt32_t
*
dgl_edge_t_first_V2
(
dglEdgeTraverser_s
* pT);
238
dglInt32_t
*
dgl_edge_t_next_V2
(
dglEdgeTraverser_s
* pT);
239
240
241
#endif
lib
vector
dglib
graph_v2.h
Generated on Wed Jun 6 2012 14:04:24 for GRASS Programmer's Manual by
1.8.1