
May 10th, 2014, 02:43 AM
#1
Creating Matrix/map for Topological sort?
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:
Code:
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.
Code:
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;
}
Last edited by siddmittal; May 10th, 2014 at 02:46 AM.

May 13th, 2014, 07:21 AM
#2
Re: Creating Matrix/map for Topological sort?
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.

May 13th, 2014, 08:53 AM
#3
Re: Creating Matrix/map for Topological sort?
Originally Posted by OReubens
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.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it.  P. D. Ouspensky

May 13th, 2014, 05:10 PM
#4
Re: Creating Matrix/map for Topological sort?
Originally Posted by D_Drmmr
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

May 14th, 2014, 12:44 AM
#5
Re: Creating Matrix/map for Topological sort?
Originally Posted by siddmittal
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
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
