GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-381f661b3f
vector/dglib/graph.c
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 with tabstop=4
21  */
22 
23 #include <stdio.h>
24 #include <string.h>
25 #include <sys/types.h>
26 #include <sys/stat.h>
27 #include <unistd.h>
28 #include <stdlib.h>
29 #include <errno.h>
30 
31 #define DGL_V2 1
32 
33 #include <grass/gis.h>
34 #include "type.h"
35 #include "tree.h"
36 #include "graph.h"
37 #include "graph_v1.h"
38 #if defined(DGL_V2)
39 #include "graph_v2.h"
40 #endif
41 #include "helpers.h"
42 
44 {
45 #ifdef DGL_STATS
46  pgraph->clkAddEdge = 0;
47  pgraph->cAddEdge = 0;
48  pgraph->clkNodeTree = 0;
49  pgraph->cNodeTree = 0;
50 #endif
51 }
52 
53 int dglInitialize(dglGraph_s *pGraph, dglByte_t Version,
54  dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize,
55  dglInt32_t *pOpaqueSet)
56 {
57  if (pGraph == NULL) {
58  return -DGL_ERR_BadArgument;
59  }
60  switch (Version) {
61  case 1:
62 #ifdef DGL_V2
63  case 2:
64  case 3:
65 #endif
66  memset(pGraph, 0, sizeof(dglGraph_s));
67  /*
68  * round attr size to the upper multiple of dglInt32_t size
69  */
70  if (NodeAttrSize % sizeof(dglInt32_t))
71  NodeAttrSize +=
72  (sizeof(dglInt32_t) - (NodeAttrSize % sizeof(dglInt32_t)));
73  if (EdgeAttrSize % sizeof(dglInt32_t))
74  EdgeAttrSize +=
75  (sizeof(dglInt32_t) - (EdgeAttrSize % sizeof(dglInt32_t)));
76  pGraph->Version = Version;
77  pGraph->NodeAttrSize = NodeAttrSize;
78  pGraph->EdgeAttrSize = EdgeAttrSize;
79  if (pOpaqueSet)
80  memcpy(&pGraph->aOpaqueSet, pOpaqueSet, sizeof(dglInt32_t) * 16);
81 #ifdef DGL_ENDIAN_BIG
82  pGraph->Endian = DGL_ENDIAN_BIG;
83 #else
84  pGraph->Endian = DGL_ENDIAN_LITTLE;
85 #endif
86  }
87  switch (Version) {
88  case 1:
89  if (dgl_initialize_V1(pGraph) < 0) {
90  return -pGraph->iErrno;
91  }
92  else
93  return 0;
94 #ifdef DGL_V2
95  case 2:
96  case 3:
97  if (dgl_initialize_V2(pGraph) < 0) {
98  return -pGraph->iErrno;
99  }
100  else
101  return 0;
102 #endif
103  }
105  return -pGraph->iErrno;
106 }
107 
108 int dglRelease(dglGraph_s *pGraph)
109 {
110  switch (pGraph->Version) {
111  case 1:
112  return dgl_release_V1(pGraph);
113 #ifdef DGL_V2
114  case 2:
115  case 3:
116  return dgl_release_V2(pGraph);
117 #endif
118  }
119  pGraph->iErrno = DGL_ERR_BadVersion;
120  return -pGraph->iErrno;
121 }
122 
124 {
125  switch (pGraph->Version) {
126  case 1:
127  return dgl_unflatten_V1(pGraph);
128 #ifdef DGL_V2
129  case 2:
130  case 3:
131  return dgl_unflatten_V2(pGraph);
132 #endif
133  }
134  pGraph->iErrno = DGL_ERR_BadVersion;
135  return -pGraph->iErrno;
136 }
137 
138 int dglFlatten(dglGraph_s *pGraph)
139 {
140  switch (pGraph->Version) {
141  case 1:
142  return dgl_flatten_V1(pGraph);
143 #ifdef DGL_V2
144  case 2:
145  case 3:
146  return dgl_flatten_V2(pGraph);
147 #endif
148  }
149  pGraph->iErrno = DGL_ERR_BadVersion;
150  return -pGraph->iErrno;
151 }
152 
154 {
155  switch (pGraph->Version) {
156  case 1:
157  return dgl_get_node_V1(pGraph, nNodeId);
158 #ifdef DGL_V2
159  case 2:
160  case 3:
161  return dgl_get_node_V2(pGraph, nNodeId);
162 #endif
163  }
164  pGraph->iErrno = DGL_ERR_BadVersion;
165  return NULL;
166 }
167 
169 {
170  if (pnNode) {
171  switch (pGraph->Version) {
172  case 1:
173  return dgl_getnode_outedgeset_V1(pGraph, pnNode);
174 #ifdef DGL_V2
175  case 2:
176  case 3:
177  return dgl_getnode_outedgeset_V2(pGraph, pnNode);
178 #endif
179  }
180  pGraph->iErrno = DGL_ERR_BadVersion;
181  return NULL;
182  }
183  return NULL;
184 }
185 
187 {
188  if (pnNode) {
189  switch (pGraph->Version) {
190  case 1:
191  pGraph->iErrno = DGL_ERR_NotSupported;
192  return NULL;
193 #ifdef DGL_V2
194  case 2:
195  case 3:
196  return dgl_getnode_inedgeset_V2(pGraph, pnNode);
197 #endif
198  }
199  pGraph->iErrno = DGL_ERR_BadVersion;
200  return NULL;
201  }
202  return NULL;
203 }
204 
205 /*
206  * Given that node id can be negative, only iErrno can report a error,
207  * thus it is initialized to zero
208  */
210 {
211  pGraph->iErrno = 0;
212  if (pnNode) {
213  switch (pGraph->Version) {
214  case 1:
215  return DGL_NODE_ID_v1(pnNode);
216 #ifdef DGL_V2
217  case 2:
218  case 3:
219  return DGL_NODE_ID_v2(pnNode);
220 #endif
221  }
222  pGraph->iErrno = DGL_ERR_BadVersion;
223  return 0;
224  }
226  return 0;
227 }
228 
230 {
231  pGraph->iErrno = 0;
232  if (pnNode) {
233  switch (pGraph->Version) {
234  case 1:
235  return DGL_NODE_STATUS_v1(pnNode);
236 #ifdef DGL_V2
237  case 2:
238  case 3:
239  return DGL_NODE_STATUS_v2(pnNode);
240 #endif
241  }
242  pGraph->iErrno = DGL_ERR_BadVersion;
243  return 0;
244  }
246  return 0;
247 }
248 
250 {
251  if (pnNode) {
252  switch (pGraph->Version) {
253  case 1:
254  return DGL_NODE_ATTR_PTR_v1(pnNode);
255 #ifdef DGL_V2
256  case 2:
257  case 3:
258  return DGL_NODE_ATTR_PTR_v2(pnNode);
259 #endif
260  }
261  pGraph->iErrno = DGL_ERR_BadVersion;
262  return NULL;
263  }
265  return NULL;
266 }
267 
268 void dglNodeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode, dglInt32_t *pnAttr)
269 {
270  if (pnNode) {
271  switch (pGraph->Version) {
272  case 1:
273  memcpy(DGL_NODE_ATTR_PTR_v1(pnNode), pnAttr, pGraph->NodeAttrSize);
274  return;
275 #ifdef DGL_V2
276  case 2:
277  case 3:
278  memcpy(DGL_NODE_ATTR_PTR_v2(pnNode), pnAttr, pGraph->NodeAttrSize);
279  return;
280 #endif
281  }
282  return;
283  }
284  return;
285 }
286 
288 {
289 #ifdef DGL_V2
290  dglInt32_t *pinedgeset;
291 #endif
292 
293  pGraph->iErrno = 0;
294  if (pnNode) {
295  switch (pGraph->Version) {
296  case 1:
297  pGraph->iErrno = DGL_ERR_NotSupported;
298  return 0;
299 #ifdef DGL_V2
300  case 2:
301  if (DGL_NODE_STATUS_v2(pnNode) & DGL_NS_ALONE)
302  return 0;
303  pinedgeset = dglNodeGet_InEdgeset(pGraph, pnNode);
304  if (pinedgeset)
305  return DGL_EDGESET_EDGECOUNT_v2(pinedgeset);
306  return 0;
307  case 3:
308  return dglNodeGet_Valence(pGraph, pnNode);
309 #endif
310  }
311  pGraph->iErrno = DGL_ERR_BadVersion;
312  return 0;
313  }
315  return 0;
316 }
317 
319 {
320  dglInt32_t *poutedgeset;
321 
322  pGraph->iErrno = 0;
323  if (pnNode) {
324  switch (pGraph->Version) {
325  case 1:
326  if (DGL_NODE_STATUS_v1(pnNode) & DGL_NS_ALONE)
327  return 0;
328  poutedgeset = dglNodeGet_OutEdgeset(pGraph, pnNode);
329  if (poutedgeset)
330  return DGL_EDGESET_EDGECOUNT_v1(poutedgeset);
331  return 0;
332 #ifdef DGL_V2
333  case 2:
334  if (DGL_NODE_STATUS_v2(pnNode) & DGL_NS_ALONE)
335  return 0;
336  poutedgeset = dglNodeGet_OutEdgeset(pGraph, pnNode);
337  if (poutedgeset)
338  return DGL_EDGESET_EDGECOUNT_v2(poutedgeset);
339  return 0;
340  case 3:
341  return dglNodeGet_Valence(pGraph, pnNode);
342 #endif
343  }
344  pGraph->iErrno = DGL_ERR_BadVersion;
345  return 0;
346  }
348  return 0;
349 }
350 
352 {
353 #ifdef DGL_V2
354  dglInt32_t *poutedgeset;
355  dglInt32_t *pinedgeset;
356  int c;
357 #endif
358 
359  pGraph->iErrno = 0;
360  if (pnNode) {
361  switch (pGraph->Version) {
362 #ifdef DGL_V2
363  case 3:
364  if (DGL_NODE_STATUS_v2(pnNode) & DGL_NS_ALONE)
365  return 0;
366  poutedgeset = dglNodeGet_OutEdgeset(pGraph, pnNode);
367  pinedgeset = dglNodeGet_InEdgeset(pGraph, pnNode);
368  c = 0;
369  if (poutedgeset)
370  c += DGL_EDGESET_EDGECOUNT_v2(poutedgeset);
371  if (pinedgeset)
372  c += DGL_EDGESET_EDGECOUNT_v2(pinedgeset);
373  return c;
374 #endif
375  }
376  pGraph->iErrno = DGL_ERR_BadVersion;
377  return 0;
378  }
380  return 0;
381 }
382 
384 {
385  pGraph->iErrno = 0;
386  if (pnEdgeset) {
387  switch (pGraph->Version) {
388  case 1:
389  return DGL_EDGESET_EDGECOUNT_v1(pnEdgeset);
390 #ifdef DGL_V2
391  case 2:
392  case 3:
393  return DGL_EDGESET_EDGECOUNT_v2(pnEdgeset);
394 #endif
395  }
396  pGraph->iErrno = DGL_ERR_BadVersion;
397  return 0;
398  }
400  return 0;
401 }
402 
404 {
405  pGraph->iErrno = 0;
406  if (pnEdge) {
407  switch (pGraph->Version) {
408  case 1:
409  return DGL_EDGE_COST_v1(pnEdge);
410 #ifdef DGL_V2
411  case 2:
412  case 3:
413  return DGL_EDGE_COST_v2(pnEdge);
414 #endif
415  }
416  pGraph->iErrno = DGL_ERR_BadVersion;
417  return 0;
418  }
420  return 0;
421 }
422 
424 {
425  pGraph->iErrno = 0;
426  if (pnEdge) {
427  switch (pGraph->Version) {
428  case 1:
429  return DGL_EDGE_ID_v1(pnEdge);
430 #ifdef DGL_V2
431  case 2:
432  case 3:
433  return DGL_EDGE_ID_v2(pnEdge);
434 #endif
435  }
436  pGraph->iErrno = DGL_ERR_BadVersion;
437  return 0;
438  }
440  return 0;
441 }
442 
444 {
445  pGraph->iErrno = 0;
446  if (pnEdge) {
447  switch (pGraph->Version) {
448  case 1:
449  if (pGraph->Flags & DGL_GS_FLAT) {
451  pGraph, DGL_EDGE_HEADNODE_OFFSET_v1(pnEdge));
452  }
453  else {
454  return dgl_get_node_V1(pGraph,
456  }
457 #ifdef DGL_V2
458  case 2:
459  case 3:
460  if (pGraph->Flags & DGL_GS_FLAT) {
462  pGraph, DGL_EDGE_HEADNODE_OFFSET_v2(pnEdge));
463  }
464  else {
465  return dgl_get_node_V2(pGraph,
467  }
468 #endif
469  }
470  pGraph->iErrno = DGL_ERR_BadVersion;
471  return NULL;
472  }
474  return NULL;
475 }
476 
478 {
479  pGraph->iErrno = 0;
480  if (pnEdge) {
481  switch (pGraph->Version) {
482  case 1:
483  if (pGraph->Flags & DGL_GS_FLAT) {
485  pGraph, DGL_EDGE_TAILNODE_OFFSET_v1(pnEdge));
486  }
487  else {
488  return dgl_get_node_V1(pGraph,
490  }
491 #ifdef DGL_V2
492  case 2:
493  case 3:
494  if (pGraph->Flags & DGL_GS_FLAT) {
496  pGraph, DGL_EDGE_TAILNODE_OFFSET_v2(pnEdge));
497  }
498  else {
499  return dgl_get_node_V2(pGraph,
501  }
502 #endif
503  }
504  pGraph->iErrno = DGL_ERR_BadVersion;
505  return NULL;
506  }
508  return NULL;
509 }
510 
512 {
513  pGraph->iErrno = 0;
514  if (pnEdge) {
515  switch (pGraph->Version) {
516  case 1:
517  return DGL_EDGE_ATTR_PTR_v1(pnEdge);
518 #ifdef DGL_V2
519  case 2:
520  case 3:
521  return DGL_EDGE_ATTR_PTR_v2(pnEdge);
522 #endif
523  }
524  pGraph->iErrno = DGL_ERR_BadVersion;
525  return NULL;
526  }
528  return NULL;
529 }
530 
531 int dglEdgeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnAttr, dglInt32_t *pnEdge)
532 {
533  if (pnEdge) {
534  switch (pGraph->Version) {
535  case 1:
536  memcpy(DGL_EDGE_ATTR_PTR_v1(pnEdge), pnAttr, pGraph->EdgeAttrSize);
537  return 0;
538 #ifdef DGL_V2
539  case 2:
540  case 3:
541  memcpy(DGL_EDGE_ATTR_PTR_v2(pnEdge), pnAttr, pGraph->EdgeAttrSize);
542  return 0;
543 #endif
544  }
545  pGraph->iErrno = DGL_ERR_BadVersion;
546  return -pGraph->iErrno;
547  }
549  return -pGraph->iErrno;
550 }
551 
553 {
554  switch (pGraph->Version) {
555  case 1:
556  return dgl_get_edge_V1(pGraph, nEdgeId);
557  break;
558 #ifdef DGL_V2
559  case 2:
560  case 3:
561  return dgl_get_edge_V2(pGraph, nEdgeId);
562  break;
563 #endif
564  }
565  pGraph->iErrno = DGL_ERR_BadVersion;
566  return NULL;
567 }
568 
569 int dglDelEdge(dglGraph_s *pGraph, dglInt32_t nEdgeId)
570 {
571  switch (pGraph->Version) {
572  case 1:
573  return dgl_del_edge_V1(pGraph, nEdgeId);
574  break;
575 #ifdef DGL_V2
576  case 2:
577  case 3:
578  return dgl_del_edge_V2(pGraph, nEdgeId);
579  break;
580 #endif
581  }
582  pGraph->iErrno = DGL_ERR_BadVersion;
583  return -pGraph->iErrno;
584 }
585 
586 int dglAddEdge(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail,
587  dglInt32_t nCost, dglInt32_t nEdge)
588 {
589  int nRet;
590 
591 #ifdef DGL_STATS
592  clock_t clk;
593 
594  clk = clock();
595  pGraph->cAddEdge++;
596 #endif
597  switch (pGraph->Version) {
598  case 1:
599  nRet = dgl_add_edge_V1(pGraph, nHead, nTail, nCost, nEdge, NULL, NULL,
600  NULL, 0);
601  break;
602 #ifdef DGL_V2
603  case 2:
604  case 3:
605  nRet = dgl_add_edge_V2(pGraph, nHead, nTail, nCost, nEdge, NULL, NULL,
606  NULL, 0);
607  break;
608 #endif
609  default:
610  pGraph->iErrno = DGL_ERR_BadVersion;
611  nRet = -pGraph->iErrno;
612  break;
613  }
614 #ifdef DGL_STATS
615  pGraph->clkAddEdge += clock() - clk;
616 #endif
617  return nRet;
618 }
619 
620 int dglAddEdgeX(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail,
621  dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr,
622  void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
623 {
624  int nRet;
625 
626 #ifdef DGL_STATS
627  clock_t clk;
628 
629  clk = clock();
630  pGraph->cAddEdge++;
631 #endif
632  switch (pGraph->Version) {
633  case 1:
634  nRet = dgl_add_edge_V1(pGraph, nHead, nTail, nCost, nEdge, pvHeadAttr,
635  pvTailAttr, pvEdgeAttr, nFlags);
636  break;
637 #ifdef DGL_V2
638  case 2:
639  case 3:
640  nRet = dgl_add_edge_V2(pGraph, nHead, nTail, nCost, nEdge, pvHeadAttr,
641  pvTailAttr, pvEdgeAttr, nFlags);
642  break;
643 #endif
644  default:
645  pGraph->iErrno = DGL_ERR_BadVersion;
646  nRet = -pGraph->iErrno;
647  break;
648  }
649 #ifdef DGL_STATS
650  pGraph->clkAddEdge += clock() - clk;
651 #endif
652  return nRet;
653 }
654 
655 int dglAddNode(dglGraph_s *pGraph, dglInt32_t nNodeId, void *pvNodeAttr,
656  dglInt32_t nFlags)
657 {
658  int nRet;
659 
660  switch (pGraph->Version) {
661  case 1:
662  nRet = dgl_add_node_V1(pGraph, nNodeId, pvNodeAttr, nFlags);
663  break;
664 #ifdef DGL_V2
665  case 2:
666  case 3:
667  nRet = dgl_add_node_V2(pGraph, nNodeId, pvNodeAttr, nFlags);
668  break;
669 #endif
670  default:
671  pGraph->iErrno = DGL_ERR_BadVersion;
672  nRet = -pGraph->iErrno;
673  break;
674  }
675  return nRet;
676 }
677 
678 int dglDelNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
679 {
680  int nRet;
681 
682  switch (pGraph->Version) {
683  case 1:
684  nRet = dgl_del_node_V1(pGraph, nNodeId);
685  break;
686 #ifdef DGL_V2
687  case 2:
688  case 3:
689  nRet = dgl_del_node_V2(pGraph, nNodeId);
690  break;
691 #endif
692  default:
693  pGraph->iErrno = DGL_ERR_BadVersion;
694  nRet = -pGraph->iErrno;
695  break;
696  }
697  return nRet;
698 }
699 
700 int dglWrite(dglGraph_s *pGraph, int fd)
701 {
702  int nRet;
703 
704  switch (pGraph->Version) {
705  case 1:
706  nRet = dgl_write_V1(pGraph, fd);
707  break;
708 #ifdef DGL_V2
709  case 2:
710  case 3:
711  nRet = dgl_write_V2(pGraph, fd);
712  break;
713 #endif
714  default:
715  pGraph->iErrno = DGL_ERR_BadVersion;
716  nRet = -pGraph->iErrno;
717  break;
718  }
719  return nRet;
720 }
721 
722 int dglRead(dglGraph_s *pGraph, int fd)
723 {
724  dglByte_t bVersion;
725  int nRet;
726 
727  if (read(fd, &bVersion, 1) != 1) {
728  pGraph->iErrno = DGL_ERR_Read;
729  nRet = -pGraph->iErrno;
730  }
731  else {
732  switch (bVersion) {
733  case 1:
734  nRet = dgl_read_V1(pGraph, fd);
735  break;
736 #ifdef DGL_V2
737  case 2:
738  case 3:
739  nRet = dgl_read_V2(pGraph, fd, bVersion);
740  break;
741 #endif
742  default:
744  nRet = -pGraph->iErrno;
745  break;
746  }
747  }
748  return nRet;
749 }
750 
751 int dglShortestPath(dglGraph_s *pGraph, dglSPReport_s **ppReport,
752  dglInt32_t nStart, dglInt32_t nDestination,
753  dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
754 {
755  int nRet;
756 
757  switch (pGraph->Version) {
758  case 1:
759  nRet = dgl_dijkstra_V1(pGraph, ppReport, NULL, nStart, nDestination,
760  fnClip, pvClipArg, pCache);
761  break;
762 #ifdef DGL_V2
763  case 2:
764  case 3:
765  nRet = dgl_dijkstra_V2(pGraph, ppReport, NULL, nStart, nDestination,
766  fnClip, pvClipArg, pCache);
767  break;
768 #endif
769  default:
770  pGraph->iErrno = DGL_ERR_BadVersion;
771  nRet = -pGraph->iErrno;
772  break;
773  }
774  return nRet;
775 }
776 
777 int dglShortestDistance(dglGraph_s *pGraph, dglInt32_t *pnDistance,
778  dglInt32_t nStart, dglInt32_t nDestination,
779  dglSPClip_fn fnClip, void *pvClipArg,
780  dglSPCache_s *pCache)
781 {
782  int nRet;
783 
784  switch (pGraph->Version) {
785  case 1:
786  nRet = dgl_dijkstra_V1(pGraph, NULL, pnDistance, nStart, nDestination,
787  fnClip, pvClipArg, pCache);
788  break;
789 #ifdef DGL_V2
790  case 2:
791  case 3:
792  nRet = dgl_dijkstra_V2(pGraph, NULL, pnDistance, nStart, nDestination,
793  fnClip, pvClipArg, pCache);
794  break;
795 #endif
796  default:
797  pGraph->iErrno = DGL_ERR_BadVersion;
798  nRet = -pGraph->iErrno;
799  break;
800  }
801  return nRet;
802 }
803 
804 int dglDepthSpanning(dglGraph_s *pgraphInput, dglGraph_s *pgraphOutput,
805  dglInt32_t nVertexNode, dglSpanClip_fn fnClip,
806  void *pvClipArg)
807 {
808  int nRet;
809  void *pvVisited;
810 
811  if (dglGet_EdgeCount(pgraphInput) == 0) { /* no span */
812  pgraphInput->iErrno = 0;
813  return 0;
814  }
815 
816 #ifndef DGL_V2
817  if (pgraphInput->Version == 2) {
818  pgraphInput->iErrno = DGL_ERR_BadVersion;
819  return -pgraphInput->iErrno;
820  }
821 #endif
822 
823  nRet = dglInitialize(pgraphOutput, dglGet_Version(pgraphInput),
824  dglGet_NodeAttrSize(pgraphInput),
825  dglGet_EdgeAttrSize(pgraphInput),
826  dglGet_Opaque(pgraphInput));
827 
828  if (nRet < 0)
829  return nRet;
830 
831  if ((pvVisited = avl_create(dglTreeNodeCompare, NULL,
832  dglTreeGetAllocator())) == NULL) {
833  pgraphInput->iErrno = DGL_ERR_MemoryExhausted;
834  return -pgraphInput->iErrno;
835  }
836 
837  switch (pgraphInput->Version) {
838  case 1:
839  nRet =
840  dgl_depthfirst_spanning_V1(pgraphInput, pgraphOutput, nVertexNode,
841  pvVisited, fnClip, pvClipArg);
842  break;
843 #ifdef DGL_V2
844  case 2:
845  case 3:
846  nRet =
847  dgl_depthfirst_spanning_V2(pgraphInput, pgraphOutput, nVertexNode,
848  pvVisited, fnClip, pvClipArg);
849  break;
850 #endif
851  default:
852  pgraphInput->iErrno = DGL_ERR_BadVersion;
853  nRet = -pgraphInput->iErrno;
854  break;
855  }
856 
857  avl_destroy(pvVisited, dglTreeNodeCancel);
858 
859  if (nRet < 0) {
860  dglRelease(pgraphOutput);
861  }
862 
863  return nRet;
864 }
865 
866 int dglDepthComponents(dglGraph_s *pgraphInput, dglGraph_s *pgraphComponents,
867  int cgraphComponents, dglSpanClip_fn fnClip,
868  void *pvClipArg)
869 {
870  int i, nret = 0;
871  dglTreeNode_s findVisited;
872  void *pvVisited;
873  dglInt32_t *pvertex, *pnode;
874 
875  if (dglGet_EdgeCount(pgraphInput) == 0) { /* no span */
876  pgraphInput->iErrno = 0;
877  return 0;
878  }
879 
880 #ifndef DGL_V2
881  if (pgraphInput->Version == 2 || pgraphInput->Version == 3) {
882  pgraphInput->iErrno = DGL_ERR_BadVersion;
883  return -pgraphInput->iErrno;
884  }
885 #endif
886 
887  if ((pvVisited = avl_create(dglTreeNodeCompare, NULL,
888  dglTreeGetAllocator())) == NULL) {
889  pgraphInput->iErrno = DGL_ERR_MemoryExhausted;
890  goto error;
891  }
892 
893  /*
894  * choose a vertex to start from
895  */
896  pvertex = NULL;
897  {
899 
900  dglNode_T_Initialize(&pT, pgraphInput);
901  for (pnode = dglNode_T_First(&pT); pnode; pnode = dglNode_T_Next(&pT)) {
902  switch (pgraphInput->Version) {
903  case 1:
904  if (DGL_NODE_STATUS_v1(pnode) & DGL_NS_HEAD)
905  pvertex = pnode;
906  break;
907 #ifdef DGL_V2
908  case 2:
909  case 3:
910  if (DGL_NODE_STATUS_v2(pnode) & DGL_NS_HEAD)
911  pvertex = pnode;
912  break;
913 #endif
914  }
915  if (pvertex)
916  break;
917  }
918  dglNode_T_Release(&pT);
919  }
920 
921  if (pvertex == NULL) {
922  pgraphInput->iErrno = DGL_ERR_UnexpectedNullPointer;
923  goto error;
924  }
925 
926  for (i = 0; i < cgraphComponents && pvertex; i++) {
927  nret = dglInitialize(&pgraphComponents[i], dglGet_Version(pgraphInput),
928  dglGet_NodeAttrSize(pgraphInput),
929  dglGet_EdgeAttrSize(pgraphInput),
930  dglGet_Opaque(pgraphInput));
931 
932  if (nret < 0)
933  goto error;
934 
935  switch (pgraphInput->Version) {
936  case 1:
937  nret = dgl_depthfirst_spanning_V1(pgraphInput, &pgraphComponents[i],
938  DGL_NODE_ID_v1(pvertex),
939  pvVisited, fnClip, pvClipArg);
940  if (nret < 0)
941  goto error;
942  break;
943 #ifdef DGL_V2
944  case 2:
945  case 3:
946  nret = dgl_depthfirst_spanning_V2(pgraphInput, &pgraphComponents[i],
947  DGL_NODE_ID_v1(pvertex),
948  pvVisited, fnClip, pvClipArg);
949  if (nret < 0)
950  goto error;
951  break;
952 #endif
953  default:
954  pgraphInput->iErrno = DGL_ERR_BadVersion;
955  nret = -pgraphInput->iErrno;
956  goto error;
957  }
958 
959  /*
960  * select next unvisited vertex
961  */
962  pvertex = NULL;
963  {
965 
966  dglNode_T_Initialize(&pT, pgraphInput);
967  for (pnode = dglNode_T_First(&pT); pnode;
968  pnode = dglNode_T_Next(&pT)) {
969  switch (pgraphInput->Version) {
970  case 1:
971  if (DGL_NODE_STATUS_v1(pnode) & DGL_NS_HEAD) {
972  findVisited.nKey = DGL_NODE_ID_v1(pnode);
973  if (avl_find(pvVisited, &findVisited) == NULL) {
974  pvertex = pnode;
975  break;
976  }
977  }
978  break;
979 #ifdef DGL_V2
980  case 2:
981  case 3:
982  if (DGL_NODE_STATUS_v2(pnode) & DGL_NS_HEAD) {
983  findVisited.nKey = DGL_NODE_ID_v2(pnode);
984  if (avl_find(pvVisited, &findVisited) == NULL) {
985  pvertex = pnode;
986  break;
987  }
988  }
989  break;
990 #endif
991  }
992  if (pvertex)
993  break;
994  }
995  dglNode_T_Release(&pT);
996  }
997  }
998 
999  avl_destroy(pvVisited, dglTreeNodeCancel);
1000  return i;
1001 
1002 error:
1003  avl_destroy(pvVisited, dglTreeNodeCancel);
1004  return nret;
1005 }
1006 
1007 int dglMinimumSpanning(dglGraph_s *pgraphInput, dglGraph_s *pgraphOutput,
1008  dglInt32_t nVertexNode, dglSpanClip_fn fnClip,
1009  void *pvClipArg)
1010 {
1011  int nRet;
1012 
1013  if (dglGet_EdgeCount(pgraphInput) == 0) { /* no span */
1014  pgraphInput->iErrno = 0;
1015  return 0;
1016  }
1017 
1018  nRet = dglInitialize(pgraphOutput, dglGet_Version(pgraphInput),
1019  dglGet_NodeAttrSize(pgraphInput),
1020  dglGet_EdgeAttrSize(pgraphInput),
1021  dglGet_Opaque(pgraphInput));
1022 
1023  if (nRet < 0)
1024  return nRet;
1025 
1026  switch (pgraphInput->Version) {
1027  case 1:
1028  nRet = dgl_minimum_spanning_V1(pgraphInput, pgraphOutput, nVertexNode,
1029  fnClip, pvClipArg);
1030  break;
1031 #ifdef DGL_V2
1032  case 2:
1033  case 3:
1034  nRet = dgl_minimum_spanning_V2(pgraphInput, pgraphOutput, nVertexNode,
1035  fnClip, pvClipArg);
1036  break;
1037 #endif
1038  default:
1039  pgraphInput->iErrno = DGL_ERR_BadVersion;
1040  nRet = -pgraphInput->iErrno;
1041  break;
1042  }
1043  if (nRet < 0) {
1044  dglRelease(pgraphOutput);
1045  }
1046  return nRet;
1047 }
1048 
1050 {
1051  int iArc;
1052 
1053  if (pSPReport) {
1054  if (pSPReport->pArc) {
1055  for (iArc = 0; iArc < pSPReport->cArc; iArc++) {
1056  if (pSPReport->pArc[iArc].pnEdge)
1057  free(pSPReport->pArc[iArc].pnEdge);
1058  }
1059  free(pSPReport->pArc);
1060  }
1061  free(pSPReport);
1062  }
1063 }
1064 
1066 {
1067  switch (pGraph->Version) {
1068  case 1:
1069  return dgl_sp_cache_initialize_V1(pGraph, pCache, 0);
1070 #ifdef DGL_V2
1071  case 2:
1072  case 3:
1073  return dgl_sp_cache_initialize_V2(pGraph, pCache, 0);
1074 #endif
1075  }
1076  pGraph->iErrno = DGL_ERR_BadVersion;
1077  return -pGraph->iErrno;
1078 }
1079 
1081 {
1082  pGraph->iErrno = 0;
1083  switch (pGraph->Version) {
1084  case 1:
1085  dgl_sp_cache_release_V1(pGraph, pCache);
1086  break;
1087 #ifdef DGL_V2
1088  case 2:
1089  case 3:
1090  dgl_sp_cache_release_V2(pGraph, pCache);
1091  break;
1092 #endif
1093  }
1094  pGraph->iErrno = DGL_ERR_BadVersion;
1095 }
1096 
1097 int dglErrno(dglGraph_s *pgraph)
1098 {
1099  return pgraph->iErrno;
1100 }
1101 
1102 char *dglStrerror(dglGraph_s *pgraph)
1103 {
1104  switch (pgraph->iErrno) {
1105  case DGL_ERR_BadVersion:
1106  return "Bad Version";
1107  case DGL_ERR_BadNodeType:
1108  return "Bad Node Type";
1110  return "Memory Exhausted";
1111  case DGL_ERR_HeapError:
1112  return "Heap Error";
1114  return "Undefined Method";
1115  case DGL_ERR_Write:
1116  return "Write";
1117  case DGL_ERR_Read:
1118  return "Read";
1119  case DGL_ERR_NotSupported:
1120  return "Not Supported";
1122  return "Unknown Byte Order";
1123  case DGL_ERR_NodeNotFound:
1124  return "Node Not Found";
1126  return "Head Node Not Found";
1128  return "Tail Node Not Found";
1129  case DGL_ERR_BadEdge:
1130  return "Bad Edge";
1132  return "Operation Not Supported On Flat-State Graph";
1134  return "Operation Not Supported On Tree-State Graph";
1136  return "Tree Search Error";
1138  return "Unexpected Null Pointer";
1140  return "Version Not Supported";
1141  case DGL_ERR_EdgeNotFound:
1142  return "Edge Not Found";
1144  return "Node Already Exist";
1146  return "Node Is A Component";
1148  return "Edge Already Exist";
1149  case DGL_ERR_BadArgument:
1150  return "Bad Argument";
1151  }
1152 
1153  return "unknown graph error code";
1154 }
1155 
1156 /*
1157  * dglGraph_s hiders
1158  */
1160 {
1161  return pgraph->Version;
1162 }
1163 void dglSet_Version(dglGraph_s *pgraph, int nVersion)
1164 {
1165  pgraph->Version = nVersion;
1166 }
1167 
1169 {
1170  return pgraph->Endian;
1171 }
1172 
1174 {
1175  return pgraph->NodeAttrSize;
1176 }
1177 
1179 {
1180  return pgraph->EdgeAttrSize;
1181 }
1182 
1184 {
1185  return pgraph->cNode;
1186 }
1187 
1189 {
1190  return pgraph->cHead;
1191 }
1192 
1194 {
1195  return pgraph->cTail;
1196 }
1197 
1199 {
1200  return pgraph->cAlone;
1201 }
1202 
1204 {
1205  return pgraph->cEdge;
1206 }
1207 
1209 {
1210  return pgraph->Flags;
1211 }
1212 
1214 {
1215  return pgraph->aOpaqueSet;
1216 }
1217 
1218 void dglSet_Opaque(dglGraph_s *pgraph, dglInt32_t *pOpaque)
1219 {
1220  memcpy(pgraph->aOpaqueSet, pOpaque, sizeof(dglInt32_t) * 16);
1221 }
1222 
1224 {
1225  switch (pgraph->Version) {
1226  case 1:
1227  return DGL_NODE_SIZEOF_v1(pgraph->NodeAttrSize);
1228 #ifdef DGL_V2
1229  case 2:
1230  case 3:
1231  return DGL_NODE_SIZEOF_v2(pgraph->NodeAttrSize);
1232 #endif
1233  }
1234  pgraph->iErrno = DGL_ERR_BadVersion;
1235  return -pgraph->iErrno;
1236 }
1237 
1239 {
1240  switch (pgraph->Version) {
1241  case 1:
1242  return DGL_EDGE_SIZEOF_v1(pgraph->NodeAttrSize);
1243 #ifdef DGL_V2
1244  case 2:
1245  case 3:
1246  return DGL_EDGE_SIZEOF_v2(pgraph->NodeAttrSize);
1247 #endif
1248  }
1249  pgraph->iErrno = DGL_ERR_BadVersion;
1250  return -pgraph->iErrno;
1251 }
1252 
1254 {
1255  return pgraph->nnCost;
1256 }
1257 
1258 void dglSet_Cost(dglGraph_s *pgraph, dglInt64_t nnCost)
1259 {
1260  pgraph->nnCost = nnCost;
1261 }
1262 
1264 {
1265  return pgraph->nFamily;
1266 }
1267 
1268 void dglSet_Family(dglGraph_s *pgraph, dglInt32_t nFamily)
1269 {
1270  pgraph->nFamily = nFamily;
1271 }
1272 
1274 {
1275  return pgraph->nOptions;
1276 }
1277 
1278 void dglSet_Options(dglGraph_s *pgraph, dglInt32_t nOptions)
1279 {
1280  pgraph->nOptions = nOptions;
1281 }
1282 
1284 {
1285  return &pGraph->edgePrioritizer;
1286 }
1287 
1289 {
1290  return &pGraph->nodePrioritizer;
1291 }
1292 
1293 /*
1294  * Node Traverse
1295  */
1297 {
1298  switch (pGraph->Version) {
1299  case 1:
1300  return dgl_node_t_initialize_V1(pGraph, pT);
1301 #ifdef DGL_V2
1302  case 2:
1303  case 3:
1304  return dgl_node_t_initialize_V2(pGraph, pT);
1305 #endif
1306  }
1307  pGraph->iErrno = DGL_ERR_BadVersion;
1308  return -pGraph->iErrno;
1309 }
1310 
1312 {
1313  switch (pT->pGraph->Version) {
1314  case 1:
1316  return;
1317 #ifdef DGL_V2
1318  case 2:
1319  case 3:
1321  return;
1322 #endif
1323  }
1325 }
1326 
1328 {
1329  switch (pT->pGraph->Version) {
1330  case 1:
1331  return dgl_node_t_first_V1(pT);
1332 #ifdef DGL_V2
1333  case 2:
1334  case 3:
1335  return dgl_node_t_first_V2(pT);
1336 #endif
1337  }
1339  return NULL;
1340 }
1341 
1343 {
1344  switch (pT->pGraph->Version) {
1345  case 1:
1346  return dgl_node_t_next_V1(pT);
1347 #ifdef DGL_V2
1348  case 2:
1349  case 3:
1350  return dgl_node_t_next_V2(pT);
1351 #endif
1352  }
1354  return NULL;
1355 }
1356 
1358 {
1359  switch (pT->pGraph->Version) {
1360  case 1:
1361  return dgl_node_t_find_V1(pT, nNodeId);
1362 #ifdef DGL_V2
1363  case 2:
1364  case 3:
1365  return dgl_node_t_find_V2(pT, nNodeId);
1366 #endif
1367  }
1369  return NULL;
1370 }
1371 
1372 /*
1373  * Edge Traverser
1374  */
1376  dglEdgePrioritizer_s *pEdgePrioritizer)
1377 {
1378  switch (pGraph->Version) {
1379  case 1:
1380  return dgl_edge_t_initialize_V1(pGraph, pT, pEdgePrioritizer);
1381 #ifdef DGL_V2
1382  case 2:
1383  case 3:
1384  return dgl_edge_t_initialize_V2(pGraph, pT, pEdgePrioritizer);
1385 #endif
1386  }
1387  pGraph->iErrno = DGL_ERR_BadVersion;
1388  return -pGraph->iErrno;
1389 }
1390 
1392 {
1393  switch (pT->pGraph->Version) {
1394  case 1:
1396  return;
1397 #ifdef DGL_V2
1398  case 2:
1399  case 3:
1401  return;
1402 #endif
1403  }
1405 }
1406 
1408 {
1409  switch (pT->pGraph->Version) {
1410  case 1:
1411  return dgl_edge_t_first_V1(pT);
1412 #ifdef DGL_V2
1413  case 2:
1414  case 3:
1415  return dgl_edge_t_first_V2(pT);
1416 #endif
1417  }
1419  return NULL;
1420 }
1421 
1423 {
1424  switch (pT->pGraph->Version) {
1425  case 1:
1426  return dgl_edge_t_next_V1(pT);
1427 #ifdef DGL_V2
1428  case 2:
1429  case 3:
1430  return dgl_edge_t_next_V2(pT);
1431 #endif
1432  }
1434  return NULL;
1435 }
1436 
1438  dglInt32_t *pnEdgeset)
1439 {
1440  switch (pGraph->Version) {
1441  case 1:
1442  return dgl_edgeset_t_initialize_V1(pGraph, pT, pnEdgeset);
1443 #ifdef DGL_V2
1444  case 2:
1445  case 3:
1446  return dgl_edgeset_t_initialize_V2(pGraph, pT, pnEdgeset);
1447 #endif
1448  }
1449  pGraph->iErrno = DGL_ERR_BadVersion;
1450  return -pGraph->iErrno;
1451 }
1452 
1454 {
1455 }
1456 
1458 {
1459  switch (pT->pGraph->Version) {
1460  case 1:
1461  return dgl_edgeset_t_first_V1(pT);
1462 #ifdef DGL_V2
1463  case 2:
1464  case 3:
1465  return dgl_edgeset_t_first_V2(pT);
1466 #endif
1467  }
1469  return NULL;
1470 }
1471 
1473 {
1474  switch (pT->pGraph->Version) {
1475  case 1:
1476  return dgl_edgeset_t_next_V1(pT);
1477 #ifdef DGL_V2
1478  case 2:
1479  case 3:
1480  return dgl_edgeset_t_next_V2(pT);
1481 #endif
1482  }
1484  return NULL;
1485 }
1486 
1487 /*
1488  * chunked I/O
1489  */
1490 
1491 #define __CIO_BEGIN 0
1492 #define __CIO_W_HEADER 1
1493 #define __CIO_W_NODEBUFFER 2
1494 #define __CIO_W_EDGEBUFFER 3
1495 #define __CIO_R_HEADER 4
1496 #define __CIO_R_NODEBUFFER 5
1497 #define __CIO_R_EDGEBUFFER 6
1498 #define __CIO_END 7
1499 
1501 {
1502  pIO->pG = pG;
1503  pIO->nState = __CIO_BEGIN;
1504  pIO->cb = 0;
1505  pIO->ib = 0;
1506  pIO->pb = NULL;
1507  return 0;
1508 }
1509 
1511 {
1512 }
1513 
1515 {
1516  unsigned char *pb;
1517  int cb;
1518 
1519  switch (pIO->nState) {
1520  case __CIO_BEGIN:
1521  pIO->pb = pIO->ab;
1522  pb = pIO->pb;
1523  memcpy(pb, &pIO->pG->Version, 1);
1524  pb += 1; /* 1 */
1525  memcpy(pb, &pIO->pG->Endian, 1);
1526  pb += 1; /* 2 */
1527  memcpy(pb, &pIO->pG->NodeAttrSize, 4);
1528  pb += 4; /* 6 */
1529  memcpy(pb, &pIO->pG->EdgeAttrSize, 4);
1530  pb += 4; /* 10 */
1531  memcpy(pb, &pIO->pG->aOpaqueSet, 64);
1532  pb += 64; /* 74 */
1533  memcpy(pb, &pIO->pG->nOptions, 4);
1534  pb += 4; /* 78 */
1535  memcpy(pb, &pIO->pG->nFamily, 4);
1536  pb += 4; /* 82 */
1537  memcpy(pb, &pIO->pG->nnCost, 8);
1538  pb += 8; /* 90 */
1539  memcpy(pb, &pIO->pG->cNode, 4);
1540  pb += 4; /* 94 */
1541  memcpy(pb, &pIO->pG->cHead, 4);
1542  pb += 4; /* 98 */
1543  memcpy(pb, &pIO->pG->cTail, 4);
1544  pb += 4; /* 102 */
1545  memcpy(pb, &pIO->pG->cAlone, 4);
1546  pb += 4; /* 106 */
1547  memcpy(pb, &pIO->pG->cEdge, 4);
1548  pb += 4; /* 110 */
1549  memcpy(pb, &pIO->pG->iNodeBuffer, 4);
1550  pb += 4; /* 114 */
1551  memcpy(pb, &pIO->pG->iEdgeBuffer, 4);
1552  pb += 4; /* 118 */
1553  pIO->cb = 118;
1554  cb = pfn(pIO->pG, pIO->pb, pIO->cb, pv);
1555  if (cb >= 0) {
1556  pIO->ib += cb;
1557  if ((pIO->cb - pIO->ib) == 0) {
1558  pIO->ib = 0;
1559  pIO->cb = pIO->pG->iNodeBuffer;
1560  pIO->pb = pIO->pG->pNodeBuffer;
1561  pIO->nState = __CIO_W_NODEBUFFER;
1562  }
1563  else {
1564  pIO->nState = __CIO_W_HEADER;
1565  }
1566  }
1567  return cb;
1568  case __CIO_W_HEADER:
1569  cb = pfn(pIO->pG, pIO->pb + pIO->ib, pIO->cb - pIO->ib, pv);
1570  if (cb > 0) {
1571  pIO->ib += cb;
1572  if ((pIO->cb - pIO->ib) == 0) {
1573  if (pIO->pG->iNodeBuffer > 0) {
1574  pIO->ib = 0;
1575  pIO->cb = pIO->pG->iNodeBuffer;
1576  pIO->pb = pIO->pG->pNodeBuffer;
1577  pIO->nState = __CIO_W_NODEBUFFER;
1578  }
1579  else if (pIO->pG->iEdgeBuffer > 0) {
1580  pIO->ib = 0;
1581  pIO->cb = pIO->pG->iEdgeBuffer;
1582  pIO->pb = pIO->pG->pEdgeBuffer;
1583  pIO->nState = __CIO_W_EDGEBUFFER;
1584  }
1585  else {
1586  pIO->nState = __CIO_END;
1587  }
1588  }
1589  else {
1590  pIO->nState = __CIO_W_HEADER;
1591  }
1592  }
1593  return cb;
1594  case __CIO_W_NODEBUFFER:
1595  cb = pfn(pIO->pG, pIO->pb + pIO->ib, pIO->cb - pIO->ib, pv);
1596  if (cb > 0) {
1597  pIO->ib += cb;
1598  if ((pIO->cb - pIO->ib) == 0) {
1599  if (pIO->pG->iEdgeBuffer > 0) {
1600  pIO->ib = 0;
1601  pIO->cb = pIO->pG->iEdgeBuffer;
1602  pIO->pb = pIO->pG->pEdgeBuffer;
1603  pIO->nState = __CIO_W_EDGEBUFFER;
1604  }
1605  else {
1606  pIO->nState = __CIO_END;
1607  }
1608  }
1609  }
1610  return cb;
1611  case __CIO_W_EDGEBUFFER:
1612  cb = pfn(pIO->pG, pIO->pb + pIO->ib, pIO->cb - pIO->ib, pv);
1613  if (cb > 0) {
1614  pIO->ib += cb;
1615  if ((pIO->cb - pIO->ib) == 0) {
1616  pIO->nState = __CIO_END;
1617  }
1618  }
1619  return cb;
1620  case __CIO_END:
1621  pfn(pIO->pG, NULL, 0, pv); /* notify end of graph */
1622  return 0;
1623  }
1624  return 0;
1625 }
1626 
1627 int dglReadChunk(dglIOContext_s *pIO, dglByte_t *pbChunk, int cbChunk)
1628 {
1629  int i, c;
1630  unsigned char *pb;
1631 
1632  switch (pIO->nState) {
1633  case __CIO_BEGIN:
1634  pIO->cb = 118;
1635  pIO->ib = 0;
1636  pIO->pb = pIO->ab;
1637 
1638  c = MIN(cbChunk, 118);
1639  memcpy(pIO->pb, pbChunk, c);
1640  pIO->ib += c;
1641  if ((pIO->cb - pIO->ib) == 0)
1642  goto init_nodebuffer;
1643  pIO->nState = __CIO_R_HEADER;
1644  return c;
1645 
1646  case __CIO_R_HEADER:
1647  c = MIN(cbChunk, pIO->cb - pIO->ib);
1648  memcpy(pIO->pb + pIO->ib, pbChunk, c);
1649  pIO->ib += c;
1650  init_nodebuffer:
1651  if ((pIO->cb - pIO->ib) == 0) {
1652  pb = pIO->pb;
1653  memcpy(&pIO->pG->Version, pb, 1);
1654  pb += 1; /* 1 */
1655  memcpy(&pIO->pG->Endian, pb, 1);
1656  pb += 1; /* 2 */
1657  memcpy(&pIO->pG->NodeAttrSize, pb, 4);
1658  pb += 4; /* 6 */
1659  memcpy(&pIO->pG->EdgeAttrSize, pb, 4);
1660  pb += 4; /* 10 */
1661  memcpy(&pIO->pG->aOpaqueSet, pb, 64);
1662  pb += 64; /* 74 */
1663  memcpy(&pIO->pG->nOptions, pb, 4);
1664  pb += 4; /* 78 */
1665  memcpy(&pIO->pG->nFamily, pb, 4);
1666  pb += 4; /* 82 */
1667  memcpy(&pIO->pG->nnCost, pb, 8);
1668  pb += 8; /* 90 */
1669  memcpy(&pIO->pG->cNode, pb, 4);
1670  pb += 4; /* 94 */
1671  memcpy(&pIO->pG->cHead, pb, 4);
1672  pb += 4; /* 98 */
1673  memcpy(&pIO->pG->cTail, pb, 4);
1674  pb += 4; /* 102 */
1675  memcpy(&pIO->pG->cAlone, pb, 4);
1676  pb += 4; /* 106 */
1677  memcpy(&pIO->pG->cEdge, pb, 4);
1678  pb += 4; /* 110 */
1679  memcpy(&pIO->pG->iNodeBuffer, pb, 4);
1680  pb += 4; /* 114 */
1681  memcpy(&pIO->pG->iEdgeBuffer, pb, 4);
1682  pb += 4; /* 118 */
1683 
1684  pIO->fSwap = 0;
1685 #ifdef DGL_ENDIAN_BIG
1686  if (pIO->pG->Endian == DGL_ENDIAN_LITTLE)
1687  pIO->fSwap = 1;
1688 #else
1689  if (pIO->pG->Endian == DGL_ENDIAN_BIG)
1690  pIO->fSwap = 1;
1691 #endif
1692  if (pIO->fSwap) {
1695  dgl_swapInt32Bytes(&pIO->pG->nOptions);
1696  dgl_swapInt32Bytes(&pIO->pG->nFamily);
1697  dgl_swapInt64Bytes(&pIO->pG->nnCost);
1698  dgl_swapInt32Bytes(&pIO->pG->cNode);
1699  dgl_swapInt32Bytes(&pIO->pG->cHead);
1700  dgl_swapInt32Bytes(&pIO->pG->cTail);
1701  dgl_swapInt32Bytes(&pIO->pG->cAlone);
1702  dgl_swapInt32Bytes(&pIO->pG->cEdge);
1705 
1706  for (i = 0; i < 16; i++) {
1707  dgl_swapInt32Bytes(&pIO->pG->aOpaqueSet[i]);
1708  }
1709 
1710 #ifdef DGL_ENDIAN_BIG
1711  pIO->pG->Endian = DGL_ENDIAN_BIG;
1712 #else
1713  pIO->pG->Endian = DGL_ENDIAN_LITTLE;
1714 #endif
1715  }
1716 
1717  if (pIO->pG->iNodeBuffer > 0) {
1718  pIO->pG->pNodeBuffer = malloc(pIO->pG->iNodeBuffer);
1719  if (pIO->pG->pNodeBuffer == NULL) {
1720  return -1;
1721  }
1722  pIO->cb = pIO->pG->iNodeBuffer;
1723  pIO->pb = pIO->pG->pNodeBuffer;
1724  pIO->ib = 0;
1725  pIO->nState = __CIO_R_NODEBUFFER;
1726  }
1727  else {
1728  goto init_edgebuffer;
1729  }
1730  }
1731  return c;
1732  case __CIO_R_NODEBUFFER:
1733  c = MIN(cbChunk, pIO->cb - pIO->ib);
1734  memcpy(pIO->pb + pIO->ib, pbChunk, c);
1735  pIO->ib += c;
1736  init_edgebuffer:
1737  if ((pIO->cb - pIO->ib) == 0) {
1738  if (pIO->pG->iEdgeBuffer > 0) {
1739  pIO->pG->pEdgeBuffer = malloc(pIO->pG->iEdgeBuffer);
1740  if (pIO->pG->pEdgeBuffer == NULL) {
1741  return -1;
1742  }
1743  pIO->cb = pIO->pG->iEdgeBuffer;
1744  pIO->pb = pIO->pG->pEdgeBuffer;
1745  pIO->ib = 0;
1746  pIO->nState = __CIO_R_EDGEBUFFER;
1747  }
1748  else {
1749  pIO->nState = __CIO_END;
1750  }
1751  }
1752  return c;
1753  case __CIO_R_EDGEBUFFER:
1754  c = MIN(cbChunk, pIO->cb - pIO->ib);
1755  memcpy(pIO->pb + pIO->ib, pbChunk, c);
1756  pIO->ib += c;
1757  if ((pIO->cb - pIO->ib) == 0) {
1758  pIO->nState = __CIO_END;
1759  }
1760  return c;
1761  case __CIO_END: {
1762  /* switch on FLAT bit */
1763  pIO->pG->Flags |= DGL_GS_FLAT;
1764 
1765  /* nodebuffer and edgebuffer are both arrays on 32 bit integer
1766  * byte order swapping is straightforward
1767  */
1768  if (pIO->fSwap && pIO->pG->iNodeBuffer > 0) {
1769  int in, cn;
1770  dglInt32_t *pn;
1771 
1772  for (cn = pIO->pG->iNodeBuffer / sizeof(dglInt32_t),
1773  pn = (dglInt32_t *)pIO->pG->pNodeBuffer, in = 0;
1774  in < cn; in++) {
1775  dgl_swapInt32Bytes(&pn[in]);
1776  }
1777  }
1778  if (pIO->fSwap && pIO->pG->iEdgeBuffer > 0) {
1779  int in, cn;
1780  dglInt32_t *pn;
1781 
1782  for (cn = pIO->pG->iEdgeBuffer / sizeof(dglInt32_t),
1783  pn = (dglInt32_t *)pIO->pG->pEdgeBuffer, in = 0;
1784  in < cn; in++) {
1785  dgl_swapInt32Bytes(&pn[in]);
1786  }
1787  }
1788  }
1789  return 0;
1790  default:
1791  return 0;
1792  }
1793 }
#define NULL
Definition: ccmath.h:32
#define MIN(a, b)
Definition: gis.h:154
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition: gis.h:47
#define DGL_ERR_VersionNotSupported
Definition: graph.h:269
int(* dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *)
Definition: graph.h:179
#define DGL_ERR_BadOnTreeGraph
Definition: graph.h:265
#define DGL_ERR_Write
Definition: graph.h:257
#define DGL_ERR_BadNodeType
Definition: graph.h:253
#define DGL_ERR_NodeIsAComponent
Definition: graph.h:272
#define DGL_ERR_UndefinedMethod
Definition: graph.h:256
#define DGL_NS_ALONE
Definition: graph.h:61
#define DGL_ERR_BadArgument
Definition: graph.h:274
#define DGL_ERR_BadVersion
Definition: graph.h:252
#define DGL_ERR_TreeSearchError
Definition: graph.h:267
int(* dglWriteChunk_fn)(dglGraph_s *, unsigned char *pbChunk, int cbChunk, void *pvArg)
Definition: graph.h:351
#define DGL_ENDIAN_LITTLE
Definition: graph.h:72
#define DGL_ERR_MemoryExhausted
Definition: graph.h:254
#define DGL_ERR_BadOnFlatGraph
Definition: graph.h:264
#define DGL_NS_HEAD
Definition: graph.h:59
#define DGL_ERR_EdgeAlreadyExist
Definition: graph.h:273
#define DGL_ERR_NotSupported
Definition: graph.h:259
#define DGL_GS_FLAT
Definition: graph.h:36
#define DGL_ERR_Read
Definition: graph.h:258
#define DGL_ENDIAN_BIG
Definition: graph.h:71
#define DGL_ERR_UnknownByteOrder
Definition: graph.h:260
#define DGL_ERR_HeadNodeNotFound
Definition: graph.h:261
#define DGL_ERR_UnexpectedNullPointer
Definition: graph.h:268
#define DGL_ERR_BadEdge
Definition: graph.h:263
#define DGL_ERR_NodeAlreadyExist
Definition: graph.h:271
int(* dglSpanClip_fn)(dglGraph_s *, dglGraph_s *, dglSpanClipInput_s *, dglSpanClipOutput_s *, void *)
Definition: graph.h:185
#define DGL_ERR_HeapError
Definition: graph.h:255
#define DGL_ERR_EdgeNotFound
Definition: graph.h:270
#define DGL_ERR_NodeNotFound
Definition: graph.h:266
#define DGL_ERR_TailNodeNotFound
Definition: graph.h:262
int dgl_initialize_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:104
int dgl_write_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:137
int dgl_read_V1(dglGraph_s *pgraph, int fd)
Definition: graph_v1.c:232
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
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_minimum_spanning_V1(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v1.c:90
int dgl_release_V1(dglGraph_s *pgraph)
Definition: graph_v1.c:117
void dgl_node_t_release_V1(dglNodeTraverser_s *pT)
dglInt32_t * dgl_edgeset_t_next_V1(dglEdgesetTraverser_s *pTraverser)
int dgl_add_node_V1(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
int dgl_unflatten_V1(dglGraph_s *pgraph)
#define DGL_EDGE_ATTR_PTR_v1(p)
Definition: graph_v1.h:90
dglInt32_t * dgl_node_t_first_V1(dglNodeTraverser_s *pT)
dglInt32_t * dgl_node_t_find_V1(dglNodeTraverser_s *pT, dglInt32_t nId)
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)
dglInt32_t * dgl_get_edge_V1(dglGraph_s *pgraph, dglInt32_t nId)
#define DGL_NODEBUFFER_SHIFT_v1(pgrp, o)
Definition: graph_v1.h:119
dglInt32_t * dgl_edge_t_first_V1(dglEdgeTraverser_s *pT)
dglInt32_t * dgl_get_node_V1(dglGraph_s *pgraph, dglInt32_t nId)
#define DGL_NODE_SIZEOF_v1(nattr)
Definition: graph_v1.h:39
dglInt32_t * dgl_node_t_next_V1(dglNodeTraverser_s *pT)
#define DGL_EDGE_COST_v1(p)
Definition: graph_v1.h:88
#define DGL_EDGESET_EDGECOUNT_v1(p)
Definition: graph_v1.h:65
#define DGL_NODE_STATUS_v1(p)
Definition: graph_v1.h:46
dglInt32_t * dgl_edgeset_t_first_V1(dglEdgesetTraverser_s *pTraverser)
#define DGL_NODE_ATTR_PTR_v1(p)
Definition: graph_v1.h:48
int dgl_node_t_initialize_V1(dglGraph_s *pGraph, dglNodeTraverser_s *pT)
int dgl_sp_cache_initialize_V1(dglGraph_s *pgraph, dglSPCache_s *pCache, dglInt32_t nStart)
dglInt32_t * dgl_edge_t_next_V1(dglEdgeTraverser_s *pT)
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)
#define DGL_EDGE_SIZEOF_v1(lattr)
Definition: graph_v1.h:80
int dgl_flatten_V1(dglGraph_s *pgraph)
#define DGL_EDGE_TAILNODE_OFFSET_v1(p)
Definition: graph_v1.h:87
#define DGL_EDGE_HEADNODE_OFFSET_v1(p)
Definition: graph_v1.h:86
dglInt32_t * dgl_getnode_outedgeset_V1(dglGraph_s *pgraph, dglInt32_t *pnode)
int dgl_edge_t_initialize_V1(dglGraph_s *pGraph, dglEdgeTraverser_s *pTraverser, dglEdgePrioritizer_s *pEP)
#define DGL_EDGE_ID_v1(p)
Definition: graph_v1.h:89
int dgl_del_edge_V1(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_del_node_V1(dglGraph_s *pgraph, dglInt32_t nId)
#define DGL_NODE_ID_v1(p)
Definition: graph_v1.h:45
void dgl_edge_t_release_V1(dglEdgeTraverser_s *pTraverser)
int dgl_dijkstra_V2(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_v2.c:61
int dgl_write_V2(dglGraph_s *pgraph, int fd)
Definition: graph_v2.c:143
int dgl_release_V2(dglGraph_s *pgraph)
Definition: graph_v2.c:123
int dgl_depthfirst_spanning_V2(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, void *pvVisited, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v2.c:76
int dgl_initialize_V2(dglGraph_s *pgraph)
Definition: graph_v2.c:104
int dgl_read_V2(dglGraph_s *pgraph, int fd, int version)
Definition: graph_v2.c:238
int dgl_minimum_spanning_V2(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut, dglInt32_t nVertex, dglSpanClip_fn fnClip, void *pvClipArg)
Definition: graph_v2.c:90
dglInt32_t * dgl_node_t_first_V2(dglNodeTraverser_s *pT)
dglInt32_t * dgl_edge_t_next_V2(dglEdgeTraverser_s *pT)
int dgl_edgeset_t_initialize_V2(dglGraph_s *pGraph, dglEdgesetTraverser_s *pTraverser, dglInt32_t *pnEdgeset)
#define DGL_NODE_ID_v2(p)
Definition: graph_v2.h:45
int dgl_add_edge_V2(dglGraph_s *pgraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr, void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
#define DGL_NODEBUFFER_SHIFT_v2(pgrp, o)
Definition: graph_v2.h:119
int dgl_flatten_V2(dglGraph_s *pgraph)
int dgl_node_t_initialize_V2(dglGraph_s *pGraph, dglNodeTraverser_s *pT)
#define DGL_EDGE_SIZEOF_v2(lattr)
Definition: graph_v2.h:80
int dgl_edge_t_initialize_V2(dglGraph_s *pGraph, dglEdgeTraverser_s *pTraverser, dglEdgePrioritizer_s *pEP)
#define DGL_EDGE_TAILNODE_OFFSET_v2(p)
Definition: graph_v2.h:87
#define DGL_EDGE_ATTR_PTR_v2(p)
Definition: graph_v2.h:91
#define DGL_NODE_SIZEOF_v2(nattr)
Definition: graph_v2.h:39
void dgl_sp_cache_release_V2(dglGraph_s *pgraph, dglSPCache_s *pCache)
int dgl_unflatten_V2(dglGraph_s *pgraph)
dglInt32_t * dgl_getnode_inedgeset_V2(dglGraph_s *pgraph, dglInt32_t *pnode)
#define DGL_EDGESET_EDGECOUNT_v2(p)
Definition: graph_v2.h:64
dglInt32_t * dgl_edgeset_t_first_V2(dglEdgesetTraverser_s *pTraverser)
dglInt32_t * dgl_edge_t_first_V2(dglEdgeTraverser_s *pT)
#define DGL_NODE_ATTR_PTR_v2(p)
Definition: graph_v2.h:48
#define DGL_EDGE_COST_v2(p)
Definition: graph_v2.h:89
int dgl_del_edge_V2(dglGraph_s *pgraph, dglInt32_t nId)
dglInt32_t * dgl_edgeset_t_next_V2(dglEdgesetTraverser_s *pTraverser)
int dgl_del_node_V2(dglGraph_s *pgraph, dglInt32_t nId)
#define DGL_EDGE_HEADNODE_OFFSET_v2(p)
Definition: graph_v2.h:86
int dgl_sp_cache_initialize_V2(dglGraph_s *pgraph, dglSPCache_s *pCache, dglInt32_t nStart)
void dgl_node_t_release_V2(dglNodeTraverser_s *pT)
dglInt32_t * dgl_get_node_V2(dglGraph_s *pgraph, dglInt32_t nId)
int dgl_add_node_V2(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
dglInt32_t * dgl_get_edge_V2(dglGraph_s *pgraph, dglInt32_t nId)
#define DGL_EDGE_ID_v2(p)
Definition: graph_v2.h:90
dglInt32_t * dgl_node_t_find_V2(dglNodeTraverser_s *pT, dglInt32_t nId)
dglInt32_t * dgl_getnode_outedgeset_V2(dglGraph_s *pgraph, dglInt32_t *pnode)
#define DGL_NODE_STATUS_v2(p)
Definition: graph_v2.h:46
void dgl_edge_t_release_V2(dglEdgeTraverser_s *pTraverser)
dglInt32_t * dgl_node_t_next_V2(dglNodeTraverser_s *pT)
void dgl_swapInt64Bytes(dglInt64_t *pn)
Definition: helpers.c:67
void dgl_swapInt32Bytes(dglInt32_t *pn)
Definition: helpers.c:54
void * malloc(YYSIZE_T)
void free(void *)
dglByte_t * pEdgeBuffer
Definition: graph.h:161
dglInt32_t NodeAttrSize
Definition: graph.h:142
dglInt32_t cTail
Definition: graph.h:148
dglInt32_t cEdge
Definition: graph.h:150
dglByte_t Endian
Definition: graph.h:141
dglInt32_t nOptions
Definition: graph.h:155
dglInt32_t EdgeAttrSize
Definition: graph.h:143
dglEdgePrioritizer_s edgePrioritizer
Definition: graph.h:164
dglInt32_t cAlone
Definition: graph.h:149
dglByte_t * pNodeBuffer
Definition: graph.h:159
dglInt32_t iEdgeBuffer
Definition: graph.h:162
dglInt32_t iNodeBuffer
Definition: graph.h:160
dglInt32_t cHead
Definition: graph.h:147
dglInt32_t nFamily
Definition: graph.h:154
int iErrno
Definition: graph.h:138
dglInt32_t cNode
Definition: graph.h:146
dglInt32_t aOpaqueSet[16]
Definition: graph.h:144
dglByte_t Version
Definition: graph.h:140
dglNodePrioritizer_s nodePrioritizer
Definition: graph.h:165
dglInt32_t Flags
Definition: graph.h:153
dglInt64_t nnCost
Definition: graph.h:151
dglInt32_t * pnEdge
Definition: graph.h:195
dglInt32_t cArc
Definition: graph.h:206
dglSPArc_s * pArc
Definition: graph.h:207
long nKey
Definition: tree.h:61
dglGraph_s * pGraph
Definition: graph.h:243
dglGraph_s * pGraph
Definition: graph.h:233
int nState
Definition: graph.h:337
dglGraph_s * pG
Definition: graph.h:336
unsigned char ab[118]
Definition: graph.h:342
unsigned char * pb
Definition: graph.h:341
dglGraph_s * pGraph
Definition: graph.h:224
void dglTreeNodeCancel(void *pvNode, void *pvParam UNUSED)
Definition: tree.c:45
int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB, void *pvParam UNUSED)
Definition: tree.c:54
void * dglTreeGetAllocator(void)
Definition: tree.c:406
#define avl_find
Definition: tree.h:38
#define avl_create
Definition: tree.h:31
#define avl_destroy
Definition: tree.h:33
long long dglInt64_t
Definition: type.h:37
unsigned char dglByte_t
Definition: type.h:35
long dglInt32_t
Definition: type.h:36
dglEdgePrioritizer_s * dglGet_EdgePrioritizer(dglGraph_s *pGraph)
dglInt32_t * dglGetEdge(dglGraph_s *pGraph, dglInt32_t nEdgeId)
void dglSet_Family(dglGraph_s *pgraph, dglInt32_t nFamily)
int dglRead(dglGraph_s *pGraph, int fd)
int dglGet_NodeAttrSize(dglGraph_s *pgraph)
dglInt32_t dglGet_Family(dglGraph_s *pgraph)
int dglWriteChunk(dglIOContext_s *pIO, dglWriteChunk_fn pfn, void *pv)
dglInt32_t * dglNode_T_First(dglNodeTraverser_s *pT)
dglInt32_t * dglNodeGet_OutEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
void dglSet_Version(dglGraph_s *pgraph, int nVersion)
#define __CIO_W_NODEBUFFER
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)
int dglGet_EdgeAttrSize(dglGraph_s *pgraph)
#define __CIO_R_EDGEBUFFER
dglInt32_t dglNodeGet_Status(dglGraph_s *pGraph, dglInt32_t *pnNode)
int dglReadChunk(dglIOContext_s *pIO, dglByte_t *pbChunk, int cbChunk)
int dglErrno(dglGraph_s *pgraph)
int dglAddEdge(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge)
int dglEdgeset_T_Initialize(dglEdgesetTraverser_s *pT, dglGraph_s *pGraph, dglInt32_t *pnEdgeset)
int dglShortestPath(dglGraph_s *pGraph, dglSPReport_s **ppReport, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
void dglIOContextRelease(dglIOContext_s *pIO UNUSED)
void dglSet_Cost(dglGraph_s *pgraph, dglInt64_t nnCost)
char * dglStrerror(dglGraph_s *pgraph)
#define __CIO_END
int dglNode_T_Initialize(dglNodeTraverser_s *pT, dglGraph_s *pGraph)
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
void dglSet_Options(dglGraph_s *pgraph, dglInt32_t nOptions)
int dglDepthSpanning(dglGraph_s *pgraphInput, dglGraph_s *pgraphOutput, dglInt32_t nVertexNode, dglSpanClip_fn fnClip, void *pvClipArg)
void dglNodeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode, dglInt32_t *pnAttr)
dglInt32_t * dglEdgeset_T_Next(dglEdgesetTraverser_s *pT)
int dglRelease(dglGraph_s *pGraph)
dglInt32_t * dglEdgeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglEdgeGet_Tail(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglEdgeGet_Head(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglEdge_T_Next(dglEdgeTraverser_s *pT)
int dglEdgeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnAttr, dglInt32_t *pnEdge)
#define __CIO_BEGIN
dglNodePrioritizer_s * dglGet_NodePrioritizer(dglGraph_s *pGraph)
#define __CIO_W_EDGEBUFFER
int dglInitialize(dglGraph_s *pGraph, dglByte_t Version, dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, dglInt32_t *pOpaqueSet)
#define __CIO_W_HEADER
int dglGet_Endianess(dglGraph_s *pgraph)
int dglGet_EdgeSize(dglGraph_s *pgraph)
int dglGet_EdgeCount(dglGraph_s *pgraph)
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
void dglFreeSPReport(dglGraph_s *pgraph UNUSED, dglSPReport_s *pSPReport)
int dglMinimumSpanning(dglGraph_s *pgraphInput, dglGraph_s *pgraphOutput, dglInt32_t nVertexNode, dglSpanClip_fn fnClip, void *pvClipArg)
int dglShortestDistance(dglGraph_s *pGraph, dglInt32_t *pnDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
int dglNodeGet_OutDegree(dglGraph_s *pGraph, dglInt32_t *pnNode)
int dglEdge_T_Initialize(dglEdgeTraverser_s *pT, dglGraph_s *pGraph, dglEdgePrioritizer_s *pEdgePrioritizer)
int dglDelEdge(dglGraph_s *pGraph, dglInt32_t nEdgeId)
int dglNodeGet_Valence(dglGraph_s *pGraph, dglInt32_t *pnNode)
int dglNodeGet_InDegree(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t * dglNode_T_Next(dglNodeTraverser_s *pT)
int dglInitializeSPCache(dglGraph_s *pGraph, dglSPCache_s *pCache)
int dglGet_NodeCount(dglGraph_s *pgraph)
int dglGet_Version(dglGraph_s *pgraph)
int dglWrite(dglGraph_s *pGraph, int fd)
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT UNUSED)
int dglGet_AloneNodeCount(dglGraph_s *pgraph)
int dglFlatten(dglGraph_s *pGraph)
dglInt32_t * dglNodeGet_InEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
int dglDepthComponents(dglGraph_s *pgraphInput, dglGraph_s *pgraphComponents, int cgraphComponents, dglSpanClip_fn fnClip, void *pvClipArg)
void dglNode_T_Release(dglNodeTraverser_s *pT)
dglInt32_t * dglEdge_T_First(dglEdgeTraverser_s *pT)
dglInt32_t dglEdgesetGet_EdgeCount(dglGraph_s *pGraph, dglInt32_t *pnEdgeset)
int dglUnflatten(dglGraph_s *pGraph)
dglInt32_t dglGet_Options(dglGraph_s *pgraph)
int dglGet_NodeSize(dglGraph_s *pgraph)
void dglEdge_T_Release(dglEdgeTraverser_s *pT)
int dglGet_TailNodeCount(dglGraph_s *pgraph)
dglInt32_t * dglGet_Opaque(dglGraph_s *pgraph)
void dglReleaseSPCache(dglGraph_s *pGraph, dglSPCache_s *pCache)
void dglSet_Opaque(dglGraph_s *pgraph, dglInt32_t *pOpaque)
int dglIOContextInitialize(dglGraph_s *pG, dglIOContext_s *pIO)
dglInt32_t * dglNode_T_Find(dglNodeTraverser_s *pT, dglInt32_t nNodeId)
void dglResetStats(dglGraph_s *pgraph UNUSED)
#define __CIO_R_NODEBUFFER
int dglDelNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
#define __CIO_R_HEADER
dglInt64_t dglGet_Cost(dglGraph_s *pgraph)
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
int dglGet_HeadNodeCount(dglGraph_s *pgraph)
int dglGet_State(dglGraph_s *pgraph)
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
int dglAddNode(dglGraph_s *pGraph, dglInt32_t nNodeId, void *pvNodeAttr, dglInt32_t nFlags)