Package com.luciad.network.algorithm.partitioning

Class 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 Details

    • 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 Details

    • 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

      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:

    • 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.