2021.1.15

## Graph and Routing EngineClass TLcdClusteredPartitioningAlgorithm

• java.lang.Object
• All Implemented Interfaces:
ILcdPartitioningAlgorithm

```public class TLcdClusteredPartitioningAlgorithm
extends java.lang.Object
implements ILcdPartitioningAlgorithm```
Implementation of a partitioning algorithm. The resulting partitioning scheme is optimized for the partitioned routing algorithm: the algorithm tries to find a partitioning scheme that minimizes the average total number of edges that is to be evaluated by the partitioned routing algorithm when calculating a route.

In practice, this means that:

• strongly connected parts of the graph will be kept together in one partition.
• if the variation in connectivity is only small, the resulting partitions will be more or less equal in size (number of edges and nodes).

The algorithm can be configured with the following parameters:

• Number of iterations: The algorithm requires a random number input, which influences the quality of the result. The algorithm will therefore perform multiple runs and will choose the best result. The larger the number of iterations, the higher the chances that a good result will be found.
• Alpha: the average fraction of evaluated edges by the A* algorithm. This number depends on the properties of the graph but is difficult to compute. The larger `alpha`, the larger the partitions (and thus the smaller the number of partitions) will be. Typical values for `alpha` are between 0.2 and 0.6. If no `alpha` value is provided, the algorithm will by default use `alpha=0.3`. It might be necessary to experiment with several values for `alpha` in order to obtain a good result.
Since:
5.1
• ### Constructor Summary

Constructors
Constructor and Description
`TLcdClusteredPartitioningAlgorithm()`
Constructs a new `TLcdClusteredPartitioningAlgorithm`.
`TLcdClusteredPartitioningAlgorithm(java.util.Random aRandom)`
Constructs a new `TLcdClusteredPartitioningAlgorithm`.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`int` `getNrIterations()`
Returns the number of iterations that is done for each partitioning.
`<N,E> ILcdPartitionedGraph<N,E>` `partition(ILcdGraph<N,E> aGraph)`
Returns a partitioned copy of the given graph.
`<N,E> ILcdPartitionedGraph<N,E>` ```partition(ILcdGraph<N,E> aGraph, java.util.Vector<E> aConstraintedEdges)```
Returns a partitioned copy of the given graph, but keeps each of the constrainted edges within one partition (none of the constrainted edges will become a boundary edge).
`<N,E> ILcdPartitionedGraph<N,E>` ```partition(ILcdGraph<N,E> aGraph, java.util.Vector<E> aConstraintedEdges, double aAlpha)```
Returns a partitioned copy of the given graph, but keeps each of the constrainted edges within one partition (none of the constrainted edges will become a boundary edge).
`<N,E> ILcdPartitionedGraph<N,E>` ```partition(ILcdGraph<N,E> aGraph, java.util.Vector<E> aConstraintedEdges, int aMaxNrPartitioningLevels, int aNrEdgesThreshold, int aMinPartitions, int aMaxPartitions)```
Returns a partitioned copy of the given graph, taking into account the specified constraints.
`void` `setNumberOfIterations(int aNrIterations)`
Sets the number of iterations that should be done for each partitioning.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### TLcdClusteredPartitioningAlgorithm

`public TLcdClusteredPartitioningAlgorithm()`
Constructs a new `TLcdClusteredPartitioningAlgorithm`.
• #### TLcdClusteredPartitioningAlgorithm

`public TLcdClusteredPartitioningAlgorithm(java.util.Random aRandom)`
Constructs a new `TLcdClusteredPartitioningAlgorithm`.
Parameters:
`aRandom` - the random number generator to be used by this algorithm.
• ### Method Detail

• #### setNumberOfIterations

`public void setNumberOfIterations(int aNrIterations)`
Sets the number of iterations that should be done for each partitioning. The default value is 2.
Parameters:
`aNrIterations` - the number of iterations that should be done for each partitioning.
Throws:
`java.lang.IllegalArgumentException` - if `aNrIterations < 1`.
`getNrIterations()`
• #### getNrIterations

`public int getNrIterations()`
Returns the number of iterations that is done for each partitioning.
Returns:
the number of iterations that is done for each partitioning.
`setNumberOfIterations(int)`
• #### partition

`public <N,E> ILcdPartitionedGraph<N,E> partition(ILcdGraph<N,E> aGraph)`
Returns a partitioned copy of the given graph.

If this method does not provide a suitable result, one can consider using the other partition methods which allow providing extra input parameters to the algorithm.

Specified by:
`partition` in interface `ILcdPartitioningAlgorithm`
Parameters:
`aGraph` - the graph to be partitioned.
Returns:
a partitioned copy of the given graph.
• #### partition

```public <N,E> ILcdPartitionedGraph<N,E> partition(ILcdGraph<N,E> aGraph,
java.util.Vector<E> aConstraintedEdges)```
Returns a partitioned copy of the given graph, but keeps each of the constrainted edges within one partition (none of the constrainted edges will become a boundary edge).

If this method does not provide a suitable result, one can consider using the other partition methods which allow providing extra input parameters to the algorithm.

Parameters:
`aGraph` - the graph to be partitioned.
`aConstraintedEdges` - the edges prohibited to become boundary edges in the partitioned graph.
Returns:
a partitioned copy of the given graph.
Throws:
`java.lang.NullPointerException` - if one of the arguments is `null`.
• #### partition

```public <N,E> ILcdPartitionedGraph<N,E> partition(ILcdGraph<N,E> aGraph,
java.util.Vector<E> aConstraintedEdges,
int aMaxNrPartitioningLevels,
int aNrEdgesThreshold,
int aMinPartitions,
int aMaxPartitions)```
Returns a partitioned copy of the given graph, taking into account the specified constraints. For large graphs, this method might return a multi-leveled partitioned graph.

This algorithm will try to find a solution by experimenting with different values of alpha, using an iterative approach. It can therefore take much more time than a partitioning with a fixed alpha value.

Parameters:
`aGraph` - the graph to be partitioned.
`aConstraintedEdges` - the edges prohibited to become boundary edges in the partitioned graph.
`aMaxNrPartitioningLevels` - the maximum number of partitioning levels.
`aNrEdgesThreshold` - the minimum number of edges a graph should have before being further partitioned.
`aMinPartitions` - the minimal number of partitions in a graph, in addition to the natural partitions (that is, the partitions that are naturally formed by converting each non-connected subgraph of graph into a partition.)
`aMaxPartitions` - the maximal number of partitions in a graph, in addition to the natural partitions
Returns:
partitioned (possibly multileveled) copy of the given graph. If the algorithm was not able to find a solution within the specified constraints, it will return the best result that was found.
• #### partition

```public <N,E> ILcdPartitionedGraph<N,E> partition(ILcdGraph<N,E> aGraph,
java.util.Vector<E> aConstraintedEdges,
double aAlpha)```
Returns a partitioned copy of the given graph, but keeps each of the constrainted edges within one partition (none of the constrainted edges will become a boundary edge).

This method provides direct access to the alpha factor, that influences the number of partitions the algorithm will create.

Parameters:
`aGraph` - the graph to be partitioned.
`aConstraintedEdges` - the edges prohibited to become boundary edges in the partitioned graph.
`aAlpha` - the alpha factor.
Returns:
a partitioned copy of the given graph.
Throws:
`java.lang.NullPointerException` - if one of the arguments is `null`.