graph_v1.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 
00032 #include "type.h"
00033 #include "tree.h"
00034 #include "graph.h"
00035 #include "graph_v1.h"
00036 #include "helpers.h"
00037 
00038 
00039 /* Template expansion
00040  */
00041 #include "v1-defs.h"
00042 #include "sp-template.c"
00043 #include "nodemgmt-template.c"
00044 #include "edgemgmt-template.c"
00045 #include "misc-template.c"
00046 
00047 
00048 /* algorithms for TREE state
00049  */
00050 #define DGL_DEFINE_TREE_PROCS 1
00051 #include "v1-defs.h"
00052 #include "sp-template.c"
00053 #include "span-template.c"
00054 #undef DGL_DEFINE_TREE_PROCS
00055 
00056 
00057 /* algorithms for FLAT state
00058  */
00059 #define DGL_DEFINE_FLAT_PROCS 1
00060 #include "v1-defs.h"
00061 #include "sp-template.c"
00062 #include "span-template.c"
00063 #undef DGL_DEFINE_FLAT_PROCS
00064 
00065 
00066 
00067 int dgl_dijkstra_V1(dglGraph_s * pgraph,
00068                     dglSPReport_s ** ppReport,
00069                     dglInt32_t * pDistance,
00070                     dglInt32_t nStart,
00071                     dglInt32_t nDestination,
00072                     dglSPClip_fn fnClip,
00073                     void *pvClipArg, dglSPCache_s * pCache)
00074 {
00075     if (pgraph->Flags & DGL_GS_FLAT) {
00076         return dgl_dijkstra_V1_FLAT(pgraph, ppReport, pDistance, nStart,
00077                                     nDestination, fnClip, pvClipArg, pCache);
00078     }
00079     else {
00080         return dgl_dijkstra_V1_TREE(pgraph, ppReport, pDistance, nStart,
00081                                     nDestination, fnClip, pvClipArg, pCache);
00082     }
00083 }
00084 
00085 
00086 int dgl_depthfirst_spanning_V1(dglGraph_s * pgraphIn,
00087                                dglGraph_s * pgraphOut,
00088                                dglInt32_t nVertex,
00089                                void *pvVisited,
00090                                dglSpanClip_fn fnClip, void *pvClipArg)
00091 {
00092     if (pgraphIn->Flags & DGL_GS_FLAT) {
00093         return dgl_span_depthfirst_spanning_V1_FLAT(pgraphIn, pgraphOut,
00094                                                     nVertex, pvVisited,
00095                                                     fnClip, pvClipArg);
00096     }
00097     else {
00098         return dgl_span_depthfirst_spanning_V1_TREE(pgraphIn, pgraphOut,
00099                                                     nVertex, pvVisited,
00100                                                     fnClip, pvClipArg);
00101     }
00102 }
00103 
00104 int dgl_minimum_spanning_V1(dglGraph_s * pgraphIn,
00105                             dglGraph_s * pgraphOut,
00106                             dglInt32_t nVertex,
00107                             dglSpanClip_fn fnClip, void *pvClipArg)
00108 {
00109     if (pgraphIn->Flags & DGL_GS_FLAT) {
00110         return dgl_span_minimum_spanning_V1_FLAT(pgraphIn, pgraphOut, nVertex,
00111                                                  fnClip, pvClipArg);
00112     }
00113     else {
00114         return dgl_span_minimum_spanning_V1_TREE(pgraphIn, pgraphOut, nVertex,
00115                                                  fnClip, pvClipArg);
00116     }
00117 }
00118 
00119 
00120 int dgl_initialize_V1(dglGraph_s * pgraph)
00121 {
00122     if (pgraph->pNodeTree == NULL)
00123         pgraph->pNodeTree =
00124             avl_create(dglTreeNodeCompare, NULL, dglTreeGetAllocator());
00125     if (pgraph->pNodeTree == NULL) {
00126         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00127         return -pgraph->iErrno;
00128     }
00129     pgraph->pEdgeTree = NULL;
00130     return 0;
00131 }
00132 
00133 int dgl_release_V1(dglGraph_s * pgraph)
00134 {
00135     pgraph->iErrno = 0;
00136 
00137     if (pgraph->pNodeTree)
00138         avl_destroy(pgraph->pNodeTree, dglTreeNodeCancel);
00139     if (pgraph->pEdgeTree)
00140         avl_destroy(pgraph->pEdgeTree, dglTreeEdgeCancel);
00141     if (pgraph->pNodeBuffer)
00142         free(pgraph->pNodeBuffer);
00143     if (pgraph->pEdgeBuffer)
00144         free(pgraph->pEdgeBuffer);
00145     if (pgraph->edgePrioritizer.pvAVL)
00146         avl_destroy(pgraph->edgePrioritizer.pvAVL, dglTreeEdgePri32Cancel);
00147     if (pgraph->nodePrioritizer.pvAVL)
00148         avl_destroy(pgraph->nodePrioritizer.pvAVL, dglTreeNodePri32Cancel);
00149 
00150     return 0;
00151 }
00152 
00153 
00154 int dgl_write_V1(dglGraph_s * pgraph, int fd)
00155 {
00156     long nret, cnt, tot;
00157 
00158     pgraph->iErrno = 0;
00159 
00160     if (write(fd, &pgraph->Version, 1) != 1) {
00161         pgraph->iErrno = DGL_ERR_Write;
00162         return -pgraph->iErrno;
00163     }
00164 
00165     if (write(fd, &pgraph->Endian, 1) != 1) {
00166         pgraph->iErrno = DGL_ERR_Write;
00167         return -pgraph->iErrno;
00168     }
00169 
00170     if (write(fd, &pgraph->NodeAttrSize, sizeof(dglInt32_t)) !=
00171         sizeof(dglInt32_t)) {
00172         pgraph->iErrno = DGL_ERR_Write;
00173         return -pgraph->iErrno;
00174     }
00175 
00176     if (write(fd, &pgraph->EdgeAttrSize, sizeof(dglInt32_t)) !=
00177         sizeof(dglInt32_t)) {
00178         pgraph->iErrno = DGL_ERR_Write;
00179         return -pgraph->iErrno;
00180     }
00181 
00182     for (cnt = 0; cnt < 16; cnt++) {
00183         if (write(fd, &pgraph->aOpaqueSet[cnt], sizeof(dglInt32_t)) !=
00184             sizeof(dglInt32_t)) {
00185             pgraph->iErrno = DGL_ERR_Write;
00186             return -pgraph->iErrno;
00187         }
00188     }
00189 
00190     if (write(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
00191         pgraph->iErrno = DGL_ERR_Write;
00192         return -pgraph->iErrno;
00193     }
00194 
00195     if (write(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00196         pgraph->iErrno = DGL_ERR_Write;
00197         return -pgraph->iErrno;
00198     }
00199 
00200     if (write(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00201         pgraph->iErrno = DGL_ERR_Write;
00202         return -pgraph->iErrno;
00203     }
00204 
00205     if (write(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00206         pgraph->iErrno = DGL_ERR_Write;
00207         return -pgraph->iErrno;
00208     }
00209 
00210     if (write(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00211         pgraph->iErrno = DGL_ERR_Write;
00212         return -pgraph->iErrno;
00213     }
00214 
00215     if (write(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00216         pgraph->iErrno = DGL_ERR_Write;
00217         return -pgraph->iErrno;
00218     }
00219 
00220     if (write(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
00221         sizeof(dglInt32_t)) {
00222         pgraph->iErrno = DGL_ERR_Write;
00223         return -pgraph->iErrno;
00224     }
00225 
00226     if (write(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
00227         sizeof(dglInt32_t)) {
00228         pgraph->iErrno = DGL_ERR_Write;
00229         return -pgraph->iErrno;
00230     }
00231 
00232     for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
00233         if ((nret = write(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
00234             pgraph->iErrno = DGL_ERR_Write;
00235             return -pgraph->iErrno;
00236         }
00237     }
00238 
00239     for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
00240         if ((nret = write(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
00241             pgraph->iErrno = DGL_ERR_Write;
00242             return -pgraph->iErrno;
00243         }
00244     }
00245 
00246     return 0;
00247 }
00248 
00249 
00250 int dgl_read_V1(dglGraph_s * pgraph, int fd)
00251 {
00252     long nret, cnt, tot;
00253     dglByte_t Endian;
00254     dglInt32_t NodeAttrSize, EdgeAttrSize;
00255     int i, cn, fSwap;
00256     dglInt32_t *pn;
00257 
00258     if (read(fd, &Endian, 1) != 1) {
00259         pgraph->iErrno = DGL_ERR_Read;
00260         return -pgraph->iErrno;
00261     }
00262 
00263     fSwap = 0;
00264 #ifdef DGL_ENDIAN_BIG
00265     if (Endian == DGL_ENDIAN_LITTLE)
00266         fSwap = 1;
00267 #else
00268     if (Endian == DGL_ENDIAN_BIG)
00269         fSwap = 1;
00270 #endif
00271 
00272     if (read(fd, &NodeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00273         pgraph->iErrno = DGL_ERR_Read;
00274         return -pgraph->iErrno;
00275     }
00276     if (fSwap)
00277         dgl_swapInt32Bytes(&NodeAttrSize);
00278 
00279     if (read(fd, &EdgeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00280         pgraph->iErrno = DGL_ERR_Read;
00281         return -pgraph->iErrno;
00282     }
00283     if (fSwap)
00284         dgl_swapInt32Bytes(&EdgeAttrSize);
00285 
00286     if ((nret =
00287          dglInitialize(pgraph, 1, NodeAttrSize, EdgeAttrSize, NULL)) < 0) {
00288         return nret;
00289     }
00290 
00291     for (cnt = 0; cnt < 16; cnt++) {
00292         if ((nret =
00293              read(fd, &pgraph->aOpaqueSet[cnt],
00294                   sizeof(dglInt32_t))) != sizeof(dglInt32_t)) {
00295             pgraph->iErrno = DGL_ERR_Read;
00296             return -pgraph->iErrno;
00297         }
00298         if (fSwap)
00299             dgl_swapInt32Bytes(&pgraph->aOpaqueSet[cnt]);
00300     }
00301 
00302     if (read(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
00303         pgraph->iErrno = DGL_ERR_Read;
00304         return -pgraph->iErrno;
00305     }
00306     if (fSwap)
00307         dgl_swapInt64Bytes(&pgraph->nnCost);
00308 
00309     if (read(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00310         pgraph->iErrno = DGL_ERR_Read;
00311         return -pgraph->iErrno;
00312     }
00313     if (fSwap)
00314         dgl_swapInt32Bytes(&pgraph->cNode);
00315 
00316     if (read(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00317         pgraph->iErrno = DGL_ERR_Read;
00318         return -pgraph->iErrno;
00319     }
00320     if (fSwap)
00321         dgl_swapInt32Bytes(&pgraph->cHead);
00322 
00323     if (read(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00324         pgraph->iErrno = DGL_ERR_Read;
00325         return -pgraph->iErrno;
00326     }
00327     if (fSwap)
00328         dgl_swapInt32Bytes(&pgraph->cTail);
00329 
00330     if (read(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00331         pgraph->iErrno = DGL_ERR_Read;
00332         return -pgraph->iErrno;
00333     }
00334     if (fSwap)
00335         dgl_swapInt32Bytes(&pgraph->cAlone);
00336 
00337     if (read(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00338         pgraph->iErrno = DGL_ERR_Read;
00339         return -pgraph->iErrno;
00340     }
00341     if (fSwap)
00342         dgl_swapInt32Bytes(&pgraph->cEdge);
00343 
00344     if (read(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
00345         sizeof(dglInt32_t)) {
00346         pgraph->iErrno = DGL_ERR_Read;
00347         return -pgraph->iErrno;
00348     }
00349     if (fSwap)
00350         dgl_swapInt32Bytes(&pgraph->iNodeBuffer);
00351 
00352     if (read(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
00353         sizeof(dglInt32_t)) {
00354         pgraph->iErrno = DGL_ERR_Read;
00355         return -pgraph->iErrno;
00356     }
00357     if (fSwap)
00358         dgl_swapInt32Bytes(&pgraph->iEdgeBuffer);
00359 
00360     if ((pgraph->pNodeBuffer = malloc(pgraph->iNodeBuffer)) == NULL) {
00361         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00362         return -pgraph->iErrno;
00363     }
00364 
00365     if ((pgraph->pEdgeBuffer = malloc(pgraph->iEdgeBuffer)) == NULL) {
00366         free(pgraph->pNodeBuffer);
00367         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00368         return -pgraph->iErrno;
00369     }
00370 
00371     for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
00372         if ((nret = read(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
00373             free(pgraph->pNodeBuffer);
00374             free(pgraph->pEdgeBuffer);
00375             pgraph->iErrno = DGL_ERR_Read;
00376             return -pgraph->iErrno;
00377         }
00378     }
00379     if (fSwap) {
00380         pn = (dglInt32_t *) pgraph->pNodeBuffer;
00381         cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
00382         for (i = 0; i < cn; i++) {
00383             dgl_swapInt32Bytes(&pn[i]);
00384         }
00385     }
00386 
00387     for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
00388         if ((nret = read(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
00389             free(pgraph->pNodeBuffer);
00390             free(pgraph->pEdgeBuffer);
00391             pgraph->iErrno = DGL_ERR_Read;
00392             return -pgraph->iErrno;
00393         }
00394     }
00395     if (fSwap) {
00396         pn = (dglInt32_t *) pgraph->pEdgeBuffer;
00397         cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
00398         for (i = 0; i < cn; i++) {
00399             dgl_swapInt32Bytes(&pn[i]);
00400         }
00401     }
00402 
00403     pgraph->Flags |= 0x1;       /* flat-state */
00404     return 0;
00405 }