GRASS Programmer's Manual 6.4.1(2011)
graph_v2.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_v2.h"
00036 #include "helpers.h"
00037 
00038 
00039 /* Template expansion
00040  */
00041 #include "v2-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 "v2-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 "v2-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_V2(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_V2_FLAT(pgraph, ppReport, pDistance, nStart,
00077                                     nDestination, fnClip, pvClipArg, pCache);
00078     }
00079     else {
00080         return dgl_dijkstra_V2_TREE(pgraph, ppReport, pDistance, nStart,
00081                                     nDestination, fnClip, pvClipArg, pCache);
00082     }
00083 }
00084 
00085 
00086 int dgl_depthfirst_spanning_V2(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_V2_FLAT(pgraphIn, pgraphOut,
00094                                                     nVertex, pvVisited,
00095                                                     fnClip, pvClipArg);
00096     }
00097     else {
00098         return dgl_span_depthfirst_spanning_V2_TREE(pgraphIn, pgraphOut,
00099                                                     nVertex, pvVisited,
00100                                                     fnClip, pvClipArg);
00101     }
00102 }
00103 
00104 int dgl_minimum_spanning_V2(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_V2_FLAT(pgraphIn, pgraphOut, nVertex,
00111                                                  fnClip, pvClipArg);
00112     }
00113     else {
00114         return dgl_span_minimum_spanning_V2_TREE(pgraphIn, pgraphOut, nVertex,
00115                                                  fnClip, pvClipArg);
00116     }
00117 }
00118 
00119 
00120 int dgl_initialize_V2(dglGraph_s * pgraph)
00121 {
00122     if (pgraph->pNodeTree == NULL)
00123         pgraph->pNodeTree =
00124             avl_create(dglTreeNode2Compare, NULL, dglTreeGetAllocator());
00125     if (pgraph->pNodeTree == NULL) {
00126         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00127         return -pgraph->iErrno;
00128     }
00129     if (pgraph->pEdgeTree == NULL)
00130         pgraph->pEdgeTree =
00131             avl_create(dglTreeEdgeCompare, NULL, dglTreeGetAllocator());
00132     if (pgraph->pEdgeTree == NULL) {
00133         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00134         return -pgraph->iErrno;
00135     }
00136     return 0;
00137 }
00138 
00139 int dgl_release_V2(dglGraph_s * pgraph)
00140 {
00141     pgraph->iErrno = 0;
00142 
00143     if (pgraph->pNodeTree)
00144         avl_destroy(pgraph->pNodeTree, dglTreeNodeCancel);
00145     if (pgraph->pEdgeTree)
00146         avl_destroy(pgraph->pEdgeTree, dglTreeEdgeCancel);
00147     if (pgraph->pNodeBuffer)
00148         free(pgraph->pNodeBuffer);
00149     if (pgraph->pEdgeBuffer)
00150         free(pgraph->pEdgeBuffer);
00151     if (pgraph->edgePrioritizer.pvAVL)
00152         avl_destroy(pgraph->edgePrioritizer.pvAVL, dglTreeEdgePri32Cancel);
00153     if (pgraph->nodePrioritizer.pvAVL)
00154         avl_destroy(pgraph->nodePrioritizer.pvAVL, dglTreeNodePri32Cancel);
00155 
00156     return 0;
00157 }
00158 
00159 
00160 int dgl_write_V2(dglGraph_s * pgraph, int fd)
00161 {
00162     long nret, cnt, tot;
00163 
00164     pgraph->iErrno = 0;
00165 
00166     if (write(fd, &pgraph->Version, 1) != 1) {
00167         pgraph->iErrno = DGL_ERR_Write;
00168         return -pgraph->iErrno;
00169     }
00170 
00171     if (write(fd, &pgraph->Endian, 1) != 1) {
00172         pgraph->iErrno = DGL_ERR_Write;
00173         return -pgraph->iErrno;
00174     }
00175 
00176     if (write(fd, &pgraph->NodeAttrSize, sizeof(dglInt32_t)) !=
00177         sizeof(dglInt32_t)) {
00178         pgraph->iErrno = DGL_ERR_Write;
00179         return -pgraph->iErrno;
00180     }
00181 
00182     if (write(fd, &pgraph->EdgeAttrSize, sizeof(dglInt32_t)) !=
00183         sizeof(dglInt32_t)) {
00184         pgraph->iErrno = DGL_ERR_Write;
00185         return -pgraph->iErrno;
00186     }
00187 
00188     for (cnt = 0; cnt < 16; cnt++) {
00189         if (write(fd, &pgraph->aOpaqueSet[cnt], sizeof(dglInt32_t)) !=
00190             sizeof(dglInt32_t)) {
00191             pgraph->iErrno = DGL_ERR_Write;
00192             return -pgraph->iErrno;
00193         }
00194     }
00195 
00196     if (write(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
00197         pgraph->iErrno = DGL_ERR_Write;
00198         return -pgraph->iErrno;
00199     }
00200 
00201     if (write(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00202         pgraph->iErrno = DGL_ERR_Write;
00203         return -pgraph->iErrno;
00204     }
00205 
00206     if (write(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00207         pgraph->iErrno = DGL_ERR_Write;
00208         return -pgraph->iErrno;
00209     }
00210 
00211     if (write(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00212         pgraph->iErrno = DGL_ERR_Write;
00213         return -pgraph->iErrno;
00214     }
00215 
00216     if (write(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00217         pgraph->iErrno = DGL_ERR_Write;
00218         return -pgraph->iErrno;
00219     }
00220 
00221     if (write(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00222         pgraph->iErrno = DGL_ERR_Write;
00223         return -pgraph->iErrno;
00224     }
00225 
00226     if (write(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
00227         sizeof(dglInt32_t)) {
00228         pgraph->iErrno = DGL_ERR_Write;
00229         return -pgraph->iErrno;
00230     }
00231 
00232     if (write(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
00233         sizeof(dglInt32_t)) {
00234         pgraph->iErrno = DGL_ERR_Write;
00235         return -pgraph->iErrno;
00236     }
00237 
00238     for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
00239         if ((nret = write(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
00240             pgraph->iErrno = DGL_ERR_Write;
00241             return -pgraph->iErrno;
00242         }
00243     }
00244 
00245     for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
00246         if ((nret = write(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
00247             pgraph->iErrno = DGL_ERR_Write;
00248             return -pgraph->iErrno;
00249         }
00250     }
00251 
00252     return 0;
00253 }
00254 
00255 
00256 int dgl_read_V2(dglGraph_s * pgraph, int fd, int version)
00257 {
00258     long nret, cnt, tot;
00259     dglByte_t Endian;
00260     dglInt32_t NodeAttrSize, EdgeAttrSize;
00261     int i, cn, fSwap;
00262     dglInt32_t *pn;
00263 
00264     if (read(fd, &Endian, 1) != 1) {
00265         pgraph->iErrno = DGL_ERR_Read;
00266         return -pgraph->iErrno;
00267     }
00268 
00269     fSwap = 0;
00270 #ifdef DGL_ENDIAN_BIG
00271     if (Endian == DGL_ENDIAN_LITTLE)
00272         fSwap = 1;
00273 #else
00274     if (Endian == DGL_ENDIAN_BIG)
00275         fSwap = 1;
00276 #endif
00277 
00278     if (read(fd, &NodeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00279         pgraph->iErrno = DGL_ERR_Read;
00280         return -pgraph->iErrno;
00281     }
00282     if (fSwap)
00283         dgl_swapInt32Bytes(&NodeAttrSize);
00284 
00285     if (read(fd, &EdgeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00286         pgraph->iErrno = DGL_ERR_Read;
00287         return -pgraph->iErrno;
00288     }
00289     if (fSwap)
00290         dgl_swapInt32Bytes(&EdgeAttrSize);
00291 
00292     if ((nret =
00293          dglInitialize(pgraph, version, NodeAttrSize, EdgeAttrSize,
00294                        NULL)) < 0) {
00295         return nret;
00296     }
00297 
00298     for (cnt = 0; cnt < 16; cnt++) {
00299         if ((nret =
00300              read(fd, &pgraph->aOpaqueSet[cnt],
00301                   sizeof(dglInt32_t))) != sizeof(dglInt32_t)) {
00302             pgraph->iErrno = DGL_ERR_Read;
00303             return -pgraph->iErrno;
00304         }
00305         if (fSwap)
00306             dgl_swapInt32Bytes(&pgraph->aOpaqueSet[cnt]);
00307     }
00308 
00309     if (read(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
00310         pgraph->iErrno = DGL_ERR_Read;
00311         return -pgraph->iErrno;
00312     }
00313     if (fSwap)
00314         dgl_swapInt64Bytes(&pgraph->nnCost);
00315 
00316     if (read(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00317         pgraph->iErrno = DGL_ERR_Read;
00318         return -pgraph->iErrno;
00319     }
00320     if (fSwap)
00321         dgl_swapInt32Bytes(&pgraph->cNode);
00322 
00323     if (read(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00324         pgraph->iErrno = DGL_ERR_Read;
00325         return -pgraph->iErrno;
00326     }
00327     if (fSwap)
00328         dgl_swapInt32Bytes(&pgraph->cHead);
00329 
00330     if (read(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00331         pgraph->iErrno = DGL_ERR_Read;
00332         return -pgraph->iErrno;
00333     }
00334     if (fSwap)
00335         dgl_swapInt32Bytes(&pgraph->cTail);
00336 
00337     if (read(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00338         pgraph->iErrno = DGL_ERR_Read;
00339         return -pgraph->iErrno;
00340     }
00341     if (fSwap)
00342         dgl_swapInt32Bytes(&pgraph->cAlone);
00343 
00344     if (read(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
00345         pgraph->iErrno = DGL_ERR_Read;
00346         return -pgraph->iErrno;
00347     }
00348     if (fSwap)
00349         dgl_swapInt32Bytes(&pgraph->cEdge);
00350 
00351     if (read(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
00352         sizeof(dglInt32_t)) {
00353         pgraph->iErrno = DGL_ERR_Read;
00354         return -pgraph->iErrno;
00355     }
00356     if (fSwap)
00357         dgl_swapInt32Bytes(&pgraph->iNodeBuffer);
00358 
00359     if (read(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
00360         sizeof(dglInt32_t)) {
00361         pgraph->iErrno = DGL_ERR_Read;
00362         return -pgraph->iErrno;
00363     }
00364     if (fSwap)
00365         dgl_swapInt32Bytes(&pgraph->iEdgeBuffer);
00366 
00367     if ((pgraph->pNodeBuffer = malloc(pgraph->iNodeBuffer)) == NULL) {
00368         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00369         return -pgraph->iErrno;
00370     }
00371 
00372     if ((pgraph->pEdgeBuffer = malloc(pgraph->iEdgeBuffer)) == NULL) {
00373         free(pgraph->pNodeBuffer);
00374         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00375         return -pgraph->iErrno;
00376     }
00377 
00378     for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
00379         if ((nret = read(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
00380             free(pgraph->pNodeBuffer);
00381             free(pgraph->pEdgeBuffer);
00382             pgraph->iErrno = DGL_ERR_Read;
00383             return -pgraph->iErrno;
00384         }
00385     }
00386     if (fSwap) {
00387         pn = (dglInt32_t *) pgraph->pNodeBuffer;
00388         cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
00389         for (i = 0; i < cn; i++) {
00390             dgl_swapInt32Bytes(&pn[i]);
00391         }
00392     }
00393 
00394     for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
00395         if ((nret = read(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
00396             free(pgraph->pNodeBuffer);
00397             free(pgraph->pEdgeBuffer);
00398             pgraph->iErrno = DGL_ERR_Read;
00399             return -pgraph->iErrno;
00400         }
00401     }
00402     if (fSwap) {
00403         pn = (dglInt32_t *) pgraph->pEdgeBuffer;
00404         cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
00405         for (i = 0; i < cn; i++) {
00406             dgl_swapInt32Bytes(&pn[i]);
00407         }
00408     }
00409 
00410     pgraph->Flags |= 0x1;       /* flat-state */
00411     return 0;
00412 }
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines