# Java Implementation of Transitive Closure and Maximum Network Flow

What is needed is a single java file which will run on the console.

It will perform the following stepts:

1) It will read in from a file of doubles called [url removed, login to view] in? to a two-dimensional array

2) It will? run a transitive closure algorithm (such as the? Warshall algorithm), as described below.

3) It will output the resulting two-dimensional array in to a new file called [url removed, login to view]

4) It will now load [url removed, login to view] in as a two dimensional array

5) It will run a maximum network flow algorithm (such as the Ford-Fulkerson algorithm) to determine the maximum flow through the network

6) It will output the resulting two-dimensional array of doubles in to a new file called [url removed, login to view]

## Deliverables

The program should make use of a transitive closure algorithm and a maximum network flow algorithm. Examples of the? algorithms in Steps (2) and (4) are provided below:

Algorithm Warshall

**Input**: The adjacency matrix of a relation R on a set with n elements.

**Procedure**:

? For each j from 1 to n

? ? ? ? ? For each i from 1 to n

? ? ? ? ? ? ? ? If T(i,j)=1, then form the Boolean or of row i and row j

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? and replace row i by it.

? ? ? ? ? ? ? ? Go on to the next i-value.

? ? ? ? ? Once you have processed each i-value, go on to the next j-value.

**Output**: The adjacency matrix T of the transitive closure of R

Algorithm Ford-Fulkerson

**Input:** Graph *G* with flow capacity *c*, a source node *s*, and a sink node *t

***Procedure:**

1. ![f(u,v) \leftarrow 0][1] for all edges (*u*,*v*)

2. While there is a path *p* from *s* to *t* in *G**f*, such that *c**f*(*u*,*v*) > 0 for all edges ![(u,v) \in p][2]:

3. Find ![c_f(p) = \min\{c_f(u,v) | (u,v) \in p\}][3]

4. For each edge ![(u,v) \in p][2]

1. ![f(u,v) \leftarrow f(u,v) + c_f(p)][4] (*Send flow along the path*)

2. ![f(v,u) \leftarrow f(v,u) - c_f(p)][5] (*The flow might be "returned" later*)

**Output:** Graph O with completed maximum network flow of all nodes

The program will be tester with multiple undisclosed test cases to ensure proper operation.

( 5 comentários ) Ann Arbor, United States

ID do Projeto: #3012296

## 3 freelancers estão ofertando em média $105 para este trabalho renardpaul See private message.$212.5 USD in 14 dias
(105 Comentários)
6.6
Bandreid

See private message.

$51 USD in 14 dias (7 Comentários) 2.2 millman See private message.$51 USD in 14 dias
(0 Comentários)
0.0