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.h
Go to the documentation of this file.
1
/*
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_H_
24
#define _DGL_GRAPH_H_
25
26
#ifdef DGL_STATS
27
#include <time.h>
28
#endif
29
30
#include "
heap.h
"
31
#include "
tree.h
"
32
33
/*
34
* Graph State bitmask - returned by dglGet_State() function
35
*/
36
#define DGL_GS_FLAT 0x1
/* otherwise is TREE */
37
38
/*
39
* Graph Family
40
*/
41
#define DGL_GF_COMPLETE 0x1
42
#define DGL_GF_BIPARTITE 0x2
43
#define DGL_GF_REGULAR 0x4
44
#define DGL_GF_BOUQUET 0x8
45
#define DGL_GF_DIPOLE 0x10
46
#define DGL_GF_PATH 0x20
47
#define DGL_GF_CYCLE 0x40
48
49
/*
50
* Graph Options
51
*/
52
#define DGL_GO_EdgePrioritize_COST 0x10
53
#define DGL_GO_EdgePrioritize_ATTR 0x20
54
#define DGL_GO_NodePrioritize_ATTR 0x40
55
56
57
/*
58
* Node Status bitmask - returned by dglNodeGet_Status()
59
*/
60
#define DGL_NS_HEAD 0x1
/* node exists as at least one edge's head (static) */
61
#define DGL_NS_TAIL 0x2
/* node exists as at least one edge's tail (static) */
62
#define DGL_NS_ALONE 0x4
/* node is a component */
63
64
65
/*
66
* Edge Status bitmask - returned by dglEdgeGet_Status()
67
*/
68
#define DGL_ES_DIRECTED 0x1
/* force edge to be directed */
69
70
71
/*
72
* Endianess Values - returned by dglGet_Endianess() function
73
*/
74
#define DGL_ENDIAN_BIG 1
75
#define DGL_ENDIAN_LITTLE 2
76
77
78
/*
79
* miscellaneous
80
*/
81
/* add-edge/add-node flags */
82
#define DGL_STRONGCONNECT 0x1
83
#define DGL_ALONE 0x2
84
#define DGL_MERGE_EDGE 0x4
85
/* */
86
87
88
89
/*
90
* Shortest Path clip definitions
91
*/
92
typedef
struct
_dglSPClipInput
93
{
94
dglInt32_t
*
pnPrevEdge
;
95
dglInt32_t
*
pnNodeFrom
;
96
dglInt32_t
*
pnEdge
;
97
dglInt32_t
*
pnNodeTo
;
98
dglInt32_t
nFromDistance
;
99
100
}
dglSPClipInput_s
;
101
102
typedef
struct
_dglSPClipOutput
103
{
104
dglInt32_t
nEdgeCost
;
105
106
}
dglSPClipOutput_s
;
107
108
109
/*
110
* Spanning clip definitions
111
*/
112
typedef
struct
_dglSpanClipInput
113
{
114
dglInt32_t
*
pnNodeFrom
;
115
dglInt32_t
*
pnEdge
;
116
dglInt32_t
*
pnNodeTo
;
117
118
}
dglSpanClipInput_s
;
119
120
typedef
struct
_dglSpanClipOutput
121
{
122
dglInt32_t
*
pnReserved
;
123
124
}
dglSpanClipOutput_s
;
125
126
127
struct
dglGraph;
128
129
/*
130
* Node Prioritizer
131
*/
132
typedef
struct
133
{
134
void
*
pvAVL
;
135
}
dglNodePrioritizer_s
;
136
137
/*
138
* Edge Prioritizer
139
*/
140
typedef
struct
141
{
142
int
cEdge
;
143
int
iEdge
;
144
dglTreeEdgePri32_s
*
pEdgePri32Item
;
145
void
*
pvAVL
;
146
}
dglEdgePrioritizer_s
;
147
148
149
/*
150
* The graph context
151
*/
152
typedef
struct
_dglGraph
153
{
154
int
iErrno
;
155
156
dglByte_t
Version
;
157
dglByte_t
Endian
;
158
dglInt32_t
NodeAttrSize
;
159
dglInt32_t
EdgeAttrSize
;
160
dglInt32_t
aOpaqueSet
[16];
161
162
dglInt32_t
cNode
;
163
dglInt32_t
cHead
;
164
dglInt32_t
cTail
;
165
dglInt32_t
cAlone
;
166
dglInt32_t
cEdge
;
167
dglInt64_t
nnCost
;
168
169
dglInt32_t
Flags
;
170
dglInt32_t
nFamily
;
171
dglInt32_t
nOptions
;
172
173
void
*
pNodeTree
;
174
void
*
pEdgeTree
;
175
dglByte_t
*
pNodeBuffer
;
176
dglInt32_t
iNodeBuffer
;
177
dglByte_t
*
pEdgeBuffer
;
178
dglInt32_t
iEdgeBuffer
;
179
180
181
dglEdgePrioritizer_s
edgePrioritizer
;
182
dglNodePrioritizer_s
nodePrioritizer
;
183
184
185
/* so far statistics are only computed by dglAddEdge() */
186
#ifdef DGL_STATS
187
clock_t clkAddEdge;
/* cycles spent during the last addedge execution */
188
int
cAddEdge;
/* # of calls to dglAddEdge() */
189
clock_t clkNodeTree;
/* cycles spent in accessing the node binary tree */
190
int
cNodeTree;
/* # of probes in the node tree */
191
#endif
192
}
193
dglGraph_s
;
194
195
/*
196
* Shortest Path clip function type
197
*/
198
typedef
int (*
dglSPClip_fn
) (
dglGraph_s
*,
dglSPClipInput_s
*,
199
dglSPClipOutput_s
*,
void
*);
200
201
/*
202
* Spanning clip function type
203
*/
204
typedef
int (*
dglSpanClip_fn
) (
dglGraph_s
*,
dglGraph_s
*,
205
dglSpanClipInput_s
*,
dglSpanClipOutput_s
*,
206
void
*);
207
208
/*
209
* An ARC defined as : from-node, to-node, edge pointer, to-node-distance (from the path starting node)
210
*/
211
typedef
struct
_dglSPArc
212
{
213
dglInt32_t
nFrom
;
214
dglInt32_t
nTo
;
215
dglInt32_t
*
pnEdge
;
216
dglInt32_t
nDistance
;
217
}
218
dglSPArc_s
;
219
220
/*
221
* Shortest Path Report
222
*/
223
typedef
struct
_dglSPReport
224
{
225
dglInt32_t
nStartNode
;
226
dglInt32_t
nDestinationNode
;
227
dglInt32_t
nDistance
;
228
dglInt32_t
cArc
;
229
dglSPArc_s
*
pArc
;
230
}
231
dglSPReport_s
;
232
233
/*
234
* Shortest Path Cache
235
*/
236
typedef
struct
237
{
238
dglInt32_t
nStartNode
;
239
dglHeap_s
NodeHeap
;
240
void
*
pvVisited
;
241
void
*
pvPredist
;
242
}
243
dglSPCache_s
;
244
245
/*
246
* Node Traverser
247
*/
248
typedef
struct
249
{
250
dglGraph_s
*
pGraph
;
251
void
*
pvAVLT
;
252
dglInt32_t
*
pnNode
;
253
}
dglNodeTraverser_s
;
254
255
/*
256
* Edgeset Traverser
257
*/
258
typedef
struct
259
{
260
dglGraph_s
*
pGraph
;
261
dglInt32_t
*
pnEdgeset
;
262
void
*
pvCurrentItem
;
263
int
cEdge,
iEdge
;
264
}
dglEdgesetTraverser_s
;
265
266
/*
267
* Edge Traverser
268
*/
269
typedef
struct
270
{
271
dglGraph_s
*
pGraph
;
272
void
*
pvAVLT
;
273
dglInt32_t
*
pnEdge
;
274
dglEdgePrioritizer_s
*
pEdgePrioritizer
;
275
}
dglEdgeTraverser_s
;
276
277
278
/*
279
* Error codes returned by dglError
280
*/
281
#define DGL_ERR_BadVersion 1
282
#define DGL_ERR_BadNodeType 2
283
#define DGL_ERR_MemoryExhausted 3
284
#define DGL_ERR_HeapError 4
285
#define DGL_ERR_UndefinedMethod 5
286
#define DGL_ERR_Write 6
287
#define DGL_ERR_Read 7
288
#define DGL_ERR_NotSupported 8
289
#define DGL_ERR_UnknownByteOrder 9
290
#define DGL_ERR_HeadNodeNotFound 10
291
#define DGL_ERR_TailNodeNotFound 11
292
#define DGL_ERR_BadEdge 12
293
#define DGL_ERR_BadOnFlatGraph 13
294
#define DGL_ERR_BadOnTreeGraph 14
295
#define DGL_ERR_NodeNotFound 15
296
#define DGL_ERR_TreeSearchError 16
297
#define DGL_ERR_UnexpectedNullPointer 17
298
#define DGL_ERR_VersionNotSupported 18
299
#define DGL_ERR_EdgeNotFound 19
300
#define DGL_ERR_NodeAlreadyExist 20
301
#define DGL_ERR_NodeIsAComponent 21
302
#define DGL_ERR_EdgeAlreadyExist 22
303
#define DGL_ERR_BadArgument 23
304
305
306
307
/*
308
* graph context management
309
*/
310
int
dglInitialize
(
dglGraph_s
* pGraph,
dglByte_t
Version,
311
dglInt32_t
NodeAttrSize,
dglInt32_t
EdgeAttrSize,
312
dglInt32_t
* pOpaqueSet);
313
int
dglRelease
(
dglGraph_s
* pGraph);
314
int
dglUnflatten
(
dglGraph_s
* pGraph);
315
int
dglFlatten
(
dglGraph_s
* pGraph);
316
void
dglResetStats
(
dglGraph_s
* pgraph);
317
318
/*
319
* node management
320
*/
321
dglInt32_t
*
dglGetNode
(
dglGraph_s
* pGraph,
dglInt32_t
nNodeId);
322
int
dglAddNode
(
dglGraph_s
* pGraph,
323
dglInt32_t
nNodeId,
void
*pvNodeAttr,
dglInt32_t
nFlags);
324
int
dglDelNode
(
dglGraph_s
* pGraph,
dglInt32_t
nNodeId);
325
dglInt32_t
dglNodeGet_Id
(
dglGraph_s
* pGraph,
dglInt32_t
* pnNode);
326
dglInt32_t
*
dglNodeGet_OutEdgeset
(
dglGraph_s
* pGraph,
dglInt32_t
* pnNode);
327
dglInt32_t
*
dglNodeGet_InEdgeset
(
dglGraph_s
* pGraph,
dglInt32_t
* pnNode);
328
dglInt32_t
dglNodeGet_Status
(
dglGraph_s
* pGraph,
dglInt32_t
* pnNode);
329
dglInt32_t
*
dglNodeGet_Attr
(
dglGraph_s
* pGraph,
dglInt32_t
* pnNode);
330
void
dglNodeSet_Attr
(
dglGraph_s
* pGraph,
dglInt32_t
* pnNode,
331
dglInt32_t
* pnAttr);
332
int
dglNodeGet_InDegree
(
dglGraph_s
* pGraph,
dglInt32_t
* pnNode);
333
int
dglNodeGet_OutDegree
(
dglGraph_s
* pGraph,
dglInt32_t
* pnNode);
334
int
dglNodeGet_Valence
(
dglGraph_s
* pGraph,
dglInt32_t
* pnNode);
335
336
/*
337
* edge management
338
*/
339
dglInt32_t
dglEdgesetGet_EdgeCount
(
dglGraph_s
* pGraph,
340
dglInt32_t
* pnOutEdgeset);
341
342
dglInt32_t
dglEdgeGet_Id
(
dglGraph_s
* pGraph,
dglInt32_t
* pnEdge);
343
dglInt32_t
dglEdgeGet_Cost
(
dglGraph_s
* pGraph,
dglInt32_t
* pnEdge);
344
dglInt32_t
*
dglEdgeGet_Head
(
dglGraph_s
* pGraph,
dglInt32_t
* pnEdge);
345
dglInt32_t
*
dglEdgeGet_Tail
(
dglGraph_s
* pGraph,
dglInt32_t
* pnEdge);
346
dglInt32_t
*
dglEdgeGet_Attr
(
dglGraph_s
* pGraph,
dglInt32_t
* pnEdge);
347
int
dglEdgeSet_Attr
(
dglGraph_s
* pGraph,
dglInt32_t
* pnAttr,
348
dglInt32_t
* pnEdge);
349
350
dglInt32_t
*
dglGetEdge
(
dglGraph_s
* pGraph,
dglInt32_t
nEdgeId);
351
352
int
dglDelEdge
(
dglGraph_s
* pGraph,
dglInt32_t
nEdgeId);
353
354
int
dglAddEdge
(
dglGraph_s
* pGraph,
355
dglInt32_t
nHead,
356
dglInt32_t
nTail,
dglInt32_t
nCost,
dglInt32_t
nEdge);
357
358
int
dglAddEdgeX
(
dglGraph_s
* pGraph,
359
dglInt32_t
nHead,
360
dglInt32_t
nTail,
361
dglInt32_t
nCost,
362
dglInt32_t
nEdge,
363
void
*pvFnodeAttr,
364
void
*pvTnodeAttr,
void
*pvEdgeAttr,
dglInt32_t
nFlags);
365
366
367
/*
368
* graph I/O
369
*/
370
int
dglWrite
(
dglGraph_s
* pGraph,
int
fd);
371
int
dglRead
(
dglGraph_s
* pGraph,
int
fd);
372
373
typedef
struct
374
{
375
dglGraph_s
*
pG
;
376
int
nState
;
377
int
fSwap
;
378
int
cb
;
379
int
ib
;
380
unsigned
char
*
pb
;
381
unsigned
char
ab[118];
/* 118 = graph header size */
382
}
dglIOContext_s
;
383
384
int
dglIOContextInitialize
(
dglGraph_s
*,
dglIOContext_s
*);
385
void
dglIOContextRelease
(
dglIOContext_s
*);
386
387
/*
388
* Chunked Write callback function type
389
*/
390
typedef
int (*
dglWriteChunk_fn
) (
dglGraph_s
*,
unsigned
char
*pbChunk,
391
int
cbChunk,
void
*pvArg);
392
393
int
dglWriteChunk
(
dglIOContext_s
*,
dglWriteChunk_fn
,
void
*pvArg);
394
int
dglReadChunk
(
dglIOContext_s
*,
dglByte_t
* pbChunk,
int
cbChunk);
395
396
397
398
/*
399
* Algorithms
400
*/
401
int
dglShortestPath
(
dglGraph_s
* pGraph,
402
dglSPReport_s
** ppReport,
403
dglInt32_t
nStartNode,
404
dglInt32_t
nDestinationNode,
405
dglSPClip_fn
fnClip,
406
void
*pvClipArg,
dglSPCache_s
* pCache);
407
int
dglShortestPathGraph
(
dglGraph_s
* pGraph,
408
dglGraph_s
* pGraphOut,
409
dglInt32_t
nStartNode,
410
dglInt32_t
nDestinationNode,
411
dglSPClip_fn
fnClip,
412
void
*pvClipArg,
dglSPCache_s
* pCache);
413
int
dglShortestDistance
(
dglGraph_s
* pGraph,
414
dglInt32_t
* pnDistance,
415
dglInt32_t
nStartNode,
416
dglInt32_t
nDestinationNode,
417
dglSPClip_fn
fnClip,
418
void
*pvClipArg,
dglSPCache_s
* pCache);
419
int
dglShortestDistanceGraph
(
dglGraph_s
* pGraph,
420
dglGraph_s
* pGraphOut,
421
dglInt32_t
nStartNode,
422
dglInt32_t
nDestinationNode,
423
dglSPClip_fn
fnClip,
424
void
*pvClipArg,
dglSPCache_s
* pCache);
425
426
int
dglInitializeSPCache
(
dglGraph_s
* pgraph,
dglSPCache_s
* pCache);
427
void
dglReleaseSPCache
(
dglGraph_s
* pgraph,
dglSPCache_s
* pCache);
428
void
dglFreeSPReport
(
dglGraph_s
* pGraph,
dglSPReport_s
* pSPReport);
429
430
int
dglDepthSpanning
(
dglGraph_s
* pgraphInput,
431
dglGraph_s
* pgraphOutput,
432
dglInt32_t
nVertexNode,
433
dglSpanClip_fn
fnClip,
void
*pvClipArg);
434
435
int
dglDepthComponents
(
dglGraph_s
* pgraphInput,
436
dglGraph_s
* pgraphComponents,
437
int
cgraphComponents,
438
dglSpanClip_fn
fnClip,
void
*pvClipArg);
439
440
int
dglMinimumSpanning
(
dglGraph_s
* pgraphInput,
441
dglGraph_s
* pgraphOutput,
442
dglInt32_t
nVertexNode,
443
dglSpanClip_fn
fnClip,
void
*pvClipArg);
444
445
/*
446
* error management
447
*/
448
int
dglErrno
(
dglGraph_s
* pgraph);
449
char
*
dglStrerror
(
dglGraph_s
* pgraph);
450
451
/*
452
* graph property hiders
453
*/
454
int
dglGet_Version
(
dglGraph_s
* pGraph);
455
void
dglSet_Version
(
dglGraph_s
* pGraph,
int
Version);
456
int
dglGet_Endianess
(
dglGraph_s
* pGraph);
457
int
dglGet_NodeAttrSize
(
dglGraph_s
* pGraph);
458
int
dglGet_EdgeAttrSize
(
dglGraph_s
* pGraph);
459
int
dglGet_NodeCount
(
dglGraph_s
* pGraph);
460
int
dglGet_HeadNodeCount
(
dglGraph_s
* pGraph);
461
int
dglGet_TailNodeCount
(
dglGraph_s
* pGraph);
462
int
dglGet_AloneNodeCount
(
dglGraph_s
* pGraph);
463
int
dglGet_EdgeCount
(
dglGraph_s
* pGraph);
464
int
dglGet_State
(
dglGraph_s
* pGraph);
465
dglInt32_t
*
dglGet_Opaque
(
dglGraph_s
* pGraph);
466
void
dglSet_Opaque
(
dglGraph_s
* pGraph,
dglInt32_t
* pOpaque);
467
int
dglGet_NodeSize
(
dglGraph_s
* pGraph);
468
int
dglGet_EdgeSize
(
dglGraph_s
* pGraph);
469
dglInt64_t
dglGet_Cost
(
dglGraph_s
* pGraph);
470
void
dglSet_Cost
(
dglGraph_s
* pGraph,
dglInt64_t
nnCost);
471
dglInt32_t
dglGet_Family
(
dglGraph_s
* pGraph);
472
void
dglSet_Family
(
dglGraph_s
* pGraph,
dglInt32_t
nFamily);
473
dglInt32_t
dglGet_Options
(
dglGraph_s
* pGraph);
474
void
dglSet_Options
(
dglGraph_s
* pGraph,
dglInt32_t
nOptions);
475
dglEdgePrioritizer_s
*
dglGet_EdgePrioritizer
(
dglGraph_s
* pGraph);
476
dglNodePrioritizer_s
*
dglGet_NodePrioritizer
(
dglGraph_s
* pGraph);
477
478
479
/*
480
* node traverser
481
*/
482
int
dglNode_T_Initialize
(
dglNodeTraverser_s
* pTraverser,
483
dglGraph_s
* pGraph);
484
void
dglNode_T_Release
(
dglNodeTraverser_s
* pTraverser);
485
dglInt32_t
*
dglNode_T_First
(
dglNodeTraverser_s
* pTraverser);
486
dglInt32_t
*
dglNode_T_Last
(
dglNodeTraverser_s
* pTraverser);
487
dglInt32_t
*
dglNode_T_Next
(
dglNodeTraverser_s
* pTraverser);
488
dglInt32_t
*
dglNode_T_Prev
(
dglNodeTraverser_s
* pTraverser);
489
dglInt32_t
*
dglNode_T_Find
(
dglNodeTraverser_s
* pTraverser,
490
dglInt32_t
nNodeId);
491
492
493
/*
494
* edgeset traverser
495
*/
496
int
dglEdgeset_T_Initialize
(
dglEdgesetTraverser_s
* pTraverser,
497
dglGraph_s
* pGraph,
dglInt32_t
* pnEdgeset);
498
void
dglEdgeset_T_Release
(
dglEdgesetTraverser_s
* pTraverser);
499
dglInt32_t
*
dglEdgeset_T_First
(
dglEdgesetTraverser_s
* pTraverser);
500
dglInt32_t
*
dglEdgeset_T_Next
(
dglEdgesetTraverser_s
* pTraverser);
501
502
503
/*
504
* edge traverser
505
*/
506
int
dglEdge_T_Initialize
(
dglEdgeTraverser_s
* pTraverser,
507
dglGraph_s
* pGraph,
508
dglEdgePrioritizer_s
* pEdgePrioritizer);
509
void
dglEdge_T_Release
(
dglEdgeTraverser_s
* pTraverser);
510
dglInt32_t
*
dglEdge_T_First
(
dglEdgeTraverser_s
* pTraverser);
511
dglInt32_t
*
dglEdge_T_Next
(
dglEdgeTraverser_s
* pTraverser);
512
513
#endif
lib
vector
dglib
graph.h
Generated on Sat Oct 5 2013 12:11:08 for GRASS Programmer's Manual by
1.8.4