GRASS Programmer's Manual
6.4.1(2011)
|
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 }