Graph Structure for Minimum Cut. More...

#include <eg_min_cut.h>

Collaboration diagram for EGalgMCgraph_t:

Data Fields
EGalgMCedge_t *	all_edges
EGalgMCnode_t *	all_nodes
unsigned int *	cut
unsigned int	cut_sz
EGlpNum_t	cut_val
EGlpNum_t	epsilon
EGsrkGraph_t	G
EGeList_t	lvl_list [5]

Detailed Description

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 )

Examples:: eg_min_cut.ex.c.

Definition at line 198 of file eg_min_cut.h.

Field Documentation

EGalgMCedge_t* EGalgMCgraph_t::all_edges

Array containing all edges of the graph.

Examples:: eg_min_cut.ex.c.

Definition at line 218 of file eg_min_cut.h.

Referenced by main().

EGalgMCnode_t* EGalgMCgraph_t::all_nodes

Array containing all nodes of the graph.

Examples:: eg_min_cut.ex.c.

Definition at line 217 of file eg_min_cut.h.

Referenced by main().

unsigned int* EGalgMCgraph_t::cut

Array storing the current cut, the size of this array should be at least EGsrkGraph_t::n_onodes

Examples:: eg_min_cut.ex.c.

Definition at line 214 of file eg_min_cut.h.

Referenced by EGalgMCtestNode(), and main().

unsigned int EGalgMCgraph_t::cut_sz

number of nodes in the current best cut, if set to zero, then no cut has been found (so far)

Definition at line 210 of file eg_min_cut.h.

Referenced by EGalgMCtestNode().

EGlpNum_t EGalgMCgraph_t::cut_val

if EGalgMCgraph_t::cut_sz is not zero, then this is the value of the (currenlty) best minimum cut found so far. otherwise is a bound on the value of the minimum cut (note that this value should be set before actually computing the minimum cut, and can be set to the value of $\delta(v)$ for some node v in the graph.