Package org.ddolib.ddo.core.heuristics.cluster

Class GHP<T>

java.lang.Object

org.ddolib.ddo.core.heuristics.cluster.GHP<T>

Type Parameters:

T - the type of states associated with the nodes

All Implemented Interfaces:

ReductionStrategy<T>

public class GHP<T>
extends Object
implements ReductionStrategy<T>

Generalized Hyperplane Partitioning (GHP) reduction strategy for decision diagram layers.

This class implements ReductionStrategy and clusters nodes in a layer using a distance-based partitioning method inspired by hyperplane separation. It requires a problem-specific StateDistance function to compute distances between states.

The GHP strategy works by:

1. Selecting two distant pivot nodes from the layer
2. Assigning each remaining node to the cluster of the closer pivot
3. Recursively splitting clusters until the desired number of clusters (maxWidth) is reached

A random number generator is used for tie-breaking and initial shuffling of the layer.

Constructor Summary

Constructors

Constructor	Description
GHP(StateDistance<T> distance)	Constructs a GHP reduction strategy with a default random seed.
GHP(StateDistance<T> distance, long seed)	Constructs a GHP reduction strategy with a specified random seed.

Method Summary

Modifier and Type	Method	Description
List<NodeSubProblem<T>>[]	defineClusters(List<NodeSubProblem<T>> layer, int maxWidth)	Partitions the given layer into clusters using Generalized Hyperplane Partitioning.
void	setSeed(long seed)	Sets the seed of the internal random number generator.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

GHP

public GHP(StateDistance<T> distance)

Constructs a GHP reduction strategy with a default random seed.

Parameters:

distance - the distance function used to compare states

GHP

public GHP(StateDistance<T> distance,
 long seed)

Constructs a GHP reduction strategy with a specified random seed.

Parameters:

distance - the distance function used to compare states

seed - the random seed

Method Details

setSeed

public void setSeed(long seed)

Sets the seed of the internal random number generator.

Parameters:

seed - the new seed value

defineClusters

public List<NodeSubProblem<T>>[] defineClusters(List<NodeSubProblem<T>> layer,
 int maxWidth)

Partitions the given layer into clusters using Generalized Hyperplane Partitioning.

The method recursively divides the layer by selecting pivot nodes and assigning nodes to the cluster of the closest pivot. All nodes in the layer are included in one of the resulting clusters, and the input layer is emptied.

Specified by:

defineClusters in interface ReductionStrategy<T>

Parameters:

layer - the list of nodes at the current layer

maxWidth - the desired number of clusters (maximum width after reduction)

Returns:

an array of clusters, each cluster being a list of nodes