Write a java program that will implement the maximum flow problem

hi,

         Please find the attachment it has the detailed question. I even added a ppt which expains about maximum flow problem in 13th and 14th slides.

Thanks&regards

ricky

  

Assignment #4 (80 Points) – COSC 5390 – Dr. Leonard Brown 
Due:  April 18, 2013 (at the beginning of class) 

 
 
Problem Description 
Write a java program that will implement the maximum flow problem discussed in class.  The 
program should read its input from a text file.  The input will be in the form of an n x n matrix, 
where n is the number of nodes in the network.  Specifically, input will consist of n lines where 
each line has a collection of n integers, with each pair of integers separated by a single space.  
The  value  in  the  i

th
  row  and  the  j

th
  column  of  the  matrix  represents  the  capacity  of  the 

connection from the i
th
 node to the j

th
 node.  A value of -1 indicates that there is no link from 

node i to node j.  Note that the matrix represents a directed network. 
 
The output of the program should be the maximum flow that can be produced by the  input 
network.   This can be computed from the sum of the outgoing flows from the source or the 
incoming flows of the sink.  The first node will be the network’s source, and the last node will 
be the network’s sink. 
 
 
Sample Input 
-1 4 2 1 -1
-1 -1 1 -1 2
-1 -1 -1 1 2
-1 -1 -1 -1 3
-1 -1 -1 -1 -1
 
 
Sample Output 
The output to the program should be the maximum flow, 6. 
 
 
Submission 
Submit  your  assignment  through  Blackboard.    If  your  assignment  contains  multiple  files,  zip 
them into a single folder before submitting. 
 
 
Notes 
Points  can  be  deducted  from  your  assignment  based  on  the  quality  of  its  presentation.  
Handwritten assignments will not be accepted. 
 

Topic V
Network Algorithms
Shortest Path
Minimum Spanning Tree
Maximum Flow
Chapter(s): 9

Network Algorithms
Many network optimization problems are actually special types of linear programming problems
Types of network problems in this topic
Shortest-Path
Minimum Spanning Tree
Maximum Flow

Network Algorithms
Example Applications
Consider a park with a narrow, winding road system for trams and park rangers
Problem 1: Determine which route from the park entrance to a given station has the smallest total distance for the operation of the trams
Problem 2: Determine where telephone lines should be laid to establish communication among all stations where total miles of lines is minimized
Problem 3: How to maximize the number of trips that can be made per day without violating the limits on any individual road (each road may have limit of number of tram trips per day)

Network Terminology
A network consists of a set of points and a set of lines connecting certain pairs of the points
The points are called nodes
The lines are called arcs (or links or edges)
The arcs of a network may have some type of flow through them
If flow through an arc is allowed in only one direction, the arc is said to be a directed arc
A network with only directed arcs is a directed network
If flow is allowed in either direction, the arc is said to be undirected
A network with only undirected arcs is an undirected network

Network Terminology
A path between two nodes is a sequence of distinct arcs connecting these nodes
A path that begins and ends at the same node is called a cycle
Two nodes are connected if the network contains at least one path between them
A connected network is a network where every pair of nodes is connected
A connected network for all n nodes that contains no cycles is a spanning tree
Every spanning tree has n-1 arcs

Network Terminology
The maximum amount of flow that can be carried on a directed arc is referred to as the arc capacity
A supply node has the property that the flow out of the node exceeds the flow into the node
A demand node has the property where the flow into the node exceeds the flow out of the node
A transshipment node satisfies the conservation of flow, so flow in equals flow out

Shortest Path
Consider a connected network with two special nodes called the origin and destination
Associated with each of the links is a nonnegative distance
Objective: find shortest path (minimum total distance) from the origin to the destination

Shortest Path
At each iteration, there are a set of solved nodes and unsolved nodes
Solved nodes: shortest paths from origin to these nodes are known
Each link from solved node to unsolved node is a candidate
Identify unsolved node with the shortest connecting link

Shortest Path
At each iteration, there are a set of solved nodes and unsolved nodes
Add the distance between the solved node and its candidate to the distance of the shortest path from the origin to the solved node
Total is shortest path to candidate node
Candidate node is now moved to solved group
Note: Should remember path by storing node that linked to the candidate
Initially, only origin is solved and other nodes are unsolved

Shortest Path
Notes
Finding shortest-path from origin to all nodes is performed by iterating until all nodes are in solved group
Algorithm works with directed arcs

Minimum Spanning Tree
Minimum Spanning Tree Problem
Given nodes of a network and the potential links and positive length for each link
Design a network by inserting enough links to satisfy the requirement that there is a path between every pair of nodes
Satisfy the above requirement in a way that minimizes the total length of the links in the network

Minimum Spanning Tree
Minimum Spanning Tree Problem
Algorithm
Select any node arbitrarily and then connect it to the nearest distinct node
Identify the unconnected node that is closest to a connected node, and then connect these two nodes
Repeat until all nodes have been connected

Maximum Flow Problem
Maximum Flow Problem
Terminology
All flow through a directed and connected network originates at one node called the source
Terminates at one other node called the sink
Remaining nodes are transshipment nodes
Flow through an arc is allowed only in the direction indicated by the arrowhead
Maximum amount of flow is given by the capacity of that arc
At source: all arcs point away from the node
At sink: all arcs point to the node
Objective is to maximize the total amount of flow from the source to the sink
Measured as amount leaving source or amount entering the sink

Maximum Flow Problem
After some flows have been assigned to the arcs, the residual network shows the remaining arc capacities (called residual capacities) for assigning additional flows
An augmenting path is a directed path from the source to the sink in the residual network such that every arc on this path has strictly positive residual capacity
Minimum of these paths is the residual capacity of the augmenting path because it represents the amount of flow that can feasibly be added to the entire path
The algorithm repeatedly selects some augmenting path and adds a flow equal to its residual capacity to that path in the original network
Continue until there are no more augmenting paths