ISCAS netlist parsing: selection of data structure ?

[Niketh]

hi all,

I am working on C++ coding of fault simulation algorithm of a digital circuit . The first step involves parsing of netlist files. The sample netlist looks like -

# Only 2,3 input gates considered ...
INPUT(1)
INPUT(2)
INPUT(3)
INPUT(6)
INPUT(7)
OUTPUT(22)
OUTPUT(23)
# comment here

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

INPUT are the primary inputs, OUTPUT are the primary outputs, gates are the intermediate nodes. I hope some of you can imagine how this circuit will look like (..:)..).I have attached a sample image file of the above circuit. At this stage i have been able to extract all relevant numbers/values and gate type from the file.

My concern is what are the appropriate data structures that i can use to model the above circuit , so that i will be able to do the following :-

1) given bool values to the inputs , i can propagate it through the intermediate nodes to the output nodes.

2) To each node , i can add customary features like fan-in array, fan-out array.

I have tried out singly linked lists . Is it possible for a node to be pointed by multiple nodes(node1,2,3...) and a node to point to multiple nodes ? And also to be able to ascertain as from which node(node1,2,3...) is the current node traversed from ? Is it possible to propagate an integer value from one node to the other ?

In that case it would be slightly helpful . Any help as earlier as possible will be appreciated.

Thank you in advance
Regards
Niketh

[nezachem]

I don't think a linked list is a right approach. You need a dependency graph, along the lines of

struct gate {
    bool result;
    bool resolved;
    gate * dep1;
    gate * dep2;
};

To calculate the output, you just simply traverse the graph starting from the output gate (remember, pull is almost always better than push):

gate::calculate()
{
    if(!resolved) {
        bool val1 = dep1->calculate();
        bool val2 = dep2->calculate();
        result = nand(val1, val2);
        resolved = true;
    }
    return result;
}

Of course, if some gates require more than one input (and/or perform functions other than nand), replace dep1 and dep2 with std::vector<gate *> dependency , and replace nand a virtual method.

[hactor]

Hello thats sound a very interesting project. You have all done fine ?