GRASS Programmer's Manual  6.5.svn(2014)-r66266
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator 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 {
99 
101 
102 typedef struct _dglSPClipOutput
103 {
105 
107 
108 
109 /*
110  * Spanning clip definitions
111  */
112 typedef struct _dglSpanClipInput
113 {
117 
119 
120 typedef struct _dglSpanClipOutput
121 {
123 
125 
126 
127 struct dglGraph;
128 
129 /*
130  * Node Prioritizer
131  */
132 typedef struct
133 {
134  void *pvAVL;
136 
137 /*
138  * Edge Prioritizer
139  */
140 typedef struct
141 {
142  int cEdge;
143  int iEdge;
145  void *pvAVL;
147 
148 
149 /*
150  * The graph context
151  */
152 typedef struct _dglGraph
153 {
154  int iErrno;
155 
161 
168 
172 
173  void *pNodeTree;
174  void *pEdgeTree;
179 
180 
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  */
199  dglSPClipOutput_s *, void *);
200 
201 /*
202  * Spanning clip function type
203  */
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 {
217 }
218 dglSPArc_s;
219 
220 /*
221  * Shortest Path Report
222  */
223 typedef struct _dglSPReport
224 {
230 }
232 
233 /*
234  * Shortest Path Cache
235  */
236 typedef struct
237 {
240  void *pvVisited;
241  void *pvPredist;
242 }
244 
245 /*
246  * Node Traverser
247  */
248 typedef struct
249 {
251  void *pvAVLT;
254 
255 /*
256  * Edgeset Traverser
257  */
258 typedef struct
259 {
263  int cEdge, iEdge;
265 
266 /*
267  * Edge Traverser
268  */
269 typedef struct
270 {
272  void *pvAVLT;
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);
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  */
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 {
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 */
383 
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);
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);
466 void dglSet_Opaque(dglGraph_s * pGraph, dglInt32_t * pOpaque);
467 int dglGet_NodeSize(dglGraph_s * pGraph);
468 int dglGet_EdgeSize(dglGraph_s * pGraph);
470 void dglSet_Cost(dglGraph_s * pGraph, dglInt64_t nnCost);
472 void dglSet_Family(dglGraph_s * pGraph, dglInt32_t nFamily);
474 void dglSet_Options(dglGraph_s * pGraph, dglInt32_t nOptions);
477 
478 
479 /*
480  * node traverser
481  */
483  dglGraph_s * pGraph);
484 void dglNode_T_Release(dglNodeTraverser_s * pTraverser);
490  dglInt32_t nNodeId);
491 
492 
493 /*
494  * edgeset traverser
495  */
497  dglGraph_s * pGraph, dglInt32_t * pnEdgeset);
501 
502 
503 /*
504  * edge traverser
505  */
507  dglGraph_s * pGraph,
508  dglEdgePrioritizer_s * pEdgePrioritizer);
509 void dglEdge_T_Release(dglEdgeTraverser_s * pTraverser);
512 
513 #endif
int dglGet_State(dglGraph_s *pgraph)
Definition: dglib/graph.c:1266
dglInt32_t * dglEdgeGet_Tail(dglGraph_s *pGraph, dglInt32_t *pnEdge)
Definition: dglib/graph.c:494
dglGraph_s * pGraph
Definition: graph.h:271
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:213
dglInt32_t cEdge
Definition: graph.h:166
dglInt32_t * dglNode_T_Prev(dglNodeTraverser_s *pTraverser)
int dglNodeGet_Valence(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:363
dglInt64_t nnCost
Definition: graph.h:167
dglInt32_t Flags
Definition: graph.h:169
struct _dglSpanClipInput dglSpanClipInput_s
int dglShortestPath(dglGraph_s *pGraph, dglSPReport_s **ppReport, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
Definition: dglib/graph.c:785
dglEdgePrioritizer_s edgePrioritizer
Definition: graph.h:181
unsigned char dglByte_t
Definition: type.h:36
dglInt32_t * pnReserved
Definition: graph.h:122
int dglAddEdge(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge)
Definition: dglib/graph.c:610
int dglEdgeset_T_Initialize(dglEdgesetTraverser_s *pT, dglGraph_s *pGraph, dglInt32_t *pnEdgeset)
Definition: dglib/graph.c:1499
struct _dglSpanClipOutput dglSpanClipOutput_s
dglInt32_t * pnEdge
Definition: graph.h:215
FILE * fd
Definition: g3dcolor.c:368
dglInt32_t nFamily
Definition: graph.h:170
dglInt32_t NodeAttrSize
Definition: graph.h:158
dglInt32_t nFromDistance
Definition: graph.h:98
dglInt32_t * pnEdge
Definition: graph.h:273
dglInt32_t * pnEdge
Definition: graph.h:96
dglInt32_t iEdgeBuffer
Definition: graph.h:178
int dglGet_HeadNodeCount(dglGraph_s *pgraph)
Definition: dglib/graph.c:1246
dglNodePrioritizer_s nodePrioritizer
Definition: graph.h:182
dglInt32_t nDistance
Definition: graph.h:216
int dglGet_TailNodeCount(dglGraph_s *pgraph)
Definition: dglib/graph.c:1251
dglInt64_t dglGet_Cost(dglGraph_s *pgraph)
Definition: dglib/graph.c:1311
int dglGet_EdgeAttrSize(dglGraph_s *pgraph)
Definition: dglib/graph.c:1236
int dglAddNode(dglGraph_s *pGraph, dglInt32_t nNodeId, void *pvNodeAttr, dglInt32_t nFlags)
Definition: dglib/graph.c:688
dglTreeEdgePri32_s * pEdgePri32Item
Definition: graph.h:144
void * pNodeTree
Definition: graph.h:173
int dglRead(dglGraph_s *pGraph, int fd)
Definition: dglib/graph.c:755
Definition: heap.h:44
dglInt32_t dglNodeGet_Status(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:234
void * pvAVLT
Definition: graph.h:272
int dglErrno(dglGraph_s *pgraph)
Definition: dglib/graph.c:1155
dglInt32_t * dglEdge_T_First(dglEdgeTraverser_s *pT)
Definition: dglib/graph.c:1468
int dglNode_T_Initialize(dglNodeTraverser_s *pT, dglGraph_s *pGraph)
Definition: dglib/graph.c:1356
struct _dglGraph dglGraph_s
int dglGet_AloneNodeCount(dglGraph_s *pgraph)
Definition: dglib/graph.c:1256
unsigned char * pb
Definition: graph.h:380
int dglShortestDistance(dglGraph_s *pGraph, dglInt32_t *pnDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
Definition: dglib/graph.c:817
int dglGet_Version(dglGraph_s *pgraph)
Definition: dglib/graph.c:1217
int dglNodeGet_OutDegree(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:329
dglInt32_t dglEdgesetGet_EdgeCount(dglGraph_s *pGraph, dglInt32_t *pnEdgeset)
Definition: dglib/graph.c:397
int dglEdgeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnAttr, dglInt32_t *pnEdge)
Definition: dglib/graph.c:550
dglInt32_t * pnEdge
Definition: graph.h:115
void dglNode_T_Release(dglNodeTraverser_s *pT)
Definition: dglib/graph.c:1371
void dglSet_Family(dglGraph_s *pgraph, dglInt32_t nFamily)
Definition: dglib/graph.c:1326
int dglIOContextInitialize(dglGraph_s *pG, dglIOContext_s *pIO)
Definition: dglib/graph.c:1563
int dglUnflatten(dglGraph_s *pGraph)
Definition: dglib/graph.c:123
dglInt32_t * pnNode
Definition: graph.h:252
int(* dglWriteChunk_fn)(dglGraph_s *, unsigned char *pbChunk, int cbChunk, void *pvArg)
Definition: graph.h:390
void * pvPredist
Definition: graph.h:241
int dglGet_NodeAttrSize(dglGraph_s *pgraph)
Definition: dglib/graph.c:1231
struct _dglSPArc dglSPArc_s
dglInt32_t nTo
Definition: graph.h:214
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
Definition: dglib/graph.c:438
int dglInitializeSPCache(dglGraph_s *pGraph, dglSPCache_s *pCache)
Definition: dglib/graph.c:1122
dglInt32_t cNode
Definition: graph.h:162
dglGraph_s * pGraph
Definition: graph.h:260
dglGraph_s * pG
Definition: graph.h:375
int dglRelease(dglGraph_s *pGraph)
Definition: dglib/graph.c:108
dglInt32_t dglGet_Options(dglGraph_s *pgraph)
Definition: dglib/graph.c:1331
int iErrno
Definition: graph.h:154
void dglEdge_T_Release(dglEdgeTraverser_s *pT)
Definition: dglib/graph.c:1452
int dglNodeGet_InDegree(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:297
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT)
Definition: dglib/graph.c:1515
void * pvVisited
Definition: graph.h:240
dglInt32_t * dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
Definition: dglib/graph.c:1519
dglInt32_t aOpaqueSet[16]
Definition: graph.h:160
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
Definition: dglib/graph.c:155
dglInt32_t * dglEdge_T_Next(dglEdgeTraverser_s *pT)
Definition: dglib/graph.c:1483
dglInt32_t * pnEdgeset
Definition: graph.h:261
dglInt32_t * pnNodeFrom
Definition: graph.h:114
dglInt32_t cTail
Definition: graph.h:164
int dglWriteChunk(dglIOContext_s *pIO, dglWriteChunk_fn pfn, void *pv)
Definition: dglib/graph.c:1577
void * pvAVLT
Definition: graph.h:251
int dglDelEdge(dglGraph_s *pGraph, dglInt32_t nEdgeId)
Definition: dglib/graph.c:593
dglInt32_t * pnPrevEdge
Definition: graph.h:94
int dglWrite(dglGraph_s *pGraph, int fd)
Definition: dglib/graph.c:733
int dglDepthComponents(dglGraph_s *pgraphInput, dglGraph_s *pgraphComponents, int cgraphComponents, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: dglib/graph.c:914
void dglNodeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode, dglInt32_t *pnAttr)
Definition: dglib/graph.c:275
dglInt32_t dglGet_Family(dglGraph_s *pgraph)
Definition: dglib/graph.c:1321
dglInt32_t nDestinationNode
Definition: graph.h:226
dglSPArc_s * pArc
Definition: graph.h:229
int dglEdge_T_Initialize(dglEdgeTraverser_s *pT, dglGraph_s *pGraph, dglEdgePrioritizer_s *pEdgePrioritizer)
Definition: dglib/graph.c:1435
int dglGet_Endianess(dglGraph_s *pgraph)
Definition: dglib/graph.c:1226
long long dglInt64_t
Definition: type.h:38
void dglReleaseSPCache(dglGraph_s *pGraph, dglSPCache_s *pCache)
Definition: dglib/graph.c:1137
int dglGet_NodeSize(dglGraph_s *pgraph)
Definition: dglib/graph.c:1281
long dglInt32_t
Definition: type.h:37
int
Definition: g3dcolor.c:48
dglInt32_t * dglNode_T_First(dglNodeTraverser_s *pT)
Definition: dglib/graph.c:1387
dglInt32_t * dglEdgeGet_Head(dglGraph_s *pGraph, dglInt32_t *pnEdge)
Definition: dglib/graph.c:458
void * pEdgeTree
Definition: graph.h:174
dglInt32_t nStartNode
Definition: graph.h:238
dglHeap_s NodeHeap
Definition: graph.h:239
void * pvCurrentItem
Definition: graph.h:262
dglInt32_t nFrom
Definition: graph.h:213
int dglGet_EdgeCount(dglGraph_s *pgraph)
Definition: dglib/graph.c:1261
dglInt32_t * pnNodeTo
Definition: graph.h:116
dglGraph_s * pGraph
Definition: graph.h:250
int dglShortestDistanceGraph(dglGraph_s *pGraph, dglGraph_s *pGraphOut, dglInt32_t nStartNode, dglInt32_t nDestinationNode, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
dglInt32_t cAlone
Definition: graph.h:165
dglInt32_t * dglNode_T_Find(dglNodeTraverser_s *pT, dglInt32_t nNodeId)
Definition: dglib/graph.c:1417
dglInt32_t nEdgeCost
Definition: graph.h:104
void dglSet_Options(dglGraph_s *pgraph, dglInt32_t nOptions)
Definition: dglib/graph.c:1336
struct _dglSPClipOutput dglSPClipOutput_s
struct _dglSPReport dglSPReport_s
dglInt32_t * dglNodeGet_OutEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:170
dglInt32_t * dglEdgeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnEdge)
Definition: dglib/graph.c:530
dglInt32_t cHead
Definition: graph.h:163
dglEdgePrioritizer_s * pEdgePrioritizer
Definition: graph.h:274
int dglDelNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
Definition: dglib/graph.c:711
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:255
dglNodePrioritizer_s * dglGet_NodePrioritizer(dglGraph_s *pGraph)
Definition: dglib/graph.c:1346
dglInt32_t * pnNodeFrom
Definition: graph.h:95
dglInt32_t * pnNodeTo
Definition: graph.h:97
dglInt32_t * dglGet_Opaque(dglGraph_s *pgraph)
Definition: dglib/graph.c:1271
dglEdgePrioritizer_s * dglGet_EdgePrioritizer(dglGraph_s *pGraph)
Definition: dglib/graph.c:1341
int dglInitialize(dglGraph_s *pGraph, dglByte_t Version, dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, dglInt32_t *pOpaqueSet)
Definition: dglib/graph.c:53
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
Definition: dglib/graph.c:418
int dglAddEdgeX(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr, void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
Definition: dglib/graph.c:647
dglInt32_t * dglGetEdge(dglGraph_s *pGraph, dglInt32_t nEdgeId)
Definition: dglib/graph.c:576
int dglDepthSpanning(dglGraph_s *pgraphInput, dglGraph_s *pgraphOutput, dglInt32_t nVertexNode, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: dglib/graph.c:849
int dglGet_EdgeSize(dglGraph_s *pgraph)
Definition: dglib/graph.c:1296
dglInt32_t cArc
Definition: graph.h:228
void dglIOContextRelease(dglIOContext_s *pIO)
Definition: dglib/graph.c:1573
void dglSet_Cost(dglGraph_s *pgraph, dglInt64_t nnCost)
Definition: dglib/graph.c:1316
dglInt32_t * dglNode_T_Last(dglNodeTraverser_s *pTraverser)
dglInt32_t nStartNode
Definition: graph.h:225
dglByte_t Version
Definition: graph.h:156
char * dglStrerror(dglGraph_s *pgraph)
Definition: dglib/graph.c:1160
void dglSet_Version(dglGraph_s *pgraph, int nVersion)
Definition: dglib/graph.c:1221
int(* dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *)
Definition: graph.h:198
int dglMinimumSpanning(dglGraph_s *pgraphInput, dglGraph_s *pgraphOutput, dglInt32_t nVertexNode, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: dglib/graph.c:1060
int dglGet_NodeCount(dglGraph_s *pgraph)
Definition: dglib/graph.c:1241
void dglFreeSPReport(dglGraph_s *pgraph, dglSPReport_s *pSPReport)
Definition: dglib/graph.c:1106
dglInt32_t EdgeAttrSize
Definition: graph.h:159
void dglSet_Opaque(dglGraph_s *pgraph, dglInt32_t *pOpaque)
Definition: dglib/graph.c:1276
dglByte_t Endian
Definition: graph.h:157
void dglResetStats(dglGraph_s *pgraph)
Definition: dglib/graph.c:43
int dglShortestPathGraph(dglGraph_s *pGraph, dglGraph_s *pGraphOut, dglInt32_t nStartNode, dglInt32_t nDestinationNode, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
struct _dglSPClipInput dglSPClipInput_s
dglInt32_t * dglNode_T_Next(dglNodeTraverser_s *pT)
Definition: dglib/graph.c:1402
dglInt32_t * dglEdgeset_T_Next(dglEdgesetTraverser_s *pT)
Definition: dglib/graph.c:1534
dglInt32_t iNodeBuffer
Definition: graph.h:176
int dglReadChunk(dglIOContext_s *pIO, dglByte_t *pbChunk, int cbChunk)
Definition: dglib/graph.c:1694
int(* dglSpanClip_fn)(dglGraph_s *, dglGraph_s *, dglSpanClipInput_s *, dglSpanClipOutput_s *, void *)
Definition: graph.h:204
dglByte_t * pEdgeBuffer
Definition: graph.h:177
dglInt32_t nOptions
Definition: graph.h:171
dglInt32_t nDistance
Definition: graph.h:227
dglInt32_t * dglNodeGet_InEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:188
int nState
Definition: graph.h:376
dglByte_t * pNodeBuffer
Definition: graph.h:175
int dglFlatten(dglGraph_s *pGraph)
Definition: dglib/graph.c:139