Creating Matrix/map for Topological sort?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Creating Matrix/map for Topological sort?

  1. #1
    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. #2
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,986

    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. #3
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,014

    Re: Creating Matrix/map for Topological sort?

    Quote Originally Posted by OReubens View Post
    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

  4. #4
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,986

    Re: Creating Matrix/map for Topological sort?

    Quote Originally Posted by D_Drmmr View Post
    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. #5
    Join Date
    Aug 2013
    Posts
    55

    Re: Creating Matrix/map for Topological sort?

    Quote Originally Posted by siddmittal View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center