|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--AbstractCCAHeuristic | +--CycleCountHeuristic
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.
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 |
public CycleCountHeuristic()
public CycleCountHeuristic(Yutsis y)
y
- the Yutsis object for which an operation has to be chosenYutsis
public CycleCountHeuristic(Yutsis y, CycleGenerator cg)
y
- the Yutsis object for which an operation has to be chosencg
- the cycle generator containing the relevant cycles of yYutsis
,
CycleGenerator
Method Detail |
public void setProblem(Yutsis y, CycleGenerator cg)
setProblem
in interface CCAHeuristic
setProblem
in class AbstractCCAHeuristic
y
- the Yutsis object for which an operation has to be chosencg
- the cycle generator containing the relevant cycles of yYutsis
,
CycleGenerator
public Cycle bestCycle(int[] bestcycleedge, int[] besticnodes, java.util.ArrayList candidates)
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.
bestcycleedge
- array where the best edge to be interchanged
out of the Cycle
will be filled inbesticnodes
- array where the best icnodes will be filled incandidates
- ArrayList which will be filled with equivalent
operations, the first corresponds to the returned
best Cycle.
Cycle
public int strategy()
#MORE_SMALLER_LESS_BIGGER
,
#CYCLE_COUNT
public void setStrategy(int strategy)
strategy
- the chosen strategy#MORE_SMALLER_LESS_BIGGER
,
#CYCLE_COUNT
public java.util.ArrayList[][] effect(int e1, int e2, int a, int b)
(e1,e2)
interchanging the edges
(e1,a)
and (e2,b)
, assuming that
the girth of y
is at least 4.
e1
- endpoint of the base edge of the interchangee2
- endpoint of the base edge of the interchangea
- endpoint of the edge (e1, a) to be interchangedb
- endpoint of the edge (e2, b) to be interchanged
public void printEffect(int e1, int e2, int a, int b, java.io.PrintStream out)
(e1,e2)
interchanging the edges
(e1,a)
and (e2,b)
, assuming that
the girth of y
is at least 4 to the given PrinStream.
e1
- endpoint of the base edge of the interchangee2
- endpoint of the base edge of the interchangea
- endpoint of the edge (e1, a) to be interchangedb
- endpoint of the edge (e2, b) to be interchangedout
- the PrintStream where the output wil be writtenpublic void printEffect(int e1, int e2, int a, int b)
(e1,e2)
interchanging the edges
(e1,a)
and (e2,b)
, assuming that
the girth of y
is at least 4 to System.out.
e1
- endpoint of the base edge of the interchangee2
- endpoint of the base edge of the interchangea
- endpoint of the edge (e1, a) to be interchangedb
- endpoint of the edge (e2, b) to be interchanged
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |