#include "graph3.h"
#include "cstdlib"

graph::graph(){
	// Nothing needs to be done except set the number of nodes to zero
	myNumberNodes = 0;
}

void graph::operator +=(const node & x){
	// First check if the node already exists in the graph
	if(getIndex(x) >= 0){
		cout << "Node " << x.getName() << " already exists" << endl;
		return;
	}
	
	// If the vector of nodes is full, resize it and resize the adjacency 
	// matrix. We'll make sure thet the length of the node vector always
	// equals the dimensions of the adjacency matrix
	if(myNumberNodes == myNodes.length()){
		myNodes.resize(2*myNumberNodes+1);
		myMatrix.resize(2*myNumberNodes+1);
		for(int i = 0; i <= 2*myNumberNodes; i++)
			myMatrix[i].resize(2*myNumberNodes+1);
	}

	// Insert the new node at the end
	myNodes[myNumberNodes] = x;

	// Since the new node has no neighbors to start with, set the
	// corresponding row and column to false
	for(int i = 0; i <= myNumberNodes; i++){
		myMatrix[myNumberNodes][i] = false;
		myMatrix[i][myNumberNodes] = false;
	}

	myNumberNodes++;

}

void graph::operator -=(const node & x){
	// get the index of the given node x
	int i = getIndex(x);	

	// Check if node exists in the graph; otherwise produce error message
	if (i < 0){
		cout << "Node " << x.getName() << " is not in the graph" << endl;
		return;
	}

	// we copy the last node into the ith slot
	myNodes[i] = myNodes[myNumberNodes-1];

	// we adjust the entries of the matrix appropriately;
	// move the last row to row i and the last column to column i
	for(int j = 0; j < myNumberNodes; j++){
		myMatrix[i][j] = myMatrix[myNumberNodes-1][j];
		myMatrix[j][i] = myMatrix[j][myNumberNodes-1];
	}
	myMatrix[i][i] = false;	

	// Reduce the number of nodes
	myNumberNodes--;


	// Shrink the myNodes vector and myMatrix, if they are more
	// than twice the number of nodes
	if (2*myNumberNodes < myNodes.length()){
		myNodes.resize(myNumberNodes);
		myMatrix.resize(myNumberNodes);
		for(int j = 0; j < myNumberNodes; j++)
			myMatrix[j].resize(myNumberNodes);
	} 

}


void graph::operator +=(const edge & x){
	// Get the indices of the two endpoints of the edge in the vector of nodes
	int i = getIndex(x.getNode1());
	int j = getIndex(x.getNode2());

	// Check if either of the endpoints are non-existant and produce error
	// message, if necessary
	if (i < 0){
		cout << "Node " << (x.getNode1()).getName() << " is not in the graph" << endl;
		return;
	}
	if (j < 0){
		cout << "Node " << (x.getNode2()).getName() << " is not in the graph" << endl;
		return;
	}

	
	// Check if edge already exists
	if (myMatrix[i][j]){
		cout << "Edge already exists" << endl;
		return;
	}	

	// Use these indices to turn on the corresponding elements in the 
	// adjacency matrix
	myMatrix[i][j] = myMatrix[j][i] = true;
}


void graph::operator -=(const edge & x){
	// Get the indices of the two endpoints of the edge in the vector of nodes
	int i = getIndex(x.getNode1());
	int j = getIndex(x.getNode2());

	// Check if either of the endpoints are non-existant and produce error
	// message, if necessary
	if (i < 0){
		cout << "Node " << (x.getNode1()).getName() << " is not in the graph" << endl;
		return;
	}
	if (j < 0){
		cout << "Node " << (x.getNode2()).getName() << " is not in the graph" << endl;
		return;
	}

	if(!myMatrix[i][j]){
		cout << "Edge does not exist in the graph" << endl;
		return;
	}

	// Use these indices to turn off the corresponding elements in the 
	// adjacency matrix
	myMatrix[i][j] = myMatrix[j][i] = false;
}

apvector<node> graph::get_neighbors(const node & x){
	// Set up a vector for the list of neighbors
	apvector<node> neighbors;	

	// Get the index of the node	
	int i = getIndex(x);
	
	// Check if node exists in the graph
	if(i < 0){
		cout << "Node " << x.getName() << " is not in the graph" << endl;
		return neighbors;
	}

	// Scan the row corresponding to the node x in the adjacency matrix
	// and pick up neighboring nodes
	for(int j = 0; j < myNumberNodes; j++)
	       if(myMatrix[i][j])
			neighbors.push_back(myNodes[j]);
	return neighbors;
}


int graph::getIndex(const node & x){
	for(int i = 0; i < myNumberNodes; i++)
		if(x == myNodes[i])
			return i;	
	return -1;
}