graph.c

#include	"grhdr.h"

/******************************************************************************
	This defines a collection of basic operations on directed graphs.
	Written by Kiem-Phong Vo (02/01/2006).
******************************************************************************/

/* CDT discipline for nodeset */
static int nodecmp(Dt_t* nodes, Void_t* one, Void_t* two, Dtdisc_t* disc)
{
	Grnode_t	*n1 = (Grnode_t*)one;
	Grnode_t	*n2 = (Grnode_t*)two;

	if(n1->label != n2->label)
		return n1->label < n2->label ? -1 : 1;
	else	return  0;
}

static void nodefree(Dt_t* nodes, Void_t* node, Dtdisc_t* disc)
{
	Graph_t		*gr = GRSTRUCTOF(Graph_t, nddc, disc);
	Grdata_t	*dt, *next;

	if(node)
	{	if(gr->disc && gr->disc->eventf)
			(*gr->disc->eventf)(gr, GR_NODE|GR_CLOSING, node, gr->disc );

		for(dt = ((Grnode_t*)node)->data; dt; dt = next)
		{	next = dt->next;
			(*dt->algo->dataf)(dt->algo, GR_NODE|GR_CLOSING, dt);
		}

		free(node);
	}
}

/* CDT discipline for edgeset */
static int edgecmp(Dt_t* edges, Void_t* one, Void_t* two, Dtdisc_t* disc)
{
	Gredge_t	*e1 = (Gredge_t*)one;
	Gredge_t	*e2 = (Gredge_t*)two;

	if(e1->tail != e2->tail)
		return e1->tail < e2->tail ? -1 : 1;
	else if(e1->head != e2->head)
		return e1->head < e2->head ? -1 : 1;
	else if(e1->label != e2->label )
		return e1->label < e2->label ? -1 : 1;
	else	return 0;
}

static void edgefree(Dt_t* edges, Void_t* edge, Dtdisc_t* disc)
{
	Graph_t		*gr = GRSTRUCTOF(Graph_t, eddc, disc);
	Grdata_t	*dt, *next;

	if(edge)
	{	if(gr->disc && gr->disc->eventf)
			(*gr->disc->eventf)(gr, GR_EDGE|GR_CLOSING, edge, gr->disc );

		for(dt = ((Gredge_t*)edge)->data; dt; dt = next)
		{	next = dt->next;
			(*dt->algo->dataf)(dt->algo, GR_EDGE|GR_CLOSING, dt);
		}

		free(edge);
	}
}

/* function to find/create/delete nodes */
Grnode_t* grnode(Graph_t* gr, Void_t* label, int type)
{
	Grnode_t	node, *nd;
	Gredge_t	*e, *enext;
	ssize_t		sz;

	if(!gr)
		return NIL(Grnode_t*);

	/* see if the node already exists */
	node.label = label;
	nd = dtsearch(gr->nodes, &node);

	if(type < 0) /* deleting a node */
	{	if(nd)
		{	for(e = nd->oedge; e; e = enext)
			{	enext = e;
				gredge(gr, e->tail, e->head, e->label, -1);
			}
			for(e = nd->iedge; e; e = enext)
			{	enext = e;
				gredge(gr, e->tail, e->head, e->label, -1);
			}
			dtdelete(gr->nodes, nd);
		}
		return NIL(Grnode_t*);
	}

	if(type == 0 || nd) /* finding only or inserting an existing node */
		return nd;

	/* making a new node */
	if((sz = gr->disc ? gr->disc->nodesz : 0) < sizeof(Grnode_t) )
		sz = sizeof(Grnode_t);
	if(!(nd = (Grnode_t*)calloc(1, sz)) )
		return NIL(Grnode_t*);

	nd->label = label;
	nd->fold = nd;

	if(gr->disc && gr->disc->eventf)
		(*gr->disc->eventf)(gr, GR_NODE|GR_OPENING, nd, gr->disc);

	return (Grnode_t*)dtinsert(gr->nodes, nd);
}

/* function to find/create/delete edges */
Gredge_t* gredge(Graph_t* gr, Grnode_t* tail, Grnode_t* head, Void_t* label, int type)
{
	Gredge_t	edge, *ed, *e, *pe;
	Grnode_t	*nd;
	ssize_t		sz;

	if(gr->type == GR_UNDIRECTED) /* enforce tail <= head */
		if(tail > head)
			{ nd = tail; tail = head; head = nd; }

	if(!(edge.tail = tail) || !(edge.head = head) )
		return NIL(Gredge_t*);

	/* see if the edge exists */
	edge.label = label;
	ed = dtsearch(gr->edges, &edge);

	if(type < 0) /* deleting */
	{	if(ed)
		{	for(pe = NIL(Gredge_t*), e = ed->tail->oedge; e; pe = e, e = e->onext)
			{	if(e == ed)
				{	if(pe)
						pe->onext = e->onext;
					else	ed->tail->oedge->onext = e->onext;
					break;
				}
			}
			for(pe = NIL(Gredge_t*), e = ed->head->iedge; e; pe = e, e = e->inext)
			{	if(e == ed)
				{	if(pe)
						pe->inext = e->inext;
					else	ed->head->iedge->inext = e->inext;
					break;
				}
			}

			dtdelete(gr->edges, ed);
		}
		return NIL(Gredge_t*);
	}

	if(type == 0 || ed) /* only searching or edge already exists */
		return ed;

	if((sz = gr->disc ? gr->disc->edgesz : 0) < sizeof(Gredge_t))
		sz = sizeof(Gredge_t);
	if(!(ed = (Gredge_t*)calloc(1, sz)) )
		return NIL(Gredge_t*);

	ed->label = label;
	ed->tail  = edge.tail;
	ed->head  = edge.head;
	ed->inext = edge.head->iedge; edge.head->iedge = ed;
	ed->onext = edge.tail->oedge; edge.tail->oedge = ed;

	if(gr->disc && gr->disc->eventf)
		(*gr->disc->eventf)(gr, GR_EDGE|GR_OPENING, ed, gr->disc);

	return (Gredge_t*)dtinsert(gr->edges, ed);
}

/* contruct/return the data associated with an algorithm */
Grdata_t* _grdata(Grdata_t** data, Gralgo_t* algo, int type)
{
	Grdata_t	*dt, *pd;

	if(type != GR_NODE && type != GR_EDGE && type != GR_GRAPH)
		return NIL(Grdata_t*);

	for(pd = NIL(Grdata_t*), dt = *data; dt; pd = dt, dt = dt->next)
		if(dt->algo == algo)
			break;
	if(pd && dt) /* isolate from list */
		pd->next = dt->next;
	else if(dt)
		*data = dt->next;
	else if(!(dt = (*algo->dataf)(algo, type|GR_OPENING, 0)) )
		return NIL(Grdata_t*);
	else	dt->algo = algo; /* set the algorithm that made this data */

	/* put this at front of list for fast future accesses */
	dt->next = *data; *data = dt;

	return dt;
}

/* restore a graph after manipulation of nodes and edges */
int grrestore(Graph_t* gr)
{
	Grnode_t	*nd;
	Gredge_t	*ed;

	for(nd = (Grnode_t*)dtflatten(gr->nodes); nd; nd = (Grnode_t*)dtlink(gr,nd))
	{	nd->oedge = nd->iedge = NIL(Gredge_t*);
		nd->fold = nd;
		nd->link = NIL(Grnode_t*);
	}
	for(ed = (Gredge_t*)dtflatten(gr->edges); ed; ed = (Gredge_t*)dtlink(gr,ed))
	{	ed->onext = ed->tail->oedge; ed->tail->oedge = ed;
		ed->inext = ed->head->iedge; ed->head->iedge = ed;
		ed->link = NIL(Gredge_t*);
	}

	return 0;
}

/* functions to open/close a graph structure */
int grclose(Graph_t* gr)
{	
	Grdata_t	*dt, *next;

	if(!gr)
		return -1;

	if(gr->disc && gr->disc->eventf )
		if((*gr->disc->eventf)(gr, GR_GRAPH|GR_CLOSING, 0, gr->disc) < 0)
			return -1;

	if(gr->nodes)
		dtclose(gr->nodes);
	if(gr->edges)
		dtclose(gr->edges);

	for(dt = gr->data; dt; dt = next)
	{	next = dt->next;
		(*dt->algo->dataf)(dt->algo, GR_GRAPH|GR_CLOSING, dt);
	}

	free(gr);
	return 0;
}

Graph_t* gropen(Grdisc_t* disc, int type)
{
	Graph_t	*gr;
	ssize_t	sz;

	if((sz = disc ? disc->graphsz : 0) < sizeof(Graph_t) )
		sz = sizeof(Graph_t);
	if(!(gr = (Graph_t*)calloc(1,sz)) )
		return NIL(Graph_t*);

	gr->type = type;

	DTDISC(&gr->nddc, 0, 0, 0, 0, nodefree, nodecmp, 0, 0, 0);
	DTDISC(&gr->eddc, 0, 0, 0, 0, edgefree, edgecmp, 0, 0, 0);

	if(!(gr->nodes = dtopen(&gr->nddc, Dtoset)) ||
	   !(gr->edges = dtopen(&gr->eddc, Dtoset)) )
	{	grclose(gr);
		return NIL(Graph_t*);
	}

	if((gr->disc = disc) && (*gr->disc->eventf)(gr, GR_GRAPH|GR_OPENING, 0, gr->disc) < 0)
	{	grclose(gr);
		return NIL(Graph_t*);
	}

	return gr;
}