gdcohan / circuits Goto Github PK

README:
This project was predicated on trying to analyze an image of a circuit and determine if it had been produced according to its specifications. The image came in the form of a .png file where the pixels were either blue, black, or white, representing pins, wires, and blank spaces respectively. The specifications would list pins that had to be connected via wires, forming "islands" of connected circuitry. The answers below are to questions regarding the design of the program. analysis.txt provides a big-O analysis of the program. The actual program is in circuit-analysis.rkt, and support code is in circuit-support.rkt.

Further documentation of the assignment can be found at:
http://www.cs.brown.edu/courses/cs019/2011/assignments/circuits

1) How do we find islands?
There are two different situations in which we need to detect islands: from the connection list, and from the image.

To detect islands from the connection list, we use a function called connections->islands. Throughout the function, we keep track of an accumulated list of islands. For every connection in the list, we look for both pins of the connection in the islands we have found so far. There are several cases we then encounter: A) Both pins are in the same island. In this case, we ignore this connection. B) Neither pin is in any island. In this case, we cons a new island containing the connected pins onto our list of islands. This also serves as our base case when the list of islands is empty. C) Only one pin is in any of the islands. In this case, we add the other pin to the island that contains the first pin. D) The two pins are in different islands. In this case, we merge the islands by using the append function.

To detect islands from the image, we use a function called image->islands. The first step of this function is to process the image, converting each pixel in the image into what we call a super-node. A super-node contains the color of the node, its row, and its column. By assumption, these are only black, white, or blue. We also store these super-nodes in a vector of vectors, rather than in a list of lists (which is how the input is originally stored). We then traverse the "super-circuit" from left to right and top to bottom. Whenever we encounter a wire or blank space, we just continue traversing. When we encounter a pin, we first check whether the pin is in our accumulated islands--if so, we just continue traversing. If not, we follow all possible connections of the pin, accumulating an island as we go along using a depth-first traversal. The function that does this is called traverse. After we have found all other pins in the island, we add this to our list of islands and continue traversing. 

2) How do we detect open circuits? 

NOTE: Our function processes open and short circuits in the same sweep of the lists of islands. 

We start by walking through the list of islands generated by the connections. For any given island that came from the connection list (hereafter referred to as a "connection island"), we find all islands in the image that contain any pin from the connection island. We keep track of these islands with indices representing their position in the list of islands. In addition, we remove the pins from the islands of the image as we find them. For example, if we have an island from the connection list that contains pins A, B, and C, and A and B are in the first island from the image while C is in the second, this function would accumulate (list 0 1). Also in this example, A, B, and C would be removed from their respective islands in the image-island list. After we have done this for all of the pins in a connection island, we process this accumulated list of indices. 

Given a list of indices, we can detect open circuits between all the islands in the list. This is because we generated the list of indices from a single connection island--thus, if there are two different indices, that means pins from one connection island have been found in two islands from the image. 

Once we have detected these open circuits, we check them against an accumulated list of open circuits so as to avoid repeating open circuit faults. If the open circuit is not already present, we add it to our list of open circuits. 

3) How do we detect short circuits? 

We generate a list of indices for each connection island, as stated above. Before moving on to the next connection island, we check each of those islands in the list of indices to see if they have any remaining pins. If they do, that means that the island contains pins from connection-islands beside the one being processed. This indicates a short circuit, as there are two pins connected in the image that should not be connected according to the connection list. 

Once we have detected these short circuits, we check them against an accumulated list of short circuits so as to avoid repeating open circuit faults. If the short circuit is not already present, we add it to our list of short circuits.

After processing all the connection islands, there may remain islands from the image that contained no pins from the connection list. If these islands consist of more than one pin, this indicates an additional short circuit between two pins that were connected when they should not have been. We then add these short-circuits to our list.