Class CycleCountHeuristic

java.lang.Object
  |
  +--AbstractCCAHeuristic
        |
        +--CycleCountHeuristic
All Implemented Interfaces:
CCAHeuristic

public class CycleCountHeuristic
extends AbstractCCAHeuristic

This class implements two heuristics, MORE_SMALLER_LESS_BIGGER and CYCLE_COUNT, for selecting operations for reducing a Yutsis object bases on the difference in the number of cycles of each length created by the different interchanges.

The MORE_SMALLER_LESS_BIGGER heuristic works as follows: For each interchange reducing a girth cycle in length the number of cycles becoming smaller and bigger are calculated. Let g be the girth of the graph. The operation which reduces the maximum number of g-cycles is preferred. If this is equal the operation which increases the minimum number of g-cycles is preferred. If this is also equal, we repeat the comparison for (g+1)-cycles, ..., (g+k)-cycles until a difference is found.

The CYCLE_COUNT heuristic works as follows: For each interchange the number of cycles of each length in the graph resulting after applying the interchange are calculated. Let g be the girth of the graph after applying the considered interchange. The operation which yields the maximum number of g-cycles is preferred.If this is equal, we repeat the comparison for (g+1)-cycles, ..., (g+k)-cycles until a difference is found.

Author:
Dries.VanDyck@rug.ac.be
See Also:
AbstractCCAHeuristic, CCAHeuristic

Constructor Summary
CycleCountHeuristic()
          Default constructor: constructs a new CycleCountHeuristic object
CycleCountHeuristic(Yutsis y)
          Constructs a new CycleCountHeuristic object and sets the problem.
CycleCountHeuristic(Yutsis y, CycleGenerator cg)
          Constructs a new CycleCountHeuristic object and sets the problem.
 
Method Summary
 Cycle bestCycle(int[] bestcycleedge, int[] besticnodes, java.util.ArrayList candidates)
          This function returns the best Cycle to reduce and fills the best edge to interchange out of the cycle (min length 4) together with the best interchange nodes in a canonical way.
 java.util.ArrayList[][] effect(int e1, int e2, int a, int b)
          Calculates the effect of the interchange on the edge (e1,e2) interchanging the edges (e1,a) and (e2,b), assuming that the girth of y is at least 4.
 void printEffect(int e1, int e2, int a, int b)
          Prints the effect of the interchange on the edge (e1,e2) interchanging the edges (e1,a) and (e2,b), assuming that the girth of y is at least 4 to System.out.
 void printEffect(int e1, int e2, int a, int b, java.io.PrintStream out)
          Prints the effect of the interchange on the edge (e1,e2) interchanging the edges (e1,a) and (e2,b), assuming that the girth of y is at least 4 to the given PrinStream.
 void setProblem(Yutsis y, CycleGenerator cg)
          Sets the Yutsis object defining for which operations must be choosen, together with the CycleGenerator delivering the relevant cycles.
 void setStrategy(int strategy)
          Sets the strategy to compare the effect of interchanges.
 int strategy()
          Returns the current strategy to compare the effect of interchanges.
 
Methods inherited from class AbstractCCAHeuristic
bestCycle, bestCycle, canonicalIC, canonicalIC, cycleGenerator, interchangeNodes, problem, setProblem
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

CycleCountHeuristic

public CycleCountHeuristic()
Default constructor: constructs a new CycleCountHeuristic object


CycleCountHeuristic

public CycleCountHeuristic(Yutsis y)
Constructs a new CycleCountHeuristic object and sets the problem. This equivalent with calling the default constructor and setProblem afterwards.

Parameters:
y - the Yutsis object for which an operation has to be chosen
See Also:
Yutsis

CycleCountHeuristic

public CycleCountHeuristic(Yutsis y,
                           CycleGenerator cg)
Constructs a new CycleCountHeuristic object and sets the problem. This equivalent with calling the default constructor and setProblem afterwards.

Parameters:
y - the Yutsis object for which an operation has to be chosen
cg - the cycle generator containing the relevant cycles of y
See Also:
Yutsis, CycleGenerator
Method Detail

setProblem

public void setProblem(Yutsis y,
                       CycleGenerator cg)
Sets the Yutsis object defining for which operations must be choosen, together with the CycleGenerator delivering the relevant cycles.

Specified by:
setProblem in interface CCAHeuristic
Overrides:
setProblem in class AbstractCCAHeuristic
Parameters:
y - the Yutsis object for which an operation has to be chosen
cg - the cycle generator containing the relevant cycles of y
See Also:
Yutsis, CycleGenerator

bestCycle

public Cycle bestCycle(int[] bestcycleedge,
                       int[] besticnodes,
                       java.util.ArrayList candidates)
This function returns the best Cycle to reduce and fills the best edge to interchange out of the cycle (min length 4) together with the best interchange nodes in a canonical way. It will use a CycleGenerator to generate all relevant cycles.

Parameters:
bestcycleedge - array where the best edge to be interchanged out of the Cycle will be filled in
besticnodes - array where the best icnodes will be filled in
candidates - ArrayList which will be filled with equivalent operations, the first corresponds to the returned best Cycle.
Returns:
the best Cycle

strategy

public int strategy()
Returns the current strategy to compare the effect of interchanges. Possible values are BIGGERSMALLER and CYCLECOUNT.

See Also:
#MORE_SMALLER_LESS_BIGGER, #CYCLE_COUNT

setStrategy

public void setStrategy(int strategy)
Sets the strategy to compare the effect of interchanges. Possible values are BIGGERSMALLER (default) and CYCLECOUNT.

Parameters:
strategy - the chosen strategy
See Also:
#MORE_SMALLER_LESS_BIGGER, #CYCLE_COUNT

effect

public java.util.ArrayList[][] effect(int e1,
                                      int e2,
                                      int a,
                                      int b)
Calculates the effect of the interchange on the edge (e1,e2) interchanging the edges (e1,a) and (e2,b), assuming that the girth of y is at least 4.

Parameters:
e1 - endpoint of the base edge of the interchange
e2 - endpoint of the base edge of the interchange
a - endpoint of the edge (e1, a) to be interchanged
b - endpoint of the edge (e2, b) to be interchanged
Returns:
an array of array of ArrayLists; the first contains all cycles which become smaller, the second all cycles become bigger; both have at index l cycles of length l+4

printEffect

public void printEffect(int e1,
                        int e2,
                        int a,
                        int b,
                        java.io.PrintStream out)
Prints the effect of the interchange on the edge (e1,e2) interchanging the edges (e1,a) and (e2,b), assuming that the girth of y is at least 4 to the given PrinStream.

Parameters:
e1 - endpoint of the base edge of the interchange
e2 - endpoint of the base edge of the interchange
a - endpoint of the edge (e1, a) to be interchanged
b - endpoint of the edge (e2, b) to be interchanged
out - the PrintStream where the output wil be written

printEffect

public void printEffect(int e1,
                        int e2,
                        int a,
                        int b)
Prints the effect of the interchange on the edge (e1,e2) interchanging the edges (e1,a) and (e2,b), assuming that the girth of y is at least 4 to System.out.

Parameters:
e1 - endpoint of the base edge of the interchange
e2 - endpoint of the base edge of the interchange
a - endpoint of the edge (e1, a) to be interchanged
b - endpoint of the edge (e2, b) to be interchanged