com.luciad.network.algorithm.partitioning

Graph and Routing EngineClass TLcdClusteredPartitioningAlgorithm

java.lang.Object

com.luciad.network.algorithm.partitioning.TLcdClusteredPartitioningAlgorithm

All Implemented Interfaces:

ILcdPartitioningAlgorithm

public class TLcdClusteredPartitioningAlgorithm
extends 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(Random aRandom) Constructs a new TLcdClusteredPartitioningAlgorithm.

Method Summary

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, 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, 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, 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(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:

IllegalArgumentException - if aNrIterations < 1

See Also:

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.

See Also:

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,
                                                 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:

NullPointerException - if one of the arguments is null.

partition

public <N,E> ILcdPartitionedGraph<N,E> partition(ILcdGraph<N,E> aGraph,
                                                 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,
                                                 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:

NullPointerException - if one of the arguments is null.