graph.cc

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

			&tempLinkNode)) //this arc to be deleted at front
		{
			tempLinkNode->linkCost = link->linkCost;
		}
	}

	else
	{
		throw new cException("Error: Could not update: Link Does not Exist");
	}
}

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


	if( graphNodeExists(link->sourceNode, &tempSource) &&
		graphNodeExists(link->destNode, &tempDest))
	{
		if( linkNodeExists(link, tempSource->outLinkNodeList,
			&tempLinkNode)) //this arc to be deleted at front
		{
			throw new cException("Error : Link already exists: could not add");
		}
	}

	else
	{
		throw new cException("Error: either source or destination nodes do not exist");
	}

	linkNode *current =  new linkNode(*link);

	// check if outgoing arcs list exists at source node

	if(tempSource->outLinkNodeList == NULL)
	{
		tempSource->outLinkNodeList = current;
		current->sourceNode = tempSource;
		current->sameSourceNode = NULL;
	}

	else
	{
		// get a pointer to the list of links orignating at this source

		tempOutList = tempSource->outLinkNodeList;
		while( tempOutList->sameSourceNode != NULL)
		{
			tempOutList = tempOutList->sameSourceNode;
		};

		tempOutList->sameSourceNode = current;
		current->sameSourceNode = NULL;
		current->sourceNode = tempSource;

	}

	// check if incoming arcs exists at destination node

	if(tempDest->inLinkNodeList == NULL)
	{
		tempDest->inLinkNodeList = current;
		current->destNode = tempDest;
		current->sameDestNode = NULL;
	}

	else
	{
		//get a pointer to the list of links terminating at this node
		tempInList = tempDest->inLinkNodeList;

		while( tempInList->sameDestNode != NULL)
		{
			tempInList = tempInList->sameDestNode;
		}

		tempInList->sameDestNode = current;
		current->destNode = tempDest;
		current->sameDestNode = NULL;
	}
}

void graphNetwork::deleteLinkNode(linkNode *current)
{
	graphNode *tempSource = NULL;
	graphNode *tempDest = NULL;
	linkNode *prevLinkNode = NULL;
	linkNode *tempLinkNode = NULL;

	// check if node exists on the outlist

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

		if( linkNodeExists(current, tempSource->outLinkNodeList,
			&tempLinkNode)) //this arc to be deleted at front
		{
			if(	tempSource->outLinkNodeList == tempLinkNode)
			{
				tempSource->outLinkNodeList = tempLinkNode->sameSourceNode;

			}
			else  // traverse the list
			{
				tempLinkNode = tempSource->outLinkNodeList;

				while( *tempLinkNode != *current)
				{
					prevLinkNode = tempLinkNode;
					tempLinkNode = tempLinkNode->sameSourceNode;
				};

				// update list
				prevLinkNode->sameSourceNode = tempLinkNode->sameSourceNode;
			}
		}

		else
		{
			throw new cException("Error Occured: The Link node does not exist");
		}

		// check if to be deleted is on the in list

		if( linkNodeExists(current, tempDest->inLinkNodeList,
			&tempLinkNode, false)) //this is the only one
		{
			if( tempDest->inLinkNodeList == tempLinkNode)
			{
				tempDest->inLinkNodeList = tempLinkNode->sameDestNode;
			}


			else  // traverse the list
			{
				tempLinkNode = tempDest->inLinkNodeList;

				while (*tempLinkNode != *current)
				{
					prevLinkNode = tempLinkNode;
					tempLinkNode = tempLinkNode->sameDestNode;
				};
				prevLinkNode->sameDestNode = tempLinkNode->sameDestNode;
			}
		}
		else
		{
			throw new cException("Error Occured: The Link node does not exist");
		}


		tempLinkNode->sourceNode = NULL;
		tempLinkNode->destNode = NULL;
		tempLinkNode->sameSourceNode = NULL;
		tempLinkNode->sameSourceNode = NULL;

		delete tempLinkNode;
	}

	else
	{
		throw new cException("Error Occured: The source node and destination nodes do not exist");
	}
}

void graphNetwork::addRouterNode(routerNode* rNode)
{
	graphNode tempNode(*rNode);
	addGraphNode( &tempNode );

}

void graphNetwork::deleteRouterNode(routerNode* rNode)
{
	graphNode tempNode(*rNode);
	deleteGraphNode( &tempNode );

}

void graphNetwork::addLink(routerNode *sourceRouter, routerNode *destRouter, float linkCost)
{
	graphNode source(*sourceRouter);
	graphNode dest(*destRouter);
	linkNode tempLink(linkCost, &source, &dest);
	addLinkNode( &source, &dest, &tempLink);
}

void graphNetwork::updateLink(routerNode *sourceRouter, routerNode *destRouter, float linkCost)
{
	graphNode source(*sourceRouter);
	graphNode dest(*destRouter);
	linkNode tempLink(linkCost, &source, &dest);
	updateLinkNode( &source, &dest, &tempLink);
}


void graphNetwork::deleteLink(routerNode *sourceRouter, routerNode *destRouter)
{
	graphNode source(*sourceRouter);
	graphNode dest(*destRouter);
	linkNode tempLink(&source, &dest);
	deleteLinkNode( &tempLink);

	if( allOutAndInLinksDeleted(&source))
	{
		deleteGraphNode(&source);
	}

	if( allOutAndInLinksDeleted(&dest))
	{
		deleteGraphNode(&dest);
	}
}

bool graphNetwork::allOutAndInLinksDeleted(graphNode *source)
{
	graphNode *tempSource = NULL;
	if( graphNodeExists(source, &tempSource))
	{
		// determine if all links orignating at this node
		// are deleted.
		if(tempSource->outLinkNodeList == NULL &&
			tempSource->inLinkNodeList == NULL)
		{
			// this node is no more a part of the graph
			return true;
		}
	}

	else
	{
		throw new cException("Error Occured: The Graph node does not exist");
	}
	return false;
}

bool graphNetwork::allOutLinksDoNotExist(routerNode *source)
{
	graphNode *tempSource = NULL;
	graphNode sourceGraphNode(*source);

	if( graphNodeExists(&sourceGraphNode, &tempSource))
	{
		// determine if all links orignating at this node
		// are deleted.
		if(tempSource->outLinkNodeList == NULL)
		{
			// this node is no more a part of the graph
			return true;
		}
	}

	else
	{
		throw new cException("Error Occured: The Graph node does not exist");
	}
	return false;

}

bool graphNetwork::allInLinksDoNotExist(routerNode *source)
{
	graphNode *tempSource = NULL;
	graphNode sourceGraphNode(*source);

	if( graphNodeExists(&sourceGraphNode, &tempSource))
	{
		// determine if all links orignating at this node
		// are deleted.
		if( tempSource->inLinkNodeList == NULL)
		{
			// this node is no more a part of the graph
			return true;
		}
	}

	else
	{
		throw new cException("Error Occured: The Graph node does not exist");
	}
	return false;
}

bool graphNetwork::linkExists(routerNode *sourceRouter, routerNode *destRouter)
{

	vector<destValue> adjacencyList;
	vector<destValue>::iterator iter;

	int numNeighbors = getSuccessrNodes( sourceRouter, adjacencyList);

	for(iter = adjacencyList.begin(); iter != adjacencyList.end(); ++iter)
	{
		destValue tempPair = *iter;
		int neighborAddress = tempPair.first.nodeID;
		if( destRouter->nodeID == neighborAddress)
		{
			return true;
		}
	} //endfor
	return false;
}

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

int graphNetwork::getSuccessrNodes(routerNode *rNode, vector<destValue> &adjacencyList)
{
	graphNode *tempSource = NULL;
	graphNode *tempDest = NULL;
	linkNode *tempOutList = NULL;
	int numNeighbors = 0;

	graphNode gNode(*rNode);
	routerNode neighborNode;
	destValue tempPair;


	if( graphNodeExists(&gNode, &tempSource))
	{
		tempOutList = tempSource->outLinkNodeList;
		while( tempOutList != NULL)
		{
			neighborNode.nodeID = tempOutList->destNode->node.nodeID;
			tempPair.first  = neighborNode;
			tempPair.second = tempOutList->linkCost;
			adjacencyList.push_back(tempPair);
			tempOutList = tempOutList->sameSourceNode;
			numNeighbors++;
		};
	}
	return numNeighbors;
}

routerNode graphNetwork::getGraphNodeAtIndex(int i)
{
	int count = 0;
	graphNode *temp;
	temp = listOfGraphNodes;

	if( i <= (numNodes-1))
	{
		while ( count != i)
		{
			temp = temp->nextGraphNode;
			count++;
		};
		return temp->node;
	}
	else
	{
		throw new cException("Error: Out of Bound Index");
	}
}


void graphNetwork::initializeGraph(char *name)
{
	int numRouter = 0;
	float dataRate = 0.0;
	float linkDelay = 0.0;
	float linkCost = 0.0;
	int sourceRouter = 0;
	int destRouter = 0;
	int numLinks = 0;
	struct routerNode dNode;
	struct routerNode sNode;


	FILE *graphFile;

	graphFile = fopen(name, "r");

	if(graphFile == NULL)
	{
		throw new cException("Error: Could not open this file");
	}
	fscanf(graphFile,"%d\n", &numRouter);


	while( !feof(graphFile)) // make all connection with channel name
	{
		fscanf(graphFile,"%d", &sourceRouter);
		fscanf(graphFile,"%d", &destRouter);
		fscanf(graphFile,"%f", &dataRate);
		fscanf(graphFile,"%f \n", &linkDelay);

		linkCost = 1/(dataRate) + linkDelay; // transmission + propagation delay
		sNode.nodeID = sourceRouter;
		dNode.nodeID = destRouter;
		addRouterNode(&sNode);
		addRouterNode(&dNode);
		addLink(&sNode, &dNode, linkCost);
	};


	fclose(graphFile);

}


graphNetwork::~graphNetwork()
{
	graphNode *start = listOfGraphNodes;
	graphNode *tempNode = start;

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

		while( out != NULL)
		{
			out = out->sameSourceNode;
			delete temp;
			temp = out;
		}

		start = start->nextGraphNode;
		delete tempNode;
		tempNode = start;
	};
}

graphNode* graphNetwork::getListOfGraphNodes()
{
	return listOfGraphNodes;
}

ostream& operator<<(ostream& os, graphNetwork& graph)
{
	graphNode *start = graph.getListOfGraphNodes();

	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;
	};
	return os;
}