graph.h

Go to the documentation of this file.

/*
 * 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 tabstop=4
 */

#ifndef _DGL_GRAPH_H_
#define _DGL_GRAPH_H_

#ifdef DGL_STATS
#include <time.h>
#endif

#include "heap.h"
#include "tree.h"

/*
 * Graph State bitmask - returned by dglGet_State() function
 */
#define DGL_GS_FLAT                     0x1     /* otherwise is TREE */

/*
 * Graph Family
 */
#define DGL_GF_COMPLETE         0x1
#define DGL_GF_BIPARTITE        0x2
#define DGL_GF_REGULAR          0x4
#define DGL_GF_BOUQUET          0x8
#define DGL_GF_DIPOLE           0x10
#define DGL_GF_PATH                     0x20
#define DGL_GF_CYCLE            0x40

/*
 * Graph Options
 */
#define DGL_GO_EdgePrioritize_COST      0x10
#define DGL_GO_EdgePrioritize_ATTR      0x20
#define DGL_GO_NodePrioritize_ATTR      0x40


/*
 * Node Status bitmask - returned by dglNodeGet_Status()
 */
#define DGL_NS_HEAD                     0x1     /* node exists as at least one edge's head (static) */
#define DGL_NS_TAIL                     0x2     /* node exists as at least one edge's tail (static) */
#define DGL_NS_ALONE            0x4     /* node is a component */


/*
 * Edge Status bitmask - returned by dglEdgeGet_Status()
 */
#define DGL_ES_DIRECTED         0x1     /* force edge to be directed */


/*
 * Endianess Values - returned by dglGet_Endianess() function
 */
#define DGL_ENDIAN_BIG          1
#define DGL_ENDIAN_LITTLE       2


/*
 * miscellaneous
 */
/* add-edge/add-node flags */
#define DGL_STRONGCONNECT       0x1
#define DGL_ALONE                       0x2
#define DGL_MERGE_EDGE          0x4
/* */



/*
 * Shortest Path clip definitions
 */
typedef struct _dglSPClipInput
{
    dglInt32_t *pnPrevEdge;
    dglInt32_t *pnNodeFrom;
    dglInt32_t *pnEdge;
    dglInt32_t *pnNodeTo;
    dglInt32_t nFromDistance;

} dglSPClipInput_s;

typedef struct _dglSPClipOutput
{
    dglInt32_t nEdgeCost;

} dglSPClipOutput_s;


/*
 * Spanning clip definitions
 */
typedef struct _dglSpanClipInput
{
    dglInt32_t *pnNodeFrom;
    dglInt32_t *pnEdge;
    dglInt32_t *pnNodeTo;

} dglSpanClipInput_s;

typedef struct _dglSpanClipOutput
{
    dglInt32_t *pnReserved;

} dglSpanClipOutput_s;


struct dglGraph;

/*
 * Node Prioritizer
 */
typedef struct
{
    void *pvAVL;
} dglNodePrioritizer_s;

/*
 * Edge Prioritizer
 */
typedef struct
{
    int cEdge;
    int iEdge;
    dglTreeEdgePri32_s *pEdgePri32Item;
    void *pvAVL;
} dglEdgePrioritizer_s;


/*
 * The graph context
 */
typedef struct _dglGraph
{
    int iErrno;

    dglByte_t Version;
    dglByte_t Endian;
    dglInt32_t NodeAttrSize;
    dglInt32_t EdgeAttrSize;
    dglInt32_t aOpaqueSet[16];

    dglInt32_t cNode;
    dglInt32_t cHead;
    dglInt32_t cTail;
    dglInt32_t cAlone;
    dglInt32_t cEdge;
    dglInt64_t nnCost;

    dglInt32_t Flags;
    dglInt32_t nFamily;
    dglInt32_t nOptions;

    void *pNodeTree;
    void *pEdgeTree;
    dglByte_t *pNodeBuffer;
    dglInt32_t iNodeBuffer;
    dglByte_t *pEdgeBuffer;
    dglInt32_t iEdgeBuffer;


    dglEdgePrioritizer_s edgePrioritizer;
    dglNodePrioritizer_s nodePrioritizer;


    /* so far statistics are only computed by dglAddEdge() */
#ifdef DGL_STATS
    clock_t clkAddEdge;         /* cycles spent during the last addedge execution */
    int cAddEdge;               /* # of calls to dglAddEdge() */
    clock_t clkNodeTree;        /* cycles spent in accessing the node binary tree */
    int cNodeTree;              /* # of probes in the node tree */
#endif
}
dglGraph_s;

/*
 * Shortest Path clip function type
 */
typedef int (*dglSPClip_fn) (dglGraph_s *, dglSPClipInput_s *,
                             dglSPClipOutput_s *, void *);

/*
 * Spanning clip function type
 */
typedef int (*dglSpanClip_fn) (dglGraph_s *, dglGraph_s *,
                               dglSpanClipInput_s *, dglSpanClipOutput_s *,
                               void *);

/*
 * An ARC defined as : from-node, to-node, edge pointer, to-node-distance (from the path starting node)
 */
typedef struct _dglSPArc
{
    dglInt32_t nFrom;
    dglInt32_t nTo;
    dglInt32_t *pnEdge;
    dglInt32_t nDistance;
}
dglSPArc_s;

/*
 * Shortest Path Report
 */
typedef struct _dglSPReport
{
    dglInt32_t nStartNode;
    dglInt32_t nDestinationNode;
    dglInt32_t nDistance;
    dglInt32_t cArc;
    dglSPArc_s *pArc;
}
dglSPReport_s;

/*
 * Shortest Path Cache
 */
typedef struct
{
    dglInt32_t nStartNode;
    dglHeap_s NodeHeap;
    void *pvVisited;
    void *pvPredist;
}
dglSPCache_s;

/*
 * Node Traverser
 */
typedef struct
{
    dglGraph_s *pGraph;
    void *pvAVLT;
    dglInt32_t *pnNode;
} dglNodeTraverser_s;

/*
 * Edgeset Traverser
 */
typedef struct
{
    dglGraph_s *pGraph;
    dglInt32_t *pnEdgeset;
    void *pvCurrentItem;
    int cEdge, iEdge;
} dglEdgesetTraverser_s;

/*
 * Edge Traverser
 */
typedef struct
{
    dglGraph_s *pGraph;
    void *pvAVLT;
    dglInt32_t *pnEdge;
    dglEdgePrioritizer_s *pEdgePrioritizer;
} dglEdgeTraverser_s;


/*
 * Error codes returned by dglError
 */
#define DGL_ERR_BadVersion                              1
#define DGL_ERR_BadNodeType                     2
#define DGL_ERR_MemoryExhausted                 3
#define DGL_ERR_HeapError                               4
#define DGL_ERR_UndefinedMethod                 5
#define DGL_ERR_Write                                   6
#define DGL_ERR_Read                                    7
#define DGL_ERR_NotSupported                    8
#define DGL_ERR_UnknownByteOrder                9
#define DGL_ERR_HeadNodeNotFound                10
#define DGL_ERR_TailNodeNotFound                11
#define DGL_ERR_BadEdge                                 12
#define DGL_ERR_BadOnFlatGraph                  13
#define DGL_ERR_BadOnTreeGraph                  14
#define DGL_ERR_NodeNotFound                    15
#define DGL_ERR_TreeSearchError                 16
#define DGL_ERR_UnexpectedNullPointer   17
#define DGL_ERR_VersionNotSupported             18
#define DGL_ERR_EdgeNotFound                    19
#define DGL_ERR_NodeAlreadyExist                20
#define DGL_ERR_NodeIsAComponent                21
#define DGL_ERR_EdgeAlreadyExist                22
#define DGL_ERR_BadArgument                             23



/*
 * graph context management
 */
int dglInitialize(dglGraph_s * pGraph, dglByte_t Version,
                  dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize,
                  dglInt32_t * pOpaqueSet);
int dglRelease(dglGraph_s * pGraph);
int dglUnflatten(dglGraph_s * pGraph);
int dglFlatten(dglGraph_s * pGraph);
void dglResetStats(dglGraph_s * pgraph);

/*
 * node management
 */
dglInt32_t *dglGetNode(dglGraph_s * pGraph, dglInt32_t nNodeId);
int dglAddNode(dglGraph_s * pGraph,
               dglInt32_t nNodeId, void *pvNodeAttr, dglInt32_t nFlags);
int dglDelNode(dglGraph_s * pGraph, dglInt32_t nNodeId);
dglInt32_t dglNodeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnNode);
dglInt32_t *dglNodeGet_OutEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode);
dglInt32_t *dglNodeGet_InEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode);
dglInt32_t dglNodeGet_Status(dglGraph_s * pGraph, dglInt32_t * pnNode);
dglInt32_t *dglNodeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode);
void dglNodeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode,
                     dglInt32_t * pnAttr);
int dglNodeGet_InDegree(dglGraph_s * pGraph, dglInt32_t * pnNode);
int dglNodeGet_OutDegree(dglGraph_s * pGraph, dglInt32_t * pnNode);
int dglNodeGet_Valence(dglGraph_s * pGraph, dglInt32_t * pnNode);

/*
 * edge management
 */
dglInt32_t dglEdgesetGet_EdgeCount(dglGraph_s * pGraph,
                                   dglInt32_t * pnOutEdgeset);

dglInt32_t dglEdgeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnEdge);
dglInt32_t dglEdgeGet_Cost(dglGraph_s * pGraph, dglInt32_t * pnEdge);
dglInt32_t *dglEdgeGet_Head(dglGraph_s * pGraph, dglInt32_t * pnEdge);
dglInt32_t *dglEdgeGet_Tail(dglGraph_s * pGraph, dglInt32_t * pnEdge);
dglInt32_t *dglEdgeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnEdge);
int dglEdgeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnAttr,
                    dglInt32_t * pnEdge);

dglInt32_t *dglGetEdge(dglGraph_s * pGraph, dglInt32_t nEdgeId);

int dglDelEdge(dglGraph_s * pGraph, dglInt32_t nEdgeId);

int dglAddEdge(dglGraph_s * pGraph,
               dglInt32_t nHead,
               dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge);

int dglAddEdgeX(dglGraph_s * pGraph,
                dglInt32_t nHead,
                dglInt32_t nTail,
                dglInt32_t nCost,
                dglInt32_t nEdge,
                void *pvFnodeAttr,
                void *pvTnodeAttr, void *pvEdgeAttr, dglInt32_t nFlags);


/*
 * graph I/O
 */
int dglWrite(dglGraph_s * pGraph, int fd);
int dglRead(dglGraph_s * pGraph, int fd);

typedef struct
{
    dglGraph_s *pG;
    int nState;
    int fSwap;
    int cb;
    int ib;
    unsigned char *pb;
    unsigned char ab[118];      /* 118 = graph header size */
} dglIOContext_s;

int dglIOContextInitialize(dglGraph_s *, dglIOContext_s *);
void dglIOContextRelease(dglIOContext_s *);

/*
 * Chunked Write callback function type
 */
typedef int (*dglWriteChunk_fn) (dglGraph_s *, unsigned char *pbChunk,
                                 int cbChunk, void *pvArg);

int dglWriteChunk(dglIOContext_s *, dglWriteChunk_fn, void *pvArg);
int dglReadChunk(dglIOContext_s *, dglByte_t * pbChunk, int cbChunk);



/*
 * Algorithms
 */
int dglShortestPath(dglGraph_s * pGraph,
                    dglSPReport_s ** ppReport,
                    dglInt32_t nStartNode,
                    dglInt32_t nDestinationNode,
                    dglSPClip_fn fnClip,
                    void *pvClipArg, dglSPCache_s * pCache);
int dglShortestPathGraph(dglGraph_s * pGraph,
                         dglGraph_s * pGraphOut,
                         dglInt32_t nStartNode,
                         dglInt32_t nDestinationNode,
                         dglSPClip_fn fnClip,
                         void *pvClipArg, dglSPCache_s * pCache);
int dglShortestDistance(dglGraph_s * pGraph,
                        dglInt32_t * pnDistance,
                        dglInt32_t nStartNode,
                        dglInt32_t nDestinationNode,
                        dglSPClip_fn fnClip,
                        void *pvClipArg, dglSPCache_s * pCache);
int dglShortestDistanceGraph(dglGraph_s * pGraph,
                             dglGraph_s * pGraphOut,
                             dglInt32_t nStartNode,
                             dglInt32_t nDestinationNode,
                             dglSPClip_fn fnClip,
                             void *pvClipArg, dglSPCache_s * pCache);

int dglInitializeSPCache(dglGraph_s * pgraph, dglSPCache_s * pCache);
void dglReleaseSPCache(dglGraph_s * pgraph, dglSPCache_s * pCache);
void dglFreeSPReport(dglGraph_s * pGraph, dglSPReport_s * pSPReport);

int dglDepthSpanning(dglGraph_s * pgraphInput,
                     dglGraph_s * pgraphOutput,
                     dglInt32_t nVertexNode,
                     dglSpanClip_fn fnClip, void *pvClipArg);

int dglDepthComponents(dglGraph_s * pgraphInput,
                       dglGraph_s * pgraphComponents,
                       int cgraphComponents,
                       dglSpanClip_fn fnClip, void *pvClipArg);

int dglMinimumSpanning(dglGraph_s * pgraphInput,
                       dglGraph_s * pgraphOutput,
                       dglInt32_t nVertexNode,
                       dglSpanClip_fn fnClip, void *pvClipArg);

/*
 * error management
 */
int dglErrno(dglGraph_s * pgraph);
char *dglStrerror(dglGraph_s * pgraph);

/*
 * graph property hiders
 */
int dglGet_Version(dglGraph_s * pGraph);
void dglSet_Version(dglGraph_s * pGraph, int Version);
int dglGet_Endianess(dglGraph_s * pGraph);
int dglGet_NodeAttrSize(dglGraph_s * pGraph);
int dglGet_EdgeAttrSize(dglGraph_s * pGraph);
int dglGet_NodeCount(dglGraph_s * pGraph);
int dglGet_HeadNodeCount(dglGraph_s * pGraph);
int dglGet_TailNodeCount(dglGraph_s * pGraph);
int dglGet_AloneNodeCount(dglGraph_s * pGraph);
int dglGet_EdgeCount(dglGraph_s * pGraph);
int dglGet_State(dglGraph_s * pGraph);
dglInt32_t *dglGet_Opaque(dglGraph_s * pGraph);
void dglSet_Opaque(dglGraph_s * pGraph, dglInt32_t * pOpaque);
int dglGet_NodeSize(dglGraph_s * pGraph);
int dglGet_EdgeSize(dglGraph_s * pGraph);
dglInt64_t dglGet_Cost(dglGraph_s * pGraph);
void dglSet_Cost(dglGraph_s * pGraph, dglInt64_t nnCost);
dglInt32_t dglGet_Family(dglGraph_s * pGraph);
void dglSet_Family(dglGraph_s * pGraph, dglInt32_t nFamily);
dglInt32_t dglGet_Options(dglGraph_s * pGraph);
void dglSet_Options(dglGraph_s * pGraph, dglInt32_t nOptions);
dglEdgePrioritizer_s *dglGet_EdgePrioritizer(dglGraph_s * pGraph);
dglNodePrioritizer_s *dglGet_NodePrioritizer(dglGraph_s * pGraph);


/*
 * node traverser
 */
int dglNode_T_Initialize(dglNodeTraverser_s * pTraverser,
                         dglGraph_s * pGraph);
void dglNode_T_Release(dglNodeTraverser_s * pTraverser);
dglInt32_t *dglNode_T_First(dglNodeTraverser_s * pTraverser);
dglInt32_t *dglNode_T_Last(dglNodeTraverser_s * pTraverser);
dglInt32_t *dglNode_T_Next(dglNodeTraverser_s * pTraverser);
dglInt32_t *dglNode_T_Prev(dglNodeTraverser_s * pTraverser);
dglInt32_t *dglNode_T_Find(dglNodeTraverser_s * pTraverser,
                           dglInt32_t nNodeId);


/*
 * edgeset traverser
 */
int dglEdgeset_T_Initialize(dglEdgesetTraverser_s * pTraverser,
                            dglGraph_s * pGraph, dglInt32_t * pnEdgeset);
void dglEdgeset_T_Release(dglEdgesetTraverser_s * pTraverser);
dglInt32_t *dglEdgeset_T_First(dglEdgesetTraverser_s * pTraverser);
dglInt32_t *dglEdgeset_T_Next(dglEdgesetTraverser_s * pTraverser);


/*
 * edge traverser
 */
int dglEdge_T_Initialize(dglEdgeTraverser_s * pTraverser,
                         dglGraph_s * pGraph,
                         dglEdgePrioritizer_s * pEdgePrioritizer);
void dglEdge_T_Release(dglEdgeTraverser_s * pTraverser);
dglInt32_t *dglEdge_T_First(dglEdgeTraverser_s * pTraverser);
dglInt32_t *dglEdge_T_Next(dglEdgeTraverser_s * pTraverser);

#endif