EGeDgraph

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:


Files

file  eg_edgraph.ex.c
file  eg_edgraph.h

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

Defines

#define EGeDgraphAddEdge(G, head_pt, tail_pt, e)
 Add an edge to a graph.
#define EGeDgraphAddNode(G, v)
 Add a node to the graph.
#define EGeDgraphChangeHead(G, e, head_pt)
 Change the head of an edge.
#define EGeDgraphChangeTail(G, e, tail_pt)
 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(edge_pt)   EGeDgraphEdgeInit(edge_pt)
 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(node_pt)   EGeDgraphNodeInit(node_pt)
 Reset the given node pointer as a node not linked to a graph.
#define EGeDgraphReset(graph_pt)   EGeDgraphInit(graph_pt)
 Reset the given graph pointer as an empty graph.

Typedefs

typedef EGeDgraph_t EGeDgraph_t
 structure that holds all graph related structures needed to define a directed graph, and to allow modifications over it.
typedef 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 EGeDgraphNode_t EGeDgraphNode_t
 structure that hold all node related structures needed to define a graph, and add/delete/modify it's structure
typedef my_dedge_t my_dedge_t
 example of an edge structure using the embeded substructures.
typedef my_dgraph_t my_dgraph_t
 example of a graph structure using the embeded substructures.
typedef 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.

Define Documentation

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

Value:

({\
  EGeDgraph_t*const __EGeDg_add_e_G = (G);\
  EGeDgraphNode_t*const __EGeDg_add_e_head = (head_pt);\
  EGeDgraphNode_t*const __EGeDg_add_e_tail = (tail_pt);\
  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.
head_pt pointer to the head node.
tail_pt pointer to the tail node.
e pointer to the edge.
Examples:
eg_edgraph.ex.c, and eg_push_relabel.ex.c.

Definition at line 196 of file eg_edgraph.h.

#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 162 of file eg_edgraph.h.

#define EGeDgraphChangeHead (  G,
e,
head_pt   ) 
 

Value:

({\
  EGeDgraphNode_t*const __EGeDg_chg_hd_head = (head_pt);\
  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.
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_edgraph.ex.c.

Definition at line 256 of file eg_edgraph.h.

#define EGeDgraphChangeTail (  G,
e,
tail_pt   ) 
 

Value:

({\
  EGeDgraphNode_t*const __EGeDg_chg_hd_tail = (tail_pt);\
  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.
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_edgraph.ex.c.

Definition at line 238 of file eg_edgraph.h.

#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 109 of file eg_edgraph.h.

#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 219 of file eg_edgraph.h.

#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 178 of file eg_edgraph.h.

#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 129 of file eg_edgraph.h.

#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 114 of file eg_edgraph.h.

#define EGeDgraphEdgeReset (  edge_pt   )     EGeDgraphEdgeInit(edge_pt)
 

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

Parameters:
edge_pt pointer to the edge to reset

Definition at line 123 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 95 of file eg_edgraph.h.

#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 150 of file eg_edgraph.h.

#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
Examples:
eg_edgraph.ex.c.

Definition at line 134 of file eg_edgraph.h.

#define EGeDgraphNodeReset (  node_pt   )     EGeDgraphNodeInit(node_pt)
 

Reset the given node pointer as a node not linked to a graph.

Parameters:
node_pt pointer to the node to reset

Definition at line 144 of file eg_edgraph.h.

#define EGeDgraphReset (  graph_pt   )     EGeDgraphInit(graph_pt)
 

Reset the given graph pointer as an empty graph.

Parameters:
graph_pt pointer to the graph to reset

Definition at line 103 of file eg_edgraph.h.

Typedef Documentation

typedef struct EGeDgraph_t EGeDgraph_t
 

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

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.

Function Documentation

static void display_DG (  my_dgraph_t *  myG  )  [inline, static]
 

Display the contents of our graph structure.

Examples:
eg_edgraph.ex.c.

Definition at line 56 of file eg_edgraph.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 105 of file eg_edgraph.ex.c.

Here is the call graph for this function:

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