GRASS Programmer's Manual  6.4.2(2012)
dglib/graph.c
Go to the documentation of this file.
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 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines