CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Creating Matrix/map for Topological sort?

1. Junior Member
Join Date
Apr 2014
Posts
6

## 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.

2. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## 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.

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.

4. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## 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

5. Banned
Join Date
Aug 2013
Posts
55

## 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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•