com.mhhe.clrs2e
Class DifferenceConstraints

java.lang.Object
  |
  +--com.mhhe.clrs2e.DifferenceConstraints

public class DifferenceConstraints

extends java.lang.Object

Class for solving a system of difference constraints, as defined in Section 24.4 of Introduction to Algorithms, Second edition.

Nested Class Summary

static class	DifferenceConstraints.BadConstraintException Inner class for a bad constraint exception.
private static class	DifferenceConstraints.Constraint Inner class for an individual constraint.

Field Summary

(package private) com.mhhe.clrs2e.SentinelDLL

system A list of the difference constraints.

Constructor Summary

DifferenceConstraints()
Creates an empty system of difference constraints.

Method Summary

void	addConstraint(int j, int i, double b) Adds a constraint xj - xi ≤ bk to the system of difference constraints.
double[]	findFeasibleSolution() Finds a feasible solution to the system of difference constraints, if a feasible solution exists.
java.lang.String	toString() Returns the String representation of this system of difference constraints.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

system

com.mhhe.clrs2e.SentinelDLL system

A list of the difference constraints.

Constructor Detail

DifferenceConstraints

public DifferenceConstraints()

Creates an empty system of difference constraints.

Method Detail

addConstraint

public void addConstraint(int j,
                          int i,
                          double b)

Adds a constraint x_j - x_i ≤ b_k to the system of difference constraints.

Parameters:

j - Index for the variable x_j. Must be at least 1.

i - Index for the variable x_i. Must be at least 1.

b - Value of b_k.

Throws:

DifferenceConstraints.BadConstraintException - if either of i or j is less than 1.

findFeasibleSolution

public double[] findFeasibleSolution()

Finds a feasible solution to the system of difference constraints, if a feasible solution exists.

Returns:

If the return value is null, then there is no feasible solution. Otherwise, the return value is an array x[0..n], where x[0] is undefined and for i = 1, 2, ..., n, the appropriate value of the feasible solution is in x[i].

toString

public java.lang.String toString()

Returns the String representation of this system of difference constraints.

Overrides:

toString in class java.lang.Object