For this assignment you will solve a connectivity problem using a new data structure. Here is a description of the problem to solve and the data structure.
The input will be a text file containing a series of positive integers, two per line. Each integer is the number of a node in a physical network, and each pair on a line represents a working two-way communications link between two nodes. Henceforth the number of a node will be used as its name, so a node is synonymous with its number. And a link is synonymous with a pair of nodes i.e. a pair of numbers.
The actual network consists of a collection of nodes and links, but some links and some nodes may be broken. The input file essentially contains the working nodes and the working links in the network. You may assume that nodes are in the range 1 through 1000 inclusive, and you may assume that the input file has the stated format, without checking. (We will not grade your program’s behavior on bad inputs.) However there may be fewer than 1000 distinct numbers in the file.
The problem to be solved by your program is this. Which nodes can communicate with each other either directly (because there’s a working link between them listed in the input), or indirectly — by messages passing through other nodes en route, following a series of working links? i.e. which nodes are connected to which, in the sense of there being a working path between them?
This notion of connectivity breaks up the nodes into one or more groups. Within a group, each node is connected directly or indirectly to each other node. A node is always deemed connected to itself. There are no connections between nodes in different groups.
Your program should output these connected groups as follows. A group should be printed with ten numbers on a line, separated by spaces, possibly over several contiguous lines. There should be a blank line between groups. Try to make the output look reasonably regular and readable (try researching the use of System.out.format).
Keeping track of Connectivity
To keep track of connectivity, use an array of integers (indexed from 1 to 1000) in an unusual way. The array will contain an unusual representation of a set of trees. Call this set of trees a forest. Each tree in the forest will represent one of the above groups of connected nodes in the network. Nodes in such a tree will be nodes from the network. It will not matter what shape such a tree is, just which nodes are in it.
When a link is read from the input, the two trees containing the two nodes of that link will be connected together into a single tree, representing the group of nodes connected to the first node of the link being joined with the group of nodes connected to the second node of the link, as they are all now connected. This is called a group_merge operation.
In a conventional representation of a tree, each node knows about its children. In our representation of a tree, each node only knows which node is its parent and since a node in a tree has only one parent, the parent can be stored in an array! Call this array p. (The maximum index of p will be 1000.)
p[n] is the node that is the parent of n
This works nicely, because nodes are just small numbers (at most 1000) and so can both index and fill an array of integers. What of the root of such a tree, what is its parent? By convention, we make the parent of a root be that root. Only the roots of trees in the forest have this property of having themselves as parents. In all other cases going from a node to its parent is taking a step towards the root of the tree it resides in.
If the node n has not been encountered then p[n] will be zero, which indicates that it is not a part of the forest. Initially all potential nodes are in this state. When a node n is first encountered because for the first time a link containing it is read from the input, then immediately p[n] is assigned the value n, before any group_merge operation is performed upon it. This makes n its own parent, which is the way we make it the root of a new tree in the forest, one containing only a single node (itself), and this is called a make_group operation. This operation should do nothing if the node n is already in a tree, i.e. has a non-zero parent p[n].
The find_group operation takes a node n and produces the root node of the tree that contains it. (This root number is used to represent the group of all nodes in that tree in the forest.) Informally this is achieved by going from n to its parent and to its parent’s parent and so forth, until a node is encountered that is its own parent, which is the root.
The find_group operation is also used to implement the group_merge operation described above, that joins two trees in the forest into one. Given two nodes n1 and n2 whose trees need to be joined into one, group_merge first finds the roots r1 and r2 of the trees containing n1 and n2 respectively by using find_group on n1 and then on n2. If r1 and r2 are the same, then nothing need be done, as n1 and n2 are in the same tree and therefore in the same group already. Otherwise the two trees need to be combined into one, and this is accomplished by making one root the parent of the other (instead of it being its own parent). So p[r1] is assigned r2 to achieve this.
The Assignment
Define the Forest class in the file Forest.java and give it a private instance variable p that is of type array of integer, to be used as described above. Write methods with the following signatures and semantics.
//construct the empty forest
public Forest()
//make a one node tree
//(if n is already in a tree do nothing)
public void make_group(int n)
//find the root of the tree containing n
//(return 0 if n is not in a tree)
public int find_group(int n)
//join together the trees containing n1 and n2
//(if n1 not in a tree, call make_group(n1) first)
//(if n2 not in a tree, call make_group(n2) first)
public void group_merge(int n1, int n2)
//return a new array g[n] = find_group(n) for each n
public int[] groups()
Now write a solution to the assignment problem in the file Conn.java with a main method that creates a single empty Forest, and for every link in the input calls group_merge on its two nodes. Finally call groups to get the results, and use the resulting array to print out the groups of nodes, each one in increasing order.
See the notes at the beginning of the assignment for further details on input and output. Read data from standard input and use input redirection to read from a file when you run the program. Write results to standard output. Do not open any files from Java.
