Detailed Description

• Study first the following article:

Valdes, J., R.E. Tarjan and E.L. Lawler, "The Recognition of Series Parallel Digraphs", SIAM Journal on Computing, Vol. 11(2), pp 298-313, (May 1982).

Note: Not all parts of the article are relevant for the project. The most important section is Section 3.3 that deals with "edge series-parallel (ESP)" graphs, but other parts of the article should also be read carefully in order to understand that section.
• The description of the CMOS complex gate network should be read from a text file with the following structure:
  • The first line gives the number of transistors in the network.
  • The second line gives the number of nets in the network.
  • Each following line describes a single transistor by means of three items. The first two are numbers corresponding to the nets to which the transistor's source and drain are connected. The third is a string that represents the signal connected to the transistor's gate.
  • The following convention should be observed for the net numbers: number 0 is reserved for the negative supply voltage (Vss), number 1 for the positive supply voltage (Vdd) and number 2 for the output of the complex gate.
  • Here is an example of a NAND gate:

       +------+ Vdd (1)
       |      |
    A ++   B ++
    -o|    -o|
      ++     ++
       |      |
       +--+---+ out (2)
          |
         ++
      A -|
         ++
          | (3)
         ++
      B -|
         ++
          |
       +--+---+ Vss (0)
          

    The file describing this network looks like:

    4
    4
    1 2 A
    2 1 B
    2 3 A
    0 3 B
    

• If the network is correct, your program should print a Boolean expression describing the complex gate's function (e.g. not(and(a,or(b,c)))). If the network is incorrect, the program should print an appropriate error message.
• Pay attention to the following issue: the article deals with directed graphs, while a transistor network is undirected (there is no distinction between the source and drain ports). How can the algorithm of the article be adapted in such a way that it can handle undirected graphs? If you do not know a solution to this question, you can assume that the input file is a directed graph and make sure that each edge has the correct direction.
• Ideally, your program should be able to deal with networks of arbitrary size. This requires dynamic data structures. You are allowed to impose a maximum network size, if you prefer to do so.
• If you run out of time, you may limit yourself to verifying twe two halves of the network (composed of pMOSTs and nMOSTs respectively) and skip the duality test.
• The algorithm of Valdes, et al. operates in linear time. One of the most important aspects of this project is that you have been sufficiently careful in your implementation in order not to introduce a higher worst-case time complexity.