Routing Wires on a Chip

In this project, you will implement a Java program that places wires on a computer chip. We abstractly represent acomputer chip as a grid of cells, where each cellis connected to the four neighboring cells(in the directions north, south, east, and west). To complicate matters, parts of the chip are already allocated for other uses and may not be used for running wires. These already-in-use parts are calledobstacles. Each obstacle is a rectangular region of the grid. Given a sequence of endpoints, the task is to connect each pair with a wire.

A coordinate is a pair of integers, with the first being the horizontal distance from the left edge of the grid, and the second being the vertical distance from the top edge of the grid. The endpoints of awireare connected by apathof coordinates. Wires may not cross one another. In addition to connecting up all the wires, your goal is to minimize the aggregate lengths of all the wires while also minimizing the execution time of your program.

For the example chip shown above, there are 4 obstacles, indicated by the shaded regions. The given endpoints for wire #1 are (2, 3) and (4, 3), and the connecting path (shown in blue) is of length 11. The path itself is (2, 3), (2, 2), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1), (6, 2), (6, 3), (5, 3), (4, 3).

File Format

The inputs directory contains descriptions of several grids that need wiring. Each of these input files ends with a .in extension.

The format of an input file is described as follows. The first two lines contain a single integer specifying the width and height, respectively of the grid. The third line is the number of rectangular obstacles on the grid. Each obstacle is described by a subsequent linecontainingfour integers, separated by spaces.The first two integers give the upper left coordinate of the obstacle and the second two integers give the lower right coordinate of the obstacle. After the obstacles, there is a line that gives the number of pairs that need to be connected by a wire. The remaining lines in the file are pairs of space-separated coordinates, where each coordinate is a pair of space-separated integers.

As an example, the contents of the small_03.in input file (annotated with comments) isshown in the box on the left. The data describes a 7 x 6 grid with four obstacles and one wire to be routed. This chip is also pictured in the image shown above. Notethe placement of the (overlapping) obstacles and the shortest path (of length 11) connecting the endpoints of wire #1.

Chip, Obstacle, and Wire

The Chip class uses a HashMap to represent the grid on which the chip components are laid out. The map associates coordinates to integers (analogous to our representation of the Board in the Flood It project). Initially, eachcell in the grid is either free (i.e.,Constants.FREE, defined to bezero), covered by an obstacle (i.e.,Constants.OBSTACLE, defined to be-1), or contains the endpoint of a wire (i.e., the wire id#).

There is a constructor in the Chip class that takes an input File of the form described above, and lays out the initial components. For example, here is how the chip pictured above is converted to text by Chip.toString().

In addition to the grid itself, a Chip also maintains a list of Obstacles and a list of Wires. There is one method in each of these classes that requires your attention.

PathFinder

Most of the work that you will do for this project involves devising and implementing arouting algorithm to connect the wires on a chip such that the overall wire length is minimized.

The connectAllWires()method takes a chip, and returns a map that associates a wire id# witha Path. A Path is a list of Coords that connects the endpoints of a wire on achip, avoiding obstacles and other paths while minimizing the total path length required to connect all wires. If the endpoints of some wire cannot be connected in the current layout, then the wire id# should not be associated to any path in the returned map.Note that a path can have the same source and destination points.

You should mark the chip's grid witha path connecting eachwire, thus preventing overlapping of paths.

The chips described in small_07.in and small_08.in are not completely solvable. In the case that you are unable to lay outa certain wire on the chip, print a message stating which wire was not connected.

You have complete freedom when it comes to devising your algorithm. Your goal is to try to find suitable layouts for as many of the sample input files as you can. Feel free to create and use any other auxiliary data structures needed by your algorithm to keep track of information. Feel free to introduce new methods into any of the existing classes.

The best way to go about this is in stages. First try to generate a layout that avoids all the obstacles. Then start experimenting with heuristics that will reduce the cost (in terms of aggregate wire length) of a layout.

If you implement some kind of priority scheme for controlling the search for a path and you choose a suitable data structure to manage path information, then you can quickly layout all the chips, including the one described in huge_01.in. At a minimum, you must be able to quickly layout all the small chips.

Testing

Incorporate a comprehensive sequences of unit tests into Testing.java. The providedvalidateLayout() method will check that a particular layout is valid fora certain grid. Feel free to use it in your own tests.

Consider creating some of your own input files and adding them to the inputs directory. If you do this, name them other_01.in, other_02.in, and so on. Try to design relatively small chips thatwill make your algorithm run slowly. Include a description of your findings in your report (see below).

Report

Create a report.txt file that includes the following five items and include it with your project.

  1. Give an English description of your solution strategy. Explain exactly how wires are connected and what you do when you are unable to make a connection.
  2. Write a high-level pseudo-code description of your algorithm to routeonewire.
  3. Enumerate any data structures you use along the way and explain their purpose in your algorithm.
  4. Tell us about any heuristics you've implemented and why you think they're useful.
  5. In a table, summarize your successes and failures each ofthe sample input files that are included with the project.

GUI

It sure would be nice if we had a GUI to display the connected wires on our chip. If you have the time and the desire, consider creating such a GUI.

Your look doesnot have to mimic the image of the chip shown above, but the obstacles and wires should be clearly visible. Think about interesting ways in whichthe user can interact with your GUI.

Be sure to include a description of your work in your report and also show off your GUI in your walkthrough. Depending on how nice your GUI is, you can potentially earn a small number of extra credit points.

Submission