Data Structures
struct	EGeDgraph_t
	structure that holds all graph related structures needed to define a directed graph, and to allow modifications over it. More...
struct	EGeDgraphEdge_t
	structure that hold all edge related structures needed to define a directed graph, and add/delete/modify it's structure More...
struct	EGeDgraphNode_t
	structure that hold all node related structures needed to define a graph, and add/delete/modify it's structure More...
struct	my_dedge_t
	example of an edge structure using the embeded substructures. More...
struct	my_dgraph_t
	example of a graph structure using the embeded substructures. More...
struct	my_dnode_t
	example of a node structure using the embeded substructures. More...
Files
file	eg_edgraph.ex.c
file	eg_edgraph.h
Defines
#define	EGeDgraphAddEdge(__G, __hpt, __tpt, __e)
	Add an edge to a graph.
#define	EGeDgraphAddNode(__G, __v)
	Add a node to the graph.
#define	EGeDgraphChangeHead(__G, __e, __hpt)
	Change the head of an edge.
#define	EGeDgraphChangeTail(__G, __e, __tpt)
	Change the tail of an edge.
#define	EGeDgraphClear(__G)
	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	EGeDgraphDelEdge(__G, __e)
	Delete an edge from a graph.
#define	EGeDgraphDelNode(__G, __v)
	Remove a node from a graph.
#define	EGeDgraphEdgeClear(__G) ;
	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	EGeDgraphEdgeInit(__e)
	Initialize an edge as an empty edge, non attached to any graph.
#define	EGeDgraphEdgeReset(__e) EGeDgraphEdgeInit(__e)
	Reset the given edge pointer as an edge not linked to a graph.
#define	EGeDgraphInit(__G)
	Initialize a graph structure as an empty graph with no members.
#define	EGeDgraphNodeClear(__G)
	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	EGeDgraphNodeInit(__v)
	Initialize a node as an empty non-attached node.
#define	EGeDgraphNodeReset(__v) EGeDgraphNodeInit(__v)
	Reset the given node pointer as a node not linked to a graph.
#define	EGeDgraphReset(__G) EGeDgraphInit(__G)
	Reset the given graph pointer as an empty graph.
Typedefs
typedef struct EGeDgraphEdge_t	EGeDgraphEdge_t
	structure that hold all edge related structures needed to define a directed graph, and add/delete/modify it's structure
typedef struct EGeDgraphNode_t	EGeDgraphNode_t
	structure that hold all node related structures needed to define a graph, and add/delete/modify it's structure
typedef struct my_dedge_t	my_dedge_t
	example of an edge structure using the embeded substructures.
typedef struct my_dgraph_t	my_dgraph_t
	example of a graph structure using the embeded substructures.
typedef struct my_dnode_t	my_dnode_t
	example of a node structure using the embeded substructures.
Functions
static void	display_DG (my_dgraph_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-05-23
- First Implementation.

Define Documentation

#define EGeDgraphAddEdge	(	__G,
		__hpt,
		__tpt,
		__e
	)

Value:

({\
  EGeDgraph_t*const __EGeDg_add_e_G = (__G);\
  EGeDgraphNode_t*const __EGeDg_add_e_head = (__hpt);\
  EGeDgraphNode_t*const __EGeDg_add_e_tail = (__tpt);\
  EGeDgraphEdge_t*const __EGeDg_add_e = (__e);\
  EGeListAddAfter(&(__EGeDg_add_e->head_cn),&(__EGeDg_add_e_head->in_edge));\
  EGeListAddAfter(&(__EGeDg_add_e->tail_cn),&(__EGeDg_add_e_tail->out_edge));\
  __EGeDg_add_e->head = __EGeDg_add_e_head;\
  __EGeDg_add_e->tail = __EGeDg_add_e_tail;\
  __EGeDg_add_e_head->in_size++;\
  __EGeDg_add_e_tail->out_size++;\
  __EGeDg_add_e_G->n_edges++;})

Add an edge to a graph.

Parameters:

	__G	pointer to the graph.
	__hpt	pointer to the head node.
	__tpt	pointer to the tail node.
	__e	pointer to the edge.

Examples:: eg_edgraph.ex.c, and eg_push_relabel.ex.c.

Definition at line 194 of file eg_edgraph.h.

Referenced by EGalgMaxClosure_PR(), EGalgMCbuildPRgraph(), and main().

#define EGeDgraphAddNode	(	__G,
		__v
	)

Value:

({\
  EGeDgraph_t*const __EGeDg_add_n_G = (__G);\
  EGeDgraphNode_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:

	__G	pointer to the graph to where we will add a node, it should be an initialized graph structure (see EGeDgraphInit).
	__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 EGeDgraphNodeInit(__v) for all nodes before adding them.

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

Examples:: eg_edgraph.ex.c, and eg_push_relabel.ex.c.

Definition at line 160 of file eg_edgraph.h.

Referenced by EGalgMaxClosure_PR(), EGalgMCbuildPRgraph(), and main().

#define EGeDgraphChangeHead	(	__G,
		__e,
		__hpt
	)

Value:

({\
  EGeDgraphNode_t*const __EGeDg_chg_hd_head = (__hpt);\
  EGeDgraphEdge_t*const __EGeDg_chg_hd_e = (__e);\
  __EGeDg_chg_hd_e->head->in_size--;\
  EGeListDel(&(__EGeDg_chg_hd_e->head_cn));\
  EGeListAddAfter(&(__EGeDg_chg_hd_e->head_cn),&(__EGeDg_chg_hd_head->in_edge));\
  __EGeDg_chg_hd_head->in_size++;\
  __EGeDg_chg_hd_e->head = __EGeDg_chg_hd_head;})

Change the head of an edge.

Parameters:

	__e	pointer to the edge whose head will be changed.
	__hpt	pointer to the new edge's head.
	__G	pointer to the graph.

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

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

Examples:: eg_edgraph.ex.c.

Definition at line 254 of file eg_edgraph.h.

Referenced by main().

#define EGeDgraphChangeTail	(	__G,
		__e,
		__tpt
	)

Value:

({\
  EGeDgraphNode_t*const __EGeDg_chg_hd_tail = (__tpt);\
  EGeDgraphEdge_t*const __EGeDg_chg_hd_e = (__e);\
  __EGeDg_chg_hd_e->tail->out_size--;\
  EGeListDel(&(__EGeDg_chg_hd_e->tail_cn));\
  EGeListAddAfter(&(__EGeDg_chg_hd_e->tail_cn),&(__EGeDg_chg_hd_tail->out_edge));\
  __EGeDg_chg_hd_tail->out_size++;\
  __EGeDg_chg_hd_e->tail = __EGeDg_chg_hd_tail;})

Change the tail of an edge.

Parameters:

	__e	pointer to the edge whose tail will be changed.
	__G	pointer to the graph.
	__tpt	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 (__e) and (__tpt) bellong to an initialized graph.

Examples:: eg_edgraph.ex.c.

Definition at line 236 of file eg_edgraph.h.

Referenced by main().

#define EGeDgraphClear ( __G )

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_edgraph.ex.c.

Definition at line 107 of file eg_edgraph.h.

Referenced by main().

#define EGeDgraphDelEdge	(	__G,
		__e
	)

Value:

({\
  EGeDgraph_t*const __EGeDg_del_e_G = (__G);\
  EGeDgraphEdge_t*const __EGeDg_del_e = (__e);\
  EGeListDel(&(__EGeDg_del_e->head_cn));\
  EGeListDel(&(__EGeDg_del_e->tail_cn));\
  __EGeDg_del_e->head->in_size--;\
  __EGeDg_del_e->tail->out_size--;\
  __EGeDg_del_e_G->n_edges--;\
  __EGeDg_del_e;})

Delete an edge from a graph.

Parameters:

	__G	pointer to the graph.
	__e	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 '__e', 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_edgraph.ex.c.

Definition at line 217 of file eg_edgraph.h.

Referenced by main().

#define EGeDgraphDelNode	(	__G,
		__v
	)

Value:

({\
  EGeDgraph_t*const __EGeDg_del_n_G = (__G);\
  EGeDgraphNode_t*const __EGeDg_del_n = (__v);\
  if(__EGeDg_del_n->in_size) EXIT(1,"trying to remove node "#__v" with "\
    "incoming edges from graph "#__G);\
  if(__EGeDg_del_n->out_size) EXIT(1,"trying to remove node "#__v" with "\
    "outgoing edges from graph "#__G);\
  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.
	__G	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_edgraph.ex.c.

Definition at line 176 of file eg_edgraph.h.

Referenced by main().

#define EGeDgraphEdgeClear ( __G ) ;

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_edgraph.ex.c.

Definition at line 127 of file eg_edgraph.h.

Referenced by main().

#define EGeDgraphEdgeInit ( __e )

Value:

({\
  EGeDgraphEdge_t*const __EGeDg_in_e = (__e);\
  __EGeDg_in_e->head_cn = (EGeList_t){0,0};\
  __EGeDg_in_e->tail_cn = (EGeList_t){0,0};\
  __EGeDg_in_e->head = __EGeDg_in_e->tail = 0;})

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

Parameters:

__e

pointer to edge be initialized

Examples:: eg_edgraph.ex.c.

Definition at line 112 of file eg_edgraph.h.

Referenced by main().

#define EGeDgraphEdgeReset ( __e ) EGeDgraphEdgeInit(__e)

Reset the given edge pointer as an edge not linked to a graph.

Parameters:

__e

pointer to the edge to reset

Definition at line 121 of file eg_edgraph.h.

#define EGeDgraphInit ( __G )

Value:

({\
  EGeDgraph_t*const __EGeDg_in_G = (__G);\
  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:

__G

pointer to the graph to be initialized

Examples:: eg_edgraph.ex.c.

Definition at line 93 of file eg_edgraph.h.

Referenced by main().

#define EGeDgraphNodeClear ( __G )

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_edgraph.ex.c.

Definition at line 148 of file eg_edgraph.h.

Referenced by main().

#define EGeDgraphNodeInit ( __v )

Value:

({\
  EGeDgraphNode_t*const __EGeDg_in_v = (__v);\
  EGeListInit(&(__EGeDg_in_v->in_edge));\
  EGeListInit(&(__EGeDg_in_v->out_edge));\
  __EGeDg_in_v->node_cn = (EGeList_t){0,0};\
  __EGeDg_in_v->in_size = __EGeDg_in_v->out_size = 0;})

Initialize a node as an empty non-attached node.

Parameters:

__v

pointer to node to be initialized