Data Structures
struct	EGeUgraph_t
	structure that holds all graph related structures needed to define a directed graph, and to allow modifications over it. More...
struct	EGeUgraphEdge_t
	structure that hold all edge related structures needed to define a directed graph, and add/delete/modify it's structure More...
struct	EGeUgraphEP_t
	Structure for endpoints of edges. More...
struct	EGeUgraphNode_t
	structure that hold all node related structures needed to define a graph, and add/delete/modify it's structure More...
struct	my_uedge_t
	example of an edge structure using the embeded substructures. More...
struct	my_ugraph_t
	example of a graph structure using the embeded substructures. More...
struct	my_unode_t
	example of a node structure using the embeded substructures. More...
Files
file	eg_eugraph.ex.c
file	eg_eugraph.h
Defines
#define	EGeUgraphAddEdge(__Gpt, __headpt, __tailpt, __ept)
	Add an edge to a graph.
#define	EGeUgraphAddNode(__Gpt, __v)
	Add a node to the graph.
#define	EGeUgraphChangeEP(__Gpt, __ept, __tailpt, __eptype)
	Change an endpoint of an edge.
#define	EGeUgraphChangeHead(__Gpt, __ept, __headpt) EGeUgraphChangeEP(__Gpt,__ept,__headpt,1)
	Change the head of an edge.
#define	EGeUgraphChangeTail(__Gpt, __ept, __tailpt) EGeUgraphChangeEP(__Gpt,__ept,__tailpt,0)
	Change the tail of an edge.
#define	EGeUgraphClear(__Gpt) ;
	Clear the structure so that we can free it (without memory leaks). Note that this macro does nothing, because it is always safe to free this structure.
#define	EGeUgraphDelEdge(__Gpt, __ept)
	Delete an edge from a graph.
#define	EGeUgraphDelNode(__Gpt, __v)
	Remove a node from a graph.
#define	EGeUgraphEdgeClear(__Gpt) ;
	Clear the structure so that we can free it (without memory leaks). Note that this macro does nothing, because it is always safe to free this structure.
#define	EGeUgraphEdgeInit(__ept) *(__ept) = (EGeUgraphEdge_t){{(EGeUgraphEP_t){(EGeList_t){0,0},0,0},(EGeUgraphEP_t){(EGeList_t){0,0},0,1}}};
	Initialize an edge as an empty edge, non attached to any graph.
#define	EGeUgraphGetAdjEdge(__edge_cn)
	Given the adjacency list connector of an edge, return the pointer to the internal edge.
#define	EGeUgraphInit(__Gpt)
	Initialize a graph structure as an empty graph with no members.
#define	EGeUgraphNodeClear(__Gpt) ;
	Clear the structure so that we can free it (without memory leaks). Note that this macro does nothing, because it is always safe to free this structure.
#define	EGeUgraphNodeInit(__v)
	Initialize a node as an empty non-attached node.
Typedefs
typedef struct EGeUgraph_t	EGeUgraph_t
	structure that holds all graph related structures needed to define a directed graph, and to allow modifications over it.
typedef struct EGeUgraphEdge_t	EGeUgraphEdge_t
	structure that hold all edge related structures needed to define a directed graph, and add/delete/modify it's structure
typedef struct EGeUgraphEP_t	EGeUgraphEP_t
	Structure for endpoints of edges.
typedef struct EGeUgraphNode_t	EGeUgraphNode_t
	structure that hold all node related structures needed to define a graph, and add/delete/modify it's structure
typedef struct my_uedge_t	my_uedge_t
	example of an edge structure using the embeded substructures.
typedef struct my_ugraph_t	my_ugraph_t
	example of a graph structure using the embeded substructures.
typedef struct my_unode_t	my_unode_t
	example of a node structure using the embeded substructures.
Functions
static void	display_UG (my_ugraph_t *myG)
	Display the contents of our graph structure.
int	main (void)
	A simple example of a directed graph using (EGdEgraph) structures.

Detailed Description

Here we define a basic directed graph structure, it holds the number of nodes and edges in the graph, as well as the in and out degree of all nodes, and allow to access the head and tail of any edge. The spirit of this implementation is to use embeded sub-structures rather than pointers to sub-structures, much in the spirit of the Linux Kernel List implementation. Wether this will help in running time is hard to say, but at least now we have two implementations (EGdGraph_t) one with embeded structures and one with pointer to sub-structures.

Version:: 0.0.1

History:

2005-06-15
- First Implementation.

Define Documentation

#define EGeUgraphAddEdge	(	__Gpt,
		__headpt,
		__tailpt,
		__ept
	)

Value:

({\
  EGeUgraph_t*const __EGeDg_add_e_G = (__Gpt);\
  EGeUgraphNode_t*const __EGeDg_add_e_head = (__headpt);\
  EGeUgraphNode_t*const __EGeDg_add_e_tail = (__tailpt);\
  EGeUgraphEdge_t*const __EGeDg_add_e = (__ept);\
  EGeListAddAfter(&(__EGeDg_add_e->ep[1].cn),&(__EGeDg_add_e_head->edges));\
  EGeListAddAfter(&(__EGeDg_add_e->ep[0].cn),&(__EGeDg_add_e_tail->edges));\
  __EGeDg_add_e->ep[1].node = __EGeDg_add_e_head;\
  __EGeDg_add_e->ep[0].node = __EGeDg_add_e_tail;\
  __EGeDg_add_e_head->degree++;\
  __EGeDg_add_e_tail->degree++;\
  __EGeDg_add_e_G->n_edges++;})

Add an edge to a graph.

Parameters:

	__Gpt	pointer to the graph.
	__headpt	pointer to the head node.
	__tailpt	pointer to the tail node.
	__ept	pointer to the edge.

Examples:: eg_eugraph.ex.c.

Definition at line 193 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphAddNode	(	__Gpt,
		__v
	)

Value:

({\
  EGeUgraph_t*const __EGeDg_add_n_G = (__Gpt);\
  EGeUgraphNode_t*const __EGeDg_add_n_v = (__v);\
  EGeListAddAfter(&(__EGeDg_add_n_v->node_cn),&(__EGeDg_add_n_G->nodes));\
  __EGeDg_add_n_G->n_nodes++;})

Add a node to the graph.

Parameters:

	__Gpt	pointer to the graph to where we will add a node, it should be an initialized graph structure (see EGeUgraphInit).
	__v	pointer to the node to be added to the graph. Note that we don't check wether the node has valid information inside (you should call EGeUgraphNodeInit(__v) for all nodes before adding them.

Returns:: the number of nodes in the graph (including the recently added node).

Examples:: eg_eugraph.ex.c.

Definition at line 161 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphChangeEP	(	__Gpt,
		__ept,
		__tailpt,
		__eptype
	)

Value:

({\
  EGeUgraphNode_t*const __EGeDg_chg_hd_tail = (__tailpt);\
  EGeUgraphEdge_t*const __EGeDg_chg_hd_e = (__ept);\
  EGeUgraphEP_t*const __EGeDg_ep = &(__EGeDg_chg_hd_e->ep[__eptype]);\
  __EGeDg_ep->node->degree--;\
  EGeListDel(&(__EGeDg_ep->cn));\
  EGeListAddAfter(&(__EGeDg_ep->cn),&(__EGeDg_chg_hd_tail->edges));\
  __EGeDg_chg_hd_tail->degree++;\
  __EGeDg_ep->node = __EGeDg_chg_hd_tail;})

Change an endpoint of an edge.

Parameters:

	__ept	pointer to the edge whose tail will be changed.
	__Gpt	pointer to the graph.
	__tailpt	pointer to the new edge's tail.
	__eptype	number of the endpoint (either 0 or 1).

Returns:: pointer to the new tail of the given edge.

Description:: Note that this function assumes that that both (__ept) and (__tailpt) bellong to an initialized graph.

Definition at line 236 of file eg_eugraph.h.

#define EGeUgraphChangeHead	(	__Gpt,
		__ept,
		__headpt
	)		EGeUgraphChangeEP(__Gpt,__ept,__headpt,1)

Change the head of an edge.

Parameters:

	__ept	pointer to the edge whose head will be changed.
	__headpt	pointer to the new edge's head.
	__Gpt	pointer to the graph.

Returns:: pointer to the new head of the given edge.

Description:: Note that this function assumes that that both (__ept) and (__headpt) bellong to an initialized graph.

Examples:: eg_eugraph.ex.c.

Definition at line 266 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphChangeTail	(	__Gpt,
		__ept,
		__tailpt
	)		EGeUgraphChangeEP(__Gpt,__ept,__tailpt,0)

Change the tail of an edge.

Parameters:

	__ept	pointer to the edge whose tail will be changed.
	__Gpt	pointer to the graph.
	__tailpt	pointer to the new edge's tail.

Returns:: pointer to the new tail of the given edge.

Description:: Note that this function assumes that that both (__ept) and (__tailpt) bellong to an initialized graph.

Examples:: eg_eugraph.ex.c.

Definition at line 255 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphClear ( __Gpt ) ;

Clear the structure so that we can free it (without memory leaks). Note that this macro does nothing, because it is always safe to free this structure.

Examples:: eg_eugraph.ex.c.

Definition at line 112 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphDelEdge	(	__Gpt,
		__ept
	)

Value:

({\
  EGeUgraph_t*const __EGeDg_del_e_G = (__Gpt);\
  EGeUgraphEdge_t*const __EGeDg_del_e = (__ept);\
  EGeListDel(&(__EGeDg_del_e->ep[1].cn));\
  EGeListDel(&(__EGeDg_del_e->ep[0].cn));\
  __EGeDg_del_e->ep[1].node->degree--;\
  __EGeDg_del_e->ep[0].node->degree--;\
  __EGeDg_del_e_G->n_edges--;\
  __EGeDg_del_e;})

Delete an edge from a graph.

Parameters:

	__Gpt	pointer to the graph.
	__ept	pointer to the edge.

Returns:: pointer to the deleted edge.

Note:: Take notice that this function won't change the values stored in the given edge '__ept', so if you access the internal information it may or may not be still valid, (depending on what else has happen with the graph in the meantime).

Examples:: eg_eugraph.ex.c.

Definition at line 216 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphDelNode	(	__Gpt,
		__v
	)

Value:

({\
  EGeUgraph_t*const __EGeDg_del_n_G = (__Gpt);\
  EGeUgraphNode_t*const __EGeDg_del_n = (__v);\
  if(__EGeDg_del_n->degree) EXIT(1,"trying to remove node "#__v" with "\
    "incoming edges from graph "#__Gpt);\
  EGeListDel(&(__EGeDg_del_n->node_cn));\
  __EGeDg_del_n_G->n_nodes--;\
  __EGeDg_del_n;})

Remove a node from a graph.

Parameters:

	__v	pointer to the node to be removed from the graph.
	__Gpt	pointer to the graph from where we will remove the node.

Returns:: pointer to the removed node.

Note:: Note that the actual definition of removing a node from a graph is not completelly well defined, since there might be some edges attached to this node, and is not clear what to do in such a case. In this implementation we chose to return an error if the degree of this node is non-zero.

Examples:: eg_eugraph.ex.c.

Definition at line 177 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphEdgeClear ( __Gpt ) ;

Clear the structure so that we can free it (without memory leaks). Note that this macro does nothing, because it is always safe to free this structure.

Examples:: eg_eugraph.ex.c.

Definition at line 123 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphEdgeInit ( __ept ) *(__ept) = (EGeUgraphEdge_t){{(EGeUgraphEP_t){(EGeList_t){0,0},0,0},(EGeUgraphEP_t){(EGeList_t){0,0},0,1}}};

Initialize an edge as an empty edge, non attached to any graph.

Parameters:

__ept

pointer to edge be initialized

Examples:: eg_eugraph.ex.c.

Definition at line 117 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphGetAdjEdge ( __edge_cn )

Value:

({\
  EGeUgraphEP_t*const __EGeUg_ep = EGcontainerOf(__edge_cn,EGeUgraphEP_t,cn);\
  EGcontainerOf(__EGeUg_ep,EGeUgraphEdge_t,ep[__EGeUg_ep->type]);})

Given the adjacency list connector of an edge, return the pointer to the internal edge.

Parameters:

__edge_cn

pointer to the edge connector as in the nodes adjacency list.

Returns:: pointer to the actual EGeUgraphEdge_t containing the connector.

Definition at line 147 of file eg_eugraph.h.

#define EGeUgraphInit ( __Gpt )

Value:

({\
  EGeUgraph_t*const __EGeDg_in_G = (__Gpt);\
  EGeListInit(&(__EGeDg_in_G->nodes));\
  __EGeDg_in_G->n_edges = __EGeDg_in_G->n_nodes = 0;})

Initialize a graph structure as an empty graph with no members.

Parameters:

__Gpt

pointer to the graph to be initialized

Examples:: eg_eugraph.ex.c.

Definition at line 103 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphNodeClear ( __Gpt ) ;

Clear the structure so that we can free it (without memory leaks). Note that this macro does nothing, because it is always safe to free this structure.

Examples:: eg_eugraph.ex.c.

Definition at line 138 of file eg_eugraph.h.

Referenced by main().

#define EGeUgraphNodeInit ( __v )

Value:

({\
  EGeUgraphNode_t*const __EGeDg_in_v = (__v);\
  EGeListInit(&(__EGeDg_in_v->edges));\
  __EGeDg_in_v->node_cn = (EGeList_t){0,0};\
  __EGeDg_in_v->degree = 0;})

Initialize a node as an empty non-attached node.

Parameters:

__v

pointer to node to be initialized