GRASS Programmer's Manual
6.4.2(2012)
|
00001 /* LIBDGL -- a Directed Graph Library implementation 00002 * Copyright (C) 2002 Roberto Micarelli 00003 * 00004 * This program is free software; you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation; either version 2 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program; if not, write to the Free Software 00016 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00017 */ 00018 00019 /* 00020 * best view with tabstop=4 00021 */ 00022 00023 #include <stdio.h> 00024 #include <string.h> 00025 #include <sys/types.h> 00026 #include <sys/stat.h> 00027 #include <unistd.h> 00028 #include <stdlib.h> 00029 #include <errno.h> 00030 00031 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 }