Creating Matrix/map for Topological sort?

[siddmittal]

I am trying to simulate the logical circuits having NAND gates. I am reading the structure from .bench file. The structure of a circuit looks like below:

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


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

It can be seen that the inputs for Gate 22 are 10 and 16 which are also NAND gates. On the other hand, for gate 10, the inputs are 1 and 3 which are simple inputs. So, i need to sort the gates topologically. Although topological sort will not affect the output for this particular example but i have big circuits also in which topological sort is required. But we can use this simple example to do the topological sort.

My effort:

I thought to create a map which will keep the information about the gate name and its indegree. But i am unable to proceed further.

void Circuit::topologicalSort()			//topological sorting (for the mixed circuits)
{

	int counter = 0;
	std::map<string, int> unsortTopoList; //this list keeps a track of gate name and its Indegree
	
	for(int i=0; i<gates.size(); i++)
	{	
		string gate_name = gates[i]->getName();
		int INDEGREE = 0;
		for(int j=0; j<gates[i]->getNumInputs(); j++)
		{
			string gate_input_name = gates[i]->getInput(j)->getName();
			int result = ( findGate(gate_input_name) ); // We trying to check if the given gate's input is also a gate or not.
			INDEGREE = INDEGREE + result;
			result = 0;
		}
		
		unsortTopoList[ gates[i]->getName() ] = INDEGREE; //This list will tell that the indegree of gate name "gate_input_vec[i][0]"
		counter++;
	}

	for(int i=0; i<counter; i++)
	{
		cout<<"\nGate: "<<gates[i]->getName()<<"  is having Indegree: "<<unsortTopoList[ gates[i]->getName() ];
	}

	cout<<"\n";
}

int Circuit::findGate( string gateName )
{
	int result = 0;

	for(int i=0; i<gates.size(); i++)
	{
		if( gateName.compare( gates[i]->getName() )  ==0 ) //"==0" means that they are same.
		{
			result= 1;
			break;
		}
		else
			result= 0;
	}
	
	return result;
}

[OReubens]

a topological sort wont help you at all if you want to handle a case like an SR flip flop (which is a pretty common use for NAND gates)

the simple solution for gate simulations is to just keep iterating over all the gates and reprocessing the output until the simulation stabilizes
THe worst case scenario is that it takes as many passes as you have gates.
if it doesn't stabilize after gate+1 passes, you have an unstable circuit.

This will work for a "small" amount of gates. for massive scale simulation there are more elaborate routines, but the big problem is any kind of feedback loop (like an SR Flip flop)

assuming there is no feedback, the solution is not to sort like you're doing here.
put all gates in a "to be considered" queue
pop a gate, if both inputs are defined, add it to the "processed" container (a list or vector), if either input is not yet defined, put it back at the end of the "to be considered" queue
repeat until queue is empty.
you now have all gates in an order that can be resolved via a single pass over the "processed" container.

[D_Drmmr]

assuming there is no feedback, the solution is not to sort like you're doing here.
put all gates in a "to be considered" queue
pop a gate, if both inputs are defined, add it to the "processed" container (a list or vector), if either input is not yet defined, put it back at the end of the "to be considered" queue
repeat until queue is empty.
you now have all gates in an order that can be resolved via a single pass over the "processed" container.

That's basically the algorithm for finding a topological order.

[OReubens]

That's basically the algorithm for finding a topological order.

I know...
but it doesn't really work with feedback loops.
THere are more elaborate systems for efficiently handling those in a sim. But you won't find a lot of info on those. it tends to be very proprietary

[zizz]

So, i need to sort the gates topologically.

It seems Boost offers a topological sort algorithm,

http://www.boost.org/doc/libs/1_55_0...ical_sort.html