GRASS Programmer's Manual
6.4.2(2012)
|
00001 /* LIBDGL -- a Directed Graph Library implementation 00002 * Copyright (C) 2002 Roberto Micarelli 00003 * 00004 * This program is free software; you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation; either version 2 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program; if not, write to the Free Software 00016 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00017 */ 00018 00019 /* 00020 * best view with tabstop=4 00021 */ 00022 00023 #include <stdio.h> 00024 #include <string.h> 00025 #include <sys/types.h> 00026 #include <sys/stat.h> 00027 #include <unistd.h> 00028 #include <stdlib.h> 00029 #include <errno.h> 00030 00031 #define DGL_V2 1 00032 00033 #include "type.h" 00034 #include "tree.h" 00035 #include "graph.h" 00036 #include "graph_v1.h" 00037 #if defined(DGL_V2) 00038 #include "graph_v2.h" 00039 #endif 00040 #include "helpers.h" 00041 00042 00043 void dglResetStats(dglGraph_s * pgraph) 00044 { 00045 #ifdef DGL_STATS 00046 pgraph->clkAddEdge = 0; 00047 pgraph->cAddEdge = 0; 00048 pgraph->clkNodeTree = 0; 00049 pgraph->cNodeTree = 0; 00050 #endif 00051 } 00052 00053 int dglInitialize(dglGraph_s * pGraph, dglByte_t Version, 00054 dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, 00055 dglInt32_t * pOpaqueSet) 00056 { 00057 if (pGraph == NULL) { 00058 return -DGL_ERR_BadArgument; 00059 } 00060 switch (Version) { 00061 case 1: 00062 #ifdef DGL_V2 00063 case 2: 00064 case 3: 00065 #endif 00066 memset(pGraph, 0, sizeof(dglGraph_s)); 00067 /* 00068 * round attr size to the upper multiple of dglInt32_t size 00069 */ 00070 if (NodeAttrSize % sizeof(dglInt32_t)) 00071 NodeAttrSize += 00072 (sizeof(dglInt32_t) - (NodeAttrSize % sizeof(dglInt32_t))); 00073 if (EdgeAttrSize % sizeof(dglInt32_t)) 00074 EdgeAttrSize += 00075 (sizeof(dglInt32_t) - (EdgeAttrSize % sizeof(dglInt32_t))); 00076 pGraph->Version = Version; 00077 pGraph->NodeAttrSize = NodeAttrSize; 00078 pGraph->EdgeAttrSize = EdgeAttrSize; 00079 if (pOpaqueSet) 00080 memcpy(&pGraph->aOpaqueSet, pOpaqueSet, sizeof(dglInt32_t) * 16); 00081 #ifdef DGL_ENDIAN_BIG 00082 pGraph->Endian = DGL_ENDIAN_BIG; 00083 #else 00084 pGraph->Endian = DGL_ENDIAN_LITTLE; 00085 #endif 00086 } 00087 switch (Version) { 00088 case 1: 00089 if (dgl_initialize_V1(pGraph) < 0) { 00090 return -pGraph->iErrno; 00091 } 00092 else 00093 return 0; 00094 #ifdef DGL_V2 00095 case 2: 00096 case 3: 00097 if (dgl_initialize_V2(pGraph) < 0) { 00098 return -pGraph->iErrno; 00099 } 00100 else 00101 return 0; 00102 #endif 00103 } 00104 pGraph->iErrno = DGL_ERR_VersionNotSupported; 00105 return -pGraph->iErrno; 00106 } 00107 00108 int dglRelease(dglGraph_s * pGraph) 00109 { 00110 switch (pGraph->Version) { 00111 case 1: 00112 return dgl_release_V1(pGraph); 00113 #ifdef DGL_V2 00114 case 2: 00115 case 3: 00116 return dgl_release_V2(pGraph); 00117 #endif 00118 } 00119 pGraph->iErrno = DGL_ERR_BadVersion; 00120 return -pGraph->iErrno; 00121 } 00122 00123 int dglUnflatten(dglGraph_s * pGraph) 00124 { 00125 switch (pGraph->Version) { 00126 case 1: 00127 return dgl_unflatten_V1(pGraph); 00128 #ifdef DGL_V2 00129 case 2: 00130 case 3: 00131 return dgl_unflatten_V2(pGraph); 00132 #endif 00133 } 00134 pGraph->iErrno = DGL_ERR_BadVersion; 00135 return -pGraph->iErrno; 00136 } 00137 00138 00139 int dglFlatten(dglGraph_s * pGraph) 00140 { 00141 switch (pGraph->Version) { 00142 case 1: 00143 return dgl_flatten_V1(pGraph); 00144 #ifdef DGL_V2 00145 case 2: 00146 case 3: 00147 return dgl_flatten_V2(pGraph); 00148 #endif 00149 } 00150 pGraph->iErrno = DGL_ERR_BadVersion; 00151 return -pGraph->iErrno; 00152 } 00153 00154 00155 dglInt32_t *dglGetNode(dglGraph_s * pGraph, dglInt32_t nNodeId) 00156 { 00157 switch (pGraph->Version) { 00158 case 1: 00159 return dgl_get_node_V1(pGraph, nNodeId); 00160 #ifdef DGL_V2 00161 case 2: 00162 case 3: 00163 return dgl_get_node_V2(pGraph, nNodeId); 00164 #endif 00165 } 00166 pGraph->iErrno = DGL_ERR_BadVersion; 00167 return NULL; 00168 } 00169 00170 dglInt32_t *dglNodeGet_OutEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode) 00171 { 00172 if (pnNode) { 00173 switch (pGraph->Version) { 00174 case 1: 00175 return dgl_getnode_outedgeset_V1(pGraph, pnNode); 00176 #ifdef DGL_V2 00177 case 2: 00178 case 3: 00179 return dgl_getnode_outedgeset_V2(pGraph, pnNode); 00180 #endif 00181 } 00182 pGraph->iErrno = DGL_ERR_BadVersion; 00183 return NULL; 00184 } 00185 return NULL; 00186 } 00187 00188 dglInt32_t *dglNodeGet_InEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode) 00189 { 00190 if (pnNode) { 00191 switch (pGraph->Version) { 00192 case 1: 00193 pGraph->iErrno = DGL_ERR_NotSupported; 00194 return NULL; 00195 #ifdef DGL_V2 00196 case 2: 00197 case 3: 00198 return dgl_getnode_inedgeset_V2(pGraph, pnNode); 00199 #endif 00200 } 00201 pGraph->iErrno = DGL_ERR_BadVersion; 00202 return NULL; 00203 } 00204 return NULL; 00205 } 00206 00207 00208 00209 /* 00210 * Given that node id can be negative, only iErrno can report a error, 00211 * thus it is initialized to zero 00212 */ 00213 dglInt32_t dglNodeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnNode) 00214 { 00215 pGraph->iErrno = 0; 00216 if (pnNode) { 00217 switch (pGraph->Version) { 00218 case 1: 00219 return DGL_NODE_ID_v1(pnNode); 00220 #ifdef DGL_V2 00221 case 2: 00222 case 3: 00223 return DGL_NODE_ID_v2(pnNode); 00224 #endif 00225 } 00226 pGraph->iErrno = DGL_ERR_BadVersion; 00227 return 0; 00228 } 00229 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00230 return 0; 00231 } 00232 00233 00234 dglInt32_t dglNodeGet_Status(dglGraph_s * pGraph, dglInt32_t * pnNode) 00235 { 00236 pGraph->iErrno = 0; 00237 if (pnNode) { 00238 switch (pGraph->Version) { 00239 case 1: 00240 return DGL_NODE_STATUS_v1(pnNode); 00241 #ifdef DGL_V2 00242 case 2: 00243 case 3: 00244 return DGL_NODE_STATUS_v2(pnNode); 00245 #endif 00246 } 00247 pGraph->iErrno = DGL_ERR_BadVersion; 00248 return 0; 00249 } 00250 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00251 return 0; 00252 } 00253 00254 00255 dglInt32_t *dglNodeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode) 00256 { 00257 if (pnNode) { 00258 switch (pGraph->Version) { 00259 case 1: 00260 return DGL_NODE_ATTR_PTR_v1(pnNode); 00261 #ifdef DGL_V2 00262 case 2: 00263 case 3: 00264 return DGL_NODE_ATTR_PTR_v2(pnNode); 00265 #endif 00266 } 00267 pGraph->iErrno = DGL_ERR_BadVersion; 00268 return NULL; 00269 } 00270 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00271 return NULL; 00272 } 00273 00274 00275 void dglNodeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode, 00276 dglInt32_t * pnAttr) 00277 { 00278 if (pnNode) { 00279 switch (pGraph->Version) { 00280 case 1: 00281 memcpy(DGL_NODE_ATTR_PTR_v1(pnNode), pnAttr, 00282 pGraph->NodeAttrSize); 00283 return; 00284 #ifdef DGL_V2 00285 case 2: 00286 case 3: 00287 memcpy(DGL_NODE_ATTR_PTR_v2(pnNode), pnAttr, 00288 pGraph->NodeAttrSize); 00289 return; 00290 #endif 00291 } 00292 return; 00293 } 00294 return; 00295 } 00296 00297 int dglNodeGet_InDegree(dglGraph_s * pGraph, dglInt32_t * pnNode) 00298 { 00299 #ifdef DGL_V2 00300 dglInt32_t *pinedgeset; 00301 #endif 00302 00303 pGraph->iErrno = 0; 00304 if (pnNode) { 00305 switch (pGraph->Version) { 00306 case 1: 00307 pGraph->iErrno = DGL_ERR_NotSupported; 00308 return 0; 00309 #ifdef DGL_V2 00310 case 2: 00311 if (DGL_NODE_STATUS_v2(pnNode) & DGL_NS_ALONE) 00312 return 0; 00313 pinedgeset = dglNodeGet_InEdgeset(pGraph, pnNode); 00314 if (pinedgeset) 00315 return DGL_EDGESET_EDGECOUNT_v2(pinedgeset); 00316 return 0; 00317 case 3: 00318 return dglNodeGet_Valence(pGraph, pnNode); 00319 #endif 00320 } 00321 pGraph->iErrno = DGL_ERR_BadVersion; 00322 return 0; 00323 } 00324 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00325 return 0; 00326 } 00327 00328 00329 int dglNodeGet_OutDegree(dglGraph_s * pGraph, dglInt32_t * pnNode) 00330 { 00331 dglInt32_t *poutedgeset; 00332 00333 pGraph->iErrno = 0; 00334 if (pnNode) { 00335 switch (pGraph->Version) { 00336 case 1: 00337 if (DGL_NODE_STATUS_v1(pnNode) & DGL_NS_ALONE) 00338 return 0; 00339 poutedgeset = dglNodeGet_OutEdgeset(pGraph, pnNode); 00340 if (poutedgeset) 00341 return DGL_EDGESET_EDGECOUNT_v1(poutedgeset); 00342 return 0; 00343 #ifdef DGL_V2 00344 case 2: 00345 if (DGL_NODE_STATUS_v2(pnNode) & DGL_NS_ALONE) 00346 return 0; 00347 poutedgeset = dglNodeGet_OutEdgeset(pGraph, pnNode); 00348 if (poutedgeset) 00349 return DGL_EDGESET_EDGECOUNT_v2(poutedgeset); 00350 return 0; 00351 case 3: 00352 return dglNodeGet_Valence(pGraph, pnNode); 00353 #endif 00354 } 00355 pGraph->iErrno = DGL_ERR_BadVersion; 00356 return 0; 00357 } 00358 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00359 return 0; 00360 } 00361 00362 00363 int dglNodeGet_Valence(dglGraph_s * pGraph, dglInt32_t * pnNode) 00364 { 00365 #ifdef DGL_V2 00366 dglInt32_t *poutedgeset; 00367 dglInt32_t *pinedgeset; 00368 int c; 00369 #endif 00370 00371 pGraph->iErrno = 0; 00372 if (pnNode) { 00373 switch (pGraph->Version) { 00374 #ifdef DGL_V2 00375 case 3: 00376 if (DGL_NODE_STATUS_v2(pnNode) & DGL_NS_ALONE) 00377 return 0; 00378 poutedgeset = dglNodeGet_OutEdgeset(pGraph, pnNode); 00379 pinedgeset = dglNodeGet_InEdgeset(pGraph, pnNode); 00380 c = 0; 00381 if (poutedgeset) 00382 c += DGL_EDGESET_EDGECOUNT_v2(poutedgeset); 00383 if (pinedgeset) 00384 c += DGL_EDGESET_EDGECOUNT_v2(pinedgeset); 00385 return c; 00386 #endif 00387 } 00388 pGraph->iErrno = DGL_ERR_BadVersion; 00389 return 0; 00390 } 00391 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00392 return 0; 00393 } 00394 00395 00396 00397 dglInt32_t dglEdgesetGet_EdgeCount(dglGraph_s * pGraph, 00398 dglInt32_t * pnEdgeset) 00399 { 00400 pGraph->iErrno = 0; 00401 if (pnEdgeset) { 00402 switch (pGraph->Version) { 00403 case 1: 00404 return DGL_EDGESET_EDGECOUNT_v1(pnEdgeset); 00405 #ifdef DGL_V2 00406 case 2: 00407 case 3: 00408 return DGL_EDGESET_EDGECOUNT_v2(pnEdgeset); 00409 #endif 00410 } 00411 pGraph->iErrno = DGL_ERR_BadVersion; 00412 return 0; 00413 } 00414 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00415 return 0; 00416 } 00417 00418 dglInt32_t dglEdgeGet_Cost(dglGraph_s * pGraph, dglInt32_t * pnEdge) 00419 { 00420 pGraph->iErrno = 0; 00421 if (pnEdge) { 00422 switch (pGraph->Version) { 00423 case 1: 00424 return DGL_EDGE_COST_v1(pnEdge); 00425 #ifdef DGL_V2 00426 case 2: 00427 case 3: 00428 return DGL_EDGE_COST_v2(pnEdge); 00429 #endif 00430 } 00431 pGraph->iErrno = DGL_ERR_BadVersion; 00432 return 0; 00433 } 00434 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00435 return 0; 00436 } 00437 00438 dglInt32_t dglEdgeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnEdge) 00439 { 00440 pGraph->iErrno = 0; 00441 if (pnEdge) { 00442 switch (pGraph->Version) { 00443 case 1: 00444 return DGL_EDGE_ID_v1(pnEdge); 00445 #ifdef DGL_V2 00446 case 2: 00447 case 3: 00448 return DGL_EDGE_ID_v2(pnEdge); 00449 #endif 00450 } 00451 pGraph->iErrno = DGL_ERR_BadVersion; 00452 return 0; 00453 } 00454 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00455 return 0; 00456 } 00457 00458 dglInt32_t *dglEdgeGet_Head(dglGraph_s * pGraph, dglInt32_t * pnEdge) 00459 { 00460 pGraph->iErrno = 0; 00461 if (pnEdge) { 00462 switch (pGraph->Version) { 00463 case 1: 00464 if (pGraph->Flags & DGL_GS_FLAT) { 00465 return DGL_NODEBUFFER_SHIFT_v1(pGraph, 00466 DGL_EDGE_HEADNODE_OFFSET_v1 00467 (pnEdge)); 00468 } 00469 else { 00470 return dgl_get_node_V1(pGraph, 00471 DGL_EDGE_HEADNODE_OFFSET_v1(pnEdge)); 00472 } 00473 #ifdef DGL_V2 00474 case 2: 00475 case 3: 00476 if (pGraph->Flags & DGL_GS_FLAT) { 00477 return DGL_NODEBUFFER_SHIFT_v2(pGraph, 00478 DGL_EDGE_HEADNODE_OFFSET_v2 00479 (pnEdge)); 00480 } 00481 else { 00482 return dgl_get_node_V2(pGraph, 00483 DGL_EDGE_HEADNODE_OFFSET_v2(pnEdge)); 00484 } 00485 #endif 00486 } 00487 pGraph->iErrno = DGL_ERR_BadVersion; 00488 return NULL; 00489 } 00490 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00491 return NULL; 00492 } 00493 00494 dglInt32_t *dglEdgeGet_Tail(dglGraph_s * pGraph, dglInt32_t * pnEdge) 00495 { 00496 pGraph->iErrno = 0; 00497 if (pnEdge) { 00498 switch (pGraph->Version) { 00499 case 1: 00500 if (pGraph->Flags & DGL_GS_FLAT) { 00501 return DGL_NODEBUFFER_SHIFT_v1(pGraph, 00502 DGL_EDGE_TAILNODE_OFFSET_v1 00503 (pnEdge)); 00504 } 00505 else { 00506 return dgl_get_node_V1(pGraph, 00507 DGL_EDGE_TAILNODE_OFFSET_v1(pnEdge)); 00508 } 00509 #ifdef DGL_V2 00510 case 2: 00511 case 3: 00512 if (pGraph->Flags & DGL_GS_FLAT) { 00513 return DGL_NODEBUFFER_SHIFT_v2(pGraph, 00514 DGL_EDGE_TAILNODE_OFFSET_v2 00515 (pnEdge)); 00516 } 00517 else { 00518 return dgl_get_node_V2(pGraph, 00519 DGL_EDGE_TAILNODE_OFFSET_v2(pnEdge)); 00520 } 00521 #endif 00522 } 00523 pGraph->iErrno = DGL_ERR_BadVersion; 00524 return NULL; 00525 } 00526 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00527 return NULL; 00528 } 00529 00530 dglInt32_t *dglEdgeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnEdge) 00531 { 00532 pGraph->iErrno = 0; 00533 if (pnEdge) { 00534 switch (pGraph->Version) { 00535 case 1: 00536 return DGL_EDGE_ATTR_PTR_v1(pnEdge); 00537 #ifdef DGL_V2 00538 case 2: 00539 case 3: 00540 return DGL_EDGE_ATTR_PTR_v2(pnEdge); 00541 #endif 00542 } 00543 pGraph->iErrno = DGL_ERR_BadVersion; 00544 return NULL; 00545 } 00546 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00547 return NULL; 00548 } 00549 00550 int dglEdgeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnAttr, 00551 dglInt32_t * pnEdge) 00552 { 00553 if (pnEdge) { 00554 switch (pGraph->Version) { 00555 case 1: 00556 memcpy(DGL_EDGE_ATTR_PTR_v1(pnEdge), pnAttr, 00557 pGraph->EdgeAttrSize); 00558 return 0; 00559 #ifdef DGL_V2 00560 case 2: 00561 case 3: 00562 memcpy(DGL_EDGE_ATTR_PTR_v2(pnEdge), pnAttr, 00563 pGraph->EdgeAttrSize); 00564 return 0; 00565 #endif 00566 } 00567 pGraph->iErrno = DGL_ERR_BadVersion; 00568 return -pGraph->iErrno; 00569 } 00570 pGraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00571 return -pGraph->iErrno; 00572 } 00573 00574 00575 00576 dglInt32_t *dglGetEdge(dglGraph_s * pGraph, dglInt32_t nEdgeId) 00577 { 00578 switch (pGraph->Version) { 00579 case 1: 00580 return dgl_get_edge_V1(pGraph, nEdgeId); 00581 break; 00582 #ifdef DGL_V2 00583 case 2: 00584 case 3: 00585 return dgl_get_edge_V2(pGraph, nEdgeId); 00586 break; 00587 #endif 00588 } 00589 pGraph->iErrno = DGL_ERR_BadVersion; 00590 return NULL; 00591 } 00592 00593 int dglDelEdge(dglGraph_s * pGraph, dglInt32_t nEdgeId) 00594 { 00595 switch (pGraph->Version) { 00596 case 1: 00597 return dgl_del_edge_V1(pGraph, nEdgeId); 00598 break; 00599 #ifdef DGL_V2 00600 case 2: 00601 case 3: 00602 return dgl_del_edge_V2(pGraph, nEdgeId); 00603 break; 00604 #endif 00605 } 00606 pGraph->iErrno = DGL_ERR_BadVersion; 00607 return -pGraph->iErrno; 00608 } 00609 00610 int dglAddEdge(dglGraph_s * pGraph, 00611 dglInt32_t nHead, 00612 dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge) 00613 { 00614 int nRet; 00615 00616 #ifdef DGL_STATS 00617 clock_t clk; 00618 00619 clk = clock(); 00620 pGraph->cAddEdge++; 00621 #endif 00622 switch (pGraph->Version) { 00623 case 1: 00624 nRet = 00625 dgl_add_edge_V1(pGraph, nHead, nTail, nCost, nEdge, NULL, NULL, 00626 NULL, 0); 00627 break; 00628 #ifdef DGL_V2 00629 case 2: 00630 case 3: 00631 nRet = 00632 dgl_add_edge_V2(pGraph, nHead, nTail, nCost, nEdge, NULL, NULL, 00633 NULL, 0); 00634 break; 00635 #endif 00636 default: 00637 pGraph->iErrno = DGL_ERR_BadVersion; 00638 nRet = -pGraph->iErrno; 00639 break; 00640 } 00641 #ifdef DGL_STATS 00642 pGraph->clkAddEdge += clock() - clk; 00643 #endif 00644 return nRet; 00645 } 00646 00647 int dglAddEdgeX(dglGraph_s * pGraph, 00648 dglInt32_t nHead, 00649 dglInt32_t nTail, 00650 dglInt32_t nCost, 00651 dglInt32_t nEdge, 00652 void *pvHeadAttr, 00653 void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags) 00654 { 00655 int nRet; 00656 00657 #ifdef DGL_STATS 00658 clock_t clk; 00659 00660 clk = clock(); 00661 pGraph->cAddEdge++; 00662 #endif 00663 switch (pGraph->Version) { 00664 case 1: 00665 nRet = 00666 dgl_add_edge_V1(pGraph, nHead, nTail, nCost, nEdge, pvHeadAttr, 00667 pvTailAttr, pvEdgeAttr, nFlags); 00668 break; 00669 #ifdef DGL_V2 00670 case 2: 00671 case 3: 00672 nRet = 00673 dgl_add_edge_V2(pGraph, nHead, nTail, nCost, nEdge, pvHeadAttr, 00674 pvTailAttr, pvEdgeAttr, nFlags); 00675 break; 00676 #endif 00677 default: 00678 pGraph->iErrno = DGL_ERR_BadVersion; 00679 nRet = -pGraph->iErrno; 00680 break; 00681 } 00682 #ifdef DGL_STATS 00683 pGraph->clkAddEdge += clock() - clk; 00684 #endif 00685 return nRet; 00686 } 00687 00688 int dglAddNode(dglGraph_s * pGraph, 00689 dglInt32_t nNodeId, void *pvNodeAttr, dglInt32_t nFlags) 00690 { 00691 int nRet; 00692 00693 switch (pGraph->Version) { 00694 case 1: 00695 nRet = dgl_add_node_V1(pGraph, nNodeId, pvNodeAttr, nFlags); 00696 break; 00697 #ifdef DGL_V2 00698 case 2: 00699 case 3: 00700 nRet = dgl_add_node_V2(pGraph, nNodeId, pvNodeAttr, nFlags); 00701 break; 00702 #endif 00703 default: 00704 pGraph->iErrno = DGL_ERR_BadVersion; 00705 nRet = -pGraph->iErrno; 00706 break; 00707 } 00708 return nRet; 00709 } 00710 00711 int dglDelNode(dglGraph_s * pGraph, dglInt32_t nNodeId) 00712 { 00713 int nRet; 00714 00715 switch (pGraph->Version) { 00716 case 1: 00717 nRet = dgl_del_node_V1(pGraph, nNodeId); 00718 break; 00719 #ifdef DGL_V2 00720 case 2: 00721 case 3: 00722 nRet = dgl_del_node_V2(pGraph, nNodeId); 00723 break; 00724 #endif 00725 default: 00726 pGraph->iErrno = DGL_ERR_BadVersion; 00727 nRet = -pGraph->iErrno; 00728 break; 00729 } 00730 return nRet; 00731 } 00732 00733 int dglWrite(dglGraph_s * pGraph, int fd) 00734 { 00735 int nRet; 00736 00737 switch (pGraph->Version) { 00738 case 1: 00739 nRet = dgl_write_V1(pGraph, fd); 00740 break; 00741 #ifdef DGL_V2 00742 case 2: 00743 case 3: 00744 nRet = dgl_write_V2(pGraph, fd); 00745 break; 00746 #endif 00747 default: 00748 pGraph->iErrno = DGL_ERR_BadVersion; 00749 nRet = -pGraph->iErrno; 00750 break; 00751 } 00752 return nRet; 00753 } 00754 00755 int dglRead(dglGraph_s * pGraph, int fd) 00756 { 00757 dglByte_t bVersion; 00758 int nRet; 00759 00760 if (read(fd, &bVersion, 1) != 1) { 00761 pGraph->iErrno = DGL_ERR_Read; 00762 nRet = -pGraph->iErrno; 00763 } 00764 else { 00765 switch (bVersion) { 00766 case 1: 00767 nRet = dgl_read_V1(pGraph, fd); 00768 break; 00769 #ifdef DGL_V2 00770 case 2: 00771 case 3: 00772 nRet = dgl_read_V2(pGraph, fd, bVersion); 00773 break; 00774 #endif 00775 default: 00776 pGraph->iErrno = DGL_ERR_VersionNotSupported; 00777 nRet = -pGraph->iErrno; 00778 break; 00779 } 00780 } 00781 return nRet; 00782 } 00783 00784 00785 int dglShortestPath(dglGraph_s * pGraph, 00786 dglSPReport_s ** ppReport, 00787 dglInt32_t nStart, 00788 dglInt32_t nDestination, 00789 dglSPClip_fn fnClip, 00790 void *pvClipArg, dglSPCache_s * pCache) 00791 { 00792 int nRet; 00793 00794 switch (pGraph->Version) { 00795 case 1: 00796 nRet = 00797 dgl_dijkstra_V1(pGraph, ppReport, NULL, nStart, nDestination, 00798 fnClip, pvClipArg, pCache); 00799 break; 00800 #ifdef DGL_V2 00801 case 2: 00802 case 3: 00803 nRet = 00804 dgl_dijkstra_V2(pGraph, ppReport, NULL, nStart, nDestination, 00805 fnClip, pvClipArg, pCache); 00806 break; 00807 #endif 00808 default: 00809 pGraph->iErrno = DGL_ERR_BadVersion; 00810 nRet = -pGraph->iErrno; 00811 break; 00812 } 00813 return nRet; 00814 } 00815 00816 00817 int dglShortestDistance(dglGraph_s * pGraph, 00818 dglInt32_t * pnDistance, 00819 dglInt32_t nStart, 00820 dglInt32_t nDestination, 00821 dglSPClip_fn fnClip, 00822 void *pvClipArg, dglSPCache_s * pCache) 00823 { 00824 int nRet; 00825 00826 switch (pGraph->Version) { 00827 case 1: 00828 nRet = 00829 dgl_dijkstra_V1(pGraph, NULL, pnDistance, nStart, nDestination, 00830 fnClip, pvClipArg, pCache); 00831 break; 00832 #ifdef DGL_V2 00833 case 2: 00834 case 3: 00835 nRet = 00836 dgl_dijkstra_V2(pGraph, NULL, pnDistance, nStart, nDestination, 00837 fnClip, pvClipArg, pCache); 00838 break; 00839 #endif 00840 default: 00841 pGraph->iErrno = DGL_ERR_BadVersion; 00842 nRet = -pGraph->iErrno; 00843 break; 00844 } 00845 return nRet; 00846 } 00847 00848 00849 int dglDepthSpanning(dglGraph_s * pgraphInput, 00850 dglGraph_s * pgraphOutput, 00851 dglInt32_t nVertexNode, 00852 dglSpanClip_fn fnClip, void *pvClipArg) 00853 { 00854 int nRet; 00855 void *pvVisited; 00856 00857 if (dglGet_EdgeCount(pgraphInput) == 0) { /* no span */ 00858 pgraphInput->iErrno = 0; 00859 return 0; 00860 } 00861 00862 #ifndef DGL_V2 00863 if (pgraphInput->Version == 2) { 00864 pgraphInput->iErrno = DGL_ERR_BadVersion; 00865 return -pgraphInput->iErrno; 00866 } 00867 #endif 00868 00869 nRet = dglInitialize(pgraphOutput, 00870 dglGet_Version(pgraphInput), 00871 dglGet_NodeAttrSize(pgraphInput), 00872 dglGet_EdgeAttrSize(pgraphInput), 00873 dglGet_Opaque(pgraphInput)); 00874 00875 if (nRet < 0) 00876 return nRet; 00877 00878 if ((pvVisited = 00879 avl_create(dglTreeNodeCompare, NULL, 00880 dglTreeGetAllocator())) == NULL) { 00881 pgraphInput->iErrno = DGL_ERR_MemoryExhausted; 00882 return -pgraphInput->iErrno; 00883 } 00884 00885 switch (pgraphInput->Version) { 00886 case 1: 00887 nRet = 00888 dgl_depthfirst_spanning_V1(pgraphInput, pgraphOutput, nVertexNode, 00889 pvVisited, fnClip, pvClipArg); 00890 break; 00891 #ifdef DGL_V2 00892 case 2: 00893 case 3: 00894 nRet = 00895 dgl_depthfirst_spanning_V2(pgraphInput, pgraphOutput, nVertexNode, 00896 pvVisited, fnClip, pvClipArg); 00897 break; 00898 #endif 00899 default: 00900 pgraphInput->iErrno = DGL_ERR_BadVersion; 00901 nRet = -pgraphInput->iErrno; 00902 break; 00903 } 00904 00905 avl_destroy(pvVisited, dglTreeNodeCancel); 00906 00907 if (nRet < 0) { 00908 dglRelease(pgraphOutput); 00909 } 00910 00911 return nRet; 00912 } 00913 00914 int dglDepthComponents(dglGraph_s * pgraphInput, 00915 dglGraph_s * pgraphComponents, 00916 int cgraphComponents, 00917 dglSpanClip_fn fnClip, void *pvClipArg) 00918 { 00919 int i, nret = 0; 00920 dglTreeNode_s findVisited; 00921 void *pvVisited; 00922 dglInt32_t *pvertex, *pnode; 00923 00924 if (dglGet_EdgeCount(pgraphInput) == 0) { /* no span */ 00925 pgraphInput->iErrno = 0; 00926 return 0; 00927 } 00928 00929 #ifndef DGL_V2 00930 if (pgraphInput->Version == 2 || pgraphInput->Version == 3) { 00931 pgraphInput->iErrno = DGL_ERR_BadVersion; 00932 return -pgraphInput->iErrno; 00933 } 00934 #endif 00935 00936 if ((pvVisited = 00937 avl_create(dglTreeNodeCompare, NULL, 00938 dglTreeGetAllocator())) == NULL) { 00939 pgraphInput->iErrno = DGL_ERR_MemoryExhausted; 00940 goto error; 00941 } 00942 00943 /* 00944 * choose a vertex to start from 00945 */ 00946 pvertex = NULL; 00947 { 00948 dglNodeTraverser_s pT; 00949 00950 dglNode_T_Initialize(&pT, pgraphInput); 00951 for (pnode = dglNode_T_First(&pT); pnode; pnode = dglNode_T_Next(&pT)) { 00952 switch (pgraphInput->Version) { 00953 case 1: 00954 if (DGL_NODE_STATUS_v1(pnode) & DGL_NS_HEAD) 00955 pvertex = pnode; 00956 break; 00957 #ifdef DGL_V2 00958 case 2: 00959 case 3: 00960 if (DGL_NODE_STATUS_v2(pnode) & DGL_NS_HEAD) 00961 pvertex = pnode; 00962 break; 00963 #endif 00964 } 00965 if (pvertex) 00966 break; 00967 } 00968 dglNode_T_Release(&pT); 00969 } 00970 00971 if (pvertex == NULL) { 00972 pgraphInput->iErrno = DGL_ERR_UnexpectedNullPointer; 00973 goto error; 00974 } 00975 00976 for (i = 0; i < cgraphComponents && pvertex; i++) { 00977 nret = dglInitialize(&pgraphComponents[i], 00978 dglGet_Version(pgraphInput), 00979 dglGet_NodeAttrSize(pgraphInput), 00980 dglGet_EdgeAttrSize(pgraphInput), 00981 dglGet_Opaque(pgraphInput)); 00982 00983 if (nret < 0) 00984 goto error; 00985 00986 switch (pgraphInput->Version) { 00987 case 1: 00988 nret = 00989 dgl_depthfirst_spanning_V1(pgraphInput, &pgraphComponents[i], 00990 DGL_NODE_ID_v1(pvertex), pvVisited, 00991 fnClip, pvClipArg); 00992 if (nret < 0) 00993 goto error; 00994 break; 00995 #ifdef DGL_V2 00996 case 2: 00997 case 3: 00998 nret = 00999 dgl_depthfirst_spanning_V2(pgraphInput, &pgraphComponents[i], 01000 DGL_NODE_ID_v1(pvertex), pvVisited, 01001 fnClip, pvClipArg); 01002 if (nret < 0) 01003 goto error; 01004 break; 01005 #endif 01006 default: 01007 pgraphInput->iErrno = DGL_ERR_BadVersion; 01008 nret = -pgraphInput->iErrno; 01009 goto error; 01010 } 01011 01012 /* 01013 * select next unvisited vertex 01014 */ 01015 pvertex = NULL; 01016 { 01017 dglNodeTraverser_s pT; 01018 01019 dglNode_T_Initialize(&pT, pgraphInput); 01020 for (pnode = dglNode_T_First(&pT); pnode; 01021 pnode = dglNode_T_Next(&pT)) { 01022 switch (pgraphInput->Version) { 01023 case 1: 01024 if (DGL_NODE_STATUS_v1(pnode) & DGL_NS_HEAD) { 01025 findVisited.nKey = DGL_NODE_ID_v1(pnode); 01026 if (avl_find(pvVisited, &findVisited) == NULL) { 01027 pvertex = pnode; 01028 break; 01029 } 01030 } 01031 break; 01032 #ifdef DGL_V2 01033 case 2: 01034 case 3: 01035 if (DGL_NODE_STATUS_v2(pnode) & DGL_NS_HEAD) { 01036 findVisited.nKey = DGL_NODE_ID_v2(pnode); 01037 if (avl_find(pvVisited, &findVisited) == NULL) { 01038 pvertex = pnode; 01039 break; 01040 } 01041 } 01042 break; 01043 #endif 01044 } 01045 if (pvertex) 01046 break; 01047 } 01048 dglNode_T_Release(&pT); 01049 } 01050 } 01051 01052 avl_destroy(pvVisited, dglTreeNodeCancel); 01053 return i; 01054 01055 error: 01056 avl_destroy(pvVisited, dglTreeNodeCancel); 01057 return nret; 01058 } 01059 01060 int dglMinimumSpanning(dglGraph_s * pgraphInput, 01061 dglGraph_s * pgraphOutput, 01062 dglInt32_t nVertexNode, 01063 dglSpanClip_fn fnClip, void *pvClipArg) 01064 { 01065 int nRet; 01066 01067 if (dglGet_EdgeCount(pgraphInput) == 0) { /* no span */ 01068 pgraphInput->iErrno = 0; 01069 return 0; 01070 } 01071 01072 nRet = dglInitialize(pgraphOutput, 01073 dglGet_Version(pgraphInput), 01074 dglGet_NodeAttrSize(pgraphInput), 01075 dglGet_EdgeAttrSize(pgraphInput), 01076 dglGet_Opaque(pgraphInput)); 01077 01078 if (nRet < 0) 01079 return nRet; 01080 01081 switch (pgraphInput->Version) { 01082 case 1: 01083 nRet = 01084 dgl_minimum_spanning_V1(pgraphInput, pgraphOutput, nVertexNode, 01085 fnClip, pvClipArg); 01086 break; 01087 #ifdef DGL_V2 01088 case 2: 01089 case 3: 01090 nRet = 01091 dgl_minimum_spanning_V2(pgraphInput, pgraphOutput, nVertexNode, 01092 fnClip, pvClipArg); 01093 break; 01094 #endif 01095 default: 01096 pgraphInput->iErrno = DGL_ERR_BadVersion; 01097 nRet = -pgraphInput->iErrno; 01098 break; 01099 } 01100 if (nRet < 0) { 01101 dglRelease(pgraphOutput); 01102 } 01103 return nRet; 01104 } 01105 01106 void dglFreeSPReport(dglGraph_s * pgraph, dglSPReport_s * pSPReport) 01107 { 01108 int iArc; 01109 01110 if (pSPReport) { 01111 if (pSPReport->pArc) { 01112 for (iArc = 0; iArc < pSPReport->cArc; iArc++) { 01113 if (pSPReport->pArc[iArc].pnEdge) 01114 free(pSPReport->pArc[iArc].pnEdge); 01115 } 01116 free(pSPReport->pArc); 01117 } 01118 free(pSPReport); 01119 } 01120 } 01121 01122 int dglInitializeSPCache(dglGraph_s * pGraph, dglSPCache_s * pCache) 01123 { 01124 switch (pGraph->Version) { 01125 case 1: 01126 return dgl_sp_cache_initialize_V1(pGraph, pCache, 0); 01127 #ifdef DGL_V2 01128 case 2: 01129 case 3: 01130 return dgl_sp_cache_initialize_V2(pGraph, pCache, 0); 01131 #endif 01132 } 01133 pGraph->iErrno = DGL_ERR_BadVersion; 01134 return -pGraph->iErrno; 01135 } 01136 01137 void dglReleaseSPCache(dglGraph_s * pGraph, dglSPCache_s * pCache) 01138 { 01139 pGraph->iErrno = 0; 01140 switch (pGraph->Version) { 01141 case 1: 01142 dgl_sp_cache_release_V1(pGraph, pCache); 01143 break; 01144 #ifdef DGL_V2 01145 case 2: 01146 case 3: 01147 dgl_sp_cache_release_V2(pGraph, pCache); 01148 break; 01149 #endif 01150 } 01151 pGraph->iErrno = DGL_ERR_BadVersion; 01152 } 01153 01154 01155 int dglErrno(dglGraph_s * pgraph) 01156 { 01157 return pgraph->iErrno; 01158 } 01159 01160 char *dglStrerror(dglGraph_s * pgraph) 01161 { 01162 switch (pgraph->iErrno) { 01163 case DGL_ERR_BadVersion: 01164 return "Bad Version"; 01165 case DGL_ERR_BadNodeType: 01166 return "Bad Node Type"; 01167 case DGL_ERR_MemoryExhausted: 01168 return "Memory Exhausted"; 01169 case DGL_ERR_HeapError: 01170 return "Heap Error"; 01171 case DGL_ERR_UndefinedMethod: 01172 return "Undefined Method"; 01173 case DGL_ERR_Write: 01174 return "Write"; 01175 case DGL_ERR_Read: 01176 return "Read"; 01177 case DGL_ERR_NotSupported: 01178 return "Not Supported"; 01179 case DGL_ERR_UnknownByteOrder: 01180 return "Unknown Byte Order"; 01181 case DGL_ERR_NodeNotFound: 01182 return "Node Not Found"; 01183 case DGL_ERR_HeadNodeNotFound: 01184 return "Head Node Not Found"; 01185 case DGL_ERR_TailNodeNotFound: 01186 return "Tail Node Not Found"; 01187 case DGL_ERR_BadEdge: 01188 return "Bad Edge"; 01189 case DGL_ERR_BadOnFlatGraph: 01190 return "Operation Not Supported On Flat-State Graph"; 01191 case DGL_ERR_BadOnTreeGraph: 01192 return "Operation Not Supported On Tree-State Graph"; 01193 case DGL_ERR_TreeSearchError: 01194 return "Tree Search Error"; 01195 case DGL_ERR_UnexpectedNullPointer: 01196 return "Unexpected Null Pointer"; 01197 case DGL_ERR_VersionNotSupported: 01198 return "Version Not Supported"; 01199 case DGL_ERR_EdgeNotFound: 01200 return "Edge Not Found"; 01201 case DGL_ERR_NodeAlreadyExist: 01202 return "Node Already Exist"; 01203 case DGL_ERR_NodeIsAComponent: 01204 return "Node Is A Component"; 01205 case DGL_ERR_EdgeAlreadyExist: 01206 return "Edge Already Exist"; 01207 case DGL_ERR_BadArgument: 01208 return "Bad Argument"; 01209 } 01210 01211 return "unknown graph error code"; 01212 } 01213 01214 /* 01215 * dglGraph_s hiders 01216 */ 01217 int dglGet_Version(dglGraph_s * pgraph) 01218 { 01219 return pgraph->Version; 01220 } 01221 void dglSet_Version(dglGraph_s * pgraph, int nVersion) 01222 { 01223 pgraph->Version = nVersion; 01224 } 01225 01226 int dglGet_Endianess(dglGraph_s * pgraph) 01227 { 01228 return pgraph->Endian; 01229 } 01230 01231 int dglGet_NodeAttrSize(dglGraph_s * pgraph) 01232 { 01233 return pgraph->NodeAttrSize; 01234 } 01235 01236 int dglGet_EdgeAttrSize(dglGraph_s * pgraph) 01237 { 01238 return pgraph->EdgeAttrSize; 01239 } 01240 01241 int dglGet_NodeCount(dglGraph_s * pgraph) 01242 { 01243 return pgraph->cNode; 01244 } 01245 01246 int dglGet_HeadNodeCount(dglGraph_s * pgraph) 01247 { 01248 return pgraph->cHead; 01249 } 01250 01251 int dglGet_TailNodeCount(dglGraph_s * pgraph) 01252 { 01253 return pgraph->cTail; 01254 } 01255 01256 int dglGet_AloneNodeCount(dglGraph_s * pgraph) 01257 { 01258 return pgraph->cAlone; 01259 } 01260 01261 int dglGet_EdgeCount(dglGraph_s * pgraph) 01262 { 01263 return pgraph->cEdge; 01264 } 01265 01266 int dglGet_State(dglGraph_s * pgraph) 01267 { 01268 return pgraph->Flags; 01269 } 01270 01271 dglInt32_t *dglGet_Opaque(dglGraph_s * pgraph) 01272 { 01273 return pgraph->aOpaqueSet; 01274 } 01275 01276 void dglSet_Opaque(dglGraph_s * pgraph, dglInt32_t * pOpaque) 01277 { 01278 memcpy(pgraph->aOpaqueSet, pOpaque, sizeof(dglInt32_t) * 16); 01279 } 01280 01281 int dglGet_NodeSize(dglGraph_s * pgraph) 01282 { 01283 switch (pgraph->Version) { 01284 case 1: 01285 return DGL_NODE_SIZEOF_v1(pgraph->NodeAttrSize); 01286 #ifdef DGL_V2 01287 case 2: 01288 case 3: 01289 return DGL_NODE_SIZEOF_v2(pgraph->NodeAttrSize); 01290 #endif 01291 } 01292 pgraph->iErrno = DGL_ERR_BadVersion; 01293 return -pgraph->iErrno; 01294 } 01295 01296 int dglGet_EdgeSize(dglGraph_s * pgraph) 01297 { 01298 switch (pgraph->Version) { 01299 case 1: 01300 return DGL_EDGE_SIZEOF_v1(pgraph->NodeAttrSize); 01301 #ifdef DGL_V2 01302 case 2: 01303 case 3: 01304 return DGL_EDGE_SIZEOF_v2(pgraph->NodeAttrSize); 01305 #endif 01306 } 01307 pgraph->iErrno = DGL_ERR_BadVersion; 01308 return -pgraph->iErrno; 01309 } 01310 01311 dglInt64_t dglGet_Cost(dglGraph_s * pgraph) 01312 { 01313 return pgraph->nnCost; 01314 } 01315 01316 void dglSet_Cost(dglGraph_s * pgraph, dglInt64_t nnCost) 01317 { 01318 pgraph->nnCost = nnCost; 01319 } 01320 01321 dglInt32_t dglGet_Family(dglGraph_s * pgraph) 01322 { 01323 return pgraph->nFamily; 01324 } 01325 01326 void dglSet_Family(dglGraph_s * pgraph, dglInt32_t nFamily) 01327 { 01328 pgraph->nFamily = nFamily; 01329 } 01330 01331 dglInt32_t dglGet_Options(dglGraph_s * pgraph) 01332 { 01333 return pgraph->nOptions; 01334 } 01335 01336 void dglSet_Options(dglGraph_s * pgraph, dglInt32_t nOptions) 01337 { 01338 pgraph->nOptions = nOptions; 01339 } 01340 01341 dglEdgePrioritizer_s *dglGet_EdgePrioritizer(dglGraph_s * pGraph) 01342 { 01343 return &pGraph->edgePrioritizer; 01344 } 01345 01346 dglNodePrioritizer_s *dglGet_NodePrioritizer(dglGraph_s * pGraph) 01347 { 01348 return &pGraph->nodePrioritizer; 01349 } 01350 01351 01352 01353 /* 01354 * Node Traverse 01355 */ 01356 int dglNode_T_Initialize(dglNodeTraverser_s * pT, dglGraph_s * pGraph) 01357 { 01358 switch (pGraph->Version) { 01359 case 1: 01360 return dgl_node_t_initialize_V1(pGraph, pT); 01361 #ifdef DGL_V2 01362 case 2: 01363 case 3: 01364 return dgl_node_t_initialize_V2(pGraph, pT); 01365 #endif 01366 } 01367 pGraph->iErrno = DGL_ERR_BadVersion; 01368 return -pGraph->iErrno; 01369 } 01370 01371 void dglNode_T_Release(dglNodeTraverser_s * pT) 01372 { 01373 switch (pT->pGraph->Version) { 01374 case 1: 01375 dgl_node_t_release_V1(pT); 01376 return; 01377 #ifdef DGL_V2 01378 case 2: 01379 case 3: 01380 dgl_node_t_release_V2(pT); 01381 return; 01382 #endif 01383 } 01384 pT->pGraph->iErrno = DGL_ERR_BadVersion; 01385 } 01386 01387 dglInt32_t *dglNode_T_First(dglNodeTraverser_s * pT) 01388 { 01389 switch (pT->pGraph->Version) { 01390 case 1: 01391 return dgl_node_t_first_V1(pT); 01392 #ifdef DGL_V2 01393 case 2: 01394 case 3: 01395 return dgl_node_t_first_V2(pT); 01396 #endif 01397 } 01398 pT->pGraph->iErrno = DGL_ERR_BadVersion; 01399 return NULL; 01400 } 01401 01402 dglInt32_t *dglNode_T_Next(dglNodeTraverser_s * pT) 01403 { 01404 switch (pT->pGraph->Version) { 01405 case 1: 01406 return dgl_node_t_next_V1(pT); 01407 #ifdef DGL_V2 01408 case 2: 01409 case 3: 01410 return dgl_node_t_next_V2(pT); 01411 #endif 01412 } 01413 pT->pGraph->iErrno = DGL_ERR_BadVersion; 01414 return NULL; 01415 } 01416 01417 dglInt32_t *dglNode_T_Find(dglNodeTraverser_s * pT, dglInt32_t nNodeId) 01418 { 01419 switch (pT->pGraph->Version) { 01420 case 1: 01421 return dgl_node_t_find_V1(pT, nNodeId); 01422 #ifdef DGL_V2 01423 case 2: 01424 case 3: 01425 return dgl_node_t_find_V2(pT, nNodeId); 01426 #endif 01427 } 01428 pT->pGraph->iErrno = DGL_ERR_BadVersion; 01429 return NULL; 01430 } 01431 01432 /* 01433 * Edge Traverser 01434 */ 01435 int dglEdge_T_Initialize(dglEdgeTraverser_s * pT, 01436 dglGraph_s * pGraph, 01437 dglEdgePrioritizer_s * pEdgePrioritizer) 01438 { 01439 switch (pGraph->Version) { 01440 case 1: 01441 return dgl_edge_t_initialize_V1(pGraph, pT, pEdgePrioritizer); 01442 #ifdef DGL_V2 01443 case 2: 01444 case 3: 01445 return dgl_edge_t_initialize_V2(pGraph, pT, pEdgePrioritizer); 01446 #endif 01447 } 01448 pGraph->iErrno = DGL_ERR_BadVersion; 01449 return -pGraph->iErrno; 01450 } 01451 01452 void dglEdge_T_Release(dglEdgeTraverser_s * pT) 01453 { 01454 switch (pT->pGraph->Version) { 01455 case 1: 01456 dgl_edge_t_release_V1(pT); 01457 return; 01458 #ifdef DGL_V2 01459 case 2: 01460 case 3: 01461 dgl_edge_t_release_V2(pT); 01462 return; 01463 #endif 01464 } 01465 pT->pGraph->iErrno = DGL_ERR_BadVersion; 01466 } 01467 01468 dglInt32_t *dglEdge_T_First(dglEdgeTraverser_s * pT) 01469 { 01470 switch (pT->pGraph->Version) { 01471 case 1: 01472 return dgl_edge_t_first_V1(pT); 01473 #ifdef DGL_V2 01474 case 2: 01475 case 3: 01476 return dgl_edge_t_first_V2(pT); 01477 #endif 01478 } 01479 pT->pGraph->iErrno = DGL_ERR_BadVersion; 01480 return NULL; 01481 } 01482 01483 dglInt32_t *dglEdge_T_Next(dglEdgeTraverser_s * pT) 01484 { 01485 switch (pT->pGraph->Version) { 01486 case 1: 01487 return dgl_edge_t_next_V1(pT); 01488 #ifdef DGL_V2 01489 case 2: 01490 case 3: 01491 return dgl_edge_t_next_V2(pT); 01492 #endif 01493 } 01494 pT->pGraph->iErrno = DGL_ERR_BadVersion; 01495 return NULL; 01496 } 01497 01498 01499 int dglEdgeset_T_Initialize(dglEdgesetTraverser_s * pT, 01500 dglGraph_s * pGraph, dglInt32_t * pnEdgeset) 01501 { 01502 switch (pGraph->Version) { 01503 case 1: 01504 return dgl_edgeset_t_initialize_V1(pGraph, pT, pnEdgeset); 01505 #ifdef DGL_V2 01506 case 2: 01507 case 3: 01508 return dgl_edgeset_t_initialize_V2(pGraph, pT, pnEdgeset); 01509 #endif 01510 } 01511 pGraph->iErrno = DGL_ERR_BadVersion; 01512 return -pGraph->iErrno; 01513 } 01514 01515 void dglEdgeset_T_Release(dglEdgesetTraverser_s * pT) 01516 { 01517 } 01518 01519 dglInt32_t *dglEdgeset_T_First(dglEdgesetTraverser_s * pT) 01520 { 01521 switch (pT->pGraph->Version) { 01522 case 1: 01523 return dgl_edgeset_t_first_V1(pT); 01524 #ifdef DGL_V2 01525 case 2: 01526 case 3: 01527 return dgl_edgeset_t_first_V2(pT); 01528 #endif 01529 } 01530 pT->pGraph->iErrno = DGL_ERR_BadVersion; 01531 return NULL; 01532 } 01533 01534 dglInt32_t *dglEdgeset_T_Next(dglEdgesetTraverser_s * pT) 01535 { 01536 switch (pT->pGraph->Version) { 01537 case 1: 01538 return dgl_edgeset_t_next_V1(pT); 01539 #ifdef DGL_V2 01540 case 2: 01541 case 3: 01542 return dgl_edgeset_t_next_V2(pT); 01543 #endif 01544 } 01545 pT->pGraph->iErrno = DGL_ERR_BadVersion; 01546 return NULL; 01547 } 01548 01549 01550 /* 01551 * chunked I/O 01552 */ 01553 01554 #define __CIO_BEGIN 0 01555 #define __CIO_W_HEADER 1 01556 #define __CIO_W_NODEBUFFER 2 01557 #define __CIO_W_EDGEBUFFER 3 01558 #define __CIO_R_HEADER 4 01559 #define __CIO_R_NODEBUFFER 5 01560 #define __CIO_R_EDGEBUFFER 6 01561 #define __CIO_END 7 01562 01563 int dglIOContextInitialize(dglGraph_s * pG, dglIOContext_s * pIO) 01564 { 01565 pIO->pG = pG; 01566 pIO->nState = __CIO_BEGIN; 01567 pIO->cb = 0; 01568 pIO->ib = 0; 01569 pIO->pb = NULL; 01570 return 0; 01571 } 01572 01573 void dglIOContextRelease(dglIOContext_s * pIO) 01574 { 01575 } 01576 01577 int dglWriteChunk(dglIOContext_s * pIO, dglWriteChunk_fn pfn, void *pv) 01578 { 01579 unsigned char *pb; 01580 int cb; 01581 01582 switch (pIO->nState) { 01583 case __CIO_BEGIN: 01584 pIO->pb = pIO->ab; 01585 pb = pIO->pb; 01586 memcpy(pb, &pIO->pG->Version, 1); 01587 pb += 1; /* 1 */ 01588 memcpy(pb, &pIO->pG->Endian, 1); 01589 pb += 1; /* 2 */ 01590 memcpy(pb, &pIO->pG->NodeAttrSize, 4); 01591 pb += 4; /* 6 */ 01592 memcpy(pb, &pIO->pG->EdgeAttrSize, 4); 01593 pb += 4; /* 10 */ 01594 memcpy(pb, &pIO->pG->aOpaqueSet, 64); 01595 pb += 64; /* 74 */ 01596 memcpy(pb, &pIO->pG->nOptions, 4); 01597 pb += 4; /* 78 */ 01598 memcpy(pb, &pIO->pG->nFamily, 4); 01599 pb += 4; /* 82 */ 01600 memcpy(pb, &pIO->pG->nnCost, 8); 01601 pb += 8; /* 90 */ 01602 memcpy(pb, &pIO->pG->cNode, 4); 01603 pb += 4; /* 94 */ 01604 memcpy(pb, &pIO->pG->cHead, 4); 01605 pb += 4; /* 98 */ 01606 memcpy(pb, &pIO->pG->cTail, 4); 01607 pb += 4; /* 102 */ 01608 memcpy(pb, &pIO->pG->cAlone, 4); 01609 pb += 4; /* 106 */ 01610 memcpy(pb, &pIO->pG->cEdge, 4); 01611 pb += 4; /* 110 */ 01612 memcpy(pb, &pIO->pG->iNodeBuffer, 4); 01613 pb += 4; /* 114 */ 01614 memcpy(pb, &pIO->pG->iEdgeBuffer, 4); 01615 pb += 4; /* 118 */ 01616 pIO->cb = 118; 01617 cb = pfn(pIO->pG, pIO->pb, pIO->cb, pv); 01618 if (cb >= 0) { 01619 pIO->ib += cb; 01620 if ((pIO->cb - pIO->ib) == 0) { 01621 pIO->ib = 0; 01622 pIO->cb = pIO->pG->iNodeBuffer; 01623 pIO->pb = pIO->pG->pNodeBuffer; 01624 pIO->nState = __CIO_W_NODEBUFFER; 01625 } 01626 else { 01627 pIO->nState = __CIO_W_HEADER; 01628 } 01629 } 01630 return cb; 01631 case __CIO_W_HEADER: 01632 cb = pfn(pIO->pG, pIO->pb + pIO->ib, pIO->cb - pIO->ib, pv); 01633 if (cb > 0) { 01634 pIO->ib += cb; 01635 if ((pIO->cb - pIO->ib) == 0) { 01636 if (pIO->pG->iNodeBuffer > 0) { 01637 pIO->ib = 0; 01638 pIO->cb = pIO->pG->iNodeBuffer; 01639 pIO->pb = pIO->pG->pNodeBuffer; 01640 pIO->nState = __CIO_W_NODEBUFFER; 01641 } 01642 else if (pIO->pG->iEdgeBuffer > 0) { 01643 pIO->ib = 0; 01644 pIO->cb = pIO->pG->iEdgeBuffer; 01645 pIO->pb = pIO->pG->pEdgeBuffer; 01646 pIO->nState = __CIO_W_EDGEBUFFER; 01647 } 01648 else { 01649 pIO->nState = __CIO_END; 01650 } 01651 } 01652 else { 01653 pIO->nState = __CIO_W_HEADER; 01654 } 01655 } 01656 return cb; 01657 case __CIO_W_NODEBUFFER: 01658 cb = pfn(pIO->pG, pIO->pb + pIO->ib, pIO->cb - pIO->ib, pv); 01659 if (cb > 0) { 01660 pIO->ib += cb; 01661 if ((pIO->cb - pIO->ib) == 0) { 01662 if (pIO->pG->iEdgeBuffer > 0) { 01663 pIO->ib = 0; 01664 pIO->cb = pIO->pG->iEdgeBuffer; 01665 pIO->pb = pIO->pG->pEdgeBuffer; 01666 pIO->nState = __CIO_W_EDGEBUFFER; 01667 } 01668 else { 01669 pIO->nState = __CIO_END; 01670 } 01671 } 01672 } 01673 return cb; 01674 case __CIO_W_EDGEBUFFER: 01675 cb = pfn(pIO->pG, pIO->pb + pIO->ib, pIO->cb - pIO->ib, pv); 01676 if (cb > 0) { 01677 pIO->ib += cb; 01678 if ((pIO->cb - pIO->ib) == 0) { 01679 pIO->nState = __CIO_END; 01680 } 01681 } 01682 return cb; 01683 case __CIO_END: 01684 pfn(pIO->pG, NULL, 0, pv); /* notify end of graph */ 01685 return 0; 01686 } 01687 return 0; 01688 } 01689 01690 #ifndef MIN 01691 #define MIN(x,y) (((x)<(y))?x:y) 01692 #endif 01693 01694 int dglReadChunk(dglIOContext_s * pIO, dglByte_t * pbChunk, int cbChunk) 01695 { 01696 int i, c; 01697 unsigned char *pb; 01698 01699 switch (pIO->nState) { 01700 case __CIO_BEGIN: 01701 pIO->cb = 118; 01702 pIO->ib = 0; 01703 pIO->pb = pIO->ab; 01704 01705 c = MIN(cbChunk, 118); 01706 memcpy(pIO->pb, pbChunk, c); 01707 pIO->ib += c; 01708 if ((pIO->cb - pIO->ib) == 0) 01709 goto init_nodebuffer; 01710 pIO->nState = __CIO_R_HEADER; 01711 return c; 01712 01713 case __CIO_R_HEADER: 01714 c = MIN(cbChunk, pIO->cb - pIO->ib); 01715 memcpy(pIO->pb + pIO->ib, pbChunk, c); 01716 pIO->ib += c; 01717 init_nodebuffer: 01718 if ((pIO->cb - pIO->ib) == 0) { 01719 pb = pIO->pb; 01720 memcpy(&pIO->pG->Version, pb, 1); 01721 pb += 1; /* 1 */ 01722 memcpy(&pIO->pG->Endian, pb, 1); 01723 pb += 1; /* 2 */ 01724 memcpy(&pIO->pG->NodeAttrSize, pb, 4); 01725 pb += 4; /* 6 */ 01726 memcpy(&pIO->pG->EdgeAttrSize, pb, 4); 01727 pb += 4; /* 10 */ 01728 memcpy(&pIO->pG->aOpaqueSet, pb, 64); 01729 pb += 64; /* 74 */ 01730 memcpy(&pIO->pG->nOptions, pb, 4); 01731 pb += 4; /* 78 */ 01732 memcpy(&pIO->pG->nFamily, pb, 4); 01733 pb += 4; /* 82 */ 01734 memcpy(&pIO->pG->nnCost, pb, 8); 01735 pb += 8; /* 90 */ 01736 memcpy(&pIO->pG->cNode, pb, 4); 01737 pb += 4; /* 94 */ 01738 memcpy(&pIO->pG->cHead, pb, 4); 01739 pb += 4; /* 98 */ 01740 memcpy(&pIO->pG->cTail, pb, 4); 01741 pb += 4; /* 102 */ 01742 memcpy(&pIO->pG->cAlone, pb, 4); 01743 pb += 4; /* 106 */ 01744 memcpy(&pIO->pG->cEdge, pb, 4); 01745 pb += 4; /* 110 */ 01746 memcpy(&pIO->pG->iNodeBuffer, pb, 4); 01747 pb += 4; /* 114 */ 01748 memcpy(&pIO->pG->iEdgeBuffer, pb, 4); 01749 pb += 4; /* 118 */ 01750 01751 pIO->fSwap = 0; 01752 #ifdef DGL_ENDIAN_BIG 01753 if (pIO->pG->Endian == DGL_ENDIAN_LITTLE) 01754 pIO->fSwap = 1; 01755 #else 01756 if (pIO->pG->Endian == DGL_ENDIAN_BIG) 01757 pIO->fSwap = 1; 01758 #endif 01759 if (pIO->fSwap) { 01760 dgl_swapInt32Bytes(&pIO->pG->NodeAttrSize); 01761 dgl_swapInt32Bytes(&pIO->pG->EdgeAttrSize); 01762 dgl_swapInt32Bytes(&pIO->pG->nOptions); 01763 dgl_swapInt32Bytes(&pIO->pG->nFamily); 01764 dgl_swapInt64Bytes(&pIO->pG->nnCost); 01765 dgl_swapInt32Bytes(&pIO->pG->cNode); 01766 dgl_swapInt32Bytes(&pIO->pG->cHead); 01767 dgl_swapInt32Bytes(&pIO->pG->cTail); 01768 dgl_swapInt32Bytes(&pIO->pG->cAlone); 01769 dgl_swapInt32Bytes(&pIO->pG->cEdge); 01770 dgl_swapInt32Bytes(&pIO->pG->iNodeBuffer); 01771 dgl_swapInt32Bytes(&pIO->pG->iEdgeBuffer); 01772 01773 for (i = 0; i < 16; i++) { 01774 dgl_swapInt32Bytes(&pIO->pG->aOpaqueSet[i]); 01775 } 01776 01777 #ifdef DGL_ENDIAN_BIG 01778 pIO->pG->Endian = DGL_ENDIAN_BIG; 01779 #else 01780 pIO->pG->Endian = DGL_ENDIAN_LITTLE; 01781 #endif 01782 } 01783 01784 if (pIO->pG->iNodeBuffer > 0) { 01785 pIO->pG->pNodeBuffer = malloc(pIO->pG->iNodeBuffer); 01786 if (pIO->pG->pNodeBuffer == NULL) { 01787 return -1; 01788 } 01789 pIO->cb = pIO->pG->iNodeBuffer; 01790 pIO->pb = pIO->pG->pNodeBuffer; 01791 pIO->ib = 0; 01792 pIO->nState = __CIO_R_NODEBUFFER; 01793 } 01794 else { 01795 goto init_edgebuffer; 01796 } 01797 } 01798 return c; 01799 case __CIO_R_NODEBUFFER: 01800 c = MIN(cbChunk, pIO->cb - pIO->ib); 01801 memcpy(pIO->pb + pIO->ib, pbChunk, c); 01802 pIO->ib += c; 01803 init_edgebuffer: 01804 if ((pIO->cb - pIO->ib) == 0) { 01805 if (pIO->pG->iEdgeBuffer > 0) { 01806 pIO->pG->pEdgeBuffer = malloc(pIO->pG->iEdgeBuffer); 01807 if (pIO->pG->pEdgeBuffer == NULL) { 01808 return -1; 01809 } 01810 pIO->cb = pIO->pG->iEdgeBuffer; 01811 pIO->pb = pIO->pG->pEdgeBuffer; 01812 pIO->ib = 0; 01813 pIO->nState = __CIO_R_EDGEBUFFER; 01814 } 01815 else { 01816 pIO->nState = __CIO_END; 01817 } 01818 } 01819 return c; 01820 case __CIO_R_EDGEBUFFER: 01821 c = MIN(cbChunk, pIO->cb - pIO->ib); 01822 memcpy(pIO->pb + pIO->ib, pbChunk, c); 01823 pIO->ib += c; 01824 if ((pIO->cb - pIO->ib) == 0) { 01825 pIO->nState = __CIO_END; 01826 } 01827 return c; 01828 case __CIO_END: 01829 { 01830 /* switch on FLAT bit */ 01831 pIO->pG->Flags |= DGL_GS_FLAT; 01832 01833 /* nodebuffer and edgebuffer are both arrays on 32 bit integer 01834 * byte order swapping is straightforward 01835 */ 01836 if (pIO->fSwap && pIO->pG->iNodeBuffer > 0) { 01837 int in, cn; 01838 dglInt32_t *pn; 01839 01840 for (cn = pIO->pG->iNodeBuffer / sizeof(dglInt32_t), 01841 pn = (dglInt32_t *) pIO->pG->pNodeBuffer, 01842 in = 0; in < cn; in++) { 01843 dgl_swapInt32Bytes(&pn[in]); 01844 } 01845 } 01846 if (pIO->fSwap && pIO->pG->iEdgeBuffer > 0) { 01847 int in, cn; 01848 dglInt32_t *pn; 01849 01850 for (cn = pIO->pG->iEdgeBuffer / sizeof(dglInt32_t), 01851 pn = (dglInt32_t *) pIO->pG->pEdgeBuffer, 01852 in = 0; in < cn; in++) { 01853 dgl_swapInt32Bytes(&pn[in]); 01854 } 01855 } 01856 } 01857 return 0; 01858 default: 01859 return 0; 01860 } 01861 }