toplog3.cpp

这个课程项目完成了给定DAG graph

// toplogical_sorting.cpp : Defines the entry point for the console application.


/********************************************************************

This C++ Program is to implement Topological sorting.

This program sorts the given nodes according to their relation pair

This program works in microsoft visual studio 2005 environment.

Author: 

Date: Sep8~Sep18,2008

*********************************************************************/


#include <iostream>
#include <string.h>
#include <stdio.h>
#include <malloc.h>
#include "header.h"


#define LENGTH sizeof(struct data_list)

using namespace std;

int node_num;
int count = 0;
//FILE *stream;

bool cycle_recur=false;
bool toplogical_order = false;


      
void topsort(int node_num, int node_recur,int num_recur, int* predecessor_recur, struct data_list** successor_recur, int* toplogical_recur, int* bag_recur)
{

	num_recur = num_recur+1;
	// the predecessor list is updated.
	toplogical_recur[num_recur] = node_recur;
	// Remove one node from the bag. There are three kinds of data. One group are in the
	// bag, they have the label 1; one group are not in and have more than one in-degree;
	// the third group have already been removed from the group, so they have -1 value for
	// bag label.
	bag_recur[node_recur] = -1;
	

	//if the toplogical sort is already found, this is output to console.
	if(num_recur == node_num){

			/*for(int i=1; i<=node_num; i++)
			      cout<<"toplogical_recur value:  "<<toplogical_recur[i]<<" ";
			    	cout<<endl; */

        //fwrite(toplogical_recur, sizeof(int), (node_num+1)*2, stream);

		for(int i=1; i<=node_num; i++)
		cout<<toplogical_recur[i]<<" ";
		cout<<endl;
		count = count + 1;
		toplogical_order = true;
		return;
	}

    
	struct data_list* data_recur = successor_recur[node_recur];
	//data_recur = successor_recur[node_recur];
	while(data_recur->data_next != NULL){
		data_recur = data_recur->data_next;
		// The predecessor list is updated
		predecessor_recur[data_recur->data] = predecessor_recur[data_recur->data] - 1;
		if(predecessor_recur[data_recur->data]==0){
			// The bag is updated
			bag_recur[data_recur->data] = 1;
		}
	}

	// the cycle label can be changed by the parallel recursive processes, so here the local
	// variable is used to prevent from confusing.
	bool cycle_local = true;
	for(int j=1; j<=node_num; j++){
		
		if(bag_recur[j] == 1){
			cycle_local = false;
			/*cout<<"in the loop:  "<<endl;
			for(int m=0; m<node_num; m++)
				cout<<toplogical_recur[m]<<" ";
			cout<<endl;*/
			int *temp_bag, *temp_toplogical,*temp_predecessor;
			temp_bag = new int[node_num+1];
			temp_toplogical = new int[node_num+1];
			temp_predecessor = new int[node_num+1];
			for(int i=1; i<=node_num; i++){
				// since the bag_recur, toplogical_recur, predecessor_recur are different among 
				// the recursive searches. Since they are pointers to the public memory. Every time,
				// they are copied to make sure are not influenced by the parallel recursive processes.
				temp_bag[i]=bag_recur[i];
				temp_toplogical[i] = toplogical_recur[i];
				temp_predecessor[i] = predecessor_recur[i];
			}
			// the successor list once established will not change in this algorithm(here the predecessor
			//list has been updated), so there is no copy step for successor list. 
			topsort(node_num, j,num_recur, temp_predecessor, successor_recur, temp_toplogical,temp_bag);
		}
	}
	
	if(cycle_local == true){
		cycle_recur = true;
		return;
	}
}



void main()
{
	int END = 0;    
    int n = 0;
	int i;

	int first_var, second_var;
	int *predecessor;

	//stream = fopen( "C:\Documents and Settings\Xin Li\My Documents\Visual Studio 2005\Projects\toplog3\data2text.txt", "wt+" );
	/*stream = fopen("C:\Documents and Settings\Xin Li\My Documents\Visual Studio 2005\Projects\toplog3\newfile.txt", "wt+");
	if(  stream == NULL ){
		printf( "The file 'newfile.text' was not opened\n" );
	}*/

	cout<<"Please input how many nodes to sort in the DAG graph:"<<endl;
	cin>>node_num;	

	predecessor = new int[node_num+1];

	// Initialize the successor list:
	struct data_list **successor;
      	successor = (struct data_list **) malloc((node_num+1)*sizeof(struct data_list *));
		for(i = 1; i <= node_num; i++)
		{

			successor[i] = (struct data_list *) malloc(LENGTH);

			successor[i]->data = i;
			successor[i]->data_next = NULL;
		}		

		for(i = 1; i <= node_num; i++)
		{
			predecessor[i] = 0;

		}
	do
	{

		cout<<"Please input the nodes relation(two integer separated"<<endl;
		cout<<"by space; the pair '0 0' will finish the input)"<<endl;
		cin>>first_var>>second_var;

		struct data_list *currnode, *newnode; 
		if(first_var != END && second_var != END){
		// if either first_var or second_var is empty, this is a single node,
        // we do not need to change the successor/predecessor lists for them

                currnode = successor[first_var];
				newnode = (struct data_list*)malloc(LENGTH);
				newnode->data = second_var;
				newnode->data_next = NULL;
				while(currnode->data_next != NULL){
						currnode = currnode->data_next;
				}
                currnode->data_next = newnode;
				predecessor[second_var] = predecessor[second_var] + 1;
				//cout<<"predecessor[second_var]"<<second_var<<endl;
				//cout<<predecessor[second_var]<<endl;
		}
	}while( first_var != END && second_var != END);

	// bag initialization 

	int *bag;
	bag = new int[node_num+1];
	/*
	for(i=1; i<=node_num; i++)
		cout<<successor[i]->data<<" ";
	cout<<endl;*/

	/*
	for(i=1; i<=node_num; i++)
		cout<<predecessor[i]<<" ";
	cout<<endl; */

	for(int i=1; i<= node_num; i++){
		if(predecessor[i] == 0){
			bag[i] = 1;
		}
		else{
			bag[i] = 0;
		}
	}
	/*
	for(int i=1; i<=node_num; i++){
		cout<<bag[i]<<" ";
	}
	cout<<endl; */
	cout<<"                                                         "<<endl;
	cout<<"---------------------------------------------------------"<<endl;
	cout<<"The toplogical sorting results are shown as follow:"      <<endl;
	cout<<"                                                         "<<endl;



    bool cycle_local = true;
	for(int j=1; j<= node_num;j++){

              
		//		successor_recur[j] = (struct data_list *) malloc(LEN);
		//		successor_recur[j]->data = j; 
		//		successor_recur[j]->data_next_next = NULL;
		//int *predecessor_recur;
		//predecessor_recur = new int[node_num+1];
		//int *bag_recur;
		//bag_recur = new int[node_num+1];
		
		int *toplogical_sort;
		toplogical_sort = new int[node_num+1];
		for(i=0; i<=node_num+1; i++)
			toplogical_sort[i] = 0;

		if(bag[j] == 1){ 
			cycle_local = false;
			int num_initial = 0;			
			int *temp_bag, *temp_toplogical,*temp_predecessor;
			temp_bag = new int[node_num+1];
			temp_toplogical = new int[node_num+1];
			temp_predecessor = new int[node_num+1];
			for(int i=1; i<=node_num; i++){
				// since the bag_recur, toplogical_recur, predecessor_recur are different among 
				// the recursive searches. Since they are pointers to the public memory. Every time,
				// they are copied to make sure are not influenced by the parallel recursive processes.
				temp_bag[i]=bag[i];
				temp_toplogical[i] = toplogical_sort[i];
				temp_predecessor[i] = predecessor[i];
			}
			// the successor list once established will not change in this algorithm(here the predecessor
			//list has been updated), so there is no copy step for successor list. 
			topsort(node_num, j,num_initial, temp_predecessor, successor, temp_toplogical,temp_bag);
		}

	}
   /*
   if( stream)
   {
      if ( fclose( stream ) )
      {
         printf( "The file 'newfile.txt' was not closed\n" );
      }
   }*/

	//if(cycle_recur&(!toplogical_order))
    if(cycle_local == true)
		cycle_recur = true;

	if(cycle_recur)
	{
		cout<<"there is cycle in this graph!"<<endl;
		cout<<"therefore the toplogical sorting is impossible!"<<endl;
	}
	else
	{
		cout<<"---------------------------------------------------------"<<endl;
		cout<<"                                                         "<<endl;
		cout<<"there are "<<count<<" topological sortings found"<<endl;
		cout<<"                                                         "<<endl;
		cout<<"---------------------------------------------------------"<<endl;
	}
	system("pause");
}