graph.cc

用OMNET++仿真蚁群的源码,是无线传感器网络仿真的一个重要工具

// -*- C++ -*-
// Copyright (C) 2003 Leherstuh f黵 Betrieb System/ Verteilte System,
// Universitaet Dortmund
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

// Author: Muddassar Farooq
// Informatik III, Universitaet Dortmund
// Germany

//-------------------------------------------------------------
// file: graph.cpp
//       (part of AntNet Routing Simulation)
//-------------------------------------------------------------

#include "graph.h"
#include <stdio.h>
#include <assert.h>


routerNode::routerNode(int address)
{
	nodeID = address;
}

routerNode::routerNode()
{
	nodeID = 0;
}

routerNode& routerNode::operator =(const routerNode& rhs)
{
	if(this == &rhs)
	{
		return *this;
	}
	else
	{
		nodeID = rhs.nodeID;
	}
	return *this;
}


bool routerNode::operator==(const routerNode rhs)
{
	if( nodeID == rhs.nodeID)
	{
		return true;
	}
	return false;
}


graphNode::graphNode()
{
	nextGraphNode = NULL;
	outLinkNodeList = NULL;
	inLinkNodeList = NULL;
}

graphNode::graphNode(routerNode rNode)
{
	node = rNode;
	nextGraphNode = NULL;
	outLinkNodeList = NULL;
	inLinkNodeList = NULL;
}

bool graphNode::operator==(const graphNode& rhs)
{
	if( node == rhs.node)
	{
		return true;
	}
	return false;
}


bool graphNode::operator!=(const graphNode& rhs)
{
	if( node == rhs.node)
	{
		return false;
	}
	return true;
}


linkNode::linkNode()
{
	sourceNode = NULL;
	destNode = NULL;
	sameSourceNode = NULL;
	sameDestNode = NULL;

}

linkNode::linkNode(float linkCost, graphNode *sourceNode, graphNode *destNode)
{
	this->linkCost = linkCost;
	this->sourceNode = sourceNode;
	this->destNode = destNode;
	this->sameSourceNode = NULL;
	this->sameDestNode = NULL;

}

linkNode::linkNode(graphNode *sourceNode, graphNode *destNode)
{
	this->sourceNode = sourceNode;
	this->destNode = destNode;
	this->sameSourceNode = NULL;
	this->sameDestNode = NULL;
}

linkNode::linkNode(linkNode &rhs)
{
	sourceNode = rhs.sourceNode;
	destNode = rhs.destNode;
	sameSourceNode = rhs.sameSourceNode;
	sameDestNode = rhs.sameDestNode;
	linkCost = rhs.linkCost;

}


bool linkNode::operator==(const linkNode& rhs)
{
	if(this->sourceNode->node == rhs.sourceNode->node
		&& (this->destNode->node == rhs.destNode->node))
	{
		return true;
	}
	return false;


}

bool linkNode::operator!=(const linkNode& rhs)
{
	if(this->sourceNode->node == rhs.sourceNode->node
		&& (this->destNode->node == rhs.destNode->node))
	{
		return false;
	}
	return true;


}


graphNetwork::graphNetwork(const char *name):cObject()
{
	listOfGraphNodes = NULL;
	numNodes = 0;
	maxAddress = -1;

}

graphNetwork::graphNetwork(const graphNetwork& rhs):cObject()
{
	graphNode *start = rhs.listOfGraphNodes;
	graphNode *tempNode = start;
	listOfGraphNodes = NULL;


	while( tempNode != NULL)
	{
		addRouterNode(&tempNode->node);
		tempNode = tempNode->nextGraphNode;
	};

	tempNode = start;
	while( tempNode != NULL)
	{
		linkNode *out = tempNode->outLinkNodeList;

		while( out != NULL)
		{
			addLink(&out->sourceNode->node, &out->destNode->node, out->linkCost);
			out = out->sameSourceNode;
		};
		tempNode = tempNode->nextGraphNode;
	};
}


graphNetwork& graphNetwork::operator= (const graphNetwork& rhs)
{
	if( this == &rhs)
	{
		return *this;
	}

	else
	{
		this->~graphNetwork();
		cObject::operator=(rhs);
		graphNode *start = rhs.listOfGraphNodes;
		graphNode *tempNode = start;
		listOfGraphNodes = NULL;


		while( tempNode != NULL)
		{
			addRouterNode(&tempNode->node);
			tempNode = tempNode->nextGraphNode;
		};

		tempNode = start;
		while( tempNode != NULL)
		{
			linkNode *out = tempNode->outLinkNodeList;

			while( out != NULL)
			{
				addLink(&out->sourceNode->node, &out->destNode->node, out->linkCost);
				out = out->sameSourceNode;
			};
			tempNode = tempNode->nextGraphNode;
		};
		return *this;
	}
}

cObject* graphNetwork::dup() const
{
	return new graphNetwork(*this);

}

void graphNetwork::info(char *buf)
{
	cObject::info(buf);
	sprintf( buf+strlen(buf), "Nodes=%d", numNodes);

}

void graphNetwork::writeContents(ostream& os)
{

	graphNode *start = listOfGraphNodes;
	while( start != NULL)
	{
		os << "\n Graph Node := " << start->node.nodeID;
		os << "\t Neighbors := ";

		linkNode *out = start->outLinkNodeList;

		while( out != NULL)
		{
			os << "  " << out->destNode->node.nodeID << "( " << out->linkCost
				<< " )";
			out = out->sameSourceNode;

		}

		start = start->nextGraphNode;
	};
}


int graphNetwork::getNumNodes()
{
	return numNodes;
}

int graphNetwork::getMaxAddress()
{
	return maxAddress;
}


bool graphNetwork::graphNodeExists(graphNode *node, graphNode **nodePtr)
{
	graphNode *temp;
	temp = listOfGraphNodes;
	while ( temp != NULL)
	{
		if(temp->node == node->node)
		{
			*nodePtr = temp;
			return true;
		}
		else
		{
			temp = temp->nextGraphNode;
		}
	};
	nodePtr = NULL;
	return false;
}

bool graphNetwork::linkNodeExists(linkNode *node, linkNode *list,
								  linkNode **nodePtr, bool outlist = true)
{
	linkNode *temp;
	temp = list;
	while ( temp != NULL)
	{
		if( *temp == *node)
		{
			*nodePtr = temp;
			return true;
		}
		else
		{
			if( outlist)
			{
				temp = temp->sameSourceNode;
			}
			else
			{
				temp = temp->sameDestNode;
			}


		}
	};
	nodePtr = NULL;
	return false;
}



void graphNetwork::addGraphNode(graphNode *node)
{
	graphNode *temp;

	if(graphNodeExists(node, &temp))
	{
		throw new cException("Error: Could not Add: Node Exists");
	}

	graphNode *tempNode = new graphNode(*node);

	if( node->node.nodeID > maxAddress)
	{
		maxAddress = node->node.nodeID;
	}

	// if list of nodes is empty, then this is the first entry

	if( listOfGraphNodes == NULL)
	{
		listOfGraphNodes = tempNode;
		tempNode->nextGraphNode = NULL; //this is the first element
	}

	else
	{
		temp = listOfGraphNodes;

		// traverse the list until its end and then add the node

		while( temp->nextGraphNode != NULL)
		{
			temp = temp->nextGraphNode;
		};

		// add the node

		temp->nextGraphNode = tempNode;
		tempNode->nextGraphNode = NULL;

	}
	numNodes++;
}

void graphNetwork::deleteGraphNode(graphNode *node)
{
	graphNode *prevGraphNode;
	graphNode *tempGraphNode = NULL;
	linkNode *outLinkNodes;
	linkNode *inLinkNodes;
	linkNode *tempLinkNode;

	if(graphNodeExists(node, &tempGraphNode))
	{
		//this is the only node in the graph

		if (listOfGraphNodes == tempGraphNode) // we need to delete at front
		{
			outLinkNodes = tempGraphNode->outLinkNodeList;

			while( outLinkNodes != NULL) //delete all link originating at this node
			{
				tempLinkNode = outLinkNodes;
				outLinkNodes = outLinkNodes->sameSourceNode;
				deleteLinkNode(tempLinkNode);
			};

			inLinkNodes = tempGraphNode->inLinkNodeList;

			while( inLinkNodes != NULL) //delete all link terminating at this node
			{
				tempLinkNode = inLinkNodes;
				inLinkNodes = inLinkNodes->sameDestNode;
				deleteLinkNode(tempLinkNode);
			};

			listOfGraphNodes = tempGraphNode->nextGraphNode;
			delete tempGraphNode;
			numNodes--;


		} // we have more than one node

		else
		{
			tempGraphNode = listOfGraphNodes;

			while( *tempGraphNode != *node)
			{
				prevGraphNode = tempGraphNode;
				tempGraphNode = tempGraphNode->nextGraphNode;
			};


			outLinkNodes = tempGraphNode->outLinkNodeList;

			while( outLinkNodes != NULL) //delete all link originating at this node
			{
				tempLinkNode = outLinkNodes;
				outLinkNodes = outLinkNodes->sameSourceNode;
				deleteLinkNode(tempLinkNode);
			};

			inLinkNodes = tempGraphNode->inLinkNodeList;

			while( inLinkNodes != NULL) //delete all link terminating at this node
			{
				tempLinkNode = inLinkNodes;
				inLinkNodes = inLinkNodes->sameDestNode;
				deleteLinkNode(tempLinkNode);
			};

			// update all the links situation and then update the list

			prevGraphNode->nextGraphNode = tempGraphNode->nextGraphNode;

			delete tempGraphNode;
			numNodes--;
		}
	}

	else
	{
		throw new cException("Error: Graph Node does not exist that needs to be deleted");
	}
}

void graphNetwork::updateLinkNode(graphNode *source, graphNode *dest, linkNode *link)
{
	graphNode *tempSource = NULL;
	graphNode *tempDest = NULL;
	linkNode *tempLinkNode = NULL;

	if( graphNodeExists(link->sourceNode, &tempSource) &&
		graphNodeExists(link->destNode, &tempDest))
	{

		if( linkNodeExists(link, tempSource->outLinkNodeList,