graph.c

C/C++ 多任务下的数据结构与算法 （周伟明）华中科技大学出版社

/*
 * Copyright (c) 2006-2008
 * Author: Weiming Zhou
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  
 */

#include <windows.h>
#include "CapiGlobal.h"
#include "SingleList.h"
#include "Graph.h"


/**	比较两个指针大小的函数

    @param	void *p1 - 要比较的指针1	
    @param	void *p2 - 要比较的指针2
    @return	INT - 0表示相等，1表示p1>p2, -1表示p1<p2	
*/
INT PointerCompare(void *p1, void *p2)
{
    if ( p1 == p2 )
    {
        return 0;
    }
    else if ( (INT)p1 < (INT)p2 )
    {
        return -1;
    }
    else
    {
        return 1;
    }
}


/**	图的节点创建函数

    @return	GRAPHNODE * - 成功返回创建的图节点指针，失败返回NULL。	
*/
GRAPHNODE * GraphNode_New()
{
    LPGRAPHNODE     pNewNode;
    pNewNode    = (GRAPHNODE *)malloc(sizeof(GRAPHNODE));
    if ( !pNewNode )
    {
        return NULL;
    }
    pNewNode->pProperties = NULL;
    pNewNode->pMagic = NULL;
    pNewNode->nMagic = -1;
    pNewNode->pEdgeList = SingleList_Create();
    if ( NULL == pNewNode->pEdgeList )
    {
        free( pNewNode );
        return NULL;
    }
    return pNewNode;
}


/**	图的节点释放函数

    @param	LPGRAPHNODE pGraphNode - 图节点指针	
    @param	DESTROYFUNC GraphNodePropDestroyFunc - 图节点属性释放函数	
    @return	void - 无	
*/
void GraphNode_Destroy(LPGRAPHNODE pGraphNode,
                  DESTROYFUNC GraphNodePropDestroyFunc )
{
    if ( NULL == pGraphNode )
    {
        return;
    }

    if ( pGraphNode->pProperties )
    {
        if ( GraphNodePropDestroyFunc )
        {
            (*GraphNodePropDestroyFunc)(pGraphNode->pProperties);
        }
    }

    if ( pGraphNode->pEdgeList != NULL ) 
    {
        /* 这里不需要释放数据, 因为边在另外链表中有保存 */
        SingleList_Destroy(pGraphNode->pEdgeList, NULL);
    }

    free(pGraphNode);
}


/**	图节点的添加边函数

    @param	LPGRAPHNODE pGraphNode - 图节点指针
    @param	LPEDGE pEdge - 边指针	
    @return	INT - CAPI_SUCCESS表示成功，CAPI_FAILED表示失败。	
*/
INT GraphNode_AddEdge(LPGRAPHNODE pGraphNode, LPEDGE pEdge)
{
    if ( NULL == pGraphNode )
    {
        return CAPI_FAILED;
    }

    if ( NULL == pEdge )
    {
        return CAPI_FAILED;
    }

    return SingleList_InsertTail(pGraphNode->pEdgeList, pEdge);
}


/**	图节点的删除边函数

    @param	LPGRAPHNODE pGraphNode - 图节点指针	
    @param	LPEDGE  pEdge - 边指针	
    @param	DESTROYFUNC EdgePropDestroyFunc - 边属性释放函数	
    @return	INT - CAPI_FAILED表示失败，CAPI_SUCCESS表示成功。	
*/
INT GraphNode_RemoveEdge(LPGRAPHNODE pGraphNode, 
                             LPEDGE  pEdge,
                             DESTROYFUNC EdgePropDestroyFunc)
{
    if ( NULL == pGraphNode )
    {
        return CAPI_FAILED;
    }

    if ( NULL == pEdge )
    {
        return CAPI_FAILED;
    }

    if ( pGraphNode->pEdgeList == NULL ) {
        return CAPI_FAILED;
    }

    return SingleList_Delete(pGraphNode->pEdgeList, pEdge, 
        PointerCompare, EdgePropDestroyFunc);

}


/**	边的创建函数

    @return	EDGE * - 成功返回创建的边指针，失败返回NULL。	
*/
EDGE * Edge_New()
{
    LPEDGE     pEdge;
     
    pEdge = (LPEDGE)malloc( sizeof(EDGE) );
    if ( NULL != pEdge )
    {
        pEdge->distance = 0;
        pEdge->pProperties = NULL;
        pEdge->nMagic = -1;
        pEdge->pNode1 = NULL;
        pEdge->pNode2 = NULL;
    }
    return pEdge;
}


/**	边的释放函数

    @param	LPEDGE pEdge - 边指针
    @param	DESTROYFUNC EdgePropDestroyFunc - 边属性释放函数	
    @return	void - 无	
*/
void Edge_Destroy(LPEDGE pEdge,
                  DESTROYFUNC EdgePropDestroyFunc)
{
    if ( NULL == pEdge )
    {
        return;
    }
    if ( pEdge->pProperties )
    {
        if ( EdgePropDestroyFunc )
        {
            (*EdgePropDestroyFunc)(pEdge->pProperties);
        }
    }
    free(pEdge);
    pEdge = NULL;
}


/**	图的创建函数

    @param	INT nNodeCount - 要创建的图的最大节点数量	
    @return	GRAPH * - 称工返回创建的图指针，失败返回NULL。	
*/
GRAPH * Graph_New(INT nNodeCount)
{
    GRAPH   *pGraph;

    if ( nNodeCount <= 0 )
    {
        return NULL;
    }

    pGraph = (GRAPH *)malloc(sizeof(GRAPH));
    if ( NULL == pGraph )
    {
        return NULL;
    }
    pGraph->nNodeCount = nNodeCount;
    pGraph->ppNodeArray = (GRAPHNODE **)malloc(nNodeCount * sizeof(GRAPHNODE *));
    if ( pGraph->ppNodeArray)
    {
        memset(pGraph->ppNodeArray, 0, nNodeCount * sizeof(GRAPHNODE *) );
        pGraph->pProperties = NULL;
        pGraph->pEdgeList = SingleList_Create();
        if ( NULL == pGraph->pEdgeList )
        {
            free(pGraph->ppNodeArray);
            free(pGraph);
            pGraph = NULL;
        }
    }
    else
    {
        free(pGraph);
        pGraph = NULL;
    }

    return pGraph;
}


/**	图的释放函数

    @param	LPGRAPH pGraph - 图的指针	
    @param	DESTROYFUNC GraphPropDestroyFunc - 图的属性释放函数	
    @param	DESTROYFUNC GraphNodePropDestroyFunc - 图的属性释放函数	
    @param	DESTROYFUNC EdgePropDestroyFunc - 边的属性释放函数	
    @return	void - 无	
*/
void Graph_Destroy(LPGRAPH pGraph,
                   DESTROYFUNC GraphPropDestroyFunc,
                   DESTROYFUNC GraphNodePropDestroyFunc,
                   DESTROYFUNC EdgePropDestroyFunc)
{
    if ( pGraph )
    {
        if ( pGraph->ppNodeArray )
        {
            INT i;
            for ( i = 0; i < pGraph->nNodeCount; i++ )
            {
                if ( pGraph->ppNodeArray[i] != NULL )
                {
                    GraphNode_Destroy(pGraph->ppNodeArray[i], 
                        GraphNodePropDestroyFunc );
                    pGraph->ppNodeArray[i] = NULL;
                }
            }
            free( pGraph->ppNodeArray );
            pGraph->ppNodeArray = NULL;
        }
        if ( pGraph->pProperties )
        {
            if ( GraphPropDestroyFunc )
            {
                (*GraphPropDestroyFunc)(pGraph->pProperties);
            }
            pGraph->pProperties = NULL;
        }

        if ( pGraph->pEdgeList )
        {
            SINGLENODE  *pNode;
            pNode = pGraph->pEdgeList->pHead;
            while ( pNode != NULL ) 
            {
                SINGLENODE	*pFreeNode;
                
                /* reset the pointers here so we don't lose them */
                pFreeNode = pNode;
                pNode = pNode->pNext;
                
                /* do data-specific purge. */
                Edge_Destroy( pFreeNode->pData, EdgePropDestroyFunc );
                
                /* free memory */
                free( pFreeNode );
            }
            free( pGraph->pEdgeList );
            pGraph->pEdgeList = NULL;
        }

        free(pGraph);
        pGraph = NULL;
    }
}


/**	获取指定图的顶点个数

    @param	GRAPH *pGraph -图的指针	
    @return	INT -成功图的顶点个数, 失败返回-1.
*/
INT Graph_GetNodeCount(GRAPH *pGraph)
{
    if ( NULL == pGraph )
    {
        return -1;
    }
    return pGraph->nNodeCount;
}


/**	获取指定图的边的数量

    @param	GRAPH *pGraph -图的指针	
    @return	INT -成功返回图的边的数量, 失败返回-1.	
*/
INT Graph_GetEdgeCount(GRAPH *pGraph)
{
    INT     nEdgeCount;

    nEdgeCount = 0;
    if ( NULL == pGraph )
    {
        return -1;
    }
    
    nEdgeCount = pGraph->pEdgeList->uCount;

    return nEdgeCount;
}

/**	计算图中两个节点间的最短路径函数
        计算完后，每个节点的pMagic用来存放到源节点最短路径的下一个节点指针
        nMagic用来存放到源节点的最短路径的总距离

    @param	LPGRAPH pGraph - 要计算的图	
    @param	LPGRAPHNODE pSrcNode - 源节点	
    @param	LPGRAPHNODE pTagNode - 目标节点	
    @return	DISTANCE - GRAPH_ERROR 表示参数错误
                           GRAPH_NOT_PATH 表示没有路径
                           成功时返回两点间最短路径的总距离