public class Solution08 extends APSP {
private Solution07 solGraph1;
private String[] strLocations;
/**
public Solution08() {
super();
// create object for basic graph operations and init order of locations.
solGraph1 = new Solution07();
strLocations = null;
}
/**
* Compute all-pairs shortest path of the given scenario with the given
* order of locations.<p>
*
* @param scenario a scenario
* @param locations array of location names (String) that defines the
* order of locations.
* @return <ul>
* <li> <code>true</code> if and only if the computation was successful.<br>
* <li> <code>false</code> if and only if the computation was NOT successful
* <ul>
* <li> at least one paramter is invalid (<code>null</code>)
* <li> at least one location name in the given array is not found in the scenario
* <li> at least one location name in the scenario is not found in the given array.
* </ul>.
* </ul>
* @since 1.0
*/
public boolean computeAPSP(IScenario scenario, String[] locations) {
int intLocations, intI, intJ, intK;
int intDik, intDkj, intNew;
if ((solGraph1 != null) && (testLocations(scenario, locations))) {
// save order of location
strLocations = locations;
intLocations = strLocations.length;
// create initial matrices.
initMatrices(scenario);
// run all iterations
for (intK = 0; intK < intLocations; ++intK)
for (intI = 0; intI < intLocations; ++intI)
for (intJ = 0; intJ < intLocations; ++intJ) {
intDik = intMatrixD[intI][intK];
intDkj = intMatrixD[intK][intJ];
// check for connection between these locations
if ((intDik < Integer.MAX_VALUE) &&
(intDkj < Integer.MAX_VALUE)) {
// compute duration using location k
intNew = intDik + intDkj;
if (intMatrixD[intI][intJ] > intNew) {
intMatrixD[intI][intJ] = intNew;
intMatrixT[intI][intJ] = intMatrixT[intK][intJ];
}
}
}
// computation was successful
return true;
}
// something was wrong
return false;
}
/**
* Returns the shortest path between the given locations as a result of the
* latest computation. The path is represented as a Vector of location names
* (<code>String</code> objects) in the right order from location1 to
* location2.<p>
*
* @param location1 the first location as String
* @param location2 the second location as String.
* @return <ul>
* <li> <code>null</code>, if and only if at least one parameter is not
* valid (<code>null</code> or unknown location) or there is no path
* between the given locations
* <li> Otherwise a Vector containing all location names to travel from
* location1 to location2 (including location1 and location2)
* </ul>
* @see java.util.Vector
* @see #computeAPSP
* @since 1.0
*/
public Vector<String> getShortestPath(String location1, String location2) {
Vector<String> vecPath;
int intLoc1, intLoc2;
// first, check parameters
if ((location1 != null) && (location2 != null)) {
// get indices of both locations.
intLoc1 = getLocationIndex(location1);
intLoc2 = getLocationIndex(location2);
// locations must be known and different
if ((intLoc1 != -1) && (intLoc2 != -1) &&
(intLoc1 != intLoc2)) {
// create vector that contains the shortest path
vecPath = new Vector<String>();
// add location names in reverse order
do {
// put current location name at the top of the vector.
vecPath.add(0, strLocations[intLoc2]);
// get next location index from matrix T.
intLoc2 = intMatrixT[intLoc1][intLoc2];
} while (intLoc2 != intLoc1);
// put first location at the top and return vector
vecPath.add(0, strLocations[intLoc1]);
return vecPath;
}
}
// something was wrong
return null;
}
/**
* Returns the duration to travel along a shortest path between the given locations
* as a result of the latest computation.<p>
*
* @param location1 the first location as String
* @param location2 the second location as String.
* @return <ul>
* <li> <code>-1</code>, if and only if at least one parameter is not valid
* (<code>null</code> or unknown location) or there is no path between the
* given locations.
* <li> Otherwise duration to travel along a shortest path from
* location1 to location2.
* </ul>
* @see #computeAPSP
* @since 1.0
*/
public int getShortestPathDuration(String location1, String location2) {
int intLoc1, intLoc2;
// first, check parameters
if ((location1 != null) && (location2 != null)) {
// get indices of both locations.
intLoc1 = getLocationIndex(location1);
intLoc2 = getLocationIndex(location2);
if ((intLoc1 != -1) && (intLoc2 != -1))
return intMatrixD[intLoc1][intLoc2];
}
// something was wrong
return -1;
}
/**
* Initialize matrices D and T according to the given parameters.<p>
*
* @param scenario a scenario
* @since 1.0
*/
private void initMatrices(IScenario scenario) {
int intLocations, intI, intJ, intValue;
// get number of locations.
intLocations = strLocations.length;
// create and initialize both matrices
intMatrixD = solGraph1.getAdjacencyMatrix(scenario, strLocations);
intMatrixT = solGraph1.getAdjacencyMatrix(scenario, strLocations);
// set all invalid values to -1 and valid values to the predecessor
for (intI = 0; intI < intLocations; ++intI)
for (intJ = 0; intJ < intLocations; ++intJ) {
intValue = intMatrixT[intI][intJ];
if ((intValue < 1) || (intValue == Integer.MAX_VALUE))
intMatrixT[intI][intJ] = -1;
else
intMatrixT[intI][intJ] = intI;
}
}
/**
* Returns the index of the given location.<p>
*
* @param location a location as String
* @return <ul>
* <li> <code>-1</code>, if and only if the location is unknown
* <li> otherwise the index in the array of locations
* </ul>
* @since 1.0
*/
private int getLocationIndex(String location) {
int intI;
// check parameter
if (location != null) {
intI = strLocations.length;
while (intI > 0) {
if (location.equalsIgnoreCase(strLocations[--intI]))
return intI;
}
}
// location name not found
return -1;
}
}
