Data Structures | Files | Defines | Typedefs | Functions | Variables

EGalgMinCut

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

Files

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

Defines

#define __MC_DEBUG_   100
 Level of profiling in the code.
#define __MC_PROFILE_   0
 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)   (counter)++

Typedefs

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.
typedef struct EGalgMCedge_t EGalgMCedge_t
 Edge structure for the Minimum Cut.
typedef struct EGalgMCgraph_t EGalgMCgraph_t
 Graph Structure for Minimum Cut.
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

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 unsigned long long __MC_profile_lvl [5] = { 0, 0, 0, 0, 0 }
 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.
static unsigned long long __MC_profile_tn = 0
static unsigned long long __MC_profile_up = 0
static char * file_name = 0
static unsigned int lvl = 5



void EGalgMCprofile (void)

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:
  • 2005-08-19
    • While computing a minimum S-T cut, choose S randomly. and T as a node at maximum distance (number of edges) from S.
    • Fix small problem with shrinking level 4
  • 2005-06-20
    • First Implementation.

Define Documentation

#define __MC_DEBUG_   100

Level of profiling in the code.

Definition at line 78 of file eg_min_cut.h.

Referenced by EGalgMCtestNode().

#define __MC_PROFILE_   0

Level of profiling in the code.

Definition at line 82 of file eg_min_cut.h.

#define __MC_VRBLVL_   100

Verbosity Level.

Definition at line 74 of file eg_min_cut.h.

Referenced by EGalgMCbuildPRgraph(), EGalgMCcomputeT(), and EGalgMCtestNode().

#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 135 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 154 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 132 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 122 of file eg_min_cut.h.

Referenced by main().

#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 186 of file eg_min_cut.h.

Referenced by main().

#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 177 of file eg_min_cut.h.

Referenced by main().

#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 246 of file eg_min_cut.h.

Referenced by main().

#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 225 of file eg_min_cut.h.

Referenced by main().

#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 256 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 163 of file eg_min_cut.h.

Referenced by main().

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

Referenced by main().

#define UPDATE (   counter  )     (counter)++

Definition at line 50 of file eg_min_cut.c.

Referenced by EGalgMCtestNode().

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

Referenced by main().

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 523 of file eg_min_cut.c.

References __MC_VRBLVL_, EGalgPRedge_t::bw, EGalgPRse_t::e, EGsrkEdge_t::edge, EGalgMCedge_t::edge, EGeUgraphNode_t::edges, EGalgPRedgeReset, EGalgPRgraphReset, EGalgPRnodeReset, EGcontainerOf, EGeDgraphAddEdge, EGeDgraphAddNode, EGeUgraphEdge_t::ep, EGalgPRedge_t::fw, EGalgPRgraph_t::G, EGsrkGraph_t::G, EGalgMCgraph_t::G, MESSAGE, EGeUgraph_t::n_edges, EGeUgraph_t::n_nodes, EGalgMCnode_t::new_id, EGeList_t::next, EGeUgraphEP_t::node, EGsrkNode_t::node, EGalgMCnode_t::node, EGeUgraph_t::nodes, TESTG, EGeUgraphEP_t::type, EGalgPRnode_t::v, and EGsrkEdge_t::weight.

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 607 of file eg_min_cut.c.

References __MC_VRBLVL_, EGalgPRnode_t::d, EGalgPRse_t::e, EGcontainerOf, EGeListAddAfter, EGeListDel, EGeListInit, EGeListIsEmpty, EGalgPRgraph_t::G, EGeDgraphEdge_t::head, EGalgPRnode_t::LVL_list, MESSAGE, EGeList_t::next, EGeDgraph_t::nodes, and EGeList_t::prev.

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 63 of file eg_min_cut.c.

References EGcontainerOf, EGalgMCnode_t::id, EGsrkNode_t::members, EGsrkNode_t::mmb_sz, EGeList_t::next, and EGalgMCnode_t::node.

Referenced by EGalgMCtestNode().

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

void EGalgMCprofile ( void   ) 

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.

Referenced by main().

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 88 of file eg_min_cut.c.

References __MC_DEBUG_, __MC_profile_tn, __MC_profile_up, __MC_VRBLVL_, CHECKRVALG, EGalgMCgraph_t::cut, EGalgMCgraph_t::cut_sz, EGalgMCgraph_t::cut_val, EGalgMCcbk_t::cutoff, EGalgMCcbk_t::do_fn, EGalgMCexpandNode(), EGfree, EGsMalloc, EGsrkGraph_t::G, EGalgMCgraph_t::G, EGalgMCnode_t::id, MESSAGE, EGsrkNode_t::mmb_sz, EGeUgraph_t::n_edges, EGeUgraph_t::n_nodes, EGalgMCnode_t::node, EGalgMCcbk_t::param, TESTL, UPDATE, and EGsrkNode_t::weight.

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 136 of file eg_min_cut.ex.c.

References EGalgMCgraph_t::all_edges, EGalgMCgraph_t::all_nodes, CHECKRVALG, mc_all_cuts_t::cut, EGalgMCgraph_t::cut, mc_all_cuts_t::cut_sz, mc_all_cuts_t::cut_val, EGalgMCgraph_t::cut_val, EGalgMCcbk_t::cutoff, EGalgMCcbk_t::do_fn, EGalgMCedge_t::edge, EGalgMC(), EGalgMCcbkInit, EGalgMCedgeClear, EGalgMCedgeInit, EGalgMCgraphClear, EGalgMCgraphInit, EGalgMCnodeClear, EGalgMCnodeInit, EGalgMCprofile(), EGalgPRprofile(), EGeListAddAfter, EGfree, EGioClose(), EGioGets(), EGioNParse(), EGioOpen(), EGlib_info(), EGlib_version(), EGlpNumClear(), EGlpNumStart(), EGsetLimits(), EGsigSet, EGsMalloc, EGsrkAddEdge, EGsrkAddNode, EGtimerReset, EGtimerStart, EGtimerStop, EGalgMCgraph_t::epsilon, file_name, EGalgMCgraph_t::G, EGalgMCedge_t::id, EGalgMCnode_t::id, lvl, EGalgMCnode_t::lvl_cn, EGalgMCgraph_t::lvl_list, mc_all_cuts_t::max_sz, mc_parseargs(), mc_usage(), EGsrkGraph_t::n_oedges, EGsrkGraph_t::n_onodes, EGalgMCnode_t::node, EGalgMCcbk_t::param, mc_all_cuts_t::sz, TESTG, EGtimer_t::time, EGsrkNode_t::weight, and EGsrkEdge_t::weight.

Here is the call graph for this function:

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

parse input

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

References file_name, lvl, and mc_usage().

Referenced by main().

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 52 of file eg_min_cut.ex.c.

References mc_all_cuts_t::cut, mc_all_cuts_t::cut_sz, mc_all_cuts_t::cut_val, EGfree, EGsMalloc, mc_all_cuts_t::max_sz, and mc_all_cuts_t::sz.

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

display usage of this program

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

Referenced by main(), and mc_parseargs().

Variable Documentation

unsigned long long __MC_profile_lvl[5] = { 0, 0, 0, 0, 0 } [static]

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.

shrinkings per level

Definition at line 33 of file eg_min_cut.c.

unsigned long long __MC_profile_tn = 0 [static]

Number of calls to EGalgMCtestNode

Definition at line 35 of file eg_min_cut.c.

Referenced by EGalgMCtestNode().

unsigned long long __MC_profile_up = 0 [static]

Number of improving cuts found

Definition at line 36 of file eg_min_cut.c.

Referenced by EGalgMCtestNode().

char* file_name = 0 [static]

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

unsigned int lvl = 5 [static]

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

Referenced by main(), and mc_parseargs().

Generated on Thu Mar 29 2012 10:10:31 for EGlib by  doxygen 1.7.1