## Question

Algori City’s planners love one‐way streets. They say it is safer for pedestrians to cross them if cars come from one direction only. So they’ve converted a lot of their streets to one‐way streets. But they have a problem: The drivers of Algori City complain that they cannot get from some parts of the city to others now. This is something the planners didn’t think of. They need help from you.

As a budding graph theorist, you know that you can represent a city’s road network as a digraph. The nodes (vertices) in the digraph are the intersections, and the arcs are the streets connecting them, such that each arc points in the direction of the one‐way traffic. You also know that such a graph can be represented as an adjacency matrix or an adjacency list. So you ask the Algori City Planning

Department to give you a street map of Algori City in the form of an adjacency matrix.

First you need to download your personal copy of the adjacency matrix.

The format of the matrix is something like the following.

0,1,1,0,0,0,0,…

0,0,1,0,0,0,0,…

0,1,0,0,0,0,1,…

…

Each row represents the node (intersection) at which the street (arc) starts. The first row is for intersection 0, the second for 1, etc., so that the nodes for the n intersections in Algori City are numbered from 0 to n‐1. The non‐zero entries in each row represent direct streets (arcs) going to the respective target intersection, i.e., the j‐th entry in row i tells us whether you can get from intersection i to intersection j by car via a direct street (arc). So, in the example above, we can see that we can get from intersection 0 to intersection 2 via a one‐way street (there is no way back), and that we can get from 1 to 2 and from 2 to 1 – presumably a two way street. Note: Each row ends with a 0 or 1 and a single newline character, not with a comma and/or dots (these are only to indicate that the row may have more entries).

Part 1 – Adjacency Matrix to Adjacency List ‐ 15 marks

Write a Java program matrix2list.java that reads a text file matrix.txt with an adjacency matrix in the format above and converts it into an adjacency list list.txt. You may assume that the file will be in the same directory as matrix2list.java. Your program must read the file but it must not ask for the file name (no user input please). The program must handle matrices of arbitrary size (up to a reasonable limit, say 10000 x 10000).

The list should have the following format (for the example above):

1,2,…

2,…

1,6,…

…

such that each row corresponds to the originating node (intersection) and each entry in each row gives the number of a target intersection. The target intersections in each row must be listed in increasing order. Note that there must be no comma (and no “…”) after the last entry in each row.

The file list.txt must not contain anything else than the list itself.

Your converter must write to the file list.txt, overwriting any previous input. Any screen output of your converter will not be marked.

You must put your name and AUID (7 or 9 digit number) in a comment at the top of the matrix2list.java file.

Part 2 – Reverse Digraph – 25 marks

Write a Java program list2reverse.java that takes list.txt as input and outputs the adjacency list for the reverse digraph (where all arcs point the opposite way) in a file reverselist.txt, using the same format as above. Again, this program must handle any size list up to 10000 nodes and 10000 outneighbours.

Your converter must write to the file reverselist.txt, overwriting any previous input. Any screen output of your converter will not be marked.

You must put your name and AUID (7 or 9 digit number) in a comment at the top of the list2reverse.java file.

Before we go on: Strategy Review

You are now ready to look for the strongly connected components in the digraph. In our case, a strongly connected component is a set of nodes (intersections) for which the following two conditions apply:

You can reach each intersection in the set from any other intersection in the set (which implies that you can drive there and back) by following one or more streets (arcs).

If you can reach an intersection that is not in the set from one that is in the set, you will not be able to return from there. Similarly, if you can reach an intersection that is in the set from one that is not in the set, you will not be able to return to there. These are outbound and inbound ``weak connections’’ of the strongly component.

If you get more than one strongly connected component, the citizens of Algori City are right: There’s at least one part of town you can’t reach from another part, and the Planning Department will need to do some more planning.

As we’ll discuss in the lectures, the reverse digraph Gr of a digraph G has the same strongly connected components as the digraph G itself. The outbound weak connections of the digraph’s strongly connected components are the inbound weak connections of the reverse digraph, and vice versa.

Say you have a digraph G with two strongly connected components A and B that are weakly connected by an arc from B to A. A DFS on G that reaches A before B results in a forest in which A and B are separate trees. If it reaches B first, then A and B end up in the same tree. In other words: A DFS on G ensures that components with weak inbound connections are either seen first or end up in the same tree at the end of weak outbound connections from components that were seen earlier. If we give the nodes in the forest FG an integer label that reflects the order in which they finished processing, the node labels on the far end of such an outbound connection are all smaller than the label of the node on the near end of the outbound arc. Note also that the only arcs between trees in F are now going from trees that finished later to trees that finished earlier. In the reverse digraph Gr, weak outbound connections become weak inbound connections. Now let’s do a DFS on Gr, such that we always start at the node with the largest label from the previous DFS run on G when we start a new tree. The very first node we pick is then the node in the last tree of the previous DFS forest FG. As trees in FG have only outgoing arcs to earlier trees, and these arcs point the other way in Gr, the tree has no outgoing arc in Gr. However, any weak internal connection that the tree contains now points “the wrong way”, meaning the tree gets split in the search forest for Gr.

Part 3 – DFS on the Digraph – 40 marks

Write a Java program dfs.java that performs a DFS on your digraph in list.txt and outputs its result to a file dfs.txt. The format of dfs.txt is as follows: Each line represents a node. The first line represents the first node that finished processing. Each following line either contains an entry for the node that finished processing or is empty if the previous line completed a tree in the DFS forest. Each nonempty line contains two integer numbers. The first number is the label of the node assigned to it during the DFS, so should start with 0 and increment by 1 with each non‐empty line. The second number is the node number. Example (with comments):

0,7

1,18

2,33

3,15

4,8

5,3

6,19

…

This should be read as “Node 7 finished processing first, followed by node 18 and node 33, which completes the first tree in the DFS search forest. The first node to complete in the next tree was 15, followed by 8, 3 and 19, which completes the second tree, …”

Once again, your program must be able to handle arbitrary size input up to the aforementioned limits.

Part 4 – DFS on the Reverse Digraph – 10 marks

Using your results from the previous sections, write a program findcomponents.java that combines the results from the previous parts that reads matrix.txt and outputs a text file components.txt that contains a comma‐separated list of the strongly connected components in matrix.txt. Apart from combining your previous work, all you need to do in this part is to perform a DFS on the reverse graph you created in Part 2. Whenever you start a new tree in the search forest, you always pick the white node that is closest to the bottom of the list you created in Part 3.

The format of components.txt must be a comma‐separated list of nodes for each strongly connected component, with one component per line, and node numbers sorted in ascending order:

9,17,22,27

1,13,21

5,6,11,18,20,23,24,26,29

…

Read: “The first strongly connected component consist of nodes 9, 17, 22, and 27, the second strongly connected component consists of nodes 1, 13 and 21, …”

Once again, your program must be able to handle arbitrary size input up to the aforementioned limits.

Part 5 – Solving Algori City’s Traffic Problem – 10 marks

You now know how many different parts Algori City has such that it is not possible to get from this part to one or more of the others, or such that it is not possible to reach it from one or more of the others by car.

For your final recommendation, the Algori City Planners have asked you for a minimum set (aren’t they cheapskates?) of new one‐way streets that will allow the citizens of Algori City to move directly from each of these parts to each other. Do not propose a street if it is already possible to get directly from a particular part to a particular other part. The new streets should always start and terminate at the lowest‐numbered intersection in each part of the city. Give your solution as a text file newstreets.txt with your AUID at the top and one arc per line in the rest of the file, such that the format is:

1234567

9,1

1,9

5,9

5,1

…

using the example from the previous part and assuming that it was already possible to reach the third strongly component from any of the first two. So, the second line means “a street from 9 to 1” etc.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

import java.io.*;import java.util.ArrayList;

import java.util.Arrays;

import java.util.Stack;

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

/**

*

* @author Srdjan

*/

public class Connect

{

public static int NodeCount=0;

public static int add=0;

public static ArrayList<int[]> Components = new ArrayList<>(); //added for storage of names of vertices.

public static ArrayList<int[]> Vertices = new ArrayList<>(); // the set of vertices on the path

public static ArrayList<String> Tree = new ArrayList<>();

public static boolean Printed=true;

/**

* @param args the command line arguments

*/

public static void main(String[] args) throws FileNotFoundException, IOException

{

BufferedReader in = new BufferedReader(new FileReader("d:\\components.txt")); // read matrix

BufferedReader in2 = new BufferedReader(new FileReader("d:\\list.txt")); // read matrix

PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("d:\\newstreets.txt")));

String row=in...