vgraph.h

#ifndef _GRAPH_H
#define _GRAPH_H	1

#include	<cdt.h>

typedef struct _grnode_s	Grnode_t;
typedef struct _gredge_s	Gredge_t;
typedef struct _graph_s		Graph_t;
typedef struct _grdisc_s	Grdisc_t;
typedef struct _grdata_s	Grdata_t;
typedef struct _gralgo_s	Gralgo_t;
typedef Grdata_t*		(*Grdata_f)_ARG_((Gralgo_t*, int, Grdata_t*));
typedef int			(*Grevent_f)_ARG_((Graph_t*, int, Void_t*, Grdisc_t*));

struct _grnode_s
{	Dtlink_t	hold;	/* CDT object holder		*/

	Void_t*		label;	/* unique node label		*/

	Gredge_t*	oedge;	/* list of outgoing edges 	*/
	Gredge_t*	iedge;	/* list of incoming edges 	*/
	Gredge_t*	elist;	/* edge list being traversed 	*/

	Grnode_t*	fold;	/* group in union-find struct	*/

	Grnode_t*	link;	/* for temporary link list	*/

	Grdata_t*	data;	/* list of algorithm data	*/
};

struct _gredge_s
{	Dtlink_t	hold;	/* CDT object holder		*/

	Grnode_t*	tail;	/* tail of edge			*/
	Grnode_t*	head;	/* head of edge			*/
	Void_t*		label;	/* (tail,head,label) ids edge	*/

	Gredge_t*	onext;	/* link for node->oedge 	*/
	Gredge_t*	inext;	/* link for node->iedge		*/

	Gredge_t*	link;	/* for temporary link list	*/

	Grdata_t*	data;	/* list of algorithm data	*/
};

struct _graph_s
{	Grdisc_t*	disc;	/* graph discipline		*/

	int		type;	/* directed or undirected	*/

	Dtdisc_t	nddc;	/* CDT discipline for nodes	*/
	Dt_t*		nodes;	/* set of nodes			*/

	Dtdisc_t	eddc;	/* CDT discipline for edges	*/
	Dt_t*		edges;	/* set of edges			*/

	Grdata_t*	data;	/* list of algorithm data	*/
};

struct _grdisc_s
{	ssize_t		nodesz;  /* size to allocate Grnode_t	*/
	ssize_t		edgesz;  /* size to allocate Gredge_t	*/
	ssize_t		graphsz; /* size to allocate Graph_t	*/
	Grevent_f	eventf;	 /* event handling function	*/
};

struct _grdata_s
{	Grdata_t*	next;	/* link list of these		*/
	Gralgo_t*	algo;	/* data is for this algorithm	*/
};

struct _gralgo_s
{	Grdata_f	dataf;	/* to create/delete algo data	*/
	int		type;
};


/* type of graph */
#define GR_DIRECTED	0
#define GR_UNDIRECTED	1


/* discipline events */
#define GR_OPENING	001000
#define GR_CLOSING	002000
#define GR_NODE		000001	/* node operation	*/
#define GR_EDGE		000002	/* edge operation	*/
#define GR_GRAPH	000004	/* graph operation	*/

/* Given s_t a struct type, e_t an element in s_t, and a_d an address of e_t,
** GROFFSETOF returns the offset of e_t in s_t, and
** GRSTRUCTOF returns the address of the struct that contains e_t.
*/
#define GROFFSETOF(_st,_e)	((ssize_t)(&((_st*)0)->_e))
#define GRSTRUCTOF(_st,_e,_a)	(_st*)((unsigned char*)(_a) - GROFFSETOF(_st,_e))

/* to initialize a discipline structure */
#define GRDISC(dc, nsz, esz, gsz, evf) \
		((dc)->nodesz = (nsz), (dc)->edgesz = (esz), \
		 (dc)->graphsz = (gsz), (dc)->eventf = (evf) )

/* big number */
#define GR_INFINITY	((~((unsigned int)0)) >> 1 )

/* for internal use of node,edge,graph types */
#define _Grnode(oo)	((Grnode_t*)(oo))
#define _Gredge(oo)	((Gredge_t*)(oo))
#define _Grgraph(oo)	((Grgraph_t*)(oo))

_BEGIN_EXTERNS_

#if _BLD_vgraph && defined(__EXPORT__)
#define extern	__EXPORT__
#endif

extern Graph_t*		gropen _ARG_((Grdisc_t*, int));
extern int		grclose _ARG_((Graph_t*));
extern int		grrestore _ARG_((Graph_t*));

extern Grnode_t*	grnode _ARG_((Graph_t*, Void_t*, int));
extern Gredge_t*	gredge _ARG_((Graph_t*, Grnode_t*, Grnode_t*, Void_t*, int));

extern Grnode_t*	grfold _ARG_((Grnode_t*, Grnode_t*));
extern Grnode_t*	_grfind _ARG_((Grnode_t*));

extern Grdata_t*	_grdata _ARG_((Grdata_t**, Gralgo_t*, int));

#undef	extern

_END_EXTERNS_

/* return the representative node for a collapsed set of nodes */
#define grfind(nn)	(_Grnode(nn)->fold == _Grnode(nn) ? _Grnode(nn) : _grfind(_Grnode(nn)) )

/* return the data associated with algorithm 'al' for the given object */
#define grdtnode(oo,al) \
	((_Grnode(oo)->data && _Grnode(oo)->data->algo == (al)) ? _Grnode(oo)->data : \
		_grdata(&_Grnode(oo)->data, (al), GR_NODE) )
#define grdtedge(oo,al) \
	((_Gredge(oo)->data && _Gredge(oo)->data->algo == (al)) ? _Gredge(oo)->data : \
		_grdata(&_Gredge(oo)->data, (al), GR_EDGE) )
#define grdtgraph(oo,al) \
	((_Grgraph(oo)->data && _Grgraph(oo)->data->algo == (al)) ? _Grgraph(oo)->data : \
		_grdata(&_Grgraph(oo)->data, (al), GR_GRAPH) )

/* for traversing all adjacent edges */
#define gradjacent(n)	((n)->elist = (n)->oedge)
#define grnextedge(n,e)	((n)->elist == (n)->iedge ? (e)-> inext : \
				((e)->onext ? (e)->onext : ((n)->elist = (n)->iedge)) )

/******************************************************************************
*	Functions germane to the algorithm to compute an optimum branching.
******************************************************************************/
_BEGIN_EXTERNS_

#if _BLD_vgraph && defined(__EXPORT__)
#define extern		extern __EXPORT__
#endif
#if !_BLD_vgraph && defined(__IMPORT__)
#define extern		extern __IMPORT__
#endif

extern Gralgo_t*	Grbranching;

#undef	extern

#if _BLD_vgraph && defined(__EXPORT__)
#define extern	__EXPORT__
#endif

extern ssize_t		grbranching _ARG_((Graph_t*));
extern ssize_t		grbrweight _ARG_((Gredge_t*, ssize_t));

#undef	extern

_END_EXTERNS_

#endif /*_GRAPH_H*/