topology.cpp

模拟P2P各种网络环境的,适合新手们的学习,不错的源码.

#include "Topology.h"
#include "Property.h"
#include "Graph.h"
#include "LinkProperty.h"
#include "NodeProperty.h"
#include "Agent.h"

ostream &operator<<(ostream &os, const vector< vector<int> > &vec);
ostream &operator<<(ostream &os, const vector< vector<unsigned long> > &vec);
ostream &operator<<(ostream &os, const vector<Node> &vec);
ostream &operator<<(ostream &os, map<string, Link> &vec);
static string intToString(int i, int j);
static void FloydWarshall(int n, vector< vector<int> >&Pk, vector< vector<unsigned long> > &Dk);

template<typename type>
inline static int ReadData(vector< vector<type> > &matrix, FILE *fp)
{
	unsigned int i, j;
	unsigned int n;
	char *pbuf;
	char buf[16 * BUFSIZ];

	if(!fp)
		return -1;
	
	n = matrix.size();	
	if(!n)
		return 0;
	if(n != matrix[0].size())
		return -1;

	for(i = 0; i < n; i++)
	{
		pbuf = fgets(buf, 16 * BUFSIZ, fp);
		if(!pbuf)
			return -1;
		
		*(pbuf + strlen(buf) - 1) = '\0';
		if(!*pbuf)
			return -1;
		
		for(j = 0; j < n; j++)
		{
			if(!*pbuf)
				return -1;
			if(typeid(type) == typeid(int))
				matrix[i][j] = atoi(pbuf);
			else if(typeid(type) == typeid(unsigned long))
				matrix[i][j] = atol(pbuf);
			else
				return -1;
			while(*pbuf != ' ' && *pbuf != '\0')
				pbuf++;
			while(*pbuf == ' ' && *pbuf != '\0')
				pbuf++;
		}
	}
	return n;
}

template<typename type>
inline static int WriteData(const vector< vector<type> > &matrix, const char *file)
{
	unsigned int i, j;
	unsigned int n;
	char word[64];
	char buf[16 * BUFSIZ];
	FILE *fp;

	if(!file)
		return -1;
	
	n = matrix.size();
	if(!n)
		return 0;
	if(n != matrix[0].size())
		return -1;

	fp = fopen(file, "a");
	if(!fp)
		return -1;
	
	for(i = 0; i < n; i++)
	{
		*buf = '\0';
		for(j = 0; j < n; j++)
		{
			if(typeid(type) == typeid(int))
				snprintf(word, 64, "%d ", (int)matrix[i][j]);
			else if(typeid(type) == typeid(unsigned long))
				snprintf(word, 64, "%ld ", (unsigned long)matrix[i][j]);
			else
				return -1;
			strcat(buf, word);
		}
		*(buf + strlen(buf) - 1) = '\n';
		fputs(buf, fp);
	}
	fclose(fp);
	return n;
}




Topology *Topology::mInstance = NULL;

Topology::Topology(): mNodeNumber(0), mLinkNumber(0)
{ }

Topology *Topology::getInstance()
{
	if(!mInstance)
		mInstance = new Topology;
	return mInstance;
}

void Topology::reset()
{
	mNodeNumber = 0;
	mLinkNumber = 0;
	mNode.clear();
	mLink.clear();
	mDelayMatrix.clear();
	mPredecessorMatrix.clear();
}

double Topology::getDelay(int id1, int id2) const
{
	if(id1 < 0 || id2 < 0 || id1 >= mNodeNumber || id2 >= mNodeNumber)
		return -1;
	else
		return mDelayMatrix[id1][id2] / MAGNIFIER;
}

double Topology::getBandwidth(int id1, int id2)
{
	string key1, key2;

	if(id1 < 0 || id2 < 0 || id1 >= mNodeNumber || id2 >= mNodeNumber)
		return -1;
	
	key1 = intToString(id1, id2);
	key2 = intToString(id2, id1);
	
	if(mLink.find(key1) != mLink.end())
		return mLink[key1].getBandwidthManager().getBandwidth();
	if(mLink.find(key2) != mLink.end())
		return mLink[key2].getBandwidthManager().getBandwidth();
	
	return -1;
}

double Topology::getAvailableBandwidth(bool flag, Agent *agent)
{
	if(!agent)
		return -1;
	int aid = agent->getID();
	int nid = agent->getNode()->getID();
	Link *pl = agent->getNode()->getVLink(agent);
	if(!pl)
		return -1;
	if(aid < nid)
		return pl->getBandwidthManager().getAvailableBandwidth(!flag);
	else
		return pl->getBandwidthManager().getAvailableBandwidth(flag);
	return -1;
}

Node *Topology::getNode(int id)
{
	if(id < 0 || id > mNodeNumber)
		return NULL;
	return &mNode[id];
}

int Topology::getNodeNumber()
{ return mNodeNumber; }

int Topology::getLinkNumber()
{ return mLinkNumber; }

Link *Topology::getLinkBetween(int id1, int id2)
{
	string key1, key2;

	if(id1 < 0 || id2 < 0 || id1 >= mNodeNumber || id2 >= mNodeNumber)
		return NULL;
	
	key1 = intToString(id1, id2);
	key2 = intToString(id2, id1);
	
	if(mLink.find(key1) != mLink.end())
		return &mLink[key1];
	if(mLink.find(key2) != mLink.end())
		return &mLink[key2];
	
	return NULL;
}

vector<Link *> Topology::getVLinkBetween(Agent *agent1, Agent *agent2)
{
	int id1, id2;
	Link *pl;
	vector<Link *> temp;
	
	id1 = agent1->getNode()->getID();
	id2 = agent2->getNode()->getID();
	pl = mNode[id1].getVLink(agent1);
	if(!pl) {
		temp.clear();
		return temp;
	}
	else
		temp.push_back(pl);

	vector<Link *> path = getAllLinkBetween(id1, id2);
	unsigned int n = path.size();
	for(unsigned int i = 0; i < n; i++)
		temp.push_back(path[n - i - 1]);
	
	pl = mNode[id2].getVLink(agent2);
	if(!pl) {
		temp.clear();
		return temp;
	}
	else
		temp.push_back(pl);
	
	return temp;
}

vector<Link *> Topology::getAllLinkBetweenOld(int id1, int id2)
{
	int pre, lastpre;
	vector<Link *> path;
	
	if(id1 < 0 || id2 < 0 || id1 >= mNodeNumber || id2 >= mNodeNumber)
		return path;
	
	if(id1 == id2)
		return path;
		
	pre = mPredecessorMatrix[id1][id2];
		
	if(pre == -1)
		return path;
	else if(pre == id1)
	{
		Link *link = getLinkBetween(id1, id2);
		if(link)
			path.push_back(link);
		return path;
	}
	
	lastpre = id2;
	do
	{
		Link *link = getLinkBetween(pre, lastpre);
		if(!link)
		{
			path.clear();
			return path;
		}
		path.push_back(link);
		lastpre = pre;
		pre = mPredecessorMatrix[id1][pre];

	}
	while(pre != -1);
	
	return path;
}

vector<Link *> Topology::getAllLinkBetween(int i, int j)
{
	int pre, lastpre;
	vector<Link *> path;
	
	int aidi = mNode[i].getAID();
	int aidj = mNode[j].getAID();
	int typei = mNode[i].getType();
	int typej = mNode[j].getType();
	int flag;

	int indexi, indexj;
	int indexa, indexA;
	int indexb, indexB;

	if(i < 0 || j < 0 || i >= mNodeNumber || j >= mNodeNumber)
		return path;
	
	if(i == j)
		return path;
	
	if(aidi == aidj)
	{
		indexi = mDomain[aidi].reverseMapTable[i];
		indexj = mDomain[aidj].reverseMapTable[j];
		flag = 1;
	}
				
	else if(typei == typej && typei == TRANSIT)
	{
		indexi = mDomain[mAsNumber].reverseMapTable[i];
		indexj = mDomain[mAsNumber].reverseMapTable[j];
		flag = 2;
	}

	else
	{
		indexi = mDomain[aidi].reverseMapTable[i];
		indexj = mDomain[aidj].reverseMapTable[j];

		set<int> &transitTablei = mDomain[aidi].transitTable;
		set<int> &transitTablej = mDomain[aidj].transitTable;
		set<int>::iterator iti;
		set<int>::iterator itj;

		unsigned long delay = UINT_MAX;

		for(iti = transitTablei.begin(); iti != transitTablei.end(); iti++)
		{
			int ida = mDomain[aidi].mapTable[*iti];
			int indexaa = *iti;
			int indexAA = mDomain[mAsNumber].reverseMapTable[ida];
			unsigned long delayItoA = mDomain[aidi].delayMatrix[indexi][*iti];	
			for(itj = transitTablej.begin(); itj != transitTablej.end(); itj++)
			{
				int idb = mDomain[aidj].mapTable[*itj];
				int indexbb = *itj;
				int indexBB = mDomain[mAsNumber].reverseMapTable[idb];
				unsigned long delayAtoB = mDomain[mAsNumber].delayMatrix[indexAA][indexBB];
				unsigned long delayBtoJ = mDomain[aidj].delayMatrix[*itj][indexj];
				if(delay > delayItoA + delayAtoB + delayBtoJ)
				{
					delay = delayItoA + delayAtoB + delayBtoJ;
					indexa = indexaa;
					indexA = indexAA;
					indexb = indexbb;
					indexB = indexBB;
				}
			}
		}
		flag = 3;
	}
	if(flag == 1)
	{	
		int idi = i, idj = j;
		pre = mDomain[aidi].predecessorMatrix[indexi][indexj];
		if(pre == -1)
			return path;
		else if(pre == indexi)
		{
			Link *link = getLinkBetween(idi, idj);
			if(link)
				path.push_back(link);
			return path;
		}
	
		lastpre = indexj;
		do
		{
			idi = mDomain[aidi].mapTable[lastpre];
			idj = mDomain[aidj].mapTable[pre];
			Link *link = getLinkBetween(idi, idj);
			if(!link)
			{
				path.clear();
				return path;
			}
			path.push_back(link);
			lastpre = pre;
			pre = mDomain[aidi].predecessorMatrix[indexi][pre];
		}
		while(pre != -1);
	
		return path;
	}
	if(flag == 2)
	{
		int idi = i, idj = j;
		pre = mDomain[mAsNumber].predecessorMatrix[indexi][indexj];
		if(pre == -1)
			return path;
		else if(pre == indexi)
		{
			Link *link = getLinkBetween(idi, idj);
			if(link)
				path.push_back(link);
			return path;
		}
	
		lastpre = indexj;
		do
		{
			idi = mDomain[mAsNumber].mapTable[lastpre];
			idj = mDomain[mAsNumber].mapTable[pre];
			Link *link = getLinkBetween(idi, idj);
			if(!link)
			{
				path.clear();
				return path;
			}
			path.push_back(link);
			lastpre = pre;
			pre = mDomain[mAsNumber].predecessorMatrix[indexi][pre];
		}
		while(pre != -1);
	
		return path;	
	}
	if(flag == 3)
	{
		int idi = i, idj = j;
		pre = mDomain[aidj].predecessorMatrix[indexb][indexj];
		if(pre != -1)
		{
			if(pre == indexb)
			{
				idi = mDomain[aidj].mapTable[indexj];
				idj = mDomain[aidj].mapTable[indexb];
				Link *link = getLinkBetween(idi, idj);
				if(link)
					path.push_back(link);
				else {
					path.clear();
					return path;
				}
			}
			else {
				lastpre = indexj;
				do
				{
					idi = mDomain[aidj].mapTable[lastpre];
					idj = mDomain[aidj].mapTable[pre];
					Link *link = getLinkBetween(idi, idj);
					if(!link)
					{
						path.clear();
						return path;
					}
					path.push_back(link);
					lastpre = pre;
					pre = mDomain[aidj].predecessorMatrix[indexb][pre];
				}
				while(pre != -1);
			}
		}