Algorithm
Development Kit 1.0

Package algs.model.network

Defines classes to represent Flow Network algorithms.

See:
          Description

Class Summary
Assignment 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.
BFS_SearchArray Encapsulate algorithm by which the augmenting path for a flow network is found.
BFS_SearchList Encapsulate algorithm by which the augmenting path for a flow network is found when the underlying data structure is represented as an adjacency list.
BipartiteMatchingMinCost A graph represents provide nodes that are to be matched with an equal number of requirer nodes.
DFS_SearchArray Encapsulate algorithm by which the augmenting path for a flow network is found.
DFS_SearchList Encapsulate algorithm by which the augmenting path for a flow network is found.
DisjointPairs<A,B> Helper class to record pairing information for the Maximum Matching problem.
EdgeInfo This class is used to model the edges of the graph which contains a network flow problem.
FlowNetwork<E> Parent abstract class for representing a flow network problem to be solved.
FlowNetworkAdjacencyList Store information regarding the graph as an adjacency list.
FlowNetworkArray Store information regarding the graph in a two-dimensional matrix.
FordFulkerson Given a flow network (see definition below) with known capacities on each directed edge, compute the maximal flow between the source vertex and the sink vertex.
Optimized Optimized implementation of Ford-Fulkerson that uses arrays for all storage.
OptimizedFlowNetwork Store information regarding the graph in a two-dimensional matrix.
Search Flow Network algorithms depend on locating an augmenting path through the network.
ShortestPathArray Encapsulate algorithm by which the augmenting path for a Minimal Cost, Maximal Flow network is found.
Transportation 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.
Transshipment Given a network having sources S, intermediate "warehouse" nodes W, and 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.
VertexInfo Stored information by augmenting flow algorithms as it progresses.
VertexStructure Records information about a vertex's forward (Outgoing) edges and backward (Incoming) edges.
 

Package algs.model.network Description

Defines classes to represent Flow Network algorithms.


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.