EGalgMinCut

Detailed Description

Here we implement the min-cut algorithm based on the srinking pre-processing of Padberg And Rinaldi in the paper "An Efficient Algorithm For The Minimum Capacity Cut Problem", Mathematical Programming 47 (1990) pages 19-36. But using as minimum s-t cut code the Push-Relabel max flow algorithm as implemented in the EGalgPushRelabel module. This implies that we only support positive edge-weights.

This implementation allows uses of diferent numbers as supported by EGlpNum module. And follows the philosophy of embeded structures as in EGalgPushRelabel module. Also, much of the approach used in this implementation come from CONCORDE's implementation.

It is usually the case that the Minimum Cut Problem is just a sub-problem of some larger problem, is for that reason that we implement (just as in CONCORDE) a callback function that is called whenever an improving solution is found, so that the user can do something with the given node-cutset and value. for more details see the definition of EGalgMCcbk_t .

Note:
If run with types like EGfp20_t, if the arithmetic produces an overflow, then we are in big trouble, note that the numbers involved in the algorithm may range up to $\sum(w_e:e\in E(G))$ .
Version:
0.0.1
History:


Files

file  eg_min_cut.c
file  eg_min_cut.ex.c
file  eg_min_cut.h

Data Structures

struct  EGalgMCcbk_t
 Call-back structure for use when an improving minimum cut is found. More...
struct  EGalgMCedge_t
 Edge structure for the Minimum Cut. More...
struct  EGalgMCgraph_t
 Graph Structure for Minimum Cut. More...
struct  EGalgMCnode_t
 Node structure for Minimum Cut. More...
struct  mc_all_cuts_t
 structure to store a set of cuts More...
#define EGalgMCprofile

Defines

#define __MC_DEBUG_   100
 Level of profiling in the code.
#define __MC_PROFILE_   100
 Level of profiling in the code.
#define __MC_VRBLVL_   100
 Verbosity Level.
#define _EGalgMChitNeighbours(NODE)
 Set all EGalgMCnode_t::hit fields of all neighbours of the given node.
#define _EGalgMCunhitNeighbours(NODE)
 Set all EGalgMCnode_t::hit fields of all neighbours of the given node.
#define EGalgMCcbkClear(cb)   EGlpNumClearVar((cb)->cutoff)
 Free all internal memory asociated with this structure (not allocated by the user).
#define EGalgMCcbkInit(cb)
 Initialize a call-back structure.
#define EGalgMCedgeClear(E)   EGsrkEdgeClear(&((E)->edge))
 Clear any internal memory (not allocated by the user) used by this structure.
#define EGalgMCedgeInit(E)
 Initialize an edge structure for use.
#define EGalgMCgraphClear(Graph)
 Clear internal memory (not allocated by the user) of a graph structure.
#define EGalgMCgraphInit(Graph)
 Initialize a graph structure for use.
#define EGalgMCidentifyNodes(Graph, N, M)
 Shrink two nodes in the graph, and update internal structures.
#define EGalgMCnodeClear(N)   EGsrkNodeClear(&((N)->node))
 Clear any internal memory (not allocated by the user) used by this structure.
#define EGalgMCnodeInit(N)
 Initialize a node structure for use.
#define UPDATE(counter)
 variables and macros to do the profiling for the algorithm, it include counting the impact of all shrinking steps, the number of improvements cuts found along the way, and how many times where the main functions called.

Typedefs

typedef EGalgMCcbk_t EGalgMCcbk_t
 Call-back structure for use when an improving minimum cut is found.
typedef int(* EGalgMCdo_f )(EGlpNum_t, const unsigned int, const unsigned int *const, void *)
 Call-back function, it receives as input the weight of the cut, the size of the newly found cut, an array containing the cut (of length at least the number of elements in the cut) as integers (as defined by the EGalgMCnode_t::id field), and a pointer to some internal data (as stored in EGalgMCcbk_t::param). The function should return zero on success, and non-zero if an error ocours, this error will be propagated through the calling functions.
typedef EGalgMCedge_t EGalgMCedge_t
 Edge structure for the Minimum Cut.
typedef EGalgMCgraph_t EGalgMCgraph_t
 Graph Structure for Minimum Cut.
typedef EGalgMCnode_t EGalgMCnode_t
 Node structure for Minimum Cut.
typedef mc_all_cuts_t mc_all_cuts_t
 structure to store a set of cuts

Functions

int EGalgMC (EGalgMCgraph_t *const G, EGalgMCcbk_t *const cb, const unsigned int max_lvl)
 Compute a minimum cut on the given graph.
static int EGalgMCbuildPRgraph (EGalgMCgraph_t *const mcG, EGalgPRgraph_t *const prG, EGalgMCnode_t **const node_map, EGalgPRnode_t *const all_pr_nodes, EGalgPRedge_t *const all_pr_edges)
 Given a current min cut graph, build a Push-Relabel graph.
static int EGalgMCcomputeT (EGalgPRgraph_t *const prG, EGalgPRnode_t *const S, EGalgPRnode_t **const T)
 Compute the farthest node in the push-relabel graph from the given starting point.
static int EGalgMCexpandNode (unsigned int *const cut, EGalgMCnode_t *const N)
 Expand all nodes shrinked within a node, and store their id-s (EGalgMCnode_t::id) in the given array (including the node itself ).
int EGalgMCidentifyPRedges (EGalgMCgraph_t *const G, EGalgMCcbk_t *const cb, const unsigned int max_lvl)
 Identify all Padberg and Rinaldy edges. i.e. shrink all edges that satisfy the conditions in their paper. we choose to make tests over pair of nodes linked by an edge.
static int EGalgMCtestNode (EGalgMCgraph_t *const G, EGalgMCcbk_t *const cb, EGalgMCnode_t *const N)
 Given a node, test if the node is a better cut (by itself) then the currently found, and if so, update the current best cut, and call the callback if it is non-NULL.
int main (int argc, char **argv)
 example of usage of the Min Cut algorithm as implemented in (EGalgMinCut).
static int mc_parseargs (int argc, char **argv)
 parse input
int mc_store_cuts (EGlpNum_t value, const unsigned int c_sz, const unsigned int *const cut, void *data)
 call-back function to store all cuts fund during the execution of the min-cut algorithm.
static void mc_usage (char **argv)
 display usage of this program

Variables

static char * file_name = 0
static unsigned int lvl = 5

Define Documentation

#define __MC_DEBUG_   100
 

Level of profiling in the code.

Definition at line 81 of file eg_min_cut.h.

#define __MC_PROFILE_   100
 

Level of profiling in the code.

Definition at line 85 of file eg_min_cut.h.

#define __MC_VRBLVL_   100
 

Verbosity Level.

Definition at line 77 of file eg_min_cut.h.

#define _EGalgMChitNeighbours (  NODE   ) 
 

Value:

{\
  e_end = &((NODE)->node.node.edges);\
  for( e_it = e_end->next; e_it != e_end; e_it = e_it->next)\
    {\
      lep = EGcontainerOf(e_it, EGeUgraphEP_t,cn);\
      o_type = lep->type ? 0U : 1U;\
      E = EGcontainerOf(lep, EGalgMCedge_t, edge.edge.ep[lep->type]);\
      M = EGcontainerOf(E->edge.edge.ep[o_type].node, EGalgMCnode_t, node.node);\
      M->hit = &(E->edge);\
    }}
Set all EGalgMCnode_t::hit fields of all neighbours of the given node.

Parameters:
NODE node whose neighbours we are going to hit.
Note that we assume tha there exist variables (not in use within the scope of this call) as e_it, e_end, lep, o_type, M and E.

Definition at line 122 of file eg_min_cut.c.

#define _EGalgMCunhitNeighbours (  NODE   ) 
 

Value:

{\
  e_end = &((NODE)->node.node.edges);\
  for( e_it = e_end->next; e_it != e_end; e_it = e_it->next)\
    {\
      lep = EGcontainerOf(e_it, EGeUgraphEP_t,cn);\
      o_type = lep->type ? 0U : 1U;\
      E = EGcontainerOf(lep, EGalgMCedge_t, edge.edge.ep[lep->type]);\
      M = EGcontainerOf(E->edge.edge.ep[o_type].node, EGalgMCnode_t, node.node);\
      M->hit = 0;\
    }}
Set all EGalgMCnode_t::hit fields of all neighbours of the given node.

Parameters:
NODE node whose neighbours we are going to hit.
Note that we assume tha there exist variables (not in use within the scope of this call) as e_it, e_end, lep, o_type, M and E.

Definition at line 141 of file eg_min_cut.c.

#define EGalgMCcbkClear (  cb   )     EGlpNumClearVar((cb)->cutoff)
 

Free all internal memory asociated with this structure (not allocated by the user).

Parameters:
cb call-back strucure to be cleared

Definition at line 149 of file eg_min_cut.h.

#define EGalgMCcbkInit (  cb   ) 
 

Value:

({\
  EGalgMCcbk_t*const _EGalgMCcb = (cb);\
  EGlpNumInitVar(_EGalgMCcb->cutoff);\
  _EGalgMCcb->param = 0;\
  _EGalgMCcb->do_fn = 0;})
Initialize a call-back structure.

Parameters:
cb call-back to be initialized.
Examples:
eg_min_cut.ex.c.

Definition at line 139 of file eg_min_cut.h.

#define EGalgMCedgeClear (  E   )     EGsrkEdgeClear(&((E)->edge))
 

Clear any internal memory (not allocated by the user) used by this structure.

Parameters:
E node to be cleared
Examples:
eg_min_cut.ex.c.

Definition at line 203 of file eg_min_cut.h.

#define EGalgMCedgeInit (  E   ) 
 

Value:

({\
  EGalgMCedge_t*const _EGalgMCe = (E);\
  EGsrkEdgeInit(&(_EGalgMCe->edge));\
  _EGalgMCe->id = UINT_MAX;})
Initialize an edge structure for use.

Parameters:
E edge to be initialized
Examples:
eg_min_cut.ex.c.

Definition at line 194 of file eg_min_cut.h.

#define EGalgMCgraphClear (  Graph   ) 
 

Value:

({\
  EGsrkGraphClear(&((Graph)->G));\
  EGlpNumClearVar((Graph)->epsilon);\
  EGlpNumClearVar((Graph)->cut_val);})
Clear internal memory (not allocated by the user) of a graph structure.

Parameters:
Graph graph to be cleared.
Examples:
eg_min_cut.ex.c.

Definition at line 263 of file eg_min_cut.h.

#define EGalgMCgraphInit (  Graph   ) 
 

Value:

({\
  EGalgMCgraph_t*const _EGalgMCg = (Graph);\
  EGsrkGraphInit(&(_EGalgMCg->G));\
  EGlpNumInitVar(_EGalgMCg->epsilon);\
  EGlpNumZero(_EGalgMCg->epsilon);\
  EGlpNumInitVar(_EGalgMCg->cut_val);\
  EGlpNumZero(_EGalgMCg->cut_val);\
  _EGalgMCg->cut_sz = 0;\
  EGeListInit(_EGalgMCg->lvl_list);\
  EGeListInit(_EGalgMCg->lvl_list+1);\
  EGeListInit(_EGalgMCg->lvl_list+2);\
  EGeListInit(_EGalgMCg->lvl_list+3);\
  EGeListInit(_EGalgMCg->lvl_list+4);\
  _EGalgMCg->cut = 0;\
  _EGalgMCg->all_nodes = 0;\
  _EGalgMCg->all_edges = 0;})
Initialize a graph structure for use.

Parameters:
Graph graph to be initialized
Examples:
eg_min_cut.ex.c.

Definition at line 242 of file eg_min_cut.h.

#define EGalgMCidentifyNodes (  Graph,
N,
M   ) 
 

Value:

({\
  EGalgMCgraph_t*const _EGalgMCg = (Graph);\
  EGalgMCnode_t*const _EGalgMCn = (N), *const _EGalgMCm = (M);\
  MESSAGE(__MC_DEBUG_,"Shrinking nodes with weight %lf %lf", \
          EGlpNumToLf(_EGalgMCn->node.weight), \
          EGlpNumToLf(_EGalgMCm->node.weight));\
  EGsrkIdentifyNodes(&(_EGalgMCg->G), &(_EGalgMCn->node), &(_EGalgMCm->node));\
  if(_EGalgMCn->lvl < 5)\
  {\
    EGeListDel(&(_EGalgMCm->lvl_cn));\
    EGeListMoveAfter(&(_EGalgMCn->lvl_cn), _EGalgMCg->lvl_list);\
  }\
  else EGeListAddAfter(&(_EGalgMCn->lvl_cn), _EGalgMCg->lvl_list);\
  _EGalgMCn->lvl = 0;})
Shrink two nodes in the graph, and update internal structures.

Parameters:
Graph current graph.
N node to keep in graph.
M node to shrink within N.

Definition at line 273 of file eg_min_cut.h.

#define EGalgMCnodeClear (  N   )     EGsrkNodeClear(&((N)->node))
 

Clear any internal memory (not allocated by the user) used by this structure.

Parameters:
N node to be cleared
Examples:
eg_min_cut.ex.c.

Definition at line 180 of file eg_min_cut.h.

#define EGalgMCnodeInit (  N   ) 
 

Value:

({\
  EGalgMCnode_t*const _EGalgMCn = (N);\
  EGsrkNodeInit(&(_EGalgMCn->node));\
  _EGalgMCn->lvl_cn = (EGeList_t){0,0};\
  _EGalgMCn->lvl = 0;\
  _EGalgMCn->id = UINT_MAX;\
  _EGalgMCn->new_id = UINT_MAX;\
  _EGalgMCn->hit = 0;})
Initialize a node structure for use.

Parameters:
N node to be initialized
Examples:
eg_min_cut.ex.c.

Definition at line 167 of file eg_min_cut.h.

#define EGalgMCprofile
 

If profiling is enable (i.e. __MC_PROFILE_ <= DEBUG), print some profiling information of the min cut used up to now, and reset all internal counters to zero, if profiling is not enabled, nothing happen.

Examples:
eg_min_cut.ex.c.

Definition at line 106 of file eg_min_cut.h.

#define UPDATE (  counter   ) 
 

variables and macros to do the profiling for the algorithm, it include counting the impact of all shrinking steps, the number of improvements cuts found along the way, and how many times where the main functions called.

Definition at line 39 of file eg_min_cut.c.

Typedef Documentation

typedef struct EGalgMCcbk_t EGalgMCcbk_t
 

Call-back structure for use when an improving minimum cut is found.

typedef int(* EGalgMCdo_f)(EGlpNum_t, const unsigned int, const unsigned int *const, void *)
 

Call-back function, it receives as input the weight of the cut, the size of the newly found cut, an array containing the cut (of length at least the number of elements in the cut) as integers (as defined by the EGalgMCnode_t::id field), and a pointer to some internal data (as stored in EGalgMCcbk_t::param). The function should return zero on success, and non-zero if an error ocours, this error will be propagated through the calling functions.

Definition at line 118 of file eg_min_cut.h.

typedef struct EGalgMCedge_t EGalgMCedge_t
 

Edge structure for the Minimum Cut.

typedef struct EGalgMCgraph_t EGalgMCgraph_t
 

Graph Structure for Minimum Cut.

Note that this structure also holds some parameters as the epsilon to use in the comparisons, the current best cut found (or bound), and the current cut found so-far. As well as an array containing all edges and nodes in thee graph (remember that when we Identify two nodes, we loose any reference to the shrinked node in the graph structure as discussed in EGsrkIdentifyNodes )

typedef struct EGalgMCnode_t EGalgMCnode_t
 

Node structure for Minimum Cut.

typedef struct mc_all_cuts_t mc_all_cuts_t
 

structure to store a set of cuts

Function Documentation

int EGalgMC (  EGalgMCgraph_t *const   G,
EGalgMCcbk_t *const   cb,
const unsigned int  max_lvl
) 
 

Compute a minimum cut on the given graph.

Parameters:
max_lvl set a limit on wich tests to perform during the Padberg-Rinaldy shrinking step. for example, if set to 1, only the first and second tests will be carried out.
G graph over wich we are working.
cb call back structure to use (if set to NULL it is not used).
Returns:
zero on success, non-zero otherwise.
This function takes as input a graph, and perform the minimum cut algorithm as described in the paper "An Efficient Algorithm For The Minimum Capacity Cut Problem", Mathematical Programming 47 (1990) pages 19-36.

Note that the graph should have all fields properly initialized.

Examples:
eg_min_cut.ex.c.

Definition at line 655 of file eg_min_cut.c.

Here is the call graph for this function:

static int EGalgMCbuildPRgraph (  EGalgMCgraph_t *const   mcG,
EGalgPRgraph_t *const   prG,
EGalgMCnode_t **const   node_map,
EGalgPRnode_t *const   all_pr_nodes,
EGalgPRedge_t *const   all_pr_edges
)  [inline, static]
 

Given a current min cut graph, build a Push-Relabel graph.

Parameters:
mcG pointer to the min cut graph.
prG pointer to the push-relabel graph, it should be previously initialized.
node_map array of mappings for nodes in the push-relabel graph, to nodes in the min cut graph. It's size should be at least n_nodes.
all_pr_nodes array containing nodes to use in the push-relabel graph, all elements should be already initialized, and the array should be of size at least n_nodes.
all_pr_edges array contaaining edges to use in the push-relabel graph, all elements should be initialized, and the array should be of size at least n_edges.
Returns:
zero on success, non-zero otherwise.

Definition at line 510 of file eg_min_cut.c.

static int EGalgMCcomputeT (  EGalgPRgraph_t *const   prG,
EGalgPRnode_t *const   S,
EGalgPRnode_t **const   T
)  [inline, static]
 

Compute the farthest node in the push-relabel graph from the given starting point.

Parameters:
prG push relabel graph.
S source node.
T where to store the farthest node.
Returns:
zero on success, non-zero otherwise

Definition at line 594 of file eg_min_cut.c.

static int EGalgMCexpandNode (  unsigned int *const   cut,
EGalgMCnode_t *const   N
)  [inline, static]
 

Expand all nodes shrinked within a node, and store their id-s (EGalgMCnode_t::id) in the given array (including the node itself ).

Parameters:
cut array where to store the cut (its size should be at least EGsrkNode_t::mmb_sz + 1).
N node to expand.
Returns:
zero on success, non-zero otherwise.

Definition at line 50 of file eg_min_cut.c.

int EGalgMCidentifyPRedges (  EGalgMCgraph_t *const   G,
EGalgMCcbk_t *const   cb,
const unsigned int  max_lvl
) 
 

Identify all Padberg and Rinaldy edges. i.e. shrink all edges that satisfy the conditions in their paper. we choose to make tests over pair of nodes linked by an edge.

Parameters:
max_lvl set a limit on wich tests to perform. for example, if set to 1, only the first and second tests will be carried out.
G graph over wich we are working.
cb call back structure to use (if set to NULL it is not used).
Returns:
zero on success, non-zero otherwise.
Note that while doing this identification process, we update the values of EGalgMCgraph_t::cut, EGalgMCgraph_t::cut_sz and EGalgMCgraph_t::cut_val, as well as performing the actual shrinking procedure.

The original theorem (for local conditions on shrinking) is the following: Let $ Z $ be a proper subset of $ V $ (the set of all nodes in the graph), $ |Z|\geq2 $ , and let

\[ P(Z) = \bigcup\left\{ N(u)\cap N(v):u\neq v, u,v\in Z \right\} \]

where $ N(u) $ if the set of neighbours of $ u $ . If there exists $ Y\subseteq P(Z) $ such that for every nonempty proper subset $ W $ of $ Z $ and for every $ T\subseteq Y $ either:

  1. $ w(\delta(W))/2 \leq w(W:(Y-T)+(Z-W)) $ or
  2. $ w(\delta(Z-W))/2 \leq w(Z-W:T+W) $ . Then there exists a minimum cut $(X:V-X)$ such that either $ Z\subseteq X $ or $ X\subseteq Z $ .

And the original theorem (in fact is the corollary 3.5 in the paper) regarding global conditions for shrinking is the following: Let $ u\neq v\in V $ , and let $ q $ be an upper bound on the minimum cut value, and $ lb_{uv} $ be a lower bound in the value of a minimum $ u-v $ cut, then if $ lb_{uv}\geq q $ the set $ \{u,v\} $ is shrinkable.

The actual tests that we perform (for every edge) are the following:

  1. If $ w(\delta(u)) < $ EGalgMCgraph_t::cut_val, update the minimum cut value and set.
  2. If $ w_{uv} \geq \min\{w(\delta(u)),w(\delta(v))\}/2 $ then we can safely shrink edge $ uv $ .
  3. If we have a triangle $ uv,\quad vw,\quad wu $ , with $ w_{uv} + w_{vw} \geq w(\delta(v))/2 $ and $ w_{uw} + w_{vw} \geq w(\delta(w))/2 $ then we can safely shrink edge $ wv $ .
  4. Compute lower bound on the cut that separates the endpoints of the current edge as :

    \[ lb_{uv}=w_{uv}+\sum\limits_{w\in N(u)\cap N(v)}\min\{w_{uw},w_{vw}\} \]

    If $ lb_{uv} \geq $ EGalgMCgraph_t::cut_val , then we can shrink the edge $ uv $ .

  5. Consider the edge $ uv $ and two common neighbours $ x,y $ . If $ w_{ux} + w_{uy} + w_{uv} \geq w(\delta(u))/2 $ and $ w_{vx} + w_{vy} + w_{vu} \geq w(\delta(v))/2 $ and at least one of $ w_{uv} + w_{uy} \geq w(\delta(u))/2 $ and $ w_{uv} + w_{vx} \geq w(\delta(v))/2 $ and at least one of $ w_{uv} + w_{ux} \geq w(\delta(u))/2 $ and $ w_{uv} + w_{vy} \geq w(\delta(v))/2 $ then we can safely shrink edge $ uv $ .

We make thiese tests in order, i.e. first we perform all level 1 tests, then level2, and so on, and whenever two nodes are Identify (shrinked) we set the level of the node to 1 (i.e. in the next test we will test the first condition). This is done using an array of (5) lists, where all nodes are distributed. Originally all nodes should be in the first lists (i.e. all nodes should be tested to improve the current best cut by themselves).

Definition at line 153 of file eg_min_cut.c.

Here is the call graph for this function:

static int EGalgMCtestNode (  EGalgMCgraph_t *const   G,
EGalgMCcbk_t *const   cb,
EGalgMCnode_t *const   N
)  [inline, static]
 

Given a node, test if the node is a better cut (by itself) then the currently found, and if so, update the current best cut, and call the callback if it is non-NULL.

Parameters:
G current min-cut graph.
cb callback structure.
N node to test.
Returns:
zero on success, non-zero otherwise.

Definition at line 75 of file eg_min_cut.c.

Here is the call graph for this function:

int main (  int  argc,
char **  argv
) 
 

example of usage of the Min Cut algorithm as implemented in (EGalgMinCut).

We read 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 algorithm, and compute the minimum global cut.

Definition at line 139 of file eg_min_cut.ex.c.

Here is the call graph for this function:

static int mc_parseargs (  int  argc,
char **  argv
)  [inline, static]
 

parse input

Examples:
eg_min_cut.ex.c.

Definition at line 100 of file eg_min_cut.ex.c.

Here is the call graph for this function:

int mc_store_cuts (  EGlpNum_t  value,
const unsigned int  c_sz,
const unsigned int *const   cut,
void *  data
) 
 

call-back function to store all cuts fund during the execution of the min-cut algorithm.

Examples:
eg_min_cut.ex.c.

Definition at line 55 of file eg_min_cut.ex.c.

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

display usage of this program

Examples:
eg_min_cut.ex.c.

Definition at line 32 of file eg_min_cut.ex.c.

Variable Documentation

char* file_name = 0 [static]
 

Examples:
eg_eheap.ex.c.

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

unsigned int lvl = 5 [static]
 

Examples:
eg_min_cut.ex.c.

Definition at line 29 of file eg_min_cut.ex.c.

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