ContactCenters
V. 0.9.9.

umontreal.iro.lecuyer.contactcenters.router
Class RoutingTableUtils

java.lang.Object
  extended by umontreal.iro.lecuyer.contactcenters.router.RoutingTableUtils

public final class RoutingTableUtils
extends Object

Provides some utility methods to manage routing tables represented using 2D arrays. Three types of routing tables are supported: type-to-group and group-to-type maps, incidence matrices and matrices of ranks. This class provides facilities to check the consistency of such routing tables, to generate one table from the other, and to format them as strings. However, converting from one routing table to another may destroy some information or force the conversion algorithm to infer information, which can lead to bad routing policies.


Method Summary
static void checkConsistency(int[][] typeToGroupMap, int[][] groupToTypeMap)
          Checks the consistency of the routing tables typeToGroupMap and groupToTypeMap.
static void checkGroupToTypeMap(int numTypes, int[][] groupToTypeMap)
          Applies a consistency check for the group-to-type map groupToTypeMap supporting K = numTypes contact types.
static void checkTypeToGroupMap(int numGroups, int[][] typeToGroupMap)
          Applies a consistency check for the type-to-group map typeToGroupMap supporting I = numGroups agent groups.
static String formatGroupToTypeMap(int[][] groupToTypeMap)
          Formats the group-to-type ordered lists as a string.
static String formatIncidence(boolean[][] m)
          Formats the incidence matrix m for each contact type and agent group.
static String formatOrderedList(int[] orderedList)
          Formats the ordered list orderedList as a string.
static String formatRanksGT(double[][] ranksGT)
          Formats the contact selection matrix of ranks ranksGT for each contact type and agent group.
static String formatRanksTG(double[][] ranksTG)
          Formats the agent selection matrix of ranks ranksTG for each contact type and agent group.
static String formatTypeToGroupMap(int[][] typeToGroupMap)
          Formats the type-to-group ordered lists as a string.
static String formatWeightsGT(double[][] weightsGT)
          Formats the contact selection weights matrix weightsGT for each contact type and agent group.
static String formatWeightsTG(double[][] weightsTG)
          Formats the agent selection weights matrix weightsTG for each contact type and agent group.
static int[][] getGroupToTypeMap(boolean[][] m)
          Constructs and returns a new group-to-type map from the incidence matrix m.
static int[][] getGroupToTypeMap(double[][] ranksGT)
          Generates a group-to-type map from the contact selection matrix of ranks ranksGT.
static int[][] getGroupToTypeMap(double[][] ranksGT, int[] typeRegions, int[] groupRegions)
          This method is similar to getGroupToTypeMap(double[][]) with a sorting algorithm adapted for the local-specialist policy.
static int[][] getGroupToTypeMap(int numGroups, int[][] typeToGroupMap)
          Generates the group-to-type map from the type-to-group map typeToGroupMap.
static boolean[][] getIncidenceFromGT(int numTypes, int[][] groupToTypeMap)
          Constructs and returns the incidence matrix from the groupToTypeMap with numTypes contact types.
static boolean[][] getIncidenceFromTG(int numGroups, int[][] typeToGroupMap)
          Constructs and returns the incidence matrix from the typeToGroupMap with numGroups agent groups.
static int[][][] getOverflowLists(double[][] ranksTG)
          Constructs and returns overflow lists from the given matrix of ranks ranksTG.
static double[][] getRanks(boolean[][] m, int[] skillCounts)
          Constructs a contact selection matrix of ranks from the incidence matrix m and skill counts skillCounts.
static double[][] getRanksFromGT(int numTypes, int[][] groupToTypeMap)
          Constructs the contact selection matrix of ranks from the groupToTypeMap with numTypes contact types.
static double[][] getRanksFromTG(int numGroups, int[][] typeToGroupMap)
          Constructs the agent selection matrix of ranks from the typeToGroupMap with numGroups agent groups.
static int[][] getTypeToGroupMap(boolean[][] m)
          Constructs and returns a new type-to-group map from the incidence matrix m.
static int[][] getTypeToGroupMap(double[][] ranksTG)
          Generates a type-to-group map from the agent selection matrix of ranks ranksTG.
static int[][] getTypeToGroupMap(double[][] ranksTG, int[] typeRegions, int[] groupRegions)
          This method is similar to getTypeToGroupMap(double[][]) with a sorting algorithm adapted for the local-specialist policy.
static int[][] getTypeToGroupMap(int numTypes, int[][] groupToTypeMap)
          Generates the type-to-group map from the group-to-type map groupToTypeMap.
static int[][] normalizeRoutingTable(int[][] table)
          Equivalent to normalizeRoutingTable (table, 0).
static int[][] normalizeRoutingTable(int[][] table, int minColumns)
          Converts the routing table table to a rectangular matrix containing table.length rows and at least minColumns columns.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

checkTypeToGroupMap

public static void checkTypeToGroupMap(int numGroups,
                                       int[][] typeToGroupMap)
Applies a consistency check for the type-to-group map typeToGroupMap supporting I = numGroups agent groups. This checks that every positive element of the given matrix corresponds to an agent group index and no group index appears more than once in an ordered list. If an inconsistency is detected, this throws an IllegalArgumentException describing the problem.

Parameters:
numGroups - the number of agent groups I.
typeToGroupMap - the type-to-group map being checked.
Throws:
NullPointerException - if typeToGroupMap or one of its elements are null.
IllegalArgumentException - if the matrix is incorrect.

checkGroupToTypeMap

public static void checkGroupToTypeMap(int numTypes,
                                       int[][] groupToTypeMap)
Applies a consistency check for the group-to-type map groupToTypeMap supporting K = numTypes contact types. This checks that every positive element of the given matrix corresponds to a contact type index and no type index appears more than once in an ordered list. If an inconsistency is detected, this throws an IllegalArgumentException describing the problem.

Parameters:
numTypes - the number of contact types K.
groupToTypeMap - the group-to-type map being checked.
Throws:
NullPointerException - if groupToTypeMap or one of its elements are null.
IllegalArgumentException - if the matrix is incorrect.

checkConsistency

public static void checkConsistency(int[][] typeToGroupMap,
                                    int[][] groupToTypeMap)
Checks the consistency of the routing tables typeToGroupMap and groupToTypeMap. It is assumed that the matrices are themselves consistent routing tables, i.e., checkTypeToGroupMap (groupToTypeMap.length, typeToGroupMap) and checkGroupToTypeMap (typeToGroupMap.length, groupToTypeMap) do not throw exceptions. This methods checks that an agent group index i appears in the ordered list for contact type k if and only if the contact type k appears in the ordered list for agent group i. If this consistency criterion is violated, an IllegalArgumentException is thrown.

Parameters:
typeToGroupMap - the type-to-group map.
groupToTypeMap - the group-to-type map.
Throws:
IllegalArgumentException - if the consistency check fails.
See Also:
checkTypeToGroupMap(int,int[][]), checkGroupToTypeMap(int,int[][])

getTypeToGroupMap

public static int[][] getTypeToGroupMap(int numTypes,
                                        int[][] groupToTypeMap)
Generates the type-to-group map from the group-to-type map groupToTypeMap. For each contact type k, this method constructs an ordered list containing all agent groups referring to it in the group-to-type map, sorted in increasing order of group identifier. It is assumed that the groupToTypeMap matrix is consistent, i.e., checkGroupToTypeMap(int,int[][]) does not throw an exception when called with it.

Parameters:
numTypes - the number of contact types K.
groupToTypeMap - the group-to-type map being processed.
Returns:
the generated type-to-group map.
See Also:
checkGroupToTypeMap(int,int[][])

getTypeToGroupMap

public static int[][] getTypeToGroupMap(boolean[][] m)
Constructs and returns a new type-to-group map from the incidence matrix m. For each column k of the rectangular matrix m, the method creates a row in the type-to-group map with a column containing value i for each true m(i, k) value. This gives lists of agent groups sorted in increasing order of group identifier.

Parameters:
m - the incidence matrix.
Returns:
the type-to-group map.
See Also:
ArrayUtil.checkRectangularMatrix(Object)

getTypeToGroupMap

public static int[][] getTypeToGroupMap(double[][] ranksTG)
Generates a type-to-group map from the agent selection matrix of ranks ranksTG. Assuming that the given matrix is rectangular, the method first uses a scheme similar to getTypeToGroupMap(boolean[][]) to get a list of agent groups sorted in increasing order of group identifier for each contact type. Each row of the resulting type-to-group map is then sorted in rank-increasing order, i.e., an agent group i1 goes before i2 if $ \rTG$(k, i1) < $ \rTG$(k, i2). If $ \rTG$(k, i1) = $ \rTG$(k, i2), i1 goes before i2 in the ordered list for contact type k if i1 < i2.

Parameters:
ranksTG - the matrix of ranks being transformed.
Returns:
the generated type-to-group map.

getTypeToGroupMap

public static int[][] getTypeToGroupMap(double[][] ranksTG,
                                        int[] typeRegions,
                                        int[] groupRegions)
This method is similar to getTypeToGroupMap(double[][]) with a sorting algorithm adapted for the local-specialist policy. Except from the agent selection matrix of ranks, the method needs arrays associating a region identifier to each contact type and agent group. For contact type k, an agent group i1 goes before an agent group i2 if the location of i1 is the same as the originating region of contacts of type k, but i2's location is different from i1's. In other words, groupRegions[i1] == typeRegions[k] and groupRegions[i2] != typeRegions[k] if i1 is before i2. Any pair (i1, i2) not meeting this extra condition is sorted using the same algorithm as in getTypeToGroupMap(double[][]).

Parameters:
ranksTG - the matrix of ranks.
typeRegions - the region identifier of each contact type.
groupRegions - the region identifier of each agent group.
Returns:
the constructed type-to-group map.

getGroupToTypeMap

public static int[][] getGroupToTypeMap(int numGroups,
                                        int[][] typeToGroupMap)
Generates the group-to-type map from the type-to-group map typeToGroupMap. For each agent group i, this method constructs a list containing all contact types referring to it in the type-to-group map, sorted in increasing order of type identifier. It is assumed that the typeToGroupMap matrix is consistent, i.e., checkTypeToGroupMap(int,int[][]) does not throw an exception when called with it.

Parameters:
numGroups - the number of agent groups I.
typeToGroupMap - the type-to-group map being processed.
Returns:
the generated group-to-type map.
See Also:
int[][])

getGroupToTypeMap

public static int[][] getGroupToTypeMap(boolean[][] m)
Constructs and returns a new group-to-type map from the incidence matrix m. For each row i of m, the method creates a row in the group-to-type map with a column having a value k for each true m(i, k) value. This gives lists of contact types sorted in increasing order of type identifier.

Parameters:
m - the incidence matrix.
Returns:
the group-to-type map.

getGroupToTypeMap

public static int[][] getGroupToTypeMap(double[][] ranksGT)
Generates a group-to-type map from the contact selection matrix of ranks ranksGT. The method first uses a scheme similar to getGroupToTypeMap(boolean[][]) to get a list of contact types sorted in increasing order of type identifier for each agent group. Each row of the resulting group-to-type map is then sorted in rank-increasing order, i.e., a contact type k1 goes before k2 if $ \rGT$(i, k1) < $ \rGT$(i, k2). If $ \rGT$(i, k1) = $ \rGT$(i, k2), k1 goes before k2 in the list if k1 < k2.

Parameters:
ranksGT - the matrix of ranks.
Returns:
the new group-to-type map.

getGroupToTypeMap

public static int[][] getGroupToTypeMap(double[][] ranksGT,
                                        int[] typeRegions,
                                        int[] groupRegions)
This method is similar to getGroupToTypeMap(double[][]) with a sorting algorithm adapted for the local-specialist policy. Except from the contact selection matrix of ranks, the method needs arrays associating a region identifier to each contact type and agent group. For each agent group i, a contact type k1 goes before a contact type k2 if the originating region of k1 is the same as the location of agent group i, but k2's originating region is different from k1's. In other words, typeRegions[k1] == groupRegions[i] and typeRegions[k2] != groupRegions[i] if k1 is before k2. Any pair (k1, k2) not meeting this extra condition is sorted using the same algorithm as in getGroupToTypeMap(double[][]).

Parameters:
ranksGT - the matrix of ranks.
typeRegions - the region identifier of each contact type.
groupRegions - the region identifier of each agent group.
Returns:
the constructed group-to-type map.

getIncidenceFromTG

public static boolean[][] getIncidenceFromTG(int numGroups,
                                             int[][] typeToGroupMap)
Constructs and returns the incidence matrix from the typeToGroupMap with numGroups agent groups. The returned incidence matrix has one row for each agent group and one column for each contact type. Element (i, k) of the matrix is true if and only agent group i is included in the list of contact type k, i.e., ik, j = k for some j. In the incidence matrix, all the ranking induced by the type-to-group map is lost. It is assumed that the type-to-group map is consistent as checked by checkTypeToGroupMap(int,int[][]).

Parameters:
numGroups - the number of agent groups.
typeToGroupMap - the type-to-group map.
Returns:
the incidence matrix.

getIncidenceFromGT

public static boolean[][] getIncidenceFromGT(int numTypes,
                                             int[][] groupToTypeMap)
Constructs and returns the incidence matrix from the groupToTypeMap with numTypes contact types. The returned incidence matrix has one row for each agent group and one column for each contact type. Element (i, k) of the matrix is true if and only if the contact type k is included in the list of agent group i, i.e., ki, j = k for some j. In the incidence matrix, all the ranking induced by the group-to-type map is lost. It is assumed that the group-to-type map is consistent as checked by checkGroupToTypeMap(int,int[][]).

Parameters:
numTypes - the number of contact types.
groupToTypeMap - the group-to-type map.
Returns:
the incidence matrix.

getRanksFromTG

public static double[][] getRanksFromTG(int numGroups,
                                        int[][] typeToGroupMap)
Constructs the agent selection matrix of ranks from the typeToGroupMap with numGroups agent groups. For each non-negative ik, j = typeToGroupMap[k][j], the rank $ \rTG$(k, ik, j) of contact type k for agent group ik, j is set to j. If i does not appear in the list of k, $ \rTG$(k, i) = ∞.

Parameters:
numGroups - the number of agent groups.
typeToGroupMap - the type-to-group map.
Returns:
the matrix of ranks.

getRanksFromGT

public static double[][] getRanksFromGT(int numTypes,
                                        int[][] groupToTypeMap)
Constructs the contact selection matrix of ranks from the groupToTypeMap with numTypes contact types. For each non-negative ki, j = groupToTypeMap[i][j], the rank $ \rGT$(i, ki, j) of contact type ki, j for agent group i is set to j. If k does not appear in the list of i, $ \rGT$(k, i) = ∞.

Parameters:
numTypes - the number of contact types.
groupToTypeMap - the group-to-type map.
Returns:
the matrix of ranks.

getRanks

public static double[][] getRanks(boolean[][] m,
                                  int[] skillCounts)
Constructs a contact selection matrix of ranks from the incidence matrix m and skill counts skillCounts. Assuming m is rectangular, this method creates a matrix of ranks with m.length rows and m[0].length columns. For each agent group i, and each contact type k, the method sets the rank to if the contact cannot be served, i.e., if m[k][i] is false. Otherwise, $ \rGT$(i, k) is set to skillCounts[i]. If skillCounts is null, skillCounts[i] is inferred by counting the number of k for which m[i][k] is true.

Parameters:
m - the incidence matrix.
skillCounts - the skill counts.
Returns:
the matrix of ranks.
Throws:
IllegalArgumentException - if m.length is different from skillCounts.length.

getOverflowLists

public static int[][][] getOverflowLists(double[][] ranksTG)
Constructs and returns overflow lists from the given matrix of ranks ranksTG. More specifically, the ranks matrix giving $ \rTG$(k, i) for all k and i is used to generate overflow lists defined as follows. For each contact type k, this method creates a list of agent groupsets sharing the same priority. The jth groupset for contact type k is denoted i(k, j) = {i = 0,…, I - 1 : $ \rTG$(k, i) = rk, j}. Here, rk, j1 < rk, j2 < ∞ for any j1 < j2. The overflow list for contact type k is then i(k, 0), i(k, 1),… Array [k][j] of the returned 3D array contains the elements of i(k, j).

Parameters:
ranksTG - the input matrix of ranks.
Returns:
the overflow lists.

formatTypeToGroupMap

public static String formatTypeToGroupMap(int[][] typeToGroupMap)
Formats the type-to-group ordered lists as a string. For each supported contact type, a line containing Contact type k: [i1, i2, ...] is generated, where i1, i2, ... correspond to agent group indices. Each ordered list is formatted using formatOrderedList(int[]).

Parameters:
typeToGroupMap - the type-to-group map being formatted.
Returns:
the type-to-group map, formatted as a string.

formatGroupToTypeMap

public static String formatGroupToTypeMap(int[][] groupToTypeMap)
Formats the group-to-type ordered lists as a string. For each supported agent group, a line containing Agent group i: [k1, k2, ...] is generated, where k1, k2, ... correspond to contact type indices. Each ordered list is formatted using formatOrderedList(int[]).

Parameters:
groupToTypeMap - the group-to-type map being formatted.
Returns:
the group-to-type map, formatted as a string.

formatRanksTG

public static String formatRanksTG(double[][] ranksTG)
Formats the agent selection matrix of ranks ranksTG for each contact type and agent group. For each contact type, the returned string contains a line giving the rank of each agent group. When a contact type cannot be served by an agent group, a - is used to represent the infinite rank.

Parameters:
ranksTG - the matrix of ranks to be formatted.
Returns:
the ranks formatted as a string.

formatRanksGT

public static String formatRanksGT(double[][] ranksGT)
Formats the contact selection matrix of ranks ranksGT for each contact type and agent group. For each agent group, the returned string contains a line giving the rank of each contact type. When a contact type cannot be served by an agent group, a - is used to represent the infinite rank.

Parameters:
ranksGT - the matrix of ranks to be formatted.
Returns:
the ranks formatted as a string.

formatWeightsTG

public static String formatWeightsTG(double[][] weightsTG)
Formats the agent selection weights matrix weightsTG for each contact type and agent group. For each contact type, the returned string contains a line giving the weight of each agent group. A - is used to represent an infinite weight.

Parameters:
weightsTG - the weights matrix to be formatted.
Returns:
the weights formatted as a string.

formatWeightsGT

public static String formatWeightsGT(double[][] weightsGT)
Formats the contact selection weights matrix weightsGT for each contact type and agent group. For each agent group, the returned string contains a line giving the weight of each contact type. A - is used to represent an infinite weight.

Parameters:
weightsGT - the weights matrix to be formatted.
Returns:
the weights formatted as a string.

formatIncidence

public static String formatIncidence(boolean[][] m)
Formats the incidence matrix m for each contact type and agent group. For each agent group, the returned string contains a line giving the contact types it can serve. Each line contains one value for each contact type. The value 0 is used if the contact cannot be served and 1 otherwise.

Parameters:
m - the incidence matrix to be formatted.
Returns:
the incidence matrix formatted as a string.

formatOrderedList

public static String formatOrderedList(int[] orderedList)
Formats the ordered list orderedList as a string. This method constructs and returns a string containing the comma-separated list of indices stored in orderedList. If a negative index is found, it is replaced with -1 and formatted in the string only if at least one positive index follows it. For example, the ordered list -2, 0, 3, -1, -1 will be formatted as -1, 0, 3.

Parameters:
orderedList - the ordered list to be formatted.
Returns:
the string representing the ordered list.

normalizeRoutingTable

public static int[][] normalizeRoutingTable(int[][] table,
                                            int minColumns)
Converts the routing table table to a rectangular matrix containing table.length rows and at least minColumns columns. Assuming the given 2D array is a valid type-to-group or group-to-type map, evaluates the maximum number of columns in each row and pads the rows with -1 for the returned 2D array to be a rectangular matrix, i.e., each row has the same number of columns. In some circumstances, this can simplify manipulation of the routing table and the returned array is still compatible with the routers since negative indices must be ignored.

Parameters:
table - the routing table to be converted.
minColumns - the minimal number of columns in the normalized routing table.
Returns:
the converted routing table.
Throws:
NullPointerException - if table or one of its elements is null.
IllegalArgumentException - if minColumns is negative.

normalizeRoutingTable

public static int[][] normalizeRoutingTable(int[][] table)
Equivalent to normalizeRoutingTable (table, 0).


ContactCenters
V. 0.9.9.

To submit a bug or ask questions, send an e-mail to Richard Simard.