graph.cpp

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

#include "Graph.h"
#include "NodeProperty.h"
#include "LinkProperty.h"
#include "BandwidthManager.h"

#ifdef BUFSIZ
#undef BUFSIZ
#define BUFSIZ 4096
#endif

Node Graph::getNode(int id) const
{
	assert(id >= 0 && id < (int)mNode.size());
	return mNode[id];
}

Graph::Graph(): mValid(false)
{ }

void Graph::setGraphFile(string file)
{ mGraphFile = file; }

string Graph::getGraphFile() const
{ return mGraphFile; }

void Graph::setComment(string comment)
{ mComment = comment; }

string Graph::getComment() const
{ return mComment; }

void Graph::setCreator(string creator)
{ mCreator = creator; }

string Graph::getCreator() const
{ return mCreator; }

void Graph::setValid(bool valid)
{ mValid = valid; }

bool Graph::isValid() const
{ return mValid; }

void Graph::addNode(const Node &node)
{ mNode.push_back(node); }

unsigned int Graph::getAsNumber() const
{ return mAsNumber; }

int Graph::getNodeNumber() const
{ return mNode.size(); }

void Graph::addLink(string key1, string key2, const Link &link)
{
	if(mLink.find(key1) != mLink.end() || mLink.find(key2) != mLink.end())
	{
		cout << "error: (in graph)add duplicate link into link set" << endl;
		exit(-1);
	}
	mLink[key1] = link;
}

int Graph::getLinkNumber() const
{ return mLink.size(); }

map<string, Link> Graph::getAllLink() const
{ return mLink; }

vector<Node> Graph::getAllNode() const
{ return mNode; }

void Graph::fromBRITEFile(string file)
{
	setCreator("Brite");
	setComment("TopDown");
	setGraphFile(file);
	readBRITEGraph(file);
}

static char *NextToken(char *);
static string intToString(int i, int j);
void Graph::readBRITEGraph(string file)
{
	/* the following codes are in c style; */
	int type, typea, typeb;
	int n;
	char *p = NULL;
	char buf[BUFSIZ];
	FILE *fp;

	Node node;
	Link link;
	NodeProperty nprop;
	LinkProperty lprop;
	BandwidthManager bmana;

	int startId;
	int nodeId;
	int asId;
	int coord;
	int from, to;
	double distance, delay, band;
	string lable, key, keya;
	int asCount = -1;
	int nodeCount = -1;
	int edgeConut = -1;
	bool flag, same;

	nprop.setTraffic("not-use");
	lprop.setCost(0);

	if(!(fp = fopen(file.c_str(), "r")))
	{
		printf("open error: %s\n", strerror(errno));
		exit(-1);
	}
	
	while(fgets(buf, BUFSIZ, fp))
	{		
		p = NextToken(buf);
		if(!p)
			continue;
		
		else if(*p == '#')
			continue;
		
		else if(strncmp(p, "Topology", strlen("Topology")) == 0)
			continue;
		
		else if(strncmp(p, "Model", strlen("Model")) == 0)
		{
			p = NextToken(NULL);
			p = NextToken(NULL);
			p = NextToken(NULL);
			p = NextToken(NULL);
			if(p != NULL && asCount == -1)
			{
				asCount = atoi(p);
				assert(asCount >= 0);
				mAsNumber = (unsigned int)asCount;
			}
			else			
				continue;
		}
		
		else if(strncmp(p, "Nodes", strlen("Nodes")) == 0)
		{
			n = 0;
			flag = true;
			p = NextToken(NULL);
			p = NextToken(NULL);
			assert(p);
			nodeCount = atoi(p);
			assert(nodeCount >= 0);
			if(nodeCount > 0)
			{
				do {
					fgets(buf, BUFSIZ, fp);
					p = NextToken(buf);
				} while(!p);
				startId = atoi(p);
				assert(startId >= 0);
				goto gn;
			}
		}
		
		else if(strncmp(p, "Edges", strlen("Edges")) == 0)
		{
			n = 0;
			flag = false;
			p = NextToken(NULL);
			p = NextToken(NULL);
			assert(p);
			edgeConut = atoi(p);
			assert(edgeConut >= 0);
			continue;
		}
		
		else if(flag == true)
		{
gn:			nodeId = atoi(p) - startId;
			assert(nodeId == n);
			node.setID(nodeId);
			
			p = NextToken(NULL);
			assert(p);
			coord = atoi(p);
			assert(coord >= 0);
			nprop.setX((unsigned long)(AMPLIFIER * coord));
			
			p = NextToken(NULL);
			assert(p);
			coord = atoi(p);
			assert(coord >= 0);
			nprop.setY((unsigned long)(AMPLIFIER * coord));
			
			p = NextToken(NULL);
			p = NextToken(NULL);
			p = NextToken(NULL);
			assert(p);
			asId = atoi(p);
			assert(asId >= 0);
			node.setAID(asId);
			
			p = NextToken(NULL);
			assert(p);	
			if(strncmp(p, "RT_NODE", 7) == 0)
			{
				nprop.setType(STUB);
				lable = "stub";
			}
			else if(strncmp(p, "RT_BORDER", 9) == 0){
				nprop.setType(TRANSIT);
				lable = "tran";
			}
			else
			{
				printf("unknown node type, abort!\n");
				exit(-1);
			}
			nprop.setLable(lable);
			
			p = NextToken(NULL);
			assert(!p);
			
			node.setProperty(nprop);
			addNode(node);
			n++;
		}
		else if(flag == false)
		{
			p = NextToken(NULL);
			assert(p);
			from = atoi(p) - startId;
			assert(from >= 0 && from < nodeCount);

			p = NextToken(NULL);
			assert(p);
			to = atoi(p) - startId;
			assert(to >= 0 && to < nodeCount);

			assert(from != to);
			if(from > to) {
				int temp = from;
				from = to;
				to = temp;
			}
			key = intToString(from, to);
			keya = intToString(to, from);

			link.setFrom(from);
			link.setTo(to);

			p = NextToken(NULL);
			assert(p);
			distance = atof(p);
			assert(distance >= 0);
			lprop.setDistance((unsigned long)(AMPLIFIER * distance));

			p = NextToken(NULL);
			assert(p);
			delay = atof(p);
			assert(delay >= 0);
			lprop.setDelay((unsigned long)(MAGNIFIER * delay));

			p = NextToken(NULL);
			assert(p);
			band = atof(p);
			assert(band >= 0);
			lprop.setBandwidth((unsigned long)(MAGNIFIER * band));
			bmana.setBandwidth((unsigned long)(MAGNIFIER * band));

			p = NextToken(NULL);
			p = NextToken(NULL);
			p = NextToken(NULL);
			typea = getNode(from).getType();
			typeb = getNode(to).getType();
			same = (getNode(from).getAID() == getNode(to).getAID());
			if(typea == STUB && typeb == STUB && same)
			{
				type = STU_STU;
				lable = "stub-stub";
			}
			else if(typea == TRANSIT && typeb == TRANSIT && same)
			{
				type = TRA_TRA_INTRA;
				lable = "tran-tran-a";
			}
			else if(typea == TRANSIT && typeb == TRANSIT && !same)
			{
				type = TRA_TRA_INTER;
				lable = "tran-tran-b";
			}
			else if(typea == STUB && typeb == TRANSIT && same)
			{
				type = STU_TRA;
				lable = "stub-tran";
			}
			else if(typea == TRANSIT && typeb == STUB && same)
			{
				type = STU_TRA;
				lable = "tran-stub";
			}
			else
			{
				printf("unknown edge type, abort!\n");
				exit(-1);
			}
			lprop.setType(type);
			lprop.setLable(lable);

			p = NextToken(NULL);
			assert(p);
			if(strncmp(p, "U", 1) == 0)
				lprop.setDirection(false);
			else if(strncmp(p, "D", 1) == 0)
				lprop.setDirection(true);
			else
			{
				printf("unknown edge type, abort!\n");
				exit(-1);
			}

			link.setProperty(lprop);
			link.setBandwidthManager(bmana);
			addLink(key, keya, link);
			mNode[from].setLinkTo(to);
			if(!link.getProperty().getDirection()) {
				mNode[to].setLinkTo(from);
			}
			n++;
		}
		else
		{
			fprintf(stderr, "error occured when parse graph file.\n");
			exit(-1);
		}
	}
	assert(nodeCount == (int)mNode.size());
	assert(edgeConut == (int)mLink.size());
	setValid(true);
	printf("parse graph file seccess\n");
	printf("as = %d\n", asCount);
	printf("node = %d, edge = %d\n", nodeCount, edgeConut);
}

static char *NextToken(char *pbuf)
{
	char *pp;
	static char *p;
	static char buf[BUFSIZ];
	if(pbuf)
	{
		strcpy(buf, pbuf);
		p = buf;
	}
 	while((*p == ' ' || *p == '\t'  || *p == '\n') && *p != '\0')
		p++;
	if(*p)
		pp = p;
	else
		pp = NULL;

	while(*p != '\0' && *p != ' ' && *p != '\t' && *p != '\n')
		p++;
	return pp;
}

ostream &operator<<(ostream &os, const Graph &graph)
{
	os << "node = " << graph.mNode.size() << endl;
	for(vector<Node>::const_iterator it = graph.mNode.begin(); it != graph.mNode.end(); it++)
		os << *it << endl;
	os << "edge = " << graph.mLink.size() << endl;
	
	for(map<string, Link>::const_iterator it = graph.mLink.begin(); it != graph.mLink.end(); it++)
		os << (*it).first << ": " << (*it).second << endl;
	return os;
}

static string intToString(int i, int j)
{
	char buf[BUFSIZ];
	string temp;
	
	snprintf(buf, BUFSIZ, "%4.4x%4.4x", i, j);
	temp = buf;
	return temp;
}