fuzzygraph.cpp

基于模糊费用最小生成树的算法 的源代码 prim算法 模糊数综合排序

#include "FuzzyGraph.h"

FuzzyGraph::FuzzyGraph( int Num, string DistFile )
{
	this->Num = Num;

	// given file exist
	FILE *dFile;
	dFile = fopen( DistFile.c_str( ), "r" );

	int row=0, col=0;
	while( !feof( dFile ) )
	{
		vector<FuzzyEdge> tempEdges;
		for( int i = 0; i < Num; i++ )
		{	
			int dist;
			float memb;
			fscanf( dFile, "%d,%f ", &dist, &memb );
			tempEdges.push_back( FuzzyEdge(dist,memb,row,col) );
			if ( Num == ++col ) col = 0;
		}
		Edges.push_back( tempEdges );
		row++;
	}
	fclose( dFile );
}

// test I/O function
void FuzzyGraph::Display( )
{
	for( int i = 0; i < Num; i++ )
	{
		for( int j = 0; j < Num; j++ )
		{ 
			cout<<Edges[i][j].from<<","<<Edges[i][j].to<<":"
				<<Edges[i][j].distance<<","<<Edges[i][j].membership<<endl; 
		}
	}
}

void FuzzyGraph::_Prim_Lee_Li( float beta )
{
	CurrentEdges.clear( );
	vector<int> V;
	vector<bool> mark;
	for( int i = 0; i < Num; i++ )
	{ V.push_back( i ); mark.push_back(false); }
	mark[0]=true;
	bool NotEnd = true;
	float CurrentR = 0;
	while( NotEnd )
	{
		vector<FuzzyEdge> CandidateEdges;
		// candidate edges
		for( i = 0; i < Num; i++ )
			if( mark[i] )
				for( int j = 0; j < Num; j++ )
					if( !mark[j] && i != j )
					{
						// add E(i,j) as current candidate
						CandidateEdges.push_back( Edges[i][j] );
					//	cout<<"Edge "<<i<<" to "<<j<<" added\n";
					}
		//cout<<endl;
		//exit(0);
		// compute all the adjacent edges
		vector<float> tempCost;
		for( i = 0; i < CandidateEdges.size(); i++ )
		{
			CurrentEdges.push_back( CandidateEdges[i] );

			double avg,var;
			double xsum=0,sum=0,x2sum=0;
			for( int j = 0; j < CurrentEdges.size(); j++ )
			{
				sum = sum+CurrentEdges[j].membership-sum*CurrentEdges[j].membership;
				xsum += sum*CurrentEdges[j].distance;
				x2sum += xsum*CurrentEdges[j].distance;
			}
			avg = xsum/sum; 
			var = x2sum/sum-pow(avg,2);// > 0 ? sqrt(x2sum/sum-pow(avg,2)) : 0;
			tempCost.push_back( beta*avg+(1-beta)*(1-var) );
			//cout<<i<<" "<<tempCost[i]<<endl;
			CurrentEdges.pop_back( );
		}	
		// add minimum cost edge to CurrentEdges
		int index = 0;
		float min = tempCost[0];
		for( i = 1; i < tempCost.size(); i++ )
			if( min > tempCost[i] && tempCost[i] > 0 )
			{
				index = i;
				min = tempCost[i];	
			}
		CurrentR = min;
		CurrentEdges.push_back(CandidateEdges[index]);
		//cout<<"Edge Added "<<CandidateEdges[index].from<<" "<<CandidateEdges[index].to<<endl;
		// update mark
		mark[CandidateEdges[index].to] = true;
		//for( i = 0; i < mark.size(); i++ )
		//	cout<<mark[i]<<" ";
		//cout<<endl;
		int count = 0;
		for( i = 0; i < mark.size(); i++ )
			if( mark[i] ) count++;
		if( count == Num ) NotEnd = false;
	}
	// test code-Display Solution
	cout<<"Final Cost: "<<CurrentR<<endl;
	for( i = 0; i < CurrentEdges.size(); i++ )
	{
		cout<<"Edge "<<i+1<<": From "<<CurrentEdges[i].from+1<<" To "<<CurrentEdges[i].to+1<<endl;
	}
}