Algorithm
Development Kit 1.0

algs.model.network
Class Transportation

java.lang.Object
  extended by algs.model.network.FlowNetwork<EdgeInfo[][]>
      extended by algs.model.network.FlowNetworkArray
          extended by algs.model.network.Transshipment
              extended by algs.model.network.Transportation
Direct Known Subclasses:
Assignment

public class Transportation
extends Transshipment

Given a network having sources S, demanders D, edge capacities c(i,j), edge costs costs[i][j] with m=|S| suppliers and n=|D| demanders, construct a flow, if one exists, which minimizes costs.

The resulting Flow Network has m + n + 2 nodes. Note that the shipping "cost" from the virtual new source and new target are zero. All edges store the shipping cost, in addition to the flow and capacity constraints.

It is assumed that the dimensions of costs matches the respective dimensions of the sup and dem vectors; if not, an exception is thrown.

If a particular shipment is not possible (or simply not selected) then the cost should be Integer.MAX_VALUE.


Field Summary
 
Fields inherited from class algs.model.network.Transshipment
m, n, w
 
Fields inherited from class algs.model.network.FlowNetwork
numVertices, sinkIndex, sourceIndex
 
Constructor Summary
Transportation(int[] sup, int[] dem, int[][] costs)
          Problem reduction is immediate since there are no intermediate warehouses.
 
Method Summary
 
Methods inherited from class algs.model.network.Transshipment
getCost, output
 
Methods inherited from class algs.model.network.FlowNetworkArray
edge, getEdgeStructure, getFlow, getMinCut, populate, toString, validate
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

Transportation

public Transportation(int[] sup,
                      int[] dem,
                      int[][] costs)
Problem reduction is immediate since there are no intermediate warehouses.

Parameters:
sup - supplier nodes
dem - demand nodes
costs - costs to ship from supplier node i to demand node j

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.