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

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5