span-template.c

Go to the documentation of this file.

/* 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 <grass/gis.h>
 
/*
 * Build the depth-first spanning tree of 'pgraphIn' into 'pgraphOut'
 * - pgraphOut must have been previously initialized by the caller and is
 * returned in TREE state
 * - I prefer using a iterative approach with a stack for 'waiting edges'
 * instead of recursion: it's cheaper to stack 8 bytes for each edge than the
 * whole function stack
 * - The visited network is passed by the caller because this function can be
 * used for two purposes:
 *   1. generate a single spanning tree (dglDepthSpanning)
 *   2. part of a loop for generating connected-components of the graph
 * (dglDepthComponents)
 */
int DGL_SPAN_DEPTHFIRST_SPANNING_FUNC(dglGraph_s *pgraphIn,
                                      dglGraph_s *pgraphOut, dglInt32_t nVertex,
                                      void *pvVisited, dglSpanClip_fn fnClip,
                                      void *pvClipArg)
{
    struct _stackItem {
        dglInt32_t *pnHead;
        dglInt32_t *pnEdge;
        int iWay;
    };
 
    struct _stackItem stackItem;
    struct _stackItem *pStackItem;
 
    dglInt32_t *pHead;
    dglInt32_t *pTail;
    dglInt32_t *pEdgeset;
    dglInt32_t *pEdge;
    long istack = 0;
    unsigned char *pstack = NULL;
    int nret;
    dglSpanClipInput_s clipInput;
    dglTreeNode_s findVisited;
    dglEdgesetTraverser_s laT;
 
    if ((pHead = dglGetNode(pgraphIn, nVertex)) == NULL) {
        pgraphIn->iErrno = DGL_ERR_HeadNodeNotFound;
        goto dfs_error;
    }
 
    /*
     * the simplest case is when vertex node is alone or has no outgoing edges,
     * the result of the spanning is a graph having only one node
     */
    if (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE ||
        (!(DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) &&
         DGL_NODE_STATUS(pHead) & DGL_NS_TAIL)) {
        nret = DGL_ADD_NODE_FUNC(pgraphOut, DGL_NODE_ID(pHead),
                                 DGL_NODE_ATTR_PTR(pHead), 0);
        if (nret < 0) {
            goto dfs_error;
        }
        return 0;
    }
 
    if ((DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) || pgraphIn->Version == 3) {
 
        pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
 
        if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
            goto dfs_error;
        }
        for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
             pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
            stackItem.pnHead = pHead;
            stackItem.pnEdge = pEdge;
            stackItem.iWay = 0;
            if ((pstack = dgl_mempush(pstack, &istack, sizeof(stackItem),
                                      &stackItem)) == NULL) {
                pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
                goto dfs_error;
            }
        }
        DGL_EDGESET_T_RELEASE_FUNC(&laT);
 
        if (pgraphIn->Version == 3) {
            pEdgeset = _DGL_INEDGESET(pgraphIn, pHead);
 
            if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
                goto dfs_error;
            }
            for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
                 pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
                if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
                    continue;
                stackItem.pnHead = pHead;
                stackItem.pnEdge = pEdge;
                stackItem.iWay = 1;
                if ((pstack = dgl_mempush(pstack, &istack, sizeof(stackItem),
                                          &stackItem)) == NULL) {
                    pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
                    goto dfs_error;
                }
            }
            DGL_EDGESET_T_RELEASE_FUNC(&laT);
        }
 
        if (dglTreeNodeAdd(pvVisited, DGL_NODE_ID(pHead)) == NULL) {
            pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
            goto dfs_error;
        }
    }
 
    while ((pStackItem = (struct _stackItem *)dgl_mempop(
                pstack, &istack, sizeof(stackItem))) != NULL) {
        pHead = pStackItem->pnHead;
        pEdge = pStackItem->pnEdge;
 
        if (pStackItem->iWay == 0)
            pTail = _DGL_EDGE_TAILNODE(pgraphIn, pEdge);
        else
            pTail = _DGL_EDGE_HEADNODE(pgraphIn, pEdge);
 
        findVisited.nKey = DGL_NODE_ID(pTail);
        if (avl_find(pvVisited, &findVisited)) { /* already visited */
            continue;
        }
 
        if (fnClip) {
            clipInput.pnNodeFrom = pHead;
            clipInput.pnEdge = pEdge;
            clipInput.pnNodeTo = pTail;
            if (fnClip(pgraphIn, pgraphOut, &clipInput, NULL, pvClipArg))
                continue;
        }
 
        if (dglTreeNodeAdd(pvVisited, DGL_NODE_ID(pTail)) == NULL) {
            pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
            goto dfs_error;
        }
 
        /* add this edge */
        nret = DGL_ADD_EDGE_FUNC(
            pgraphOut, DGL_NODE_ID(pHead), DGL_NODE_ID(pTail),
            DGL_EDGE_COST(pEdge), DGL_EDGE_ID(pEdge), DGL_NODE_ATTR_PTR(pHead),
            DGL_NODE_ATTR_PTR(pTail), DGL_EDGE_ATTR_PTR(pEdge), 0);
 
        if (nret < 0) {
            goto dfs_error;
        }
 
        if ((DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) || pgraphIn->Version == 3) {
 
            pEdgeset = _DGL_OUTEDGESET(pgraphIn, pTail);
            if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
                goto dfs_error;
            }
            for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
                 pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
                stackItem.pnHead = pTail;
                stackItem.pnEdge = pEdge;
                stackItem.iWay = 0;
                if ((pstack = dgl_mempush(pstack, &istack, sizeof(stackItem),
                                          &stackItem)) == NULL) {
                    pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
                    goto dfs_error;
                }
            }
            DGL_EDGESET_T_RELEASE_FUNC(&laT);
 
            if (pgraphIn->Version == 3) {
                pEdgeset = _DGL_INEDGESET(pgraphIn, pTail);
                if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) <
                    0) {
                    goto dfs_error;
                }
                for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
                     pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
                    if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
                        continue;
                    stackItem.pnHead = pTail;
                    stackItem.pnEdge = pEdge;
                    stackItem.iWay = 1;
                    if ((pstack = dgl_mempush(pstack, &istack,
                                              sizeof(stackItem), &stackItem)) ==
                        NULL) {
                        pgraphIn->iErrno = DGL_ERR_MemoryExhausted;
                        goto dfs_error;
                    }
                }
                DGL_EDGESET_T_RELEASE_FUNC(&laT);
            }
        }
    }
 
    if (pstack)
        free(pstack);
    return 0;
 
dfs_error:
    if (pstack)
        free(pstack);
    return -pgraphIn->iErrno;
}
 
/*
 * Use a edge prioritized, tree growing scheme (aka Prim algorithm) in order to
 * be applicable to both undirected graphs (minimum spanning tree - MST) and
 * digraphs (minimum arborescense tree - MAT)
 * The vertex argument is ignored in MST (when algorithm is applied to a
 * version 3 undirected graph).
 */
int DGL_SPAN_MINIMUM_SPANNING_FUNC(dglGraph_s *pgraphIn, dglGraph_s *pgraphOut,
                                   dglInt32_t nVertex,
                                   dglSpanClip_fn fnClip UNUSED,
                                   void *pvClipArg UNUSED)
{
    dglInt32_t *pHead, *pTail, *pEdgeset, *pEdge;
    dglHeap_s FrontEdgeHeap;
    dglHeapData_u HeapData;
    dglHeapNode_s HeapItem;
    dglTreeNode_s *pPredistItem, findItem;
    dglEdgesetTraverser_s laT;
    int nret;
 
    dglHeapInit(&FrontEdgeHeap);
 
    if (pgraphIn->Version == 3) { /* undirected: pick up the first node */
        dglNodeTraverser_s pT;
 
        DGL_NODE_T_INITIALIZE_FUNC(pgraphIn, &pT);
        pHead = DGL_NODE_T_FIRST_FUNC(&pT);
        DGL_NODE_T_RELEASE_FUNC(&pT);
    }
    else { /* directed: pick up the arborescense origin */
        pHead = DGL_GET_NODE_FUNC(pgraphIn, nVertex);
    }
 
    if (pHead == NULL) {
        pgraphIn->iErrno = DGL_ERR_HeadNodeNotFound;
        goto mst_error;
    }
 
    if (DGL_NODE_STATUS(pHead) & DGL_NS_HEAD ||
        DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) {
 
        if ((DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) ||
            (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) || pgraphIn->Version == 3) {
            if (DGL_ADD_NODE_FUNC(pgraphOut, DGL_NODE_ID(pHead),
                                  DGL_NODE_ATTR_PTR(pHead), 0) < 0) {
                goto mst_error;
            }
 
            if (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) {
                dglHeapFree(&FrontEdgeHeap, NULL);
                return 0;
            }
 
            pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
            if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
                goto mst_error;
            }
            for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
                 pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
                HeapData.pv = pEdge;
                if (dglHeapInsertMin(&FrontEdgeHeap, DGL_EDGE_COST(pEdge), 0,
                                     HeapData) < 0) {
                    pgraphIn->iErrno = DGL_ERR_HeapError;
                    goto mst_error;
                }
            }
            DGL_EDGESET_T_RELEASE_FUNC(&laT);
            if (pgraphIn->Version == 3) {
                pEdgeset = _DGL_INEDGESET(pgraphIn, pHead);
                if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) <
                    0) {
                    goto mst_error;
                }
                for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
                     pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
                    if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
                        continue;
                    HeapData.pv = pEdge;
                    if (dglHeapInsertMin(&FrontEdgeHeap, DGL_EDGE_COST(pEdge),
                                         1, HeapData) < 0) {
                        pgraphIn->iErrno = DGL_ERR_HeapError;
                        goto mst_error;
                    }
                }
                DGL_EDGESET_T_RELEASE_FUNC(&laT);
            }
        }
    }
    else {
        pgraphIn->iErrno = DGL_ERR_BadEdge;
        goto mst_error;
    }
 
    while (dglHeapExtractMin(&FrontEdgeHeap, &HeapItem) == 1) {
        pEdge = HeapItem.value.pv;
 
        if (HeapItem.flags == 0) {
            if ((pHead = _DGL_EDGE_HEADNODE(pgraphIn, pEdge)) == NULL) {
                pgraphIn->iErrno = DGL_ERR_UnexpectedNullPointer;
                goto mst_error;
            }
            if ((pTail = _DGL_EDGE_TAILNODE(pgraphIn, pEdge)) == NULL) {
                pgraphIn->iErrno = DGL_ERR_UnexpectedNullPointer;
                goto mst_error;
            }
        }
        else if (pgraphIn->Version == 3) {
            if ((pTail = _DGL_EDGE_HEADNODE(pgraphIn, pEdge)) == NULL) {
                pgraphIn->iErrno = DGL_ERR_UnexpectedNullPointer;
                goto mst_error;
            }
            if ((pHead = _DGL_EDGE_TAILNODE(pgraphIn, pEdge)) == NULL) {
                pgraphIn->iErrno = DGL_ERR_UnexpectedNullPointer;
                goto mst_error;
            }
        }
        else
            continue;
 
        findItem.nKey = DGL_NODE_ID(pTail);
 
        if ((pPredistItem = avl_find(pgraphOut->pNodeTree, &findItem)) !=
            NULL) {
            continue;
        }
 
        nret = DGL_ADD_EDGE_FUNC(
            pgraphOut, DGL_NODE_ID(pHead), DGL_NODE_ID(pTail),
            DGL_EDGE_COST(pEdge), DGL_EDGE_ID(pEdge), DGL_NODE_ATTR_PTR(pHead),
            DGL_NODE_ATTR_PTR(pTail), DGL_EDGE_ATTR_PTR(pEdge), 0);
 
        if (nret < 0) {
            goto mst_error;
        }
 
        pHead = pTail;
 
        if ((DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) || pgraphIn->Version == 3) {
            pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
            if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) < 0) {
                goto mst_error;
            }
            for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
                 pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
                HeapData.pv = pEdge;
                if (dglHeapInsertMin(&FrontEdgeHeap, DGL_EDGE_COST(pEdge), 0,
                                     HeapData) < 0) {
                    pgraphIn->iErrno = DGL_ERR_HeapError;
                    goto mst_error;
                }
            }
            if (pgraphIn->Version == 3) {
                DGL_EDGESET_T_RELEASE_FUNC(&laT);
                pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
                if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn, &laT, pEdgeset) <
                    0) {
                    goto mst_error;
                }
                for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
                     pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
                    if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
                        continue;
                    HeapData.pv = pEdge;
                    if (dglHeapInsertMin(&FrontEdgeHeap, DGL_EDGE_COST(pEdge),
                                         1, HeapData) < 0) {
                        pgraphIn->iErrno = DGL_ERR_HeapError;
                        goto mst_error;
                    }
                }
                DGL_EDGESET_T_RELEASE_FUNC(&laT);
            }
        }
    }
    dglHeapFree(&FrontEdgeHeap, NULL);
    return 0;
 
mst_error:
    dglHeapFree(&FrontEdgeHeap, NULL);
    return -pgraphIn->iErrno;
}