Viki

#define _CRT_SECURE_NO_WARNINGS
#include "Edge.h"
#include "Node.h"

#include "Graph.h"

#include <math.h>


Graph::Graph()
{

}

Graph::~Graph()
{
	//delete [] nodeLink;
	//delete [] edges;
}

void Graph::setVars(int nodecnt,int edgecnt,int SpringEmbedderIterations,double K,double C,
		double MaxRepulsiveForceDistance, double MaxNodeMovement,int MinDiagramSize, int BorderSize,
		int width,int height)
{
	//nodeLink = new Node * [nodecnt];
	//edges = new Edge[edgecnt];
	gc.nodeCount = nodecnt;
	gc.edgeCount = edgecnt;
	gc.SpringEmbedderIterations = SpringEmbedderIterations;
	gc.K = K;
	gc.C = C;
	gc.MaxRepulsiveForceDistance = MaxRepulsiveForceDistance;
	gc.MaxNodeMovement = MaxNodeMovement;
	gc.MinDiagramSize = MinDiagramSize;
	gc.BorderSize = BorderSize;

	gc.width = width;
	gc.height = height;
}

void Graph::doLayout()
{
	std::list <Node>::iterator c = nodes.begin();
	c++;
	for (int it = 0;it < gc.SpringEmbedderIterations;it++)
		for (std::list <Node>::iterator a = nodes.begin();a != nodes.end();a++,c++)
			for (std::list <Node>::iterator b = c;b != nodes.end();b++)
			{
				Node *nodeA = &(*a);
				Node *nodeB = &(*b);
				double deltaX = nodeB->getX() - nodeA->getX();
				double deltaY = nodeB->getY() - nodeA->getY();

				double distanceSquared = deltaX * deltaX + deltaY * deltaY;

				if (distanceSquared < 0.01) 
				{
					deltaX = (rand() % 2) / 10 + 0.1;
					deltaY = (rand() % 2) / 10 + 0.1;
					distanceSquared = deltaX * deltaX + deltaY * deltaY;
				}
				double distance = sqrt(distanceSquared);

				if (distance < gc.MaxRepulsiveForceDistance) 
				{
					double repulsiveForce = (gc.K * gc.K / distance);
						                        
					nodeB->setFX(nodeB->getFX() + (repulsiveForce * deltaX / distance));
					nodeB->setFY(nodeB->getFY() + (repulsiveForce * deltaY / distance));
					nodeA->setFX(nodeA->getFX() - (repulsiveForce * deltaX / distance));
					nodeA->setFY(nodeA->getFY() - (repulsiveForce * deltaY / distance));
				}
		// Calculate forces acting on nodes due to edge attractions.
		for (ei = edges.begin(); ei != edges.end(); ei++) 
		{
			Edge edge = *ei;
			Node nodeA = ei->getSource();
			Node nodeB = ei->getTarget();
			double deltaX = nodeB.getX() - nodeA.getX();
			double deltaY = nodeB.getY() - nodeA.getY();

			double distanceSquared = deltaX * deltaX + deltaY * deltaY;

			// Avoid division by zero error or Nodes flying off to
			// infinity.  Pretend there is an arbitrary distance between
			// the Nodes.
			if (distanceSquared < 0.01) 
			{
				deltaX = (rand() % 2) / 10 + 0.1;
				deltaY = (rand() % 2) / 10 + 0.1;
				distanceSquared = deltaX * deltaX + deltaY * deltaY;
			}

			double distance = sqrt(distanceSquared);

			if (distance > gc.MaxRepulsiveForceDistance) 
				distance = gc.MaxRepulsiveForceDistance;

			distanceSquared = distance * distance;

			double attractiveForce = (distanceSquared - gc.K * gc.K) / gc.K;

			// Make edges stronger if people know each other.
			double weight = edge.getWeight();
			if (weight < 1)
				weight = 1;

			attractiveForce *= (log(weight) * 0.5) + 1;
			nodeB.setFX(nodeB.getFX() - attractiveForce * deltaX / distance);
			nodeB.setFY(nodeB.getFY() - attractiveForce * deltaY / distance);
			nodeA.setFX(nodeA.getFX() + attractiveForce * deltaX / distance);
			nodeA.setFY(nodeA.getFY() + attractiveForce * deltaY / distance);
			ei->copyNodes(nodeA,nodeB);
		}
		// Now move each node to its new location...
		for (std::list <Node>::iterator a = nodes.begin();a != nodes.end();a++)
		{
			Node *node = &(*a);

			double xMovement = gc.C * node->getFX();
			double yMovement = gc.C * node->getFY();

			// Limit movement values to stop nodes flying into oblivion.
			double max = gc.MaxNodeMovement;
			if (xMovement > max)
				xMovement = max;
			else if (xMovement < -max)
				xMovement = -max;
			if (yMovement > max)
				yMovement = max;
			else if (yMovement < -max)
				yMovement = -max;

			node->setX(node->getX() + xMovement);
			node->setY(node->getY() + yMovement);

			// Reset the forces
			node->setFX(0);
			node->setFY(0);
		}
	}
}

void Graph::calcBounds()
{
	minX = 4294967296;
	maxX = -4294967296;
	minY = 4294967296;
	maxY = -4294967296;
	maxWeight = 0;


	for (std::list <Node>::iterator a = nodes.begin();a != nodes.end();a++)
	{
		Node *node = &(*a);

		if (node->getX() > maxX)
		maxX = node->getX();

		if (node->getX() < minX)
		minX = node->getX();

		if (node->getY() > maxY)
		maxY = node->getY();

		if (node->getY() < minY)
		 minY = node->getY();
	}

	// Increase size if too small.
	double minSize = gc.MinDiagramSize;
	if (maxX - minX < minSize) 
	{
		double midX = (maxX + minX) / 2;
		minX = midX - (minSize / 2);
		maxX = midX + (minSize / 2);
	}
	if (maxY - minY < minSize) 
	{
		double midY = (maxY + minY) / 2;
		minY = midY - (minSize / 2);
		maxY = midY + (minSize / 2);
	}

	// Jibble the boundaries to maintain the aspect ratio.
	double xyRatio = ((maxX - minX) / (maxY - minY)) / (gc.width / gc.height);
	if (xyRatio > 1) 
	{
		// diagram is wider than it is high.
		double dy = maxY - minY;
		dy = dy * xyRatio - dy;
		minY = minY - dy / 2;
		maxY = maxY + dy / 2;
	}
	else if (xyRatio < 1) 
	{
		// Diagram is higher than it is wide.
		double dx = maxX - minX;
		dx = dx / xyRatio - dx;
		minX = minX - dx / 2;
		maxX = maxX + dx / 2;
	}
	ni = nodes.begin();
}

void Graph::calcPositions()
{
	for (std::list <Node>::iterator a = nodes.begin();a != nodes.end();a++)
	{
		Node *node = &(*a);
		node->setX((float)((int)((gc.width * (node->getX() - minX) / (maxX - minX)) + gc.BorderSize)));
		node->setY((float)((int)((gc.height * (node->getY() - minY) / (maxY - minY)) + gc.BorderSize)));
	}
}

void Graph::getNode(int slot,char *data)
{
	if (ni == nodes.end())
		ni = nodes.begin();
	sprintf(data,"%d %d",ni->getX(),ni->getY());
	ni++;
}
void Graph::getEdge(int slot, char *data)
{
	ei = edges.begin();
	sprintf(data,"%d %d %d %d",ei[slot].getSource().getX(),ei[slot].getSource().getY(),
		ei[slot].getTarget().getX(),ei[slot].getTarget().getY());
}
void Graph::addNode(std::string nick, double weight, int slot)
{
	Node node;
	node.setVars(nick,weight,slot);
	nodes.push_back(node);
}
void Graph::addEdge(int source, int target, double weight,int slot)
{
	Edge edge;
	Node na;
	Node nb;
	bool f1,f2;
	f1 = false;
	f2 = false;
	for (std::list <Node>::iterator a = nodes.begin();a != nodes.end();a++)
	{
		if (a->getSlot() == source)
		{
			na = *a;
			f1 = true;
		}
		else if (a->getSlot() == target)
		{
			nb = *a;
			f2 = true;
		}
		if ((f1) && (f2))
			break;
	}
	edge.setVars(&na,&nb,weight);
	edges.push_back(edge);
	//edges[slot].setVars(&nodes[source],&nodes[target],weight);
}