Geografic-Information-System/lib/vector/dglib/graph_v2.c

/* LIBDGL -- a Directed Graph Library implementation
 * Copyright (C) 2002 Roberto Micarelli
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

/*
 * best view with tabstop=4
 */

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <stdlib.h>
#include <errno.h>


#include "type.h"
#include "tree.h"
#include "graph.h"
#include "graph_v2.h"
#include "helpers.h"


/* Template expansion
 */
#include "v2-defs.h"
#include "sp-template.c"
#include "nodemgmt-template.c"
#include "edgemgmt-template.c"
#include "misc-template.c"


/* algorithms for TREE state
 */
#define DGL_DEFINE_TREE_PROCS 1
#include "v2-defs.h"
#include "sp-template.c"
#include "span-template.c"
#undef DGL_DEFINE_TREE_PROCS


/* algorithms for FLAT state
 */
#define DGL_DEFINE_FLAT_PROCS 1
#include "v2-defs.h"
#include "sp-template.c"
#include "span-template.c"
#undef DGL_DEFINE_FLAT_PROCS



int dgl_dijkstra_V2(dglGraph_s * pgraph,
		    dglSPReport_s ** ppReport,
		    dglInt32_t * pDistance,
		    dglInt32_t nStart,
		    dglInt32_t nDestination,
		    dglSPClip_fn fnClip,
		    void *pvClipArg, dglSPCache_s * pCache)
{
    if (pgraph->Flags & DGL_GS_FLAT) {
	return dgl_dijkstra_V2_FLAT(pgraph, ppReport, pDistance, nStart,
				    nDestination, fnClip, pvClipArg, pCache);
    }
    else {
	return dgl_dijkstra_V2_TREE(pgraph, ppReport, pDistance, nStart,
				    nDestination, fnClip, pvClipArg, pCache);
    }
}


int dgl_depthfirst_spanning_V2(dglGraph_s * pgraphIn,
			       dglGraph_s * pgraphOut,
			       dglInt32_t nVertex,
			       void *pvVisited,
			       dglSpanClip_fn fnClip, void *pvClipArg)
{
    if (pgraphIn->Flags & DGL_GS_FLAT) {
	return dgl_span_depthfirst_spanning_V2_FLAT(pgraphIn, pgraphOut,
						    nVertex, pvVisited,
						    fnClip, pvClipArg);
    }
    else {
	return dgl_span_depthfirst_spanning_V2_TREE(pgraphIn, pgraphOut,
						    nVertex, pvVisited,
						    fnClip, pvClipArg);
    }
}

int dgl_minimum_spanning_V2(dglGraph_s * pgraphIn,
			    dglGraph_s * pgraphOut,
			    dglInt32_t nVertex,
			    dglSpanClip_fn fnClip, void *pvClipArg)
{
    if (pgraphIn->Flags & DGL_GS_FLAT) {
	return dgl_span_minimum_spanning_V2_FLAT(pgraphIn, pgraphOut, nVertex,
						 fnClip, pvClipArg);
    }
    else {
	return dgl_span_minimum_spanning_V2_TREE(pgraphIn, pgraphOut, nVertex,
						 fnClip, pvClipArg);
    }
}


int dgl_initialize_V2(dglGraph_s * pgraph)
{
    if (pgraph->pNodeTree == NULL)
	pgraph->pNodeTree =
	    avl_create(dglTreeNode2Compare, NULL, dglTreeGetAllocator());
    if (pgraph->pNodeTree == NULL) {
	pgraph->iErrno = DGL_ERR_MemoryExhausted;
	return -pgraph->iErrno;
    }
    if (pgraph->pEdgeTree == NULL)
	pgraph->pEdgeTree =
	    avl_create(dglTreeEdgeCompare, NULL, dglTreeGetAllocator());
    if (pgraph->pEdgeTree == NULL) {
	pgraph->iErrno = DGL_ERR_MemoryExhausted;
	return -pgraph->iErrno;
    }
    return 0;
}

int dgl_release_V2(dglGraph_s * pgraph)
{
    pgraph->iErrno = 0;

    if (pgraph->pNodeTree)
	avl_destroy(pgraph->pNodeTree, dglTreeNodeCancel);
    if (pgraph->pEdgeTree)
	avl_destroy(pgraph->pEdgeTree, dglTreeEdgeCancel);
    if (pgraph->pNodeBuffer)
	free(pgraph->pNodeBuffer);
    if (pgraph->pEdgeBuffer)
	free(pgraph->pEdgeBuffer);
    if (pgraph->edgePrioritizer.pvAVL)
	avl_destroy(pgraph->edgePrioritizer.pvAVL, dglTreeEdgePri32Cancel);
    if (pgraph->nodePrioritizer.pvAVL)
	avl_destroy(pgraph->nodePrioritizer.pvAVL, dglTreeNodePri32Cancel);

    return 0;
}


int dgl_write_V2(dglGraph_s * pgraph, int fd)
{
    long nret, cnt, tot;

    pgraph->iErrno = 0;

    if (write(fd, &pgraph->Version, 1) != 1) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->Endian, 1) != 1) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->NodeAttrSize, sizeof(dglInt32_t)) !=
	sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->EdgeAttrSize, sizeof(dglInt32_t)) !=
	sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    for (cnt = 0; cnt < 16; cnt++) {
	if (write(fd, &pgraph->aOpaqueSet[cnt], sizeof(dglInt32_t)) !=
	    sizeof(dglInt32_t)) {
	    pgraph->iErrno = DGL_ERR_Write;
	    return -pgraph->iErrno;
	}
    }

    if (write(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
	sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    if (write(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
	sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Write;
	return -pgraph->iErrno;
    }

    for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
	if ((nret = write(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
	    pgraph->iErrno = DGL_ERR_Write;
	    return -pgraph->iErrno;
	}
    }

    for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
	if ((nret = write(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
	    pgraph->iErrno = DGL_ERR_Write;
	    return -pgraph->iErrno;
	}
    }

    return 0;
}


int dgl_read_V2(dglGraph_s * pgraph, int fd, int version)
{
    long nret, cnt, tot;
    dglByte_t Endian;
    dglInt32_t NodeAttrSize, EdgeAttrSize;
    int i, cn, fSwap;
    dglInt32_t *pn;

    if (read(fd, &Endian, 1) != 1) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }

    fSwap = 0;
#ifdef DGL_ENDIAN_BIG
    if (Endian == DGL_ENDIAN_LITTLE)
	fSwap = 1;
#else
    if (Endian == DGL_ENDIAN_BIG)
	fSwap = 1;
#endif

    if (read(fd, &NodeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt32Bytes(&NodeAttrSize);

    if (read(fd, &EdgeAttrSize, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt32Bytes(&EdgeAttrSize);

    if ((nret =
	 dglInitialize(pgraph, version, NodeAttrSize, EdgeAttrSize,
		       NULL)) < 0) {
	return nret;
    }

    for (cnt = 0; cnt < 16; cnt++) {
	if ((nret =
	     read(fd, &pgraph->aOpaqueSet[cnt],
		  sizeof(dglInt32_t))) != sizeof(dglInt32_t)) {
	    pgraph->iErrno = DGL_ERR_Read;
	    return -pgraph->iErrno;
	}
	if (fSwap)
	    dgl_swapInt32Bytes(&pgraph->aOpaqueSet[cnt]);
    }

    if (read(fd, &pgraph->nnCost, sizeof(dglInt64_t)) != sizeof(dglInt64_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt64Bytes(&pgraph->nnCost);

    if (read(fd, &pgraph->cNode, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt32Bytes(&pgraph->cNode);

    if (read(fd, &pgraph->cHead, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt32Bytes(&pgraph->cHead);

    if (read(fd, &pgraph->cTail, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt32Bytes(&pgraph->cTail);

    if (read(fd, &pgraph->cAlone, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt32Bytes(&pgraph->cAlone);

    if (read(fd, &pgraph->cEdge, sizeof(dglInt32_t)) != sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt32Bytes(&pgraph->cEdge);

    if (read(fd, &pgraph->iNodeBuffer, sizeof(dglInt32_t)) !=
	sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt32Bytes(&pgraph->iNodeBuffer);

    if (read(fd, &pgraph->iEdgeBuffer, sizeof(dglInt32_t)) !=
	sizeof(dglInt32_t)) {
	pgraph->iErrno = DGL_ERR_Read;
	return -pgraph->iErrno;
    }
    if (fSwap)
	dgl_swapInt32Bytes(&pgraph->iEdgeBuffer);

    if ((pgraph->pNodeBuffer = malloc(pgraph->iNodeBuffer)) == NULL) {
	pgraph->iErrno = DGL_ERR_MemoryExhausted;
	return -pgraph->iErrno;
    }

    if ((pgraph->pEdgeBuffer = malloc(pgraph->iEdgeBuffer)) == NULL) {
	free(pgraph->pNodeBuffer);
	pgraph->iErrno = DGL_ERR_MemoryExhausted;
	return -pgraph->iErrno;
    }

    for (tot = 0, cnt = pgraph->iNodeBuffer; tot < cnt; tot += nret) {
	if ((nret = read(fd, &pgraph->pNodeBuffer[tot], cnt - tot)) <= 0) {
	    free(pgraph->pNodeBuffer);
	    free(pgraph->pEdgeBuffer);
	    pgraph->iErrno = DGL_ERR_Read;
	    return -pgraph->iErrno;
	}
    }
    if (fSwap) {
	pn = (dglInt32_t *) pgraph->pNodeBuffer;
	cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
	for (i = 0; i < cn; i++) {
	    dgl_swapInt32Bytes(&pn[i]);
	}
    }

    for (tot = 0, cnt = pgraph->iEdgeBuffer; tot < cnt; tot += nret) {
	if ((nret = read(fd, &pgraph->pEdgeBuffer[tot], cnt - tot)) <= 0) {
	    free(pgraph->pNodeBuffer);
	    free(pgraph->pEdgeBuffer);
	    pgraph->iErrno = DGL_ERR_Read;
	    return -pgraph->iErrno;
	}
    }
    if (fSwap) {
	pn = (dglInt32_t *) pgraph->pEdgeBuffer;
	cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
	for (i = 0; i < cn; i++) {
	    dgl_swapInt32Bytes(&pn[i]);
	}
    }

    pgraph->Flags |= 0x1;	/* flat-state */
    return 0;
}