Maximum edge cuts


Data Structures

class  branchMaxCut
 Branch & bound implementation for maximum edge cuts. More...

Enumerations

enum  abstractMixedGraph::TMethMaxCut {
  abstractMixedGraph::MAX_CUT_DEFAULT = -1,
  abstractMixedGraph::MAX_CUT_GRASP = 0,
  abstractMixedGraph::MAX_CUT_TREE = 1,
  abstractMixedGraph::MAX_CUT_TJOIN = 2
}

Functions

TFloat abstractGraph::MXC_Heuristic (TMethMaxCut method, TNode s=NoNode, TNode t=NoNode) throw (ERRange,ERRejected)
TFloat abstractGraph::MXC_HeuristicTree (TNode s=NoNode, TNode t=NoNode) throw (ERRange,ERRejected)
TFloat abstractGraph::MXC_DualTJoin (TNode s=NoNode) throw (ERRange,ERRejected)
TFloat abstractMixedGraph::MaxCut (TNode s=NoNode, TNode t=NoNode) throw (ERRange)
TFloat abstractMixedGraph::MaxCut (TMethMaxCut method, TNode s=NoNode, TNode t=NoNode) throw (ERRange)
TFloat abstractMixedGraph::MXC_LocalSearch (TNode *nodeColour, TNode s=NoNode, TNode t=NoNode) throw (ERRange,ERRejected)
virtual TFloat abstractMixedGraph::MXC_Heuristic (abstractMixedGraph::TMethMaxCut method, TNode s=NoNode, TNode t=NoNode) throw (ERRange,ERRejected)
TFloat abstractMixedGraph::MXC_HeuristicGRASP (TNode s=NoNode, TNode t=NoNode) throw (ERRange)
TFloat abstractMixedGraph::MXC_BranchAndBound (TNode s=NoNode, TNode t=NoNode, TFloat lowerBound=InfFloat) throw (ERRange)

Enumeration Type Documentation

enum TMethMaxCut [inherited]
 

Alternative methods for the maximum cut solver.

Enumerator:
MAX_CUT_DEFAULT  Apply the default method set in goblinController::methMaxCut.
MAX_CUT_GRASP  Apply the 1/2 approximating GRASP heuristic method.
MAX_CUT_TREE  Apply the tree heuristic method.
MAX_CUT_TJOIN  Apply the dual T-join method.

Function Documentation

TFloat MaxCut (  TMethMaxCut  method,
TNode  s = NoNode,
TNode  t = NoNode
)  throw (ERRange) [inherited]
 

Compute a maximum weight edge cut.

Parameters:
method A TMethMaxCut value specifying the applied construction heuristic
s A left-hand node index or NoNode
t A right-hand node index or NoNode
Returns:
The weight of the constructed edge cut
This is the public interface to all maximum edge cut methods. The resulting edge cut is provided by the node colour register. As for other NP-hard problem solvers, the procedure does the following:

TFloat MaxCut (  TNode  s = NoNode,
TNode  t = NoNode
)  throw (ERRange) [inherited]
 

Compute a maximum weight edge cut.

Parameters:
s A left-hand node index or NoNode
t A right-hand node index or NoNode
Returns:
The weight of the constructed edge cut

TFloat MXC_BranchAndBound (  TNode  s = NoNode,
TNode  t = NoNode,
TFloat  lowerBound = InfFloat
)  throw (ERRange) [protected, inherited]
 

Exact solution of the maximum weight edge cut problem.

Parameters:
s A left-hand node index or NoNode
t A right-hand node index or NoNode
lowerBound An initial bound for pruning the branch tree
Returns:
The weight of the improved edge cut
This implements a branch and bound scheme. But due to the poor problem relexation, it is basically enumeration.

TFloat MXC_DualTJoin (  TNode  s = NoNode  )  throw (ERRange,ERRejected) [protected, inherited]
 

Exact solution of the undirected planar maximum weight edge cut problem.

Parameters:
s A left-hand node index or NoNode
Returns:
The weight of the constructed edge cut
This determines a T-join in the undirected dual graph.

The procedure is restricted to non-negative edge lengths!

TFloat MXC_Heuristic (  abstractMixedGraph::TMethMaxCut  method,
TNode  s = NoNode,
TNode  t = NoNode
)  throw (ERRange,ERRejected) [protected, virtual, inherited]
 

Approximate maximum weight edge cut.

Parameters:
method A TMethMaxCut value specifying the applied method
s A left-hand node index or NoNode
t A right-hand node index or NoNode
Returns:
The weight of the constructed edge cut
In this base class implementation, MXC_HeuristicGRASP() is called.

TFloat MXC_Heuristic (  TMethMaxCut  method,
TNode  s = NoNode,
TNode  t = NoNode
)  throw (ERRange,ERRejected) [protected, inherited]
 

Approximate maximum weight edge cut.

Parameters:
method A TMethMaxCut value specifying the applied method
s A left-hand node index or NoNode
t A right-hand node index or NoNode
Returns:
The weight of the constructed edge cut
Depending on methMaxCut, this either calls MXC_HeuristicGRASP(), MXC_HeuristicTree() or MXC_DualTJoin().

TFloat MXC_HeuristicGRASP (  TNode  s = NoNode,
TNode  t = NoNode
)  throw (ERRange) [protected, inherited]
 

Approximate maximum weight edge cut by using a GRASP scheme.

Parameters:
s A left-hand node index or NoNode
t A right-hand node index or NoNode
Returns:
The weight of the constructed edge cut
This assigns colours to the nodes step by step. In each iteration, a candidate list with a few nodes is generated and from this list, an arbitrary node is chosen. Then, this node is always added to the most profitable component.

If the graph is undirected, the cut weight is at least 1/2 of the sum of arc weights.

If CT.methLocal==LOCAL_OPTIMIZE, MXC_LocalSearch() is called for postprocessing.

TFloat MXC_HeuristicTree (  TNode  s = NoNode,
TNode  t = NoNode
)  throw (ERRange,ERRejected) [protected, inherited]
 

Approximate maximum weight edge cut by using a maximum spanning tree.

Parameters:
s A left-hand node index or NoNode
t A right-hand node index or NoNode
Returns:
The weight of the constructed edge cut
This sets the bipartition according to a maximum weight spanning tree and the root node s. In particular, the graph must be connected. If methLocal==LOCAL_OPTIMIZE, MXC_LocalSearch() is called for postprocessing.

TFloat MXC_LocalSearch (  TNode *  nodeColour,
TNode  s = NoNode,
TNode  t = NoNode
)  throw (ERRange,ERRejected) [inherited]
 

Compute a maximum weight edge cut.

Parameters:
nodeColour A pointer to an array of node colours
s A left-hand node index or NoNode
t A right-hand node index or NoNode
Returns:
The weight of the improved edge cut
This considers the edge cut defined by the nodeColour[] array. For every node, it is checked if moving the node to the other partition subset increases the weight. If such nodes exist, the node which admits the biggest increase is moved (greedy strategy).