EGeUgraph

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.

Files

file eg_eugraph.ex.c

file eg_eugraph.h

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...

Defines

#define EGeUgraphAddEdge(G, head_pt, tail_pt, e)

Add an edge to a graph.

#define EGeUgraphAddNode(G, v)

Add a node to the graph.

#define EGeUgraphChangeEP(G, e, tail_pt, ep_type)

Change an endpoint of an edge.

#define EGeUgraphChangeHead(G, e, head_pt)   EGeUgraphChangeEP(G,e,head_pt,1)

Change the head of an edge.

#define EGeUgraphChangeTail(G, e, tail_pt)   EGeUgraphChangeEP(G,e,tail_pt,0)

Change the tail of an edge.

#define EGeUgraphClear(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 EGeUgraphDelEdge(G, e)

Delete an edge from a graph.

#define EGeUgraphDelNode(G, v)

Remove a node from a graph.

#define EGeUgraphEdgeClear(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 EGeUgraphEdgeInit(e)   *(e) = (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(G)

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

#define EGeUgraphNodeClear(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 EGeUgraphNodeInit(v)

Initialize a node as an empty non-attached node.

Typedefs

typedef EGeUgraph_t EGeUgraph_t

structure that holds all graph related structures needed to define a directed graph, and to allow modifications over it.

typedef 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 EGeUgraphEP_t EGeUgraphEP_t

Structure for endpoints of edges.

typedef EGeUgraphNode_t EGeUgraphNode_t

structure that hold all node related structures needed to define a graph, and add/delete/modify it's structure

typedef my_uedge_t my_uedge_t

example of an edge structure using the embeded substructures.

typedef my_ugraph_t my_ugraph_t

example of a graph structure using the embeded substructures.

typedef 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.

Define Documentation

#define EGeUgraphAddEdge ( G,
head_pt,
tail_pt,
e )

Value:
({\ EGeUgraph_t*const __EGeDg_add_e_G = (G);\ EGeUgraphNode_t*const __EGeDg_add_e_head = (head_pt);\ EGeUgraphNode_t*const __EGeDg_add_e_tail = (tail_pt);\ EGeUgraphEdge_t*const __EGeDg_add_e = (e);\ 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:

G pointer to the graph.

head_pt pointer to the head node.

tail_pt pointer to the tail node.

e pointer to the edge.

Examples:
eg_eugraph.ex.c.

Definition at line 195 of file eg_eugraph.h.

#define EGeUgraphAddNode ( G,
v )

Value:
({\ EGeUgraph_t*const __EGeDg_add_n_G = (G);\ 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:

G 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 163 of file eg_eugraph.h.

#define EGeUgraphChangeEP ( G,
e,
tail_pt,
ep_type )

Value:
({\ EGeUgraphNode_t*const __EGeDg_chg_hd_tail = (tail_pt);\ EGeUgraphEdge_t*const __EGeDg_chg_hd_e = (e);\ EGeUgraphEP_t*const __EGeDg_ep = &(__EGeDg_chg_hd_e->ep[ep_type]);\ __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:

e pointer to the edge whose tail will be changed.

G pointer to the graph.

tail_pt pointer to the new edge's tail.

ep_type 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 (e) and (tail_pt) bellong to an initialized graph.

Definition at line 238 of file eg_eugraph.h.

#define EGeUgraphChangeHead ( G,
e,
head_pt ) EGeUgraphChangeEP(G,e,head_pt,1)

Change the head of an edge.

Parameters:

e pointer to the edge whose head will be changed.

head_pt 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 (head_pt) bellong to an initialized graph.

Examples:
eg_eugraph.ex.c.

Definition at line 268 of file eg_eugraph.h.

#define EGeUgraphChangeTail ( G,
e,
tail_pt ) EGeUgraphChangeEP(G,e,tail_pt,0)

Change the tail of an edge.

Parameters:

e pointer to the edge whose tail will be changed.

G pointer to the graph.

tail_pt 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 (tail_pt) bellong to an initialized graph.

Examples:
eg_eugraph.ex.c.

Definition at line 257 of file eg_eugraph.h.

#define EGeUgraphClear ( 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_eugraph.ex.c.

Definition at line 114 of file eg_eugraph.h.

#define EGeUgraphDelEdge ( G,
e )

Value:
({\ EGeUgraph_t*const __EGeDg_del_e_G = (G);\ EGeUgraphEdge_t*const __EGeDg_del_e = (e);\ 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:

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

Definition at line 218 of file eg_eugraph.h.

#define EGeUgraphDelNode ( G,
v )

Value:
({\ EGeUgraph_t*const __EGeDg_del_n_G = (G);\ EGeUgraphNode_t*const __EGeDg_del_n = (v);\ if(__EGeDg_del_n->degree) EXIT(1,"trying to remove node "#v" with "\ "incoming 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_eugraph.ex.c.

Definition at line 179 of file eg_eugraph.h.

#define EGeUgraphEdgeClear ( 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_eugraph.ex.c.

Definition at line 125 of file eg_eugraph.h.

#define EGeUgraphEdgeInit ( e ) *(e) = (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:

e pointer to edge be initialized

Examples:
eg_eugraph.ex.c.

Definition at line 119 of file eg_eugraph.h.

#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 149 of file eg_eugraph.h.

#define EGeUgraphInit ( G )

Value:
({\ EGeUgraph_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_eugraph.ex.c.

Definition at line 105 of file eg_eugraph.h.

#define EGeUgraphNodeClear ( 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_eugraph.ex.c.

Definition at line 140 of file eg_eugraph.h.

#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

Examples:
eg_eugraph.ex.c.

Definition at line 130 of file eg_eugraph.h.

Typedef Documentation

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.

Function Documentation

static void display_UG ( my_ugraph_t * myG ) [inline, static]

Display the contents of our graph structure.

Examples:
eg_eugraph.ex.c.

Definition at line 56 of file eg_eugraph.ex.c.

int main ( void )

A simple example of a directed graph using (EGdEgraph) structures.

Returns:
zero on success, non-zero- otherwise.

Description:
Show how to use a directed graph, modify it and display it's contents

Definition at line 97 of file eg_eugraph.ex.c.
Here is the call graph for this function:

Generated on Mon Jan 30 08:55:32 2006 for EGlib by

1.4.5


Files
file	eg_eugraph.ex.c
file	eg_eugraph.h
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...
Defines
#define	EGeUgraphAddEdge(G, head_pt, tail_pt, e)
	Add an edge to a graph.
#define	EGeUgraphAddNode(G, v)
	Add a node to the graph.
#define	EGeUgraphChangeEP(G, e, tail_pt, ep_type)
	Change an endpoint of an edge.
#define	EGeUgraphChangeHead(G, e, head_pt) EGeUgraphChangeEP(G,e,head_pt,1)
	Change the head of an edge.
#define	EGeUgraphChangeTail(G, e, tail_pt) EGeUgraphChangeEP(G,e,tail_pt,0)
	Change the tail of an edge.
#define	EGeUgraphClear(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	EGeUgraphDelEdge(G, e)
	Delete an edge from a graph.
#define	EGeUgraphDelNode(G, v)
	Remove a node from a graph.
#define	EGeUgraphEdgeClear(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	EGeUgraphEdgeInit(e) *(e) = (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(G)
	Initialize a graph structure as an empty graph with no members.
#define	EGeUgraphNodeClear(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	EGeUgraphNodeInit(v)
	Initialize a node as an empty non-attached node.
Typedefs
typedef EGeUgraph_t	EGeUgraph_t
	structure that holds all graph related structures needed to define a directed graph, and to allow modifications over it.
typedef 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 EGeUgraphEP_t	EGeUgraphEP_t
	Structure for endpoints of edges.
typedef EGeUgraphNode_t	EGeUgraphNode_t
	structure that hold all node related structures needed to define a graph, and add/delete/modify it's structure
typedef my_uedge_t	my_uedge_t
	example of an edge structure using the embeded substructures.
typedef my_ugraph_t	my_ugraph_t
	example of a graph structure using the embeded substructures.
typedef 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.