i want to analyze a combinational digital circuit. An ASCII file contains the description of the circuit, according to the following format:
<name> <logic gate> <inputs> <outputs> <input 1>…<last input> <output> <delay>
<name>is a string with no more than 20 chars with the name of the logic gate.
<logic gate>is a string with no more than 20 chars that identifies the type of logic gate. It can be
<inputs>is an integer equal to 0 for INPUT, 1 for NOT or OUTPUT, 2 for AND, and OR.
<outputs>is an integer equal to 0 for OUTPUT, or greter than 0 otherwise.
<last input>, <output>are strings with no more than 20 chars each, which identifies the names of the input/output net for the logic gates.
<delay>is an integer that identifies the time the logic gate takes for computing its function.
The program, after reading the file containing the circuit description, has to compute the critical path of the circuit, which can be defined as the path connecting a gate of type INPUT with one of type OUTPUT for whom the sum of the delay of the gates in the path is the highest among all the possible paths in the circuit.
Can anyone please tell me the data structures that are best suited for storing the information the program has to elaborate. How could i load the the data structure into the memory?
A INPUT 0 1 net1 1 B INPUT 0 1 net2 1 C INPUT 0 1 net3 1 G1 NOT 1 1 net1 net4 1 G2 OR 2 1 met3 net4 net5 1 G3 AND 2 1 net4 net2 net6 2 G4 AND 2 1 net6 net5 net7 2 D OUTPUT 1 0 net6 1 E OUTPUT 1 0 E 1 In this example the critical path is A/G1/G2/G4/E with a delay of 7.
How can i implent this.?
If I understand your question correctly, you're really wanting to know which algorithm should you use in order to compute the critical path. This seems similar to a "what is the shortest path?"-type of question. I'd recommendDijkstra's Algorithmfor this problem.