graph.cpp

#include "graph.hpp"

// defining inifnity as the biggest possible value for an int
Graph::Graph() : infinity(std::numeric_limits<int>::max()) {}

/*  takes the Node's id as parameter
	returns the index of the Node as an int
 */
int Graph::getIndexFromId(const int &id) const {
	// start out index from something that shouldn't be possible
	int index = -1;

	// iterate through the whole whole vector of Nodes, until the one is found
	for (int i = 0; i < nodes.size(); ++i) {
		if (nodes[i]->id == id) {
			index = i;
			break;
		}
	}

	return index;
}

/*  takes a node pointer as parameter
 *  adds it to the vector of nodes
 *  resizes the adjacency matrix to accomodate new node
 *  returns true if succesful
 */
bool Graph::addNode(Node *node) {
	// add new node to the vector of nodes
	nodes.emplace_back(node);

	// add one extra element to every row in the adjacency matrix
	for (int i = 0; i < matrix.size(); ++i) {
		matrix[i].emplace_back(infinity);
	}

	// create temporary vector that will be the new row in the matrix
	std::vector<int> temp;
	// fill vector with 'infinity', as many elements as required
	temp.reserve(matrix.size() + 1);
	for (int i = 0; i < temp.capacity(); ++i) {
		temp.emplace_back(infinity);
	}
	// add the temporary vector to the adjacency matrix
	matrix.emplace_back(temp);

	return true;
}

/*
 *	takes id of a node as parameter
 *	removes node with the given id from the node vector
 *	and removes all the node's edges from the adjacency matrix
 */
void Graph::removeNode(const int &id) {
	// get the given node's index in the node vector
	int index = getIndexFromId(id);

	// starting at the removable node
	for (int i = index; i < nodes.size() - 1; ++i) {
		// shift all nodes forward by one in the node vector,
		nodes[i] = nodes[i + 1];
	}

	// erase last element of vector
	nodes.erase(nodes.begin() + nodes.size() - 1);

	int size = matrix.size();

	// shift the adjacency matrix leftward
	for (int i = 0; i < size; ++i) {
		for (int j = index; j < size - 1; ++j) {
			// move all elements in a given row leftward
			matrix[i][j] = matrix[i][j + 1];
		}

		// erase last element of the row
		matrix[i].erase(matrix[i].begin() + size - 1);
	}

	// shift the adjacency matrix upwards
	for (int j = 0; j < size - 1; ++j) {
		for (int i = index; i < size - 1; ++i) {
			// move all elements upwards row-by-row
			matrix[i][j] = matrix[i + 1][j];
		}
	}
	// erase last row of matrix
	matrix.erase(matrix.begin() + size - 1);
}

 /*
 *	adds a new edge to the graph
 *	takes 2 ids and a distance between them as parameters
 *	returns true if successful, false if unsuccesful
 */
bool Graph::addEdge(const int &id1, const int &id2, const int &distance) {
	// determine the index of both nodes in the node vector
	int from = getIndexFromId(id1);
	int to = getIndexFromId(id2);

	// return false in case at least one of the nodes weren't found
	if (from == -1 || to == -1) {
		return false;
	}

	// add connection into the adjacency matrix
	matrix[from][to] = distance;
	return true;
}

 /*
	takes two nodes' ids as parameters
	removes the connection from between those nodes from the adjacency matrix
 */

void Graph::removeEdge(const int &id1, const int &id2) {
	// determine the index of both nodes in the node vector
	int from = getIndexFromId(id1);
	int to = getIndexFromId(id2);

	// in case at least one of the nodes weren't found
	if (from == -1 || to == -1) {
		return;
	}

	// set the distance between the two given nodes to infinity
	matrix[from][to] = infinity;
}

// method to get the graph's size (number of nodes)
int Graph::size() const {
	return matrix.size();
}

// method to make cout able to print the adjacency matrix to stdout
std::ostream &operator<<(std::ostream &os, const Graph &g) {
    for (int i = 0; i < g.matrix.size(); ++i) {
		for (int j = 0; j < g.matrix.size(); ++j) {
			os << g.matrix[i][j] << " ";
	    }
		os << std::endl;
    }
    return os;
}