Keywords: Java, directed graph, linked list

The diagram below is an example of a directed graph. Each edge has an arrow denoting its direction. Node 2 is considered adjacent to node 1 if there is a directed edge from 1 to 2. 1 will only be adjacent to 2 if there is also an edge from 2 to 1. It is possible to associate a matrix called the adjacency matrix with a graph. Adj[i,j] = 1 if and only if there is an edge from node i to node j in the graph. If Adj[i,j] = 0 then there is no edge from node i to node j. We will assume that our adjacency matrices contain only 1s or 0s. In a graph, one is usually interested in the possible paths from one node to another. The ones which are the most useful are the ones which do not contain loops (cycles), i.e.. do not visit a node more than once. The node sequence 1 2 4 is an example of a path with no loops. 1 2 2 4 1 3 is an example of a path with a cycle and a loop. An allowable exception is for the starting and ending node to be the same. 1 2 1 is OK but not 1 2 1 2 4 1.

Write a program in JAVA to read in the number of nodes in the graph and the corresponding adjacency matrix, one row at a time from the input file (see below). Copy the adjacency matrix to your output file. The program can use recursion or iteration to find and list all possible non-looping paths between all possible pairs of nodes. It is ok if the start and end nodes are the same but otherwise the nodes should not repeat within the path. If no path exists for a particular pair of nodes then print 'No Path Found'. Check out all possible paths in each graph. Represent the adjacency matrix using a linked allocation. You may not use LinkedList.

Use Java 7 or 8 (JDK 1.7 or 1.8) to take an input file, read and process the data in a specific way (outlined above) and put results in an output file. Use of standard libraries is restricted to standard I/O calls and standard math functions, etc. In other words, you can't use LinkedList. Use named files to handle I/O. No hardcoded file names. Enter file names as command line prompts. Do NOT use GUI/console input of data. Output files must: Contain the input as well as contain answers to the required input. Be user friendly with additional labels, lines, and white space. Have statistical information as needed.

See below for the required input.

4

0 1 1 0

1 1 1 1

1 0 0 0

1 1 0 1

6

0 1 0 1 1 0

1 0 0 1 1 0

0 0 1 0 0 1

0 0 0 0 1 0

1 0 0 0 0 0

0 0 1 0 0 1

3

0 1 1

1 0 1

1 1 0

"To Nodes" 0 110 Adjacency "From11 1 1 Matrix Nodes" 1 0 0 0 4 "To Nodes" 0 110 Adjacency "From11 1 1 Matrix Nodes" 1 0 0 0 4