vector/dglib/graph.c

Go to the documentation of this file.

/* LIBDGL -- a Directed Graph Library implementation
 * SPDX-FileCopyrightText: 2002 Roberto Micarelli
 * SPDX-FileCopyrightText: GRASS Development Team
 * SPDX-License-Identifier: GPL-2.0-or-later
 */
 
/*
 * 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>
 
#define DGL_V2 1
 
#include <grass/gis.h>
#include "type.h"
#include "tree.h"
#include "graph.h"
#include "graph_v1.h"
#if defined(DGL_V2)
#include "graph_v2.h"
#endif
#include "helpers.h"
 
void dglResetStats(dglGraph_s *pgraph G_UNUSED)
{
#ifdef DGL_STATS
    pgraph->clkAddEdge = 0;
    pgraph->cAddEdge = 0;
    pgraph->clkNodeTree = 0;
    pgraph->cNodeTree = 0;
#endif
}
 
int dglInitialize(dglGraph_s *pGraph, dglByte_t Version,
                  dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize,
                  dglInt32_t *pOpaqueSet)
{
    if (pGraph == NULL) {
        return -DGL_ERR_BadArgument;
    }
    switch (Version) {
    case 1:
#ifdef DGL_V2
    case 2:
    case 3:
#endif
        memset(pGraph, 0, sizeof(dglGraph_s));
        /*
         * round attr size to the upper multiple of dglInt32_t size
         */
        if (NodeAttrSize % sizeof(dglInt32_t))
            NodeAttrSize +=
                (sizeof(dglInt32_t) - (NodeAttrSize % sizeof(dglInt32_t)));
        if (EdgeAttrSize % sizeof(dglInt32_t))
            EdgeAttrSize +=
                (sizeof(dglInt32_t) - (EdgeAttrSize % sizeof(dglInt32_t)));
        pGraph->Version = Version;
        pGraph->NodeAttrSize = NodeAttrSize;
        pGraph->EdgeAttrSize = EdgeAttrSize;
        if (pOpaqueSet)
            memcpy(&pGraph->aOpaqueSet, pOpaqueSet, sizeof(dglInt32_t) * 16);
#ifdef DGL_ENDIAN_BIG
        pGraph->Endian = DGL_ENDIAN_BIG;
#else
        pGraph->Endian = DGL_ENDIAN_LITTLE;
#endif
    }
    switch (Version) {
    case 1:
        if (dgl_initialize_V1(pGraph) < 0) {
            return -pGraph->iErrno;
        }
        else
            return 0;
#ifdef DGL_V2
    case 2:
    case 3:
        if (dgl_initialize_V2(pGraph) < 0) {
            return -pGraph->iErrno;
        }
        else
            return 0;
#endif
    }
    pGraph->iErrno = DGL_ERR_VersionNotSupported;
    return -pGraph->iErrno;
}
 
int dglRelease(dglGraph_s *pGraph)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_release_V1(pGraph);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_release_V2(pGraph);
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return -pGraph->iErrno;
}
 
int dglUnflatten(dglGraph_s *pGraph)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_unflatten_V1(pGraph);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_unflatten_V2(pGraph);
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return -pGraph->iErrno;
}
 
int dglFlatten(dglGraph_s *pGraph)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_flatten_V1(pGraph);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_flatten_V2(pGraph);
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return -pGraph->iErrno;
}
 
dglInt32_t *dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_get_node_V1(pGraph, nNodeId);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_get_node_V2(pGraph, nNodeId);
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return NULL;
}
 
dglInt32_t *dglNodeGet_OutEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
{
    if (pnNode) {
        switch (pGraph->Version) {
        case 1:
            return dgl_getnode_outedgeset_V1(pGraph, pnNode);
#ifdef DGL_V2
        case 2:
        case 3:
            return dgl_getnode_outedgeset_V2(pGraph, pnNode);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return NULL;
    }
    return NULL;
}
 
dglInt32_t *dglNodeGet_InEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
{
    if (pnNode) {
        switch (pGraph->Version) {
        case 1:
            pGraph->iErrno = DGL_ERR_NotSupported;
            return NULL;
#ifdef DGL_V2
        case 2:
        case 3:
            return dgl_getnode_inedgeset_V2(pGraph, pnNode);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return NULL;
    }
    return NULL;
}
 
/*
 * Given that node id can be negative, only iErrno can report a error,
 * thus it is initialized to zero
 */
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
{
    pGraph->iErrno = 0;
    if (pnNode) {
        switch (pGraph->Version) {
        case 1:
            return DGL_NODE_ID_v1(pnNode);
#ifdef DGL_V2
        case 2:
        case 3:
            return DGL_NODE_ID_v2(pnNode);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return 0;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return 0;
}
 
dglInt32_t dglNodeGet_Status(dglGraph_s *pGraph, dglInt32_t *pnNode)
{
    pGraph->iErrno = 0;
    if (pnNode) {
        switch (pGraph->Version) {
        case 1:
            return DGL_NODE_STATUS_v1(pnNode);
#ifdef DGL_V2
        case 2:
        case 3:
            return DGL_NODE_STATUS_v2(pnNode);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return 0;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return 0;
}
 
dglInt32_t *dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
{
    if (pnNode) {
        switch (pGraph->Version) {
        case 1:
            return DGL_NODE_ATTR_PTR_v1(pnNode);
#ifdef DGL_V2
        case 2:
        case 3:
            return DGL_NODE_ATTR_PTR_v2(pnNode);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return NULL;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return NULL;
}
 
void dglNodeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode, dglInt32_t *pnAttr)
{
    if (pnNode) {
        switch (pGraph->Version) {
        case 1:
            memcpy(DGL_NODE_ATTR_PTR_v1(pnNode), pnAttr, pGraph->NodeAttrSize);
            return;
#ifdef DGL_V2
        case 2:
        case 3:
            memcpy(DGL_NODE_ATTR_PTR_v2(pnNode), pnAttr, pGraph->NodeAttrSize);
            return;
#endif
        }
        return;
    }
    return;
}
 
int dglNodeGet_InDegree(dglGraph_s *pGraph, dglInt32_t *pnNode)
{
#ifdef DGL_V2
    dglInt32_t *pinedgeset;
#endif
 
    pGraph->iErrno = 0;
    if (pnNode) {
        switch (pGraph->Version) {
        case 1:
            pGraph->iErrno = DGL_ERR_NotSupported;
            return 0;
#ifdef DGL_V2
        case 2:
            if (DGL_NODE_STATUS_v2(pnNode) & DGL_NS_ALONE)
                return 0;
            pinedgeset = dglNodeGet_InEdgeset(pGraph, pnNode);
            if (pinedgeset)
                return DGL_EDGESET_EDGECOUNT_v2(pinedgeset);
            return 0;
        case 3:
            return dglNodeGet_Valence(pGraph, pnNode);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return 0;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return 0;
}
 
int dglNodeGet_OutDegree(dglGraph_s *pGraph, dglInt32_t *pnNode)
{
    dglInt32_t *poutedgeset;
 
    pGraph->iErrno = 0;
    if (pnNode) {
        switch (pGraph->Version) {
        case 1:
            if (DGL_NODE_STATUS_v1(pnNode) & DGL_NS_ALONE)
                return 0;
            poutedgeset = dglNodeGet_OutEdgeset(pGraph, pnNode);
            if (poutedgeset)
                return DGL_EDGESET_EDGECOUNT_v1(poutedgeset);
            return 0;
#ifdef DGL_V2
        case 2:
            if (DGL_NODE_STATUS_v2(pnNode) & DGL_NS_ALONE)
                return 0;
            poutedgeset = dglNodeGet_OutEdgeset(pGraph, pnNode);
            if (poutedgeset)
                return DGL_EDGESET_EDGECOUNT_v2(poutedgeset);
            return 0;
        case 3:
            return dglNodeGet_Valence(pGraph, pnNode);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return 0;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return 0;
}
 
int dglNodeGet_Valence(dglGraph_s *pGraph, dglInt32_t *pnNode)
{
#ifdef DGL_V2
    dglInt32_t *poutedgeset;
    dglInt32_t *pinedgeset;
    int c;
#endif
 
    pGraph->iErrno = 0;
    if (pnNode) {
        switch (pGraph->Version) {
#ifdef DGL_V2
        case 3:
            if (DGL_NODE_STATUS_v2(pnNode) & DGL_NS_ALONE)
                return 0;
            poutedgeset = dglNodeGet_OutEdgeset(pGraph, pnNode);
            pinedgeset = dglNodeGet_InEdgeset(pGraph, pnNode);
            c = 0;
            if (poutedgeset)
                c += DGL_EDGESET_EDGECOUNT_v2(poutedgeset);
            if (pinedgeset)
                c += DGL_EDGESET_EDGECOUNT_v2(pinedgeset);
            return c;
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return 0;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return 0;
}
 
dglInt32_t dglEdgesetGet_EdgeCount(dglGraph_s *pGraph, dglInt32_t *pnEdgeset)
{
    pGraph->iErrno = 0;
    if (pnEdgeset) {
        switch (pGraph->Version) {
        case 1:
            return DGL_EDGESET_EDGECOUNT_v1(pnEdgeset);
#ifdef DGL_V2
        case 2:
        case 3:
            return DGL_EDGESET_EDGECOUNT_v2(pnEdgeset);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return 0;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return 0;
}
 
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
{
    pGraph->iErrno = 0;
    if (pnEdge) {
        switch (pGraph->Version) {
        case 1:
            return DGL_EDGE_COST_v1(pnEdge);
#ifdef DGL_V2
        case 2:
        case 3:
            return DGL_EDGE_COST_v2(pnEdge);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return 0;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return 0;
}
 
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
{
    pGraph->iErrno = 0;
    if (pnEdge) {
        switch (pGraph->Version) {
        case 1:
            return DGL_EDGE_ID_v1(pnEdge);
#ifdef DGL_V2
        case 2:
        case 3:
            return DGL_EDGE_ID_v2(pnEdge);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return 0;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return 0;
}
 
dglInt32_t *dglEdgeGet_Head(dglGraph_s *pGraph, dglInt32_t *pnEdge)
{
    pGraph->iErrno = 0;
    if (pnEdge) {
        switch (pGraph->Version) {
        case 1:
            if (pGraph->Flags & DGL_GS_FLAT) {
                return DGL_NODEBUFFER_SHIFT_v1(
                    pGraph, DGL_EDGE_HEADNODE_OFFSET_v1(pnEdge));
            }
            else {
                return dgl_get_node_V1(pGraph,
                                       DGL_EDGE_HEADNODE_OFFSET_v1(pnEdge));
            }
#ifdef DGL_V2
        case 2:
        case 3:
            if (pGraph->Flags & DGL_GS_FLAT) {
                return DGL_NODEBUFFER_SHIFT_v2(
                    pGraph, DGL_EDGE_HEADNODE_OFFSET_v2(pnEdge));
            }
            else {
                return dgl_get_node_V2(pGraph,
                                       DGL_EDGE_HEADNODE_OFFSET_v2(pnEdge));
            }
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return NULL;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return NULL;
}
 
dglInt32_t *dglEdgeGet_Tail(dglGraph_s *pGraph, dglInt32_t *pnEdge)
{
    pGraph->iErrno = 0;
    if (pnEdge) {
        switch (pGraph->Version) {
        case 1:
            if (pGraph->Flags & DGL_GS_FLAT) {
                return DGL_NODEBUFFER_SHIFT_v1(
                    pGraph, DGL_EDGE_TAILNODE_OFFSET_v1(pnEdge));
            }
            else {
                return dgl_get_node_V1(pGraph,
                                       DGL_EDGE_TAILNODE_OFFSET_v1(pnEdge));
            }
#ifdef DGL_V2
        case 2:
        case 3:
            if (pGraph->Flags & DGL_GS_FLAT) {
                return DGL_NODEBUFFER_SHIFT_v2(
                    pGraph, DGL_EDGE_TAILNODE_OFFSET_v2(pnEdge));
            }
            else {
                return dgl_get_node_V2(pGraph,
                                       DGL_EDGE_TAILNODE_OFFSET_v2(pnEdge));
            }
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return NULL;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return NULL;
}
 
dglInt32_t *dglEdgeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnEdge)
{
    pGraph->iErrno = 0;
    if (pnEdge) {
        switch (pGraph->Version) {
        case 1:
            return DGL_EDGE_ATTR_PTR_v1(pnEdge);
#ifdef DGL_V2
        case 2:
        case 3:
            return DGL_EDGE_ATTR_PTR_v2(pnEdge);
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return NULL;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return NULL;
}
 
int dglEdgeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnAttr, dglInt32_t *pnEdge)
{
    if (pnEdge) {
        switch (pGraph->Version) {
        case 1:
            memcpy(DGL_EDGE_ATTR_PTR_v1(pnEdge), pnAttr, pGraph->EdgeAttrSize);
            return 0;
#ifdef DGL_V2
        case 2:
        case 3:
            memcpy(DGL_EDGE_ATTR_PTR_v2(pnEdge), pnAttr, pGraph->EdgeAttrSize);
            return 0;
#endif
        }
        pGraph->iErrno = DGL_ERR_BadVersion;
        return -pGraph->iErrno;
    }
    pGraph->iErrno = DGL_ERR_UnexpectedNullPointer;
    return -pGraph->iErrno;
}
 
dglInt32_t *dglGetEdge(dglGraph_s *pGraph, dglInt32_t nEdgeId)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_get_edge_V1(pGraph, nEdgeId);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_get_edge_V2(pGraph, nEdgeId);
        break;
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return NULL;
}
 
int dglDelEdge(dglGraph_s *pGraph, dglInt32_t nEdgeId)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_del_edge_V1(pGraph, nEdgeId);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_del_edge_V2(pGraph, nEdgeId);
        break;
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return -pGraph->iErrno;
}
 
int dglAddEdge(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail,
               dglInt32_t nCost, dglInt32_t nEdge)
{
    int nRet;
 
#ifdef DGL_STATS
    clock_t clk;
 
    clk = clock();
    pGraph->cAddEdge++;
#endif
    switch (pGraph->Version) {
    case 1:
        nRet = dgl_add_edge_V1(pGraph, nHead, nTail, nCost, nEdge, NULL, NULL,
                               NULL, 0);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        nRet = dgl_add_edge_V2(pGraph, nHead, nTail, nCost, nEdge, NULL, NULL,
                               NULL, 0);
        break;
#endif
    default:
        pGraph->iErrno = DGL_ERR_BadVersion;
        nRet = -pGraph->iErrno;
        break;
    }
#ifdef DGL_STATS
    pGraph->clkAddEdge += clock() - clk;
#endif
    return nRet;
}
 
int dglAddEdgeX(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail,
                dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr,
                void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
{
    int nRet;
 
#ifdef DGL_STATS
    clock_t clk;
 
    clk = clock();
    pGraph->cAddEdge++;
#endif
    switch (pGraph->Version) {
    case 1:
        nRet = dgl_add_edge_V1(pGraph, nHead, nTail, nCost, nEdge, pvHeadAttr,
                               pvTailAttr, pvEdgeAttr, nFlags);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        nRet = dgl_add_edge_V2(pGraph, nHead, nTail, nCost, nEdge, pvHeadAttr,
                               pvTailAttr, pvEdgeAttr, nFlags);
        break;
#endif
    default:
        pGraph->iErrno = DGL_ERR_BadVersion;
        nRet = -pGraph->iErrno;
        break;
    }
#ifdef DGL_STATS
    pGraph->clkAddEdge += clock() - clk;
#endif
    return nRet;
}
 
int dglAddNode(dglGraph_s *pGraph, dglInt32_t nNodeId, void *pvNodeAttr,
               dglInt32_t nFlags)
{
    int nRet;
 
    switch (pGraph->Version) {
    case 1:
        nRet = dgl_add_node_V1(pGraph, nNodeId, pvNodeAttr, nFlags);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        nRet = dgl_add_node_V2(pGraph, nNodeId, pvNodeAttr, nFlags);
        break;
#endif
    default:
        pGraph->iErrno = DGL_ERR_BadVersion;
        nRet = -pGraph->iErrno;
        break;
    }
    return nRet;
}
 
int dglDelNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
{
    int nRet;
 
    switch (pGraph->Version) {
    case 1:
        nRet = dgl_del_node_V1(pGraph, nNodeId);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        nRet = dgl_del_node_V2(pGraph, nNodeId);
        break;
#endif
    default:
        pGraph->iErrno = DGL_ERR_BadVersion;
        nRet = -pGraph->iErrno;
        break;
    }
    return nRet;
}
 
int dglWrite(dglGraph_s *pGraph, int fd)
{
    int nRet;
 
    switch (pGraph->Version) {
    case 1:
        nRet = dgl_write_V1(pGraph, fd);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        nRet = dgl_write_V2(pGraph, fd);
        break;
#endif
    default:
        pGraph->iErrno = DGL_ERR_BadVersion;
        nRet = -pGraph->iErrno;
        break;
    }
    return nRet;
}
 
int dglRead(dglGraph_s *pGraph, int fd)
{
    dglByte_t bVersion;
    int nRet;
 
    if (read(fd, &bVersion, 1) != 1) {
        pGraph->iErrno = DGL_ERR_Read;
        nRet = -pGraph->iErrno;
    }
    else {
        switch (bVersion) {
        case 1:
            nRet = dgl_read_V1(pGraph, fd);
            break;
#ifdef DGL_V2
        case 2:
        case 3:
            nRet = dgl_read_V2(pGraph, fd, bVersion);
            break;
#endif
        default:
            pGraph->iErrno = DGL_ERR_VersionNotSupported;
            nRet = -pGraph->iErrno;
            break;
        }
    }
    return nRet;
}
 
int dglShortestPath(dglGraph_s *pGraph, dglSPReport_s **ppReport,
                    dglInt32_t nStart, dglInt32_t nDestination,
                    dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
{
    int nRet;
 
    switch (pGraph->Version) {
    case 1:
        nRet = dgl_dijkstra_V1(pGraph, ppReport, NULL, nStart, nDestination,
                               fnClip, pvClipArg, pCache);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        nRet = dgl_dijkstra_V2(pGraph, ppReport, NULL, nStart, nDestination,
                               fnClip, pvClipArg, pCache);
        break;
#endif
    default:
        pGraph->iErrno = DGL_ERR_BadVersion;
        nRet = -pGraph->iErrno;
        break;
    }
    return nRet;
}
 
int dglShortestDistance(dglGraph_s *pGraph, dglInt32_t *pnDistance,
                        dglInt32_t nStart, dglInt32_t nDestination,
                        dglSPClip_fn fnClip, void *pvClipArg,
                        dglSPCache_s *pCache)
{
    int nRet;
 
    switch (pGraph->Version) {
    case 1:
        nRet = dgl_dijkstra_V1(pGraph, NULL, pnDistance, nStart, nDestination,
                               fnClip, pvClipArg, pCache);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        nRet = dgl_dijkstra_V2(pGraph, NULL, pnDistance, nStart, nDestination,
                               fnClip, pvClipArg, pCache);
        break;
#endif
    default:
        pGraph->iErrno = DGL_ERR_BadVersion;
        nRet = -pGraph->iErrno;
        break;
    }
    return nRet;
}
 
int dglDepthSpanning(dglGraph_s *pgraphInput, dglGraph_s *pgraphOutput,
                     dglInt32_t nVertexNode, dglSpanClip_fn fnClip,
                     void *pvClipArg)
{
    int nRet;
    void *pvVisited;
 
    if (dglGet_EdgeCount(pgraphInput) == 0) { /* no span */
        pgraphInput->iErrno = 0;
        return 0;
    }
 
#ifndef DGL_V2
    if (pgraphInput->Version == 2) {
        pgraphInput->iErrno = DGL_ERR_BadVersion;
        return -pgraphInput->iErrno;
    }
#endif
 
    nRet = dglInitialize(pgraphOutput, dglGet_Version(pgraphInput),
                         dglGet_NodeAttrSize(pgraphInput),
                         dglGet_EdgeAttrSize(pgraphInput),
                         dglGet_Opaque(pgraphInput));
 
    if (nRet < 0)
        return nRet;
 
    if ((pvVisited = avl_create(dglTreeNodeCompare, NULL,
                                dglTreeGetAllocator())) == NULL) {
        pgraphInput->iErrno = DGL_ERR_MemoryExhausted;
        return -pgraphInput->iErrno;
    }
 
    switch (pgraphInput->Version) {
    case 1:
        nRet =
            dgl_depthfirst_spanning_V1(pgraphInput, pgraphOutput, nVertexNode,
                                       pvVisited, fnClip, pvClipArg);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        nRet =
            dgl_depthfirst_spanning_V2(pgraphInput, pgraphOutput, nVertexNode,
                                       pvVisited, fnClip, pvClipArg);
        break;
#endif
    default:
        pgraphInput->iErrno = DGL_ERR_BadVersion;
        nRet = -pgraphInput->iErrno;
        break;
    }
 
    avl_destroy(pvVisited, dglTreeNodeCancel);
 
    if (nRet < 0) {
        dglRelease(pgraphOutput);
    }
 
    return nRet;
}
 
int dglDepthComponents(dglGraph_s *pgraphInput, dglGraph_s *pgraphComponents,
                       int cgraphComponents, dglSpanClip_fn fnClip,
                       void *pvClipArg)
{
    int i, nret = 0;
    dglTreeNode_s findVisited;
    void *pvVisited;
    dglInt32_t *pvertex, *pnode;
 
    if (dglGet_EdgeCount(pgraphInput) == 0) { /* no span */
        pgraphInput->iErrno = 0;
        return 0;
    }
 
#ifndef DGL_V2
    if (pgraphInput->Version == 2 || pgraphInput->Version == 3) {
        pgraphInput->iErrno = DGL_ERR_BadVersion;
        return -pgraphInput->iErrno;
    }
#endif
 
    if ((pvVisited = avl_create(dglTreeNodeCompare, NULL,
                                dglTreeGetAllocator())) == NULL) {
        pgraphInput->iErrno = DGL_ERR_MemoryExhausted;
        goto error;
    }
 
    /*
     * choose a vertex to start from
     */
    pvertex = NULL;
    {
        dglNodeTraverser_s pT;
 
        dglNode_T_Initialize(&pT, pgraphInput);
        for (pnode = dglNode_T_First(&pT); pnode; pnode = dglNode_T_Next(&pT)) {
            switch (pgraphInput->Version) {
            case 1:
                if (DGL_NODE_STATUS_v1(pnode) & DGL_NS_HEAD)
                    pvertex = pnode;
                break;
#ifdef DGL_V2
            case 2:
            case 3:
                if (DGL_NODE_STATUS_v2(pnode) & DGL_NS_HEAD)
                    pvertex = pnode;
                break;
#endif
            }
            if (pvertex)
                break;
        }
        dglNode_T_Release(&pT);
    }
 
    if (pvertex == NULL) {
        pgraphInput->iErrno = DGL_ERR_UnexpectedNullPointer;
        goto error;
    }
 
    for (i = 0; i < cgraphComponents && pvertex; i++) {
        nret = dglInitialize(&pgraphComponents[i], dglGet_Version(pgraphInput),
                             dglGet_NodeAttrSize(pgraphInput),
                             dglGet_EdgeAttrSize(pgraphInput),
                             dglGet_Opaque(pgraphInput));
 
        if (nret < 0)
            goto error;
 
        switch (pgraphInput->Version) {
        case 1:
            nret = dgl_depthfirst_spanning_V1(pgraphInput, &pgraphComponents[i],
                                              DGL_NODE_ID_v1(pvertex),
                                              pvVisited, fnClip, pvClipArg);
            if (nret < 0)
                goto error;
            break;
#ifdef DGL_V2
        case 2:
        case 3:
            nret = dgl_depthfirst_spanning_V2(pgraphInput, &pgraphComponents[i],
                                              DGL_NODE_ID_v1(pvertex),
                                              pvVisited, fnClip, pvClipArg);
            if (nret < 0)
                goto error;
            break;
#endif
        default:
            pgraphInput->iErrno = DGL_ERR_BadVersion;
            nret = -pgraphInput->iErrno;
            goto error;
        }
 
        /*
         * select next unvisited vertex
         */
        pvertex = NULL;
        {
            dglNodeTraverser_s pT;
 
            dglNode_T_Initialize(&pT, pgraphInput);
            for (pnode = dglNode_T_First(&pT); pnode;
                 pnode = dglNode_T_Next(&pT)) {
                switch (pgraphInput->Version) {
                case 1:
                    if (DGL_NODE_STATUS_v1(pnode) & DGL_NS_HEAD) {
                        findVisited.nKey = DGL_NODE_ID_v1(pnode);
                        if (avl_find(pvVisited, &findVisited) == NULL) {
                            pvertex = pnode;
                            break;
                        }
                    }
                    break;
#ifdef DGL_V2
                case 2:
                case 3:
                    if (DGL_NODE_STATUS_v2(pnode) & DGL_NS_HEAD) {
                        findVisited.nKey = DGL_NODE_ID_v2(pnode);
                        if (avl_find(pvVisited, &findVisited) == NULL) {
                            pvertex = pnode;
                            break;
                        }
                    }
                    break;
#endif
                }
                if (pvertex)
                    break;
            }
            dglNode_T_Release(&pT);
        }
    }
 
    avl_destroy(pvVisited, dglTreeNodeCancel);
    return i;
 
error:
    avl_destroy(pvVisited, dglTreeNodeCancel);
    return nret;
}
 
int dglMinimumSpanning(dglGraph_s *pgraphInput, dglGraph_s *pgraphOutput,
                       dglInt32_t nVertexNode, dglSpanClip_fn fnClip,
                       void *pvClipArg)
{
    int nRet;
 
    if (dglGet_EdgeCount(pgraphInput) == 0) { /* no span */
        pgraphInput->iErrno = 0;
        return 0;
    }
 
    nRet = dglInitialize(pgraphOutput, dglGet_Version(pgraphInput),
                         dglGet_NodeAttrSize(pgraphInput),
                         dglGet_EdgeAttrSize(pgraphInput),
                         dglGet_Opaque(pgraphInput));
 
    if (nRet < 0)
        return nRet;
 
    switch (pgraphInput->Version) {
    case 1:
        nRet = dgl_minimum_spanning_V1(pgraphInput, pgraphOutput, nVertexNode,
                                       fnClip, pvClipArg);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        nRet = dgl_minimum_spanning_V2(pgraphInput, pgraphOutput, nVertexNode,
                                       fnClip, pvClipArg);
        break;
#endif
    default:
        pgraphInput->iErrno = DGL_ERR_BadVersion;
        nRet = -pgraphInput->iErrno;
        break;
    }
    if (nRet < 0) {
        dglRelease(pgraphOutput);
    }
    return nRet;
}
 
void dglFreeSPReport(dglGraph_s *pgraph G_UNUSED, dglSPReport_s *pSPReport)
{
    int iArc;
 
    if (pSPReport) {
        if (pSPReport->pArc) {
            for (iArc = 0; iArc < pSPReport->cArc; iArc++) {
                if (pSPReport->pArc[iArc].pnEdge)
                    free(pSPReport->pArc[iArc].pnEdge);
            }
            free(pSPReport->pArc);
        }
        free(pSPReport);
    }
}
 
int dglInitializeSPCache(dglGraph_s *pGraph, dglSPCache_s *pCache)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_sp_cache_initialize_V1(pGraph, pCache, 0);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_sp_cache_initialize_V2(pGraph, pCache, 0);
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return -pGraph->iErrno;
}
 
void dglReleaseSPCache(dglGraph_s *pGraph, dglSPCache_s *pCache)
{
    pGraph->iErrno = 0;
    switch (pGraph->Version) {
    case 1:
        dgl_sp_cache_release_V1(pGraph, pCache);
        break;
#ifdef DGL_V2
    case 2:
    case 3:
        dgl_sp_cache_release_V2(pGraph, pCache);
        break;
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
}
 
int dglErrno(dglGraph_s *pgraph)
{
    return pgraph->iErrno;
}
 
char *dglStrerror(dglGraph_s *pgraph)
{
    switch (pgraph->iErrno) {
    case DGL_ERR_BadVersion:
        return "Bad Version";
    case DGL_ERR_BadNodeType:
        return "Bad Node Type";
    case DGL_ERR_MemoryExhausted:
        return "Memory Exhausted";
    case DGL_ERR_HeapError:
        return "Heap Error";
    case DGL_ERR_UndefinedMethod:
        return "Undefined Method";
    case DGL_ERR_Write:
        return "Write";
    case DGL_ERR_Read:
        return "Read";
    case DGL_ERR_NotSupported:
        return "Not Supported";
    case DGL_ERR_UnknownByteOrder:
        return "Unknown Byte Order";
    case DGL_ERR_NodeNotFound:
        return "Node Not Found";
    case DGL_ERR_HeadNodeNotFound:
        return "Head Node Not Found";
    case DGL_ERR_TailNodeNotFound:
        return "Tail Node Not Found";
    case DGL_ERR_BadEdge:
        return "Bad Edge";
    case DGL_ERR_BadOnFlatGraph:
        return "Operation Not Supported On Flat-State Graph";
    case DGL_ERR_BadOnTreeGraph:
        return "Operation Not Supported On Tree-State Graph";
    case DGL_ERR_TreeSearchError:
        return "Tree Search Error";
    case DGL_ERR_UnexpectedNullPointer:
        return "Unexpected Null Pointer";
    case DGL_ERR_VersionNotSupported:
        return "Version Not Supported";
    case DGL_ERR_EdgeNotFound:
        return "Edge Not Found";
    case DGL_ERR_NodeAlreadyExist:
        return "Node Already Exist";
    case DGL_ERR_NodeIsAComponent:
        return "Node Is A Component";
    case DGL_ERR_EdgeAlreadyExist:
        return "Edge Already Exist";
    case DGL_ERR_BadArgument:
        return "Bad Argument";
    }
 
    return "unknown graph error code";
}
 
/*
 * dglGraph_s hiders
 */
int dglGet_Version(dglGraph_s *pgraph)
{
    return pgraph->Version;
}
void dglSet_Version(dglGraph_s *pgraph, int nVersion)
{
    pgraph->Version = nVersion;
}
 
int dglGet_Endianess(dglGraph_s *pgraph)
{
    return pgraph->Endian;
}
 
int dglGet_NodeAttrSize(dglGraph_s *pgraph)
{
    return pgraph->NodeAttrSize;
}
 
int dglGet_EdgeAttrSize(dglGraph_s *pgraph)
{
    return pgraph->EdgeAttrSize;
}
 
int dglGet_NodeCount(dglGraph_s *pgraph)
{
    return pgraph->cNode;
}
 
int dglGet_HeadNodeCount(dglGraph_s *pgraph)
{
    return pgraph->cHead;
}
 
int dglGet_TailNodeCount(dglGraph_s *pgraph)
{
    return pgraph->cTail;
}
 
int dglGet_AloneNodeCount(dglGraph_s *pgraph)
{
    return pgraph->cAlone;
}
 
int dglGet_EdgeCount(dglGraph_s *pgraph)
{
    return pgraph->cEdge;
}
 
int dglGet_State(dglGraph_s *pgraph)
{
    return pgraph->Flags;
}
 
dglInt32_t *dglGet_Opaque(dglGraph_s *pgraph)
{
    return pgraph->aOpaqueSet;
}
 
void dglSet_Opaque(dglGraph_s *pgraph, dglInt32_t *pOpaque)
{
    memcpy(pgraph->aOpaqueSet, pOpaque, sizeof(dglInt32_t) * 16);
}
 
int dglGet_NodeSize(dglGraph_s *pgraph)
{
    switch (pgraph->Version) {
    case 1:
        return DGL_NODE_SIZEOF_v1(pgraph->NodeAttrSize);
#ifdef DGL_V2
    case 2:
    case 3:
        return DGL_NODE_SIZEOF_v2(pgraph->NodeAttrSize);
#endif
    }
    pgraph->iErrno = DGL_ERR_BadVersion;
    return -pgraph->iErrno;
}
 
int dglGet_EdgeSize(dglGraph_s *pgraph)
{
    switch (pgraph->Version) {
    case 1:
        return DGL_EDGE_SIZEOF_v1(pgraph->NodeAttrSize);
#ifdef DGL_V2
    case 2:
    case 3:
        return DGL_EDGE_SIZEOF_v2(pgraph->NodeAttrSize);
#endif
    }
    pgraph->iErrno = DGL_ERR_BadVersion;
    return -pgraph->iErrno;
}
 
dglInt64_t dglGet_Cost(dglGraph_s *pgraph)
{
    return pgraph->nnCost;
}
 
void dglSet_Cost(dglGraph_s *pgraph, dglInt64_t nnCost)
{
    pgraph->nnCost = nnCost;
}
 
dglInt32_t dglGet_Family(dglGraph_s *pgraph)
{
    return pgraph->nFamily;
}
 
void dglSet_Family(dglGraph_s *pgraph, dglInt32_t nFamily)
{
    pgraph->nFamily = nFamily;
}
 
dglInt32_t dglGet_Options(dglGraph_s *pgraph)
{
    return pgraph->nOptions;
}
 
void dglSet_Options(dglGraph_s *pgraph, dglInt32_t nOptions)
{
    pgraph->nOptions = nOptions;
}
 
dglEdgePrioritizer_s *dglGet_EdgePrioritizer(dglGraph_s *pGraph)
{
    return &pGraph->edgePrioritizer;
}
 
dglNodePrioritizer_s *dglGet_NodePrioritizer(dglGraph_s *pGraph)
{
    return &pGraph->nodePrioritizer;
}
 
/*
 * Node Traverse
 */
int dglNode_T_Initialize(dglNodeTraverser_s *pT, dglGraph_s *pGraph)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_node_t_initialize_V1(pGraph, pT);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_node_t_initialize_V2(pGraph, pT);
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return -pGraph->iErrno;
}
 
void dglNode_T_Release(dglNodeTraverser_s *pT)
{
    switch (pT->pGraph->Version) {
    case 1:
        dgl_node_t_release_V1(pT);
        return;
#ifdef DGL_V2
    case 2:
    case 3:
        dgl_node_t_release_V2(pT);
        return;
#endif
    }
    pT->pGraph->iErrno = DGL_ERR_BadVersion;
}
 
dglInt32_t *dglNode_T_First(dglNodeTraverser_s *pT)
{
    switch (pT->pGraph->Version) {
    case 1:
        return dgl_node_t_first_V1(pT);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_node_t_first_V2(pT);
#endif
    }
    pT->pGraph->iErrno = DGL_ERR_BadVersion;
    return NULL;
}
 
dglInt32_t *dglNode_T_Next(dglNodeTraverser_s *pT)
{
    switch (pT->pGraph->Version) {
    case 1:
        return dgl_node_t_next_V1(pT);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_node_t_next_V2(pT);
#endif
    }
    pT->pGraph->iErrno = DGL_ERR_BadVersion;
    return NULL;
}
 
dglInt32_t *dglNode_T_Find(dglNodeTraverser_s *pT, dglInt32_t nNodeId)
{
    switch (pT->pGraph->Version) {
    case 1:
        return dgl_node_t_find_V1(pT, nNodeId);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_node_t_find_V2(pT, nNodeId);
#endif
    }
    pT->pGraph->iErrno = DGL_ERR_BadVersion;
    return NULL;
}
 
/*
 * Edge Traverser
 */
int dglEdge_T_Initialize(dglEdgeTraverser_s *pT, dglGraph_s *pGraph,
                         dglEdgePrioritizer_s *pEdgePrioritizer)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_edge_t_initialize_V1(pGraph, pT, pEdgePrioritizer);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_edge_t_initialize_V2(pGraph, pT, pEdgePrioritizer);
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return -pGraph->iErrno;
}
 
void dglEdge_T_Release(dglEdgeTraverser_s *pT)
{
    switch (pT->pGraph->Version) {
    case 1:
        dgl_edge_t_release_V1(pT);
        return;
#ifdef DGL_V2
    case 2:
    case 3:
        dgl_edge_t_release_V2(pT);
        return;
#endif
    }
    pT->pGraph->iErrno = DGL_ERR_BadVersion;
}
 
dglInt32_t *dglEdge_T_First(dglEdgeTraverser_s *pT)
{
    switch (pT->pGraph->Version) {
    case 1:
        return dgl_edge_t_first_V1(pT);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_edge_t_first_V2(pT);
#endif
    }
    pT->pGraph->iErrno = DGL_ERR_BadVersion;
    return NULL;
}
 
dglInt32_t *dglEdge_T_Next(dglEdgeTraverser_s *pT)
{
    switch (pT->pGraph->Version) {
    case 1:
        return dgl_edge_t_next_V1(pT);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_edge_t_next_V2(pT);
#endif
    }
    pT->pGraph->iErrno = DGL_ERR_BadVersion;
    return NULL;
}
 
int dglEdgeset_T_Initialize(dglEdgesetTraverser_s *pT, dglGraph_s *pGraph,
                            dglInt32_t *pnEdgeset)
{
    switch (pGraph->Version) {
    case 1:
        return dgl_edgeset_t_initialize_V1(pGraph, pT, pnEdgeset);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_edgeset_t_initialize_V2(pGraph, pT, pnEdgeset);
#endif
    }
    pGraph->iErrno = DGL_ERR_BadVersion;
    return -pGraph->iErrno;
}
 
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT G_UNUSED)
{
}
 
dglInt32_t *dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
{
    switch (pT->pGraph->Version) {
    case 1:
        return dgl_edgeset_t_first_V1(pT);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_edgeset_t_first_V2(pT);
#endif
    }
    pT->pGraph->iErrno = DGL_ERR_BadVersion;
    return NULL;
}
 
dglInt32_t *dglEdgeset_T_Next(dglEdgesetTraverser_s *pT)
{
    switch (pT->pGraph->Version) {
    case 1:
        return dgl_edgeset_t_next_V1(pT);
#ifdef DGL_V2
    case 2:
    case 3:
        return dgl_edgeset_t_next_V2(pT);
#endif
    }
    pT->pGraph->iErrno = DGL_ERR_BadVersion;
    return NULL;
}
 
/*
 * chunked I/O
 */
 
#define __CIO_BEGIN        0
#define __CIO_W_HEADER     1
#define __CIO_W_NODEBUFFER 2
#define __CIO_W_EDGEBUFFER 3
#define __CIO_R_HEADER     4
#define __CIO_R_NODEBUFFER 5
#define __CIO_R_EDGEBUFFER 6
#define __CIO_END          7
 
int dglIOContextInitialize(dglGraph_s *pG, dglIOContext_s *pIO)
{
    pIO->pG = pG;
    pIO->nState = __CIO_BEGIN;
    pIO->cb = 0;
    pIO->ib = 0;
    pIO->pb = NULL;
    return 0;
}
 
void dglIOContextRelease(dglIOContext_s *pIO G_UNUSED)
{
}
 
int dglWriteChunk(dglIOContext_s *pIO, dglWriteChunk_fn pfn, void *pv)
{
    unsigned char *pb;
    int cb;
 
    switch (pIO->nState) {
    case __CIO_BEGIN:
        pIO->pb = pIO->ab;
        pb = pIO->pb;
        memcpy(pb, &pIO->pG->Version, 1);
        pb += 1; /* 1 */
        memcpy(pb, &pIO->pG->Endian, 1);
        pb += 1; /* 2 */
        memcpy(pb, &pIO->pG->NodeAttrSize, 4);
        pb += 4; /* 6 */
        memcpy(pb, &pIO->pG->EdgeAttrSize, 4);
        pb += 4; /* 10 */
        memcpy(pb, &pIO->pG->aOpaqueSet, 64);
        pb += 64; /* 74 */
        memcpy(pb, &pIO->pG->nOptions, 4);
        pb += 4; /* 78 */
        memcpy(pb, &pIO->pG->nFamily, 4);
        pb += 4; /* 82 */
        memcpy(pb, &pIO->pG->nnCost, 8);
        pb += 8; /* 90 */
        memcpy(pb, &pIO->pG->cNode, 4);
        pb += 4; /* 94 */
        memcpy(pb, &pIO->pG->cHead, 4);
        pb += 4; /* 98 */
        memcpy(pb, &pIO->pG->cTail, 4);
        pb += 4; /* 102 */
        memcpy(pb, &pIO->pG->cAlone, 4);
        pb += 4; /* 106 */
        memcpy(pb, &pIO->pG->cEdge, 4);
        pb += 4; /* 110 */
        memcpy(pb, &pIO->pG->iNodeBuffer, 4);
        pb += 4; /* 114 */
        memcpy(pb, &pIO->pG->iEdgeBuffer, 4);
        pb += 4; /* 118 */
        pIO->cb = 118;
        cb = pfn(pIO->pG, pIO->pb, pIO->cb, pv);
        if (cb >= 0) {
            pIO->ib += cb;
            if ((pIO->cb - pIO->ib) == 0) {
                pIO->ib = 0;
                pIO->cb = pIO->pG->iNodeBuffer;
                pIO->pb = pIO->pG->pNodeBuffer;
                pIO->nState = __CIO_W_NODEBUFFER;
            }
            else {
                pIO->nState = __CIO_W_HEADER;
            }
        }
        return cb;
    case __CIO_W_HEADER:
        cb = pfn(pIO->pG, pIO->pb + pIO->ib, pIO->cb - pIO->ib, pv);
        if (cb > 0) {
            pIO->ib += cb;
            if ((pIO->cb - pIO->ib) == 0) {
                if (pIO->pG->iNodeBuffer > 0) {
                    pIO->ib = 0;
                    pIO->cb = pIO->pG->iNodeBuffer;
                    pIO->pb = pIO->pG->pNodeBuffer;
                    pIO->nState = __CIO_W_NODEBUFFER;
                }
                else if (pIO->pG->iEdgeBuffer > 0) {
                    pIO->ib = 0;
                    pIO->cb = pIO->pG->iEdgeBuffer;
                    pIO->pb = pIO->pG->pEdgeBuffer;
                    pIO->nState = __CIO_W_EDGEBUFFER;
                }
                else {
                    pIO->nState = __CIO_END;
                }
            }
            else {
                pIO->nState = __CIO_W_HEADER;
            }
        }
        return cb;
    case __CIO_W_NODEBUFFER:
        cb = pfn(pIO->pG, pIO->pb + pIO->ib, pIO->cb - pIO->ib, pv);
        if (cb > 0) {
            pIO->ib += cb;
            if ((pIO->cb - pIO->ib) == 0) {
                if (pIO->pG->iEdgeBuffer > 0) {
                    pIO->ib = 0;
                    pIO->cb = pIO->pG->iEdgeBuffer;
                    pIO->pb = pIO->pG->pEdgeBuffer;
                    pIO->nState = __CIO_W_EDGEBUFFER;
                }
                else {
                    pIO->nState = __CIO_END;
                }
            }
        }
        return cb;
    case __CIO_W_EDGEBUFFER:
        cb = pfn(pIO->pG, pIO->pb + pIO->ib, pIO->cb - pIO->ib, pv);
        if (cb > 0) {
            pIO->ib += cb;
            if ((pIO->cb - pIO->ib) == 0) {
                pIO->nState = __CIO_END;
            }
        }
        return cb;
    case __CIO_END:
        pfn(pIO->pG, NULL, 0, pv); /* notify end of graph */
        return 0;
    }
    return 0;
}
 
int dglReadChunk(dglIOContext_s *pIO, dglByte_t *pbChunk, int cbChunk)
{
    int i, c;
    unsigned char *pb;
 
    switch (pIO->nState) {
    case __CIO_BEGIN:
        pIO->cb = 118;
        pIO->ib = 0;
        pIO->pb = pIO->ab;
 
        c = MIN(cbChunk, 118);
        memcpy(pIO->pb, pbChunk, c);
        pIO->ib += c;
        if ((pIO->cb - pIO->ib) == 0)
            goto init_nodebuffer;
        pIO->nState = __CIO_R_HEADER;
        return c;
 
    case __CIO_R_HEADER:
        c = MIN(cbChunk, pIO->cb - pIO->ib);
        memcpy(pIO->pb + pIO->ib, pbChunk, c);
        pIO->ib += c;
    init_nodebuffer:
        if ((pIO->cb - pIO->ib) == 0) {
            pb = pIO->pb;
            memcpy(&pIO->pG->Version, pb, 1);
            pb += 1; /* 1 */
            memcpy(&pIO->pG->Endian, pb, 1);
            pb += 1; /* 2 */
            memcpy(&pIO->pG->NodeAttrSize, pb, 4);
            pb += 4; /* 6 */
            memcpy(&pIO->pG->EdgeAttrSize, pb, 4);
            pb += 4; /* 10 */
            memcpy(&pIO->pG->aOpaqueSet, pb, 64);
            pb += 64; /* 74 */
            memcpy(&pIO->pG->nOptions, pb, 4);
            pb += 4; /* 78 */
            memcpy(&pIO->pG->nFamily, pb, 4);
            pb += 4; /* 82 */
            memcpy(&pIO->pG->nnCost, pb, 8);
            pb += 8; /* 90 */
            memcpy(&pIO->pG->cNode, pb, 4);
            pb += 4; /* 94 */
            memcpy(&pIO->pG->cHead, pb, 4);
            pb += 4; /* 98 */
            memcpy(&pIO->pG->cTail, pb, 4);
            pb += 4; /* 102 */
            memcpy(&pIO->pG->cAlone, pb, 4);
            pb += 4; /* 106 */
            memcpy(&pIO->pG->cEdge, pb, 4);
            pb += 4; /* 110 */
            memcpy(&pIO->pG->iNodeBuffer, pb, 4);
            pb += 4; /* 114 */
            memcpy(&pIO->pG->iEdgeBuffer, pb, 4);
            pb += 4; /* 118 */
 
            pIO->fSwap = 0;
#ifdef DGL_ENDIAN_BIG
            if (pIO->pG->Endian == DGL_ENDIAN_LITTLE)
                pIO->fSwap = 1;
#else
            if (pIO->pG->Endian == DGL_ENDIAN_BIG)
                pIO->fSwap = 1;
#endif
            if (pIO->fSwap) {
                dgl_swapInt32Bytes(&pIO->pG->NodeAttrSize);
                dgl_swapInt32Bytes(&pIO->pG->EdgeAttrSize);
                dgl_swapInt32Bytes(&pIO->pG->nOptions);
                dgl_swapInt32Bytes(&pIO->pG->nFamily);
                dgl_swapInt64Bytes(&pIO->pG->nnCost);
                dgl_swapInt32Bytes(&pIO->pG->cNode);
                dgl_swapInt32Bytes(&pIO->pG->cHead);
                dgl_swapInt32Bytes(&pIO->pG->cTail);
                dgl_swapInt32Bytes(&pIO->pG->cAlone);
                dgl_swapInt32Bytes(&pIO->pG->cEdge);
                dgl_swapInt32Bytes(&pIO->pG->iNodeBuffer);
                dgl_swapInt32Bytes(&pIO->pG->iEdgeBuffer);
 
                for (i = 0; i < 16; i++) {
                    dgl_swapInt32Bytes(&pIO->pG->aOpaqueSet[i]);
                }
 
#ifdef DGL_ENDIAN_BIG
                pIO->pG->Endian = DGL_ENDIAN_BIG;
#else
                pIO->pG->Endian = DGL_ENDIAN_LITTLE;
#endif
            }
 
            if (pIO->pG->iNodeBuffer > 0) {
                pIO->pG->pNodeBuffer = malloc(pIO->pG->iNodeBuffer);
                if (pIO->pG->pNodeBuffer == NULL) {
                    return -1;
                }
                pIO->cb = pIO->pG->iNodeBuffer;
                pIO->pb = pIO->pG->pNodeBuffer;
                pIO->ib = 0;
                pIO->nState = __CIO_R_NODEBUFFER;
            }
            else {
                goto init_edgebuffer;
            }
        }
        return c;
    case __CIO_R_NODEBUFFER:
        c = MIN(cbChunk, pIO->cb - pIO->ib);
        memcpy(pIO->pb + pIO->ib, pbChunk, c);
        pIO->ib += c;
    init_edgebuffer:
        if ((pIO->cb - pIO->ib) == 0) {
            if (pIO->pG->iEdgeBuffer > 0) {
                pIO->pG->pEdgeBuffer = malloc(pIO->pG->iEdgeBuffer);
                if (pIO->pG->pEdgeBuffer == NULL) {
                    return -1;
                }
                pIO->cb = pIO->pG->iEdgeBuffer;
                pIO->pb = pIO->pG->pEdgeBuffer;
                pIO->ib = 0;
                pIO->nState = __CIO_R_EDGEBUFFER;
            }
            else {
                pIO->nState = __CIO_END;
            }
        }
        return c;
    case __CIO_R_EDGEBUFFER:
        c = MIN(cbChunk, pIO->cb - pIO->ib);
        memcpy(pIO->pb + pIO->ib, pbChunk, c);
        pIO->ib += c;
        if ((pIO->cb - pIO->ib) == 0) {
            pIO->nState = __CIO_END;
        }
        return c;
    case __CIO_END: {
        /* switch on FLAT bit */
        pIO->pG->Flags |= DGL_GS_FLAT;
 
        /* nodebuffer and edgebuffer are both arrays on 32 bit integer
         * byte order swapping is straightforward
         */
        if (pIO->fSwap && pIO->pG->iNodeBuffer > 0) {
            int in, cn;
            dglInt32_t *pn;
 
            for (cn = pIO->pG->iNodeBuffer / sizeof(dglInt32_t),
                pn = (dglInt32_t *)pIO->pG->pNodeBuffer, in = 0;
                 in < cn; in++) {
                dgl_swapInt32Bytes(&pn[in]);
            }
        }
        if (pIO->fSwap && pIO->pG->iEdgeBuffer > 0) {
            int in, cn;
            dglInt32_t *pn;
 
            for (cn = pIO->pG->iEdgeBuffer / sizeof(dglInt32_t),
                pn = (dglInt32_t *)pIO->pG->pEdgeBuffer, in = 0;
                 in < cn; in++) {
                dgl_swapInt32Bytes(&pn[in]);
            }
        }
    }
        return 0;
    default:
        return 0;
    }
}