ramsey .cpp

Ramsey 的实现

/************************************************************************/
/*                          Ramsey                                      */
/************************************************************************/
#include <iostream>
#include <map>
#include <list>
#include <algorithm>
using namespace std;

struct dest_weight 
{
	int dest;
	int weight;
	
	dest_weight(int x)
	{
		dest = x;
		weight = rand()%2;
	}
	dest_weight(int x, int z)
	{
		dest = x;
		weight = z;
	}

};

typedef map<int,list<dest_weight>* >::value_type value_type;

class Ramsey
{
public:
	Ramsey():graph(0),edge_list(0),red(0),blu(0){}
	~Ramsey(){delete graph; delete edge_list;}
	void Creatgraph();
	int get_weight(const int&,const int&);
	bool contains_edge(const int&,const int&);
	void Tri_find();
private:
	int y,red,blu;
	map<int,list<dest_weight>* > * graph;
	list<dest_weight> * edge_list;
};

void main()
{
	Ramsey q;
	q.Creatgraph();
	q.Tri_find();
}

void Ramsey::Creatgraph()
{
	cout<<"Enter note num:"<<endl;
	cin>>y;
	
	graph = new map<int,list<dest_weight>* >;
	for (int i=1;i<=y;i++)
	{
		edge_list = new list<dest_weight>;
		graph->insert(value_type(i,edge_list));	
	}
	
	map<int,list<dest_weight>* >::iterator iter = graph->begin(),end_iter = graph->end();
	while (iter!=end_iter)
	{
		for (int j=1;j<=y;j++)
		{
			if (j!=iter->first)
			{
				if (contains_edge(j,iter->first))
				{
					iter->second->push_back(dest_weight(j,get_weight(j,iter->first)));
				}
				else
				{
					iter->second->push_back(dest_weight(j));
				}
			}		
		}
		iter++;
	}
    	
	iter = graph->begin(),end_iter = graph->end();
	while (iter!=end_iter)
	{
		cout<<iter->first<<" - ";
		list<dest_weight> * edge_list1 = iter->second;
		list<dest_weight>::iterator it = edge_list1->begin(),end_it = edge_list1->end();
		while (it!=end_it)
		{
			cout<<"("<<it->dest<<",";
			cout<<it->weight<<") ";
			it++;
		}	
		cout<<endl;
		iter++;
	}
}

int Ramsey::get_weight(const int& v1,const int& v2)
{
	map<int,list<dest_weight>* >::iterator iter,end_iter;

	iter = graph->find(v1);
	if (iter!=graph->end() && graph->find(v2)!=graph->end())
	{
		list<dest_weight> * edge_list1 = iter->second;
		list<dest_weight>::iterator it_list = edge_list1->begin();

		while (it_list!=edge_list1->end())
		{
			if (it_list->dest==v2)
			{
				return it_list->weight;			
			}
			it_list++;
		}
	}
	return -1;
}

bool Ramsey::contains_edge(const int& v1,const int& v2)
{
	map<int,list<dest_weight>* >::iterator iter,end_iter;
	iter = graph->find(v1);
	if (iter!=graph->end() && graph->find(v2)!=graph->end())
	{
		list<dest_weight> * edge_list1 = iter->second;
		list<dest_weight>::iterator it_list = edge_list1->begin();

		while (it_list!=edge_list1->end())
		{
			if (it_list->dest==v2)
			{
				return true;			
			}
			it_list++;
		}
	}
	return false;
}

void Ramsey::Tri_find()
{
	for (int i=1;i<y;i++)
	{ 
		for (int k=1;k<=y-2;k++)
		{
			for (int j=1;j<=y;j++)
			{
				if (j>i+k)
				{				
					if (get_weight(i,i+k)==get_weight(i+k,j))
					{
						if (get_weight(j,i)==get_weight(i,i+k))
						{
							if(get_weight(j,i)==0)
							{
								cout<<"可形成红色三角型:"<<endl;
							    cout<<i<<"-"<<i+k<<"-"<<j<<endl;
								red++;
							}
							if(get_weight(j,i)==1)
							{
								cout<<"可形成蓝色三角型:"<<endl;
							    cout<<i<<"-"<<i+k<<"-"<<j<<endl;
								blu++;
							}
						}
					}				
				}
			}
		}
	}
	cout<<"red="<<red<<endl;
	cout<<"blu="<<blu<<endl;
}