代码拉取完成,页面将自动刷新
/*------------------------------------------------------------------*//*{{{*/
/* Copyright (C) SSE-USTC, 2014-2015 */
/* */
/* FILE NAME : graph.c */
/* PRINCIPAL AUTHOR : qcLiu */
/* LANGUAGE : C */
/* TARGET ENVIRONMENT : ANY */
/* DATE OF FIRST RELEASE : 2015/02/03 */
/*------------------------------------------------------------------*/
/*
* Revision log:
*//*}}}*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "graph.h"
static void throwException(char* info)
{
printf("Exception: %s\n", info);
exit(0);
}
/*
* Init the Graph.
* @qcliu 2015/02/04
*/
Graph* initGraph(char* name)
{
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->name = name;
graph->vnode = initLinkedList();
graph->visiualize = NULL;
return graph;
}
/*
* Return the count of VNode in the graph.
* @qcliu 2015/02/04
*/
int getVNodeNum(Graph* graph)
{
if (graph == NULL)
throwException("graph is NULL! @ getVNodeNum");
return graph->vnode->length;
}
/*
* Return the sum of the edge in the graph.
* @qcliu 2015/02/04
*/
int getEdgeNum(Graph* graph)
{
if (graph == NULL)
throwException("graph is NULL! @ getEdgeNum");
int edge_count = 0;
LNode* ptr = GETLINK(graph->vnode)->next;
while (ptr != NULL)
{
VNode* vnode = ptr->data;
edge_count += vnode->edge->length;
ptr = ptr->next;
}
return edge_count;
}
/*
* Add new node. The arg data is <T>.
* NOTE: The linkedlist's elements is vnode. So the vnode->data
* is the <T>.
* @qcliu 2015/02/04
*/
int addVNode(Graph* graph, void* data)
{
if (data == NULL || graph == NULL)
throwException("graph is NULL! @addVNode\n");
//first check weather the data is already in the graph->vnode
LNode* ptr = GETLINK(graph->vnode)->next;
int i;
while (ptr != NULL)
{
VNode* vnode = ptr->data;
if (vnode->data == data)
throwException("the data is already in the graph->vnode!! @addVNode");
ptr = ptr->next;
}
VNode* vnode = (VNode*)malloc(sizeof(VNode));
//initVNode
vnode->data = data;
vnode->edge = initLinkedList();
vnode->indegree = 0;
vnode->outdegree = 0;
vnode->prev = initLinkedList();
vnode->succ = initLinkedList();
addLast(graph->vnode, vnode);
return 1;
}
/*
* Find the data<T> from the graph's vnode_list. The return value
* is VNode type.
* @qcliu 2015/02/04
*/
VNode* findVNodeInGraph(Graph* graph, void* data)
{
if (graph == NULL || data == NULL)
throwException("graph is NULL! @findVNodeInGraph");
LNode* ptr = GETLINK(graph->vnode)->next;
while (ptr != NULL)
{
VNode* vnode = ptr->data;
if (vnode->data == data)
return vnode;
ptr = ptr->next;
}
return NULL;
}
/*
* The arg from and to are VNode. Init the edge and add
* the edge to the linkedlist of from's edge.
* @qcliu 2015/02/04
*/
static int addEdge0(Graph* graph, VNode* from, VNode* to)
{
from->outdegree++;
to->indegree++;
//init edge
Edge* edge = (Edge*)malloc(sizeof(Edge));
edge->from = from;
edge->to = to;
//deal with the succ and prev
if (findLNodeinList(from->succ, to) == NULL)
addLast(from->succ, to);
if (findLNodeinList(to->prev, from) == NULL)
addLast(to->prev, from);
return addLast(from->edge, edge);
}
/*
* Add Edge. The arg from and to are <T>. First check weather the
* corresponding VNode exist.
* @qcliu 2015/02/04
*/
int addEdge(Graph* graph, void* from, void* to)
{
VNode* f = findVNodeInGraph(graph, from);
VNode* t = findVNodeInGraph(graph, to);
if (f == NULL || t == NULL)
throwException("from or to is NULL! @addEdge");
return addEdge0(graph, f, t);
}
/*
* This is to delet the vnode in the given graph.
* NOTE: Deal with the edges in the same time.
* @qcliu 2015/02/09
*/
static int removeVNode0(Graph* graph, VNode* vnode)
{
LNode* ptr = GETLINK(vnode->edge)->next;
while (ptr != NULL)
{
Edge* edge = ptr->data;
edge->to->indegree--;
edge->from->outdegree++;
ptr = ptr->next;
}
LNode* prev = GETLINK(vnode->prev)->next;
while (prev != NULL)
{
VNode* prev_node = prev->data;
LNode* prev_edge = GETLINK(prev_node->edge)->next;
while (prev_edge != NULL)
{
Edge* edge = prev_edge->data;
if (edge->to == vnode)
{
removeFromList(prev_node->edge, edge);
}
prev_edge = prev_edge->next;
}
prev = prev->next;
}
return removeFromList(graph->vnode, vnode);
}
/*
* Delet the data<T> in the given graph. First according to the
* given data<T> found the vnode.
* @qcliu 2015/02/09
*/
int removeVNode(Graph* graph, void* data)
{
if (graph == NULL || data == NULL)
throwException("graph is NULL or data is NULL! @removeVNode");
VNode* vnode = findVNodeInGraph(graph, data);
if (!vnode)
throwException("The data is not exist in the graph! @removeVNode");
else
return removeVNode0(graph, vnode);
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。