Hey guys!

This week, I highly focused on implementing the basic PODEM algorithm. For a recap, check out the following pseudocode that I am using as a reference:

https://link.springer.com/book/10.1007/978-1-4419-7548-5

https://link.springer.com/book/10.1007/978-1-4419-7548-5

My Progress:

Parser:

I started this week by implementing the parser, which should adhere to the following requirements:

  1. Independent on the data sequence (the gates, input, output pins could be put in any order).
  2. Easily adjustable to accommodate any format.

For the sake of testing, I followed the file format provided in the GitHub repo. However, the second requirement is fulfilled by using regular expressions for parsing the file, and the first requirement is fulfilled by building the graph only after reading the whole file and parsing all the data.

Here is an example of the current file format and the corresponding regular expressions:

# c17
# 5 inputs
# 2 outputs
# 0 inverter
# 6 gates ( 6 NANDs )

INPUT(1)
INPUT(2)
INPUT(3)
INPUT(6)
INPUT(7)

OUTPUT(22)
OUTPUT(23)

10 = NAND(1, 3)
11 = NAND(3, 6)
16 = NAND(2, 11)
19 = NAND(11, 7)
22 = NAND(10, 16)
23 = NAND(16, 19)

Corresponding regular expressions:

# Define regular expression patterns
input_pattern = re.compile(r"INPUT\\((\\d+)\\)")  # Matches input gates
output_pattern = re.compile(r"OUTPUT\\((\\d+)\\)")  # Matches output gates
gate_pattern = re.compile(r"(\\d+) = (\\w+)\\(([\\d, ]+)\\)")  # Matches gates

Graph Building

After parsing the circuit description, the next step was to build the graph representation of the circuit. Here’s a detailed explanation in pseudocode: