EGsrkGraph

Detailed Description

This is a group of functions, macros and types designed to work with graphs that are shrinkable, meaning that we can take two nodes in the (current) graph, and shrink them into a single node, and at the same time collapse all edges that become loops and if two edges are parallel, keep just one (but keep a reference to the collapsed edge). At the same time the shrunken nodes keep a list to the nodes 'embeded' or 'shrunken' into the given node. More details in the structure definition and in the example. Note that this implementation only support undirected graphs with actual weights on the edges, the weights must be of type EGlpNum_t, and their values are updated during the shrinking procedure, so if anyone want to have the original values omewere else, they will have to keep an extra copy outside. Most of the ideas used in this implementation come from CONCORDE.

Version:: 0.0.1

History:

2005-06-01
- First Implementation.

Files

file eg_shrink_graph.c

file eg_shrink_graph.ex.c

file eg_shrink_graph.h

Data Structures

struct EGsrkEdge_t

Edge structure for shrinkable graphs. More...

struct EGsrkGraph_t

Graph structure for shrinkable graphs. More...

struct EGsrkNode_t

Node structure for shrinkable graphs. More...

Defines

#define EG_SRK_DEBUG   100

debuigging level, the lower the more debugging is carried out

#define EGsrkAddEdge(lG, head_pt, tail_pt, E)

Add a EGsrkEdge_t edge to a EGsrkGraph_t graph.

#define EGsrkAddNode(graph, N)   EGeUgraphAddNode(&((graph)->G),&((N)->node))

Add a EGsrkNode_t node to a EGsrkGraph_t graph.

#define EGsrkEdgeClear(e_edge)

Clear internal memory (not allocated by the user) of an edge structure.

#define EGsrkEdgeInit(e_edge)

Initialize an edge structure.

#define EGsrkGraphClear(graph)   EGeUgraphClear(&((graph)->G))

Clear internal memory (not allocated by the user) of a graph structure.

#define EGsrkGraphInit(graph)

Initialize a graph structure.

#define EGsrkNodeClear(e_node)

Clear internal memory (not allocated by the user) of a node structure.

#define EGsrkNodeInit(e_node)

Initialize a node structure.

Typedefs

typedef EGsrkEdge_t EGsrkEdge_t

Edge structure for shrinkable graphs.

typedef EGsrkGraph_t EGsrkGraph_t

Graph structure for shrinkable graphs.

typedef EGsrkNode_t EGsrkNode_t

Node structure for shrinkable graphs.

Functions

static void display_srkG (EGsrkGraph_t *G, EGsrkNode_t *const all_nodes, EGsrkEdge_t *const all_edges)

given a EGsrkGraph_t structure, display the current shrunken graph and it's node weights

EGsrkNode_t * EGsrkIdentifyNodes (EGsrkGraph_t *const G, EGsrkNode_t *const base, EGsrkNode_t *const srkN)

Given two nodes in the current shrunken graph, shrunk them into one node.

int main (int argc, char **argv)

This program read a graph a file from the input whose two first numbers are the number of nodes and edges (we assume that the graph is undirected ), and then a 3-tupla with head tail capacity. we use the last field (capacity) as the capacity of the edge. Once this graph has been read, we create a EGsrkGraph, and then we shrink the graph until two nodes remain. printing the graph at every iteration.

static void srk_usage (char **argv)

display usage of this program

Define Documentation

#define EG_SRK_DEBUG 100

debuigging level, the lower the more debugging is carried out

Definition at line 60 of file eg_shrink_graph.h.

#define EGsrkAddEdge ( lG,
head_pt,
tail_pt,
E )

Value:
({\ EGsrkNode_t*const _EGsrkH = (head_pt);\ EGsrkNode_t*const _EGsrkT = (tail_pt);\ EGsrkEdge_t*const _EGsrkE = (E);\ EGlpNumAddTo(_EGsrkH->weight,_EGsrkE->weight);\ EGlpNumAddTo(_EGsrkT->weight,_EGsrkE->weight);\ EGeUgraphAddEdge(&((lG)->G),&(_EGsrkH->node),&(_EGsrkT->node),&(_EGsrkE->edge));})
Add a EGsrkEdge_t edge to a EGsrkGraph_t graph.

Parameters:

lG graph were to add the edge.

head_pt head node of the edge.

tail_pt tail node of the edge.

E edge to be added with end-points head_pt and tail_pt. Note that this function will update the accumulated weight of both endpoints of the newly added edge according to the value stored in the EGsrkEdge_t::weight field.

Examples:
eg_min_cut.ex.c, and eg_shrink_graph.ex.c.

Definition at line 180 of file eg_shrink_graph.h.

#define EGsrkAddNode ( graph,
N ) EGeUgraphAddNode(&((graph)->G),&((N)->node))

Add a EGsrkNode_t node to a EGsrkGraph_t graph.

Parameters:

graph graph were to add the node.

N node to add to the graph.

Returns:
zero on success, non-zero otherwise.

Examples:
eg_min_cut.ex.c, and eg_shrink_graph.ex.c.

Definition at line 168 of file eg_shrink_graph.h.

#define EGsrkEdgeClear ( e_edge )

Value:
({\ EGeUgraphEdgeClear(&((e_edge)->edge));\ EGlpNumClearVar((e_edge)->weight);})
Clear internal memory (not allocated by the user) of an edge structure.

Parameters:

e_edge

Examples:
eg_shrink_graph.ex.c.

Definition at line 123 of file eg_shrink_graph.h.

#define EGsrkEdgeInit ( e_edge )

Value:
({\ EGsrkEdge_t*const _EGsrkE = (e_edge);\ EGeUgraphEdgeInit(&(_EGsrkE->edge));\ EGeListInit(&(_EGsrkE->members));\ _EGsrkE->mmb_sz = 0;\ EGlpNumInitVar(_EGsrkE->weight);\ EGlpNumZero(_EGsrkE->weight);})
Initialize an edge structure.

Parameters:

e_edge

Examples:
eg_shrink_graph.ex.c.

Definition at line 111 of file eg_shrink_graph.h.

#define EGsrkGraphClear ( graph ) EGeUgraphClear(&((graph)->G))

Clear internal memory (not allocated by the user) of a graph structure.

Parameters:

graph

Examples:
eg_shrink_graph.ex.c.

Definition at line 139 of file eg_shrink_graph.h.

#define EGsrkGraphInit ( graph )

Value:
({\ EGsrkGraph_t*const _EGsrkG = (graph);\ EGeUgraphInit(&(_EGsrkG->G));\ _EGsrkG->n_onodes = _EGsrkG->n_oedges = 0;})
Initialize a graph structure.

Parameters:

graph graph to be initialized

Examples:
eg_shrink_graph.ex.c.

Definition at line 130 of file eg_shrink_graph.h.

#define EGsrkNodeClear ( e_node )

Value:
({\ EGeUgraphNodeClear(&((e_node)->node));\ EGlpNumClearVar((e_node)->weight);})
Clear internal memory (not allocated by the user) of a node structure.

Parameters:

e_node

Examples:
eg_shrink_graph.ex.c.

Definition at line 158 of file eg_shrink_graph.h.

#define EGsrkNodeInit ( e_node )

Value:
({\ EGsrkNode_t*const _EGsrkN = (e_node);\ EGeUgraphNodeInit(&(_EGsrkN->node));\ EGeListInit(&(_EGsrkN->members));\ _EGsrkN->mmb_sz = 0;\ _EGsrkN->hit = 0;\ EGesInit(&(_EGsrkN->parent));\ EGlpNumInitVar(_EGsrkN->weight);\ EGlpNumZero(_EGsrkN->weight);})
Initialize a node structure.

Parameters:

e_node node to be initialized

Examples:
eg_shrink_graph.ex.c.

Definition at line 144 of file eg_shrink_graph.h.

Typedef Documentation

typedef struct EGsrkEdge_t EGsrkEdge_t

Edge structure for shrinkable graphs.

typedef struct EGsrkGraph_t EGsrkGraph_t

Graph structure for shrinkable graphs.

typedef struct EGsrkNode_t EGsrkNode_t

Node structure for shrinkable graphs.

Function Documentation

static void display_srkG ( EGsrkGraph_t * G,

EGsrkNode_t *const all_nodes,

EGsrkEdge_t *const all_edges

) [inline, static]

given a EGsrkGraph_t structure, display the current shrunken graph and it's node weights

Examples:
eg_shrink_graph.ex.c.

Definition at line 36 of file eg_shrink_graph.ex.c.

EGsrkNode_t * EGsrkIdentifyNodes ( EGsrkGraph_t *const G,

EGsrkNode_t *const base,

EGsrkNode_t *const srkN

)

Given two nodes in the current shrunken graph, shrunk them into one node.

Parameters:

G pointer to the graph where we are working

base first node.

srkN second node.

Returns:
pointer to the new representing node.

Note:
We assume that the field EGsrkNode_t::hit is identically NULL for all nodes currently in the shrunken graph (including base and srkN).
We allways assume that N1 will be the representing node.
Take note that this structure can't get back the pointer to the srkN node, the user should take care of that if needed.

Examples:
eg_shrink_graph.ex.c.

Definition at line 28 of file eg_shrink_graph.c.

int main ( int argc,

char ** argv

)

This program read a graph a file from the input whose two first numbers are the number of nodes and edges (we assume that the graph is undirected ), and then a 3-tupla with head tail capacity. we use the last field (capacity) as the capacity of the edge. Once this graph has been read, we create a EGsrkGraph, and then we shrink the graph until two nodes remain. printing the graph at every iteration.

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

static void srk_usage ( char ** argv ) [inline, static]

display usage of this program

Examples:
eg_shrink_graph.ex.c.

Definition at line 28 of file eg_shrink_graph.ex.c.

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

1.4.5


Files
file	eg_shrink_graph.c
file	eg_shrink_graph.ex.c
file	eg_shrink_graph.h
Data Structures
struct	EGsrkEdge_t
	Edge structure for shrinkable graphs. More...
struct	EGsrkGraph_t
	Graph structure for shrinkable graphs. More...
struct	EGsrkNode_t
	Node structure for shrinkable graphs. More...
Defines
#define	EG_SRK_DEBUG 100
	debuigging level, the lower the more debugging is carried out
#define	EGsrkAddEdge(lG, head_pt, tail_pt, E)
	Add a EGsrkEdge_t edge to a EGsrkGraph_t graph.
#define	EGsrkAddNode(graph, N) EGeUgraphAddNode(&((graph)->G),&((N)->node))
	Add a EGsrkNode_t node to a EGsrkGraph_t graph.
#define	EGsrkEdgeClear(e_edge)
	Clear internal memory (not allocated by the user) of an edge structure.
#define	EGsrkEdgeInit(e_edge)
	Initialize an edge structure.
#define	EGsrkGraphClear(graph) EGeUgraphClear(&((graph)->G))
	Clear internal memory (not allocated by the user) of a graph structure.
#define	EGsrkGraphInit(graph)
	Initialize a graph structure.
#define	EGsrkNodeClear(e_node)
	Clear internal memory (not allocated by the user) of a node structure.
#define	EGsrkNodeInit(e_node)
	Initialize a node structure.
Typedefs
typedef EGsrkEdge_t	EGsrkEdge_t
	Edge structure for shrinkable graphs.
typedef EGsrkGraph_t	EGsrkGraph_t
	Graph structure for shrinkable graphs.
typedef EGsrkNode_t	EGsrkNode_t
	Node structure for shrinkable graphs.
Functions
static void	display_srkG (EGsrkGraph_t G, EGsrkNode_t const all_nodes, EGsrkEdge_t *const all_edges)
	given a EGsrkGraph_t structure, display the current shrunken graph and it's node weights
EGsrkNode_t *	EGsrkIdentifyNodes (EGsrkGraph_t const G, EGsrkNode_t const base, EGsrkNode_t *const srkN)
	Given two nodes in the current shrunken graph, shrunk them into one node.
int	main (int argc, char **argv)
	This program read a graph a file from the input whose two first numbers are the number of nodes and edges (we assume that the graph is undirected ), and then a 3-tupla with head tail capacity. we use the last field (capacity) as the capacity of the edge. Once this graph has been read, we create a EGsrkGraph, and then we shrink the graph until two nodes remain. printing the graph at every iteration.
static void	srk_usage (char **argv)
	display usage of this program