Algorithm
Development Kit 1.0

algs.model.network
Class Assignment

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
                  extended by algs.model.network.Assignment

public class Assignment
extends Transportation

Given a bipartite graph of provider nodes P, requirer nodes R, and edge costs c(i,j) for assigning a provider pi to a requirer ri. Goal is to maximize the number of job assignments while minimizing the overall 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.

If a particular assignment is not possible 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
Assignment(int[][] costs)
           
 
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

Assignment

public Assignment(int[][] costs)

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.