Geografic-Information-System/lib/vector/dglib/edgemgmt-template.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
 */


/*
 * Add edge can be performed on TREE state graph. If the state is FLAT
 * return BadOnFlatGraph error.
 */
int DGL_ADD_EDGE_FUNC(dglGraph_s * pgraph,
		      dglInt32_t nHead,
		      dglInt32_t nTail,
		      dglInt32_t nCost,
		      dglInt32_t nEdge,
		      void *pvHeadAttr,
		      void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
{
    dglInt32_t *pHead;
    dglInt32_t *pTail;
    dglInt32_t *pEdgeset;
    dglInt32_t *pEdge;
    DGL_T_NODEITEM_TYPE *pHeadNodeItem;
    DGL_T_NODEITEM_TYPE *pTailNodeItem;

#if defined(_DGL_V2)
    dglInt32_t *pinEdgeset;
    dglTreeEdge_s *pEdgeItem;
    dglTreeEdge_s findEdge;
#endif

    if (pgraph->Flags & DGL_GS_FLAT) {
	pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
	return -pgraph->iErrno;
    }

#ifdef DGL_STATS
    {
	clock_t clk = clock();
#endif

	if ((pHeadNodeItem =
	     DGL_T_NODEITEM_Add(pgraph->pNodeTree, nHead)) == NULL ||
	    (pTailNodeItem =
	     DGL_T_NODEITEM_Add(pgraph->pNodeTree, nTail)) == NULL) {
	    pgraph->iErrno = DGL_ERR_MemoryExhausted;
	    return -pgraph->iErrno;
	}

#ifdef DGL_STATS
	pgraph->clkNodeTree += clock() - clk;
	pgraph->cNodeTree++;
	pgraph->cNodeTree++;
    }
#endif

    if (DGL_T_NODEITEM_NodePTR(pHeadNodeItem) == NULL) {
	if ((pHead = DGL_NODE_ALLOC(pgraph->NodeAttrSize)) == NULL) {
	    pgraph->iErrno = DGL_ERR_MemoryExhausted;
	    return -1;
	}
	DGL_NODE_STATUS(pHead) = 0;
	DGL_T_NODEITEM_Set_NodePTR(pHeadNodeItem, pHead);
	pgraph->cNode++;
	pgraph->cHead++;
    }
    else {
	pHead = DGL_T_NODEITEM_NodePTR(pHeadNodeItem);
	if (!(DGL_NODE_STATUS(pHead) & DGL_NS_HEAD))
	    pgraph->cHead++;
    }

    if (DGL_T_NODEITEM_NodePTR(pTailNodeItem) == NULL) {
	if ((pTail = DGL_NODE_ALLOC(pgraph->NodeAttrSize)) == NULL) {
	    pgraph->iErrno = DGL_ERR_MemoryExhausted;
	    return -pgraph->iErrno;
	}
	DGL_NODE_STATUS(pTail) = 0;
	DGL_T_NODEITEM_Set_NodePTR(pTailNodeItem, pTail);
	pgraph->cNode++;
	pgraph->cTail++;
    }
    else {
	pTail = DGL_T_NODEITEM_NodePTR(pTailNodeItem);
	if (!(DGL_NODE_STATUS(pTail) & DGL_NS_TAIL))
	    pgraph->cTail++;
    }


    DGL_NODE_STATUS(pHead) |= DGL_NS_HEAD;
    DGL_NODE_STATUS(pTail) |= DGL_NS_TAIL;

    if (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) {
	DGL_NODE_STATUS(pHead) &= ~DGL_NS_ALONE;
	pgraph->cAlone--;
    }

    if (DGL_NODE_STATUS(pTail) & DGL_NS_ALONE) {
	DGL_NODE_STATUS(pTail) &= ~DGL_NS_ALONE;
	pgraph->cAlone--;
    }

    DGL_NODE_ID(pHead) = nHead;
    DGL_NODE_ID(pTail) = nTail;

    DGL_NODE_EDGESET_OFFSET(pHead) = -1;
    DGL_NODE_EDGESET_OFFSET(pTail) = -1;

    if (pvHeadAttr && pgraph->NodeAttrSize) {
	memcpy(DGL_NODE_ATTR_PTR(pHead), pvHeadAttr, pgraph->NodeAttrSize);
    }

    if (pvTailAttr && pgraph->NodeAttrSize) {
	memcpy(DGL_NODE_ATTR_PTR(pTail), pvTailAttr, pgraph->NodeAttrSize);
    }


    /*
       if ( DGL_T_NODEITEM_OutEdgesetPTR(pTailNodeItem) == NULL )
       {
       pEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize );
       if ( pEdgeset == NULL ) {
       pgraph->iErrno = DGL_ERR_MemoryExhausted;
       return -pgraph->iErrno;
       }
       DGL_EDGESET_EDGECOUNT(pEdgeset) = 0;
       DGL_T_NODEITEM_Set_OutEdgesetPTR(pTailNodeItem,pEdgeset);
       }
     */

    if ((pEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pHeadNodeItem)) == NULL) {
	pEdgeset = DGL_EDGESET_ALLOC(1, pgraph->EdgeAttrSize);
	if (pEdgeset == NULL) {
	    pgraph->iErrno = DGL_ERR_MemoryExhausted;
	    return -pgraph->iErrno;
	}
	DGL_EDGESET_EDGECOUNT(pEdgeset) = 0;
	DGL_T_NODEITEM_Set_OutEdgesetPTR(pHeadNodeItem, pEdgeset);
    }
    else {
	pEdgeset = DGL_EDGESET_REALLOC(pEdgeset,
				       DGL_EDGESET_EDGECOUNT(pEdgeset) + 1,
				       pgraph->EdgeAttrSize);

	if (pEdgeset == NULL) {
	    pgraph->iErrno = DGL_ERR_MemoryExhausted;
	    return -pgraph->iErrno;
	}
	DGL_T_NODEITEM_Set_OutEdgesetPTR(pHeadNodeItem, pEdgeset);
    }

#if defined(_DGL_V2)
    /*
       if ( DGL_T_NODEITEM_InEdgesetPTR(pHeadNodeItem) == NULL )
       {
       pinEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize );
       if ( pinEdgeset == NULL ) {
       pgraph->iErrno = DGL_ERR_MemoryExhausted;
       return -pgraph->iErrno;
       }
       DGL_EDGESET_EDGECOUNT(pinEdgeset) = 0;
       DGL_T_NODEITEM_Set_InEdgesetPTR(pHeadNodeItem,pinEdgeset);
       }
     */

    if ((pinEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pTailNodeItem)) == NULL) {
	pinEdgeset = DGL_EDGESET_ALLOC(1, pgraph->EdgeAttrSize);
	if (pinEdgeset == NULL) {
	    pgraph->iErrno = DGL_ERR_MemoryExhausted;
	    return -pgraph->iErrno;
	}
	DGL_EDGESET_EDGECOUNT(pinEdgeset) = 0;
	DGL_T_NODEITEM_Set_InEdgesetPTR(pTailNodeItem, pinEdgeset);
    }
    else {
	pinEdgeset = DGL_EDGESET_REALLOC(pinEdgeset,
					 DGL_EDGESET_EDGECOUNT(pinEdgeset) +
					 1, pgraph->EdgeAttrSize);

	if (pinEdgeset == NULL) {
	    pgraph->iErrno = DGL_ERR_MemoryExhausted;
	    return -pgraph->iErrno;
	}
	DGL_T_NODEITEM_Set_InEdgesetPTR(pTailNodeItem, pinEdgeset);
    }

    /*
     * Set the edge-tree
     */
    findEdge.nKey = nEdge;

    if ((pEdgeItem = dglTreeEdgeAdd(pgraph->pEdgeTree, nEdge)) == NULL) {
	pgraph->iErrno = DGL_ERR_MemoryExhausted;
	return -pgraph->iErrno;
    }
    if (pEdgeItem->pv) {
	pgraph->iErrno = DGL_ERR_EdgeAlreadyExist;
	return -pgraph->iErrno;
    }
    if ((pEdgeItem->pv = DGL_EDGE_ALLOC(pgraph->EdgeAttrSize)) == NULL) {
	pgraph->iErrno = DGL_ERR_MemoryExhausted;
	return -pgraph->iErrno;
    }

    /*
     * assign edge id
     */
    pEdgeset[DGL_EDGESET_EDGECOUNT(pEdgeset) + 1] = nEdge;
    pinEdgeset[DGL_EDGESET_EDGECOUNT(pinEdgeset) + 1] = nEdge;
    ++DGL_EDGESET_EDGECOUNT(pEdgeset);
    ++DGL_EDGESET_EDGECOUNT(pinEdgeset);

    /*
       printf( "add edge: node %ld(%ld,%ld) -> %ld(%ld,%ld)\n",
       DGL_NODE_ID(pHead), DGL_EDGESET_EDGECOUNT(pEdgeset),0,
       DGL_NODE_ID(pTail), 0,DGL_EDGESET_EDGECOUNT(pinEdgeset));
     */


    pEdge = pEdgeItem->pv;
#endif

#if defined(_DGL_V1)
    pEdge =
	DGL_EDGESET_EDGE_PTR(pEdgeset, DGL_EDGESET_EDGECOUNT(pEdgeset),
			     pgraph->EdgeAttrSize);
    DGL_EDGESET_EDGECOUNT(pEdgeset)++;
#endif

    DGL_EDGE_HEADNODE_OFFSET(pEdge) = nHead;	/* will be an offset after flattening */
    DGL_EDGE_TAILNODE_OFFSET(pEdge) = nTail;	/* will be an offset after flattening */
    DGL_EDGE_COST(pEdge) = nCost;
    DGL_EDGE_ID(pEdge) = nEdge;

#if !defined(_DGL_V1)
    if (nFlags & DGL_ES_DIRECTED)
	DGL_EDGE_STATUS(pEdge) = DGL_ES_DIRECTED;
    else
	DGL_EDGE_STATUS(pEdge) = 0;
#endif

    pgraph->cEdge++;
    pgraph->nnCost += (dglInt64_t) nCost;

    if (pvEdgeAttr && pgraph->EdgeAttrSize) {
	memcpy(DGL_EDGE_ATTR_PTR(pEdge), pvEdgeAttr, pgraph->EdgeAttrSize);
    }

    /*
     * If requested add a cost-weighted entry into the edge prioritizer
     */
#if !defined(_DGL_V1)
    if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
	if (dgl_edge_prioritizer_add
	    (pgraph, DGL_EDGE_ID(pEdge), DGL_EDGE_COST(pEdge)) < 0) {
	    return -pgraph->iErrno;
	}
    }
#endif

    if (nFlags & DGL_STRONGCONNECT) {
	return DGL_ADD_EDGE_FUNC(pgraph, nTail, nHead, nCost, nEdge,
				 pvHeadAttr, pvTailAttr, pvEdgeAttr,
				 nFlags & ~DGL_STRONGCONNECT);
    }

    return 0;
}

int DGL_DEL_EDGE_FUNC(dglGraph_s * pgraph, dglInt32_t nEdge)
{
#if defined(_DGL_V1)
    pgraph->iErrno = DGL_ERR_NotSupported;
    return -pgraph->iErrno;
#else
    dglTreeEdge_s *pEdgeItem, findEdgeItem;
    dglInt32_t *pEdge;

    if (pgraph->Flags & DGL_GS_FLAT) {
	pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
	return -pgraph->iErrno;
    }

    if (pgraph->pEdgeTree == NULL) {
	pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
	return -pgraph->iErrno;
    }

    findEdgeItem.nKey = nEdge;
    if ((pEdgeItem = avl_find(pgraph->pEdgeTree, &findEdgeItem)) == NULL) {
	pgraph->iErrno = DGL_ERR_EdgeNotFound;
	return -pgraph->iErrno;
    }

    pEdge = pEdgeItem->pv;

    if (DGL_DEL_NODE_INEDGE_FUNC
	(pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0) {
	return -pgraph->iErrno;
    }

    if (DGL_DEL_NODE_OUTEDGE_FUNC
	(pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0) {
	return -pgraph->iErrno;
    }


    /* prioritizer sync
     */
    if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
	if (dgl_edge_prioritizer_del
	    (pgraph, DGL_EDGE_ID(pEdge), DGL_EDGE_COST(pEdge)) < 0) {
	    return -pgraph->iErrno;
	}
    }
    /*
     */
    pgraph->cEdge--;
    pgraph->nnCost -= (dglInt64_t) DGL_EDGE_COST(pEdge);

    avl_delete(pgraph->pEdgeTree, pEdgeItem);
    dglTreeEdgeCancel(pEdgeItem, NULL);
    return 0;
#endif
}

dglInt32_t *DGL_GET_EDGE_FUNC(dglGraph_s * pgraph, dglInt32_t nEdge)
{
#if defined(_DGL_V1)
    pgraph->iErrno = DGL_ERR_NotSupported;
    return NULL;
#else
    register dglInt32_t top;	/* top of table */
    register dglInt32_t pos;	/* current position to compare */
    register dglInt32_t bot;	/* bottom of table */
    register dglInt32_t *pref;
    register int cwords;	/* size of a edge in words of 32 bit */
    register dglTreeEdge_s *ptreeEdge;
    dglTreeEdge_s findEdge;
    dglInt32_t id;

    pgraph->iErrno = 0;
    if (pgraph->Flags & DGL_GS_FLAT) {
	cwords = DGL_EDGE_WSIZE(pgraph->EdgeAttrSize);
	/*bot    = pgraph->iEdgeBuffer / DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize); */
	bot = pgraph->cEdge;
	top = 0;
	pos = 0;
	pref = (dglInt32_t *) pgraph->pEdgeBuffer;

	/* perform a binary search
	 */
	while (top != bot) {
	    pos = top + (bot - top) / 2;
	    id = DGL_EDGE_ID(&pref[pos * cwords]);
	    if (id == nEdge) {
		break;
	    }
	    else if (nEdge < id) {
		bot = pos;
	    }
	    else if (nEdge > id) {
		top = pos + 1;
	    }
	}
	if (top == bot) {
	    return NULL;
	}
	return &pref[pos * cwords];
    }
    else {
	findEdge.nKey = nEdge;
	ptreeEdge = avl_find(pgraph->pEdgeTree, &findEdge);
	if (ptreeEdge && ptreeEdge->pv) {
	    return ptreeEdge->pv;
	}
	return NULL;
    }
#endif
}