DaniWeb Forum Index > Software Development > C++

C++ RSS

Directed graph

•

Join Date: Dec 2008

Posts: 1

Reputation: steve2up is an unknown quantity at this point

Solved Threads: 0

steve2up

Offline

Newbie Poster

Directed graph

Dec 1st, 2008

Hi everyone, I am a U.student from China, I would like ask a question about my assignment.

For the directed graph, I would like to perform topological sort for sorting up nodes, but I encountered some problem in queue which is able to be removed or added with certain elements.

My question is how I can perform queue in topological sort function? my algorithm is here

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
// The topological sort
void DGraph::topologicalSort(){
	if(isTPSorted==false){
		int j=0;
		Queue ts;
		while(ts.size()!=0)
			/*dequeue()  dequeue for queue*/
		for(int i=0;i<50;i++){
			if (visitedTable[i]>=0 && inDegTable[i] == 0)
				/*enqueue(i)  enqueue for queue*/
		}
		while(ts.size()>0){                           
	                predTable[j]=dequeue();/*putting into predTable*/
			int a=predTable[j];
			j++;
			for(int k=0;k<50;k++){
				if(adjMatrix[a][k]==1){ 
					inDegTable[k]--;
					if (inDegTable[k] == 0){
				             /*enqueue(k) enqueue for queue*/
					}
				}
 
			}
		}
		isTPSorted = true;
	}
	return;
}
// The topological sort
void DGraph::topologicalSort(){
	if(isTPSorted==false){
		int j=0;
		Queue ts;
		while(ts.size()!=0)
			/*dequeue()  dequeue for queue*/
		for(int i=0;i<50;i++){
			if (visitedTable[i]>=0 && inDegTable[i] == 0)
				/*enqueue(i)  enqueue for queue*/
		}
		while(ts.size()>0){                           
	                predTable[j]=dequeue();/*putting into predTable*/
			int a=predTable[j];
			j++;
			for(int k=0;k<50;k++){
				if(adjMatrix[a][k]==1){ 
					inDegTable[k]--;
					if (inDegTable[k] == 0){
				             /*enqueue(k) enqueue for queue*/
					}
				}
				
			}
		}
		isTPSorted = true;
	}
	return;
}

my professor gave a hint to perform queue:

In the implementation of the topological sort, a queue data structure is required. he said I can use the queue from the standard template library. Here are some short descriptions of the functions provided by the STL queue.

empty : true if the queue has no elements
front pop: returns a reference to the ﬁrst
push : element of a queue removes the ﬁrst element of a queue adds an element to the end of the queue

For example, include header <queue> and declare my queue as std::queue <int> Queue. And use push as Queue.push(int).

I could find some information in http://www.sgi.com/tech/stl/queue.html. but I don't catch up the point.

Thank you very much

Last edited by Ancient Dragon; Dec 1st, 2008 at 10:48 pm. Reason: add code tags