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