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...
Files
file	eg_shrink_graph.c
file	eg_shrink_graph.ex.c
file	eg_shrink_graph.h
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 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.
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

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.

Define Documentation

#define EG_SRK_DEBUG 100

debuigging level, the lower the more debugging is carried out

Definition at line 57 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 177 of file eg_shrink_graph.h.

Referenced by main().

#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 165 of file eg_shrink_graph.h.

Referenced by main().

#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 120 of file eg_shrink_graph.h.

Referenced by main().

#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 108 of file eg_shrink_graph.h.

Referenced by main().

#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 136 of file eg_shrink_graph.h.

Referenced by main().

#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 127 of file eg_shrink_graph.h.

Referenced by main().

#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 155 of file eg_shrink_graph.h.

Referenced by main().

#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 141 of file eg_shrink_graph.h.

Referenced by main().

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.

References EGeUgraphNode_t::edges, EGcontainerOf, EGeListIsEmpty, EGsrkGraph_t::G, EGsrkEdge_t::members, EGsrkNode_t::members, EGeUgraph_t::n_nodes, EGeList_t::next, EGsrkNode_t::node, EGeUgraphEP_t::type, EGsrkEdge_t::weight, and EGsrkNode_t::weight.

Referenced by main().

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.

Referenced by main().

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.

References display_srkG(), EGcontainerOf, EGfree, EGlib_info(), EGlib_version(), EGlpNumClear(), EGlpNumStart(), EGsetLimits(), EGsigSet, EGsMalloc, EGsrkAddEdge, EGsrkAddNode, EGsrkEdgeClear, EGsrkEdgeInit, EGsrkGraphClear, EGsrkGraphInit, EGsrkIdentifyNodes(), EGsrkNodeClear, EGsrkNodeInit, EGsrkGraph_t::G, EGeUgraph_t::n_nodes, EGsrkGraph_t::n_oedges, EGsrkGraph_t::n_onodes, EGeList_t::next, EGsrkNode_t::node, EGeUgraphNode_t::node_cn, EGeUgraph_t::nodes, srk_usage(), and TESTG.