temelia/src/graph.c

/*!
 Temelia - Graph algorithms implementation source file

 Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia)

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/graph.h"
#include "include/vector.h"
#include "include/queue.h"
#include "include/pair.h"
#include "include/sort.h"
#include "include/heap.h"
#include <stdlib.h>

struct _graph_t
{
	/*! Maximum number of vertices */
	unsigned int size;

	/*! Array of vertices */
	vector_t vertices;

	/*! Graph context */
	void *graph;

	/*! Vertex delete function */
	void (*vertex_delete)(vertex_t);

	/*! Edge delete function */
	void(*edge_delete)(edge_t);

	/*! Pointer to the graph implementation */
	graph_implementation_t implementation;
};

// === Private functions declaration ===
/*!
 * @brief DFS travel starting from node.
 * Complexity O(V)
 *
 * @param Graph
 * @param Node identifier
 */
static void _graph_dfs(graph_t graph, unsigned int node);

/*!
 * @brief BFS travel.
 * Complexity O(V)
 *
 * @param Graph
 * @param Node identifier
 */
static void _graph_bfs(graph_t graph, unsigned int node);

/*!
 * @brief Time variable, used to synchronize operations.
 * Library doesn't export it because user shouldn't care about this variable.
 */
static unsigned int current_time = 0;

/*!
 * @brief Resets parameters of all vertices to their default value :
 * 1. unvisited
 * 2. colored with WHITE
 * 3. parent nil (-1)
 * 4. time_start and time_travel 0
 * Complexity O(V)
 *
 * @param Graph
 */
static void _graph_reset_vertices(graph_t graph);

/*!
 * @brief Core function for finding articulation points. It's based on DFS and compares times
 * when vertices are discovered in order to find the cut-vertices.
 * Complexity O(E/V))
 *
 * @param Graph
 * @param Current node
 * @param Color array
 * @param Time start array
 * @param Low time array
 * @param Parent array
 * @param Cut-vertex array. A vertex v is cut-vertex only if cut_vertex[v] = 1
 */
unsigned int _articulation_points_travel(graph_t graph, unsigned int u,
		int *color, unsigned int *start, unsigned int *low,
		unsigned int *parent, int *cut_vertex);

/*!
 * @brief Modified DFS travel used to find cycles contained by a graph.
 * Complexity O(V)
 *
 * @param Graph
 * @param Current node
 * @param Linked list where the next cycle is stored
 * @param Pointer to parent
 * @param Pointer to color
 * @param Pointer to visited
 * */
static void _cycles_travel(graph_t graph, unsigned int current_node,
		linked_list_t current_cycles, unsigned int *parent, int *color,
		int *visited);

/*!
 * @brief Rebuilds the path from current_node to next_node, basing on parents vector.
 * Complexity O(V)
 *
 * @param Current node identifier
 * @param Next node identifier
 * @param Parent array
 * @param Linked list where the cycle will be stored
 */
static void _rebuild_cycle(unsigned int current_node, unsigned int next_node,
		unsigned int *parent, linked_list_t small_cycle);

/*!
 * @brief Comparison function used by Kruskal's algorithm to compare set nodes.
 * @param First node identifier.
 * @param Second node identifier.
 */
static int _compare_nodes_unsigned(void *x, void *y, void *context);

/*!
 * @brief Internal function comparing time of two unsigned int vertex identifiers.
 */
static int _compare_nodes_strongly_connected_components(void *x, void *y,
		void *context);

/*!
 * @brief Comparison function used by Dijkstra's algorithm. It uses as context the distance vector.
 * @param First vertex identifier.
 * @param Second vertex identifier.
 */
static int _compare_dijkstra(void *x, void *y, void *context);

/*!
 * @brief Comparison function used by Prim's algorithm. It uses as context a pointer to minimum weights.
 * @param First vertex identifier
 * @param Second vertex identifier
 */
static int _compare_prim(void *x, void *y, void *context);

/*!
 * @brief Comparison function used by Kruskal's algorithm to sort edges by their cost.
 * @param First edge reference
 * @param Second edge reference
 */
static int _compare_edges_kruskal(void *x, void *y, void *context);

/*!
 * @brief Comparison function used by Kruskal's algorithm to compare set nodes.
 * @param First node identifier
 * @param Second node identifier
 */
static int _compare_nodes_kruskal(void *x, void *y, void *context);

/*!
 * @brief Sets the flow matrix keys to 0 double value.
 * Complexity O(V*V)
 *
 * @param Flow matrix
 */
static void _init_flow(matrix_t flow);

/*!
 * @brief Returns the minimum flow over a path in graph.
 * Complexity O(V)
 *
 * @param Graph
 * @param Flow matrix
 * @param Path list
 */
static double _min_flow_path(graph_t graph, matrix_t max_flow,
		linked_list_t path);

/*!
 * @brief Computes max_flow using DFS travel - used by Ford-Fulkerson algorithm.
 * Complexity O(E*max_flow)
 *
 * @param Graph
 * @param Start node identifier - source; this variable is changing because DFS travels
 * the vertices in a recursive way
 * @param End node identifier - destination
 * @param Path, where the result is stored
 * @param Max flow matrix
 */
static void _flow_dfs(graph_t graph, unsigned int current_node,
		unsigned int destination, linked_list_t path, matrix_t max_flow);

/*!
 * @brief Computer max_flow using BFS travel - used by Edmonds-Karp algorithm.
 * Complexity O(V*E*E)
 *
 * @param Graph
 * @param Start node identifier - source
 * @param End node identifier - destination
 * @param Path, where the result is stored
 * @param Max flow matrix
 */
static void _flow_bfs(graph_t graph, unsigned int source,
		unsigned int destination, linked_list_t path, matrix_t max_flow);

/*!
 * @brief Iterates over a path and actualizes the flow on it; the function add the min_flow to
 * all the edges from the path.
 * Complexity O(V)
 *
 * @param Flow matrix
 * @param Path
 * @param Minimum flow value
 */
static void _add_flow_on_path(matrix_t max_flow, linked_list_t path,
		double min_flow);

/*!
 * @brief Returns the capacity of edge between vertices i and j.
 * Complexity O(1)
 *
 * @param Graph
 * @param First vertex identifier
 * @param Second vertex identifier
 */
INLINE static double CAPACITY(graph_t graph, unsigned int i, unsigned int j);

/*!
 * @brief Returns the flow of edge between vertices i and j.
 * Complexity O(1)
 *
 * @param Flow matrix
 * @param First vertex identifier
 * @param Second vertex identifier
 */
INLINE static double FLOW(matrix_t max_flow, unsigned int i, unsigned int j);

// === End ===

graph_t graph_new(unsigned int max, graph_implementation_t implementation,
		void(*m_vertex_delete)(vertex_t), void(*m_edge_delete)(edge_t))
{
	graph_t graph;

	LOGGER(
			"[graph new] max size %u, implementation %p, vertex destructor %p, edge destructor\n",
			max, implementation, m_vertex_delete, m_edge_delete);

	_ASSERT(max, <=, 0, INVALID_INPUT, NULL);
	_ASSERT(implementation, ==, NULL, NULL_POINTER, NULL);

	graph = (struct _graph_t *) _new(sizeof(struct _graph_t));

	graph->size = max;
	graph->implementation = implementation;

	graph->graph = graph->implementation->new_g(max);
	_ASSERT(graph->graph, ==, NULL, NULL_POINTER, NULL);

	graph->vertices = vector_new(max);
	_ASSERT(graph->vertices, ==, NULL, NULL_POINTER, NULL);

	if (m_vertex_delete)
		graph->vertex_delete = m_vertex_delete;
	else
		graph->vertex_delete = vertex_delete;

	if (m_edge_delete)
		graph->edge_delete = m_edge_delete;
	else
		graph->edge_delete = edge_delete;

	// free() is the default destructor
	if (graph->implementation->delete_vertex_context == NULL)
		graph->implementation->delete_vertex_context = (void(*)(void **)) free;

	return graph;
}

static void _graph_delete_edge(edge_t key, void *context)
{
	((void(*)(edge_t)) context)(key);
}

void graph_delete(graph_t graph)
{
	unsigned int i;

	LOGGER("[graph delete] graph %p\n", graph);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);

	graph->implementation->iterate_edges(graph->graph, _graph_delete_edge,
			graph->edge_delete);
	graph->implementation->delete_g(graph->graph);

	for (i = 0; i < graph->size; i++)
		graph->vertex_delete(vector_get_key_at(graph->vertices, i));
	vector_delete(graph->vertices);
	graph->size = 0;

	_delete(graph);
}

unsigned int graph_add_vertex(graph_t graph, char *label, void *key)
{
	unsigned int i, n;
	int empty_place = 0;
	vertex_t vertex;

	LOGGER("[graph add vertex] graph %p, label %s, key %p\n", graph, label, key);

	_ASSERT(graph, ==, NULL, NULL_POINTER, (unsigned int) -1);
	_ASSERT((unsigned int) vector_get_size(graph->vertices), >= , graph->size, FULL, (unsigned int) -1);

	vertex = vertex_new(label, (unsigned int) vector_get_size(graph->vertices), key);

	_ASSERT(vertex, ==, NULL, NULL_POINTER, -1);

	// Find an empty place to insert the vertex.
	n = vector_get_size(graph->vertices);
	for (i = 0; i < n; i++)
	{
		if (vector_get_key_at(graph->vertices, i) == NULL)
		{
			vector_set_key_at(graph->vertices, i, vertex);
			empty_place = 1;
			break;
		}
	}

	if (empty_place)
		return i;

	// If no empty place found, add the vertex to the end
	vector_push_back(graph->vertices, vertex);

	return vector_get_size(graph->vertices) - 1;
}

vertex_t graph_remove_vertex(graph_t graph, unsigned int identifier)
{
	vertex_t vertex;
	unsigned int i, n;

	LOGGER("[graph remove vertex] graph %p, vertex %u\n", graph, identifier);

	_ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), EMPTY, NULL);

	vertex = vector_get_key_at(graph->vertices, identifier);
	vector_set_key_at(graph->vertices, identifier, NULL);

	if (graph->implementation->delete_vertex_edges)
		graph->implementation->delete_vertex_edges(graph->graph, identifier,
				graph->edge_delete);
	else
	{
		n = graph->size;
		for (i = 0; i < n; i++)
		{
			graph->edge_delete(graph->implementation->get_edge(graph->graph, i,
					identifier));
			graph->edge_delete(graph->implementation->get_edge(graph->graph,
					identifier, i));
		}
	}

	return vertex;
}

int graph_is_vertex(graph_t graph, unsigned int identifier)
{
	LOGGER("[graph is vertex] graph %p, identifier %u\n", graph, identifier);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, 0);

	return vector_get_key_at(graph->vertices, identifier) != NULL;
}

vertex_t graph_get_vertex(graph_t graph, unsigned int identifier)
{
	LOGGER("[graph get vertex] graph %p, identifier %u\n", graph, identifier);

	_ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);

	return vector_get_key_at(graph->vertices, identifier);
}

edge_t graph_get_edge(graph_t graph, unsigned int identifier1,
		unsigned int identifier2)
{
	LOGGER("[graph get edge] graph %p, identifier1 %u, identifier2 %u\n",
			graph, identifier1, identifier2);

	_ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(identifier1, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);
	_ASSERT(identifier2, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);

	return graph->implementation->get_edge(graph->graph, identifier1,
			identifier2);
}

void graph_add_edge(graph_t graph, unsigned int vertex1, unsigned int vertex2,
		double cost, char *label, void *key)
{
	vertex_t m_vertex1, m_vertex2;
	edge_t edge;

	LOGGER(
			"[graph add edge] graph %p, identifier1 %u, identifier2 %u, cost %lf, label %s, key %p\n",
			graph, vertex1, vertex2, cost, label, key);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(vertex1, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, );
	_ASSERT(vertex2, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, );

	m_vertex1 = vector_get_key_at(graph->vertices, vertex1);
	m_vertex2 = vector_get_key_at(graph->vertices, vertex2);

	_ASSERT(m_vertex1, ==, NULL, NULL_POINTER,);
	_ASSERT(m_vertex2, ==, NULL, NULL_POINTER,);

	// Create an edge between the two vertices.
	edge = edge_new(m_vertex1, m_vertex2, cost, label, key);
	_ASSERT(edge, ==, NULL, NULL_POINTER,);
	graph->implementation->add_edge(graph->graph, vertex1, vertex2, edge);
}

edge_t graph_remove_edge(graph_t graph, unsigned int vertex1,
		unsigned int vertex2)
{
	LOGGER("[graph remove edge] graph %p, identifier1 %u, identifier2 %u\n",
			graph, vertex1, vertex2);

	_ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(vertex1, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);
	_ASSERT(vertex2, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, NULL);

	return graph->implementation->remove_edge(graph->graph, vertex1, vertex2);
}

int graph_is_edge(graph_t graph, unsigned int vertex1, unsigned int vertex2)
{
	LOGGER("[graph is edge] graph %p, identifier1 %u, identifier2 %u\n", graph,
			vertex1, vertex2);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(vertex1, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);
	_ASSERT(vertex2, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);

	return graph->implementation->get_edge(graph->graph, vertex1, vertex2)
			!= NULL;
}

int graph_is_empty(graph_t graph)
{
	LOGGER("[graph is empty] graph %p\n", graph);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);

	return vector_get_size(graph->vertices) == 0;
}

unsigned int graph_get_size(graph_t graph)
{
	unsigned int count = 0, i, n;

	LOGGER("[graph get size] graph %p\n", graph);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);

	n = vector_get_size(graph->vertices);
	for (i = 0; i < n; i++)
		if (vector_get_key_at(graph->vertices, i) != NULL)
			count++;
	return count;
}

unsigned int graph_get_dimension(graph_t graph)
{
	unsigned int count = 0, i, j, n;

	LOGGER("[graph get dimension] graph %p\n", graph);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);

	if (graph->implementation->dimension)
		return graph->implementation->dimension(graph->graph);

	// dimension() not implemented, use default algorithm
	n = vector_get_size(graph->vertices);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (graph->implementation->get_edge(graph->graph, i, j) != NULL)
				count++;
	return count;
}

unsigned int graph_vertex_degree(graph_t graph, unsigned int identifier)
{
	unsigned int i, n, degree = 0;

	LOGGER("[graph vertex degree] graph %p, identifier %u\n", graph, identifier);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);

	if (graph->implementation->vertex_degree)
		return graph->implementation->vertex_degree(graph->graph, identifier);

	// vertex_degree() not implemented, use default algorithm
	n = vector_get_size(graph->vertices);
	for (i = 0; i < n; i++)
	{
		if (graph->implementation->get_edge(graph->graph, identifier, i))
			degree++;
		if (graph->implementation->get_edge(graph->graph, i, identifier))
			degree++;
	}

	return degree;
}

unsigned int graph_vertex_out_degree(graph_t graph, unsigned int identifier)
{
	unsigned int i, n, out_degree = 0;

	LOGGER("[graph out vertex degree] graph %p, identifier %u\n", graph,
			identifier);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(graph->implementation, ==, NULL, NULL_POINTER, -1);
	_ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);

	if (graph->implementation->vertex_out_degree)
		return graph->implementation->vertex_out_degree(graph->graph,
				identifier);

	// vertex_out_degree() not implemented, use default algorithm
	n = vector_get_size(graph->vertices);
	for (i = 0; i < n; i++)
		if (graph->implementation->get_edge(graph->graph, identifier, i))
			out_degree++;
	return out_degree;
}

unsigned int graph_vertex_in_degree(graph_t graph, unsigned int identifier)
{
	unsigned int i, n, in_degree = 0;

	LOGGER("[graph in vertex degree] graph %p, identifier %u\n", graph,
			identifier);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(graph->implementation, ==, NULL, NULL_POINTER, -1);
	_ASSERT(identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT, -1);

	if (graph->implementation->vertex_in_degree)
		return graph->implementation->vertex_in_degree(graph->graph, identifier);

	// vertex_in_degree() not implemented, use default algorithm
	n = vector_get_size(graph->vertices);
	for (i = 0; i < n; i++)
		if (graph->implementation->get_edge(graph->graph, i, identifier))
			in_degree++;
	return in_degree;
}

void graph_iterate_vertices(graph_t graph, void vertex_handler(vertex_t v,
		void *context), void *context)
{
	unsigned int i, n;

	LOGGER(
			"[graph iterate vertices] graph %p, vertex handler %p, context %p\n",
			graph, vertex_handler, context);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(vertex_handler, ==, NULL, NULL_POINTER,);

	n = vector_get_size(graph->vertices);
	for (i = 0; i < n; i++)
		if (vector_get_key_at(graph->vertices, i))
			vertex_handler(vector_get_key_at(graph->vertices, i), context);
}

void graph_iterate_edges(graph_t graph, void edge_handler(edge_t e,
		void *context), void *context)
{

	LOGGER("[graph vertex degree] graph %p, edge handler %p, context %p\n",
			graph, edge_handler, context);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(edge_handler, ==, NULL, NULL_POINTER,);

	graph->implementation->iterate_edges(graph->graph, edge_handler, context);
}

void graph_transpose_graph(graph_t graph)
{
	LOGGER("[graph transpose] graph %p\n", graph);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);

	graph->implementation->transpose(graph->graph);
}

void graph_dfs(graph_t graph, unsigned int start_vertex_identifier)
{
	unsigned int node, nodes_number;

	LOGGER("[graph dfs] graph %p, start vertex %u\n", graph,
			start_vertex_identifier);

	_ASSERT(graph, ==, NULL, NULL_POINTER, );

	graph_set_current_time(0);

	if (start_vertex_identifier == (unsigned int) -1)
	{
		nodes_number = vector_get_size(graph->vertices);

		for (node = 0; node < nodes_number; node++)
			_graph_dfs(graph, node);
	}
	else
	{
		_ASSERT(start_vertex_identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT,);
		_graph_dfs(graph, start_vertex_identifier);
	}
}

void graph_bfs(graph_t graph, unsigned int start_vertex_identifier)
{
	unsigned int node, nodes_number;

	LOGGER("[graph bfs] graph %p, start vertex %u\n", graph,
			start_vertex_identifier);

	_ASSERT(graph, ==, NULL, NULL_POINTER, );

	graph_set_current_time(0);

	if (start_vertex_identifier == (unsigned int) -1)
	{
		nodes_number = vector_get_size(graph->vertices);

		for (node = 0; node < nodes_number; node++)
			_graph_bfs(graph, node);
	}
	else
	{
		_ASSERT(start_vertex_identifier, >=, (unsigned int) vector_get_size(graph->vertices), INVALID_INPUT,);
		_graph_bfs(graph, start_vertex_identifier);
	}
}

void graph_reset_vertices(graph_t graph)
{
	LOGGER("[graph reset vertices] graph %p\n", graph);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);

	_graph_reset_vertices(graph);
}

int graph_is_undirected(graph_t graph)
{
	unsigned int i, j, n;
	edge_t u, v;

	LOGGER("[graph is undirected] graph %p\n", graph);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);

	n = vector_get_size(graph->vertices);

	// If there exists an edge from a node to itseft then it's
	// not undirected.
	for (i = 0; i < n; i++)
		if (graph_get_edge(graph, i, i))
			return 0;

	for (i = 0; i < n - 1; i++)
	{
		for (j = i + 1; j < n; j++)
		{
			u = graph_get_edge(graph, i, j);
			v = graph_get_edge(graph, j, i);

			// If there is a pair of NULL and not-NULL edges
			// then the graph_t is undirected
			if ((u && !v) || (v && !u))
				return 0;
		}
	}
	return 1;
}

void graph_set_current_time(unsigned int time)
{
	LOGGER("[graph set current time] time %d\n", time);
	current_time = time;
}

int graph_get_current_time()
{
	LOGGER("[graph get current time] time %d\n", current_time);
	return current_time;
}

void graph_dfs_edges_classification(graph_t graph)
{
	unsigned int i, j, nodes_number, type;
	vertex_t u, v;
	void *context;

	LOGGER("[graph dfs edges classification] graph %p\n", graph);

	_ASSERT(graph, ==, NULL, NULL_POINTER, );

	/*
	 * Start a complete DFS travel in order to compute values,
	 * requested by the classification.
	 */
	graph_dfs(graph, -1);

	type = DFS_UNKNOWN_EDGE;

	nodes_number = vector_get_size(graph->vertices);

	for (i = 0; i < nodes_number; i++)
	{
		u = vector_get_key_at(graph->vertices, i);
		v = graph->implementation->first_vertex(graph->graph, i, &context);

		while (1)
		{
			if (v == NULL)
				break;

			j = vertex_get_identifier(v);

			if (i == j)
				type = DFS_BACK_EDGE;
			//	t_start[u] < t_start[v] < t_stop[v] < t_stop[v]
			else if (vertex_get_time_start(u) < vertex_get_time_start(v)
					&& vertex_get_time_stop(v) < vertex_get_time_stop(u))
			{
				//  parent[v] = u => tree edge
				if (vertex_get_parent_identifier(v) == vertex_get_identifier(u))
					type = DFS_TREE_EDGE;
				// parent[v] != u => forward edge
				else
					type = DFS_FORWARD_EDGE;
			}
			// t_start[v] < t_start[u] < t_stop[u] < t_stop[v].
			else if (vertex_get_time_start(v) < vertex_get_time_start(u)
					&& vertex_get_time_stop(u) < vertex_get_time_stop(v))
				type = DFS_BACK_EDGE;
			// t_start[v] < t_stop[v] < t_start[u] < t_stop[u].
			else if (vertex_get_time_stop(v) < vertex_get_time_start(u))
				type = DFS_CROSS_EDGE;

			edge_set_type(graph_get_edge(graph, i, j), type);
			v = graph->implementation->next_vertex(graph->graph, i, &context);
		}
	}
}

void graph_bfs_edges_classification(graph_t graph)
{
	unsigned int i, j, k, nodes_number, type;
	vertex_t u, v;
	void *context;

	LOGGER("[graph bfs edges classification] graph %p\n", graph);

	_ASSERT(graph, ==, NULL, NULL_POINTER, );

	/*
	 * Start a complete BFS travel in order to compute values,
	 * requested by the classification.
	 */

	graph_bfs(graph, -1);

	type = BFS_UNKNOWN_EDGE;

	nodes_number = vector_get_size(graph->vertices);
	for (i = 0; i < nodes_number; i++)
	{
		u = vector_get_key_at(graph->vertices, i);
		v = graph->implementation->first_vertex(graph->graph, i, &context);

		while (1)
		{
			if (v == NULL)
				break;

			j = vertex_get_identifier(v);

			// u = parent[v]
			if (i == vertex_get_parent_identifier(v))
				type = BFS_TREE_EDGE;
			else
			{
				k = i;
				while (k != (unsigned) -1 && k != j)
					k = vertex_get_parent_identifier(vector_get_key_at(
							graph->vertices, k));
				if (k != (unsigned) -1)
					type = BFS_BACK_EDGE;
				// parent[..parent[u]] = v;
				else if (vertex_get_cost(v) <= (vertex_get_cost(u) + 1))
					type = BFS_CROSS_EDGE;
			}
			edge_set_type(graph_get_edge(graph, i, j), type);
			v = graph->implementation->next_vertex(graph->graph, i, &context);
		}
	}
}

void graph_connected_components(graph_t graph,
		linked_list_t connected_components, int check)
{
	unsigned int nodes_number, node, it, current_time, max_time, this_time;
	vertex_t u;
	linked_list_t add;

	LOGGER(
			"[graph connected components] graph %p, connected components %p, check %d\n",
			graph, connected_components, (int) check);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(connected_components, ==, NULL, NULL_POINTER,);

	if (check)
		if (!graph_is_undirected(graph))
			return;

	graph_set_current_time(0);
	nodes_number = vector_get_size(graph->vertices);

	max_time = current_time = 0;
	for (node = 0; node < nodes_number; node++)
	{
		_graph_dfs(graph, node);
		/*
		 * Find the maximum stop time in order to find a new connected component
		 * of the current graph_t. It contains the vertices of which
		 * t_start and t_stop is between current_time and max_time
		 */
		for (it = 0; it < nodes_number; it++)
		{
			this_time = vertex_get_time_stop(vector_get_key_at(graph->vertices,
					it));
			if (max_time < this_time)
				max_time = this_time;
		}

		add = linked_list_new();

		for (it = 0; it < nodes_number; it++)
		{
			u = vector_get_key_at(graph->vertices, it);
			this_time = vertex_get_time_stop(u);

			if (this_time > current_time && this_time <= max_time)
				linked_list_push_back(add, (void *) it);
		}

		current_time = max_time;
		if (linked_list_get_size(add) > 0)
			linked_list_push_back(connected_components, add);
		else
			linked_list_delete(add);
	}
}

static void *key_at(void *data, int index)
{
	return (void *) ((unsigned int *) data)[index];
}

static void set_key_at(void *data, int index, void *new_value)
{
	((unsigned int *) data)[index] = (unsigned int) new_value;
}

void graph_strongly_connected_components(graph_t graph,
		linked_list_t strongly_connected_components)
{
	unsigned int *vertices, i, j, nodes_number, t_start, t_stop, aux;
	linked_list_t add;

	LOGGER("[graph strongly connected components] graph %p, list %p\n", graph,
			strongly_connected_components);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(strongly_connected_components, ==, NULL, NULL_POINTER,);

	// Make a complete DFS travel and sort the vertices after t_stop.
	graph_dfs(graph, -1);
	nodes_number = vector_get_size(graph->vertices);
	vertices = (unsigned int *) _new(nodes_number * sizeof(unsigned int));

	for (i = 0; i < nodes_number; i++)
		vertices[i] = i;

	quick_sort(vertices, nodes_number, key_at, set_key_at,
			_compare_nodes_strongly_connected_components, graph->vertices);

	graph_transpose_graph(graph);
	graph_set_current_time(0);
	_graph_reset_vertices(graph);
	for (i = 0; i < nodes_number; i++)
	{
		if (vertex_get_visited(vector_get_key_at(graph->vertices, i)))
			continue;
		t_start = graph_get_current_time();
		_graph_dfs(graph, vertices[i]);
		t_stop = graph_get_current_time();

		add = linked_list_new();

		for (j = 0; j < nodes_number; j++)
		{
			aux = vertex_get_time_stop(vector_get_key_at(graph->vertices, j));
			if (aux > t_start && aux <= t_stop)
				linked_list_push_back(add, (void *) j);
		}

		if (linked_list_get_size(add) > 0)
			linked_list_push_back(strongly_connected_components, add);
		else
			// Delete allocated memory in order to avoid memory leaks.
			linked_list_delete(add);
	}

	_delete(vertices);
	graph_transpose_graph(graph);
}

int graph_topological_sort(graph_t graph, linked_list_t sort)
{
	unsigned int i, j, nodes_number;
	int ok, dead_lock;

	LOGGER("[graph topological sort] graph %p, list %p\n", graph, sort);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(sort, ==, NULL, NULL_POINTER, -1);

	_graph_reset_vertices(graph);
	nodes_number = vector_get_size(graph->vertices);

	while (1)
	{
		dead_lock = 1;
		for (i = 0; i < nodes_number; i++)
		{
			ok = 1;
			// Check if there is a vertex with 0 in-degree. I simulate
			// edges removing by visiting nodes.
			for (j = 0; j < nodes_number; j++)
			{
				if (!vertex_get_visited(vector_get_key_at(graph->vertices, j))
						&& graph_is_edge(graph, j, i))
				{
					ok = 0;
					break;
				}
			}

			if (ok
					&& !vertex_get_visited(
							vector_get_key_at(graph->vertices, i)))
			{
				// If vertex i has 0 in-degree then add it to
				// topological sort list and visit it.
				linked_list_push_back(sort, (void *) i);
				vertex_set_visited(vector_get_key_at(graph->vertices, i), 1);
				dead_lock = 0;
			}
		}

		if (linked_list_get_size(sort) == nodes_number)
			break;

		if (dead_lock)
			return -1;
	}

	graph_reset_vertices(graph);
	return 0;
}

int graph_bipartite(graph_t graph, linked_list_t first_set,
		linked_list_t second_set)
{
	unsigned int i, j, n, ok;
	vertex_t vertex;
	void *context;

	LOGGER("[graph bipartite] graph %p, first set %p, second set %p\n", graph,
			first_set, second_set);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(first_set, ==, NULL, NULL_POINTER, -1);
	_ASSERT(second_set, ==, NULL, NULL_POINTER, -1);

	// Do a complete BFS travel.
	graph_bfs(graph, -1);

	n = vector_get_size(graph->vertices);

	// Check if all pairs of neighbors don't have even sum distance.
	for (i = 0; i < n - 1; i++)
	{
		vertex = graph->implementation->first_vertex(graph->graph, i, &context);

		ok = 1;
		while (1)
		{
			if (vertex == NULL)
				break;

			j = vertex_get_identifier(vertex);
			if (j > i)
			{
				if (!(vertex_get_cost(vector_get_key_at(graph->vertices, i))
						+ vertex_get_cost(vector_get_key_at(graph->vertices, j))))
					ok = 0;
			}
			else
			{
				graph->implementation->delete_vertex_context(&context);
				break;
			}

			vertex = graph->implementation->next_vertex(graph->graph, i,
					&context);
		}

		if (!ok)
			return 1;
	}

	// For-each vertex in graph, if it's distance is odd add to A, else
	// add it to B.
	for (i = 0; i < n; i++)
	{
		if (((unsigned int) vertex_get_cost(vector_get_key_at(graph->vertices,
				i))) % 2)
			linked_list_push_back(first_set, (void *) i);
		else
			linked_list_push_back(second_set, (void *) i);
	}

	return 0;
}

unsigned int graph_diameter(graph_t graph, unsigned int *first_node,
		unsigned int *second_node)
{
	unsigned int max1, max2, i, n, aux;

	LOGGER("[graph diameter] graph %p, first node %p, second node %p\n", graph,
			first_node, second_node);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(first_node, ==, NULL, NULL_POINTER, -1);
	_ASSERT(second_node, ==, NULL, NULL_POINTER, -1);

	// Make two BFS travels: first, starting from first node of graph_t
	// and the second, starting from a leaf node of the first travel.
	// Return the leaf nodes and the distance between them.

	_graph_reset_vertices(graph);

	_graph_bfs(graph, 0);

	n = vector_get_size(graph->vertices);

	max1 = max2 = 0;

	for (i = 0; i < n; i++)
	{
		aux = (unsigned int) vertex_get_cost(vector_get_key_at(graph->vertices,
				i));
		if (max1 < (unsigned int) aux)
		{
			max1 = aux;
			*first_node = i;
		}
	}

	_graph_reset_vertices(graph);

	_graph_bfs(graph, *first_node);

	for (i = 0; i < n; i++)
	{
		aux = (unsigned int) vertex_get_cost(vector_get_key_at(graph->vertices,
				i));
		if (max2 < (unsigned int) aux)
		{
			max2 = aux;
			*second_node = i;
		}
	}

	_graph_reset_vertices(graph);

	return MAX(max1, max2);
}

void graph_articulation_points(graph_t graph, linked_list_t articulation_points)
{
	unsigned int i, n, *parent, *low, *start;
	int *color, *cut_vertex;

	LOGGER("[graph articulation points] graph %p, articulation points\n",
			graph, articulation_points);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(articulation_points, ==, NULL, NULL_POINTER,);

	n = vector_get_size(graph->vertices);
	parent = (unsigned int *) _new(n * sizeof(unsigned int));
	low = (unsigned int *) _new(n * sizeof(unsigned int));
	start = (unsigned int *) _new(n * sizeof(unsigned int));
	color = (int *) _new(n * sizeof(int));
	cut_vertex = (int *) _new(n * sizeof(int));

	for (i = 0; i < n; i++)
	{
		parent[i] = (unsigned int) -1;
		low[i] = 0;
		start[i] = 0;
		cut_vertex[i] = 0;
		color[i] = WHITE;
	}

	for (i = 0; i < n; i++)
	{
		if (color[i] == WHITE)
		{
			if (_articulation_points_travel(graph, i, color, start, low,
					parent, cut_vertex) > 1)
				cut_vertex[i] = 1;
			else
				cut_vertex[i] = 0;
		}
	}

	for (i = 0; i < n; i++)
		if (cut_vertex[i])
			linked_list_push_back(articulation_points, (void *) i);

	_delete(parent);
	_delete(low);
	_delete(start);
	_delete(color);
	_delete(cut_vertex);
}

static void _graph_bridges_edges_handler(edge_t edge, void *context)
{
	int **_bridges = (int **) context;
	_bridges[vertex_get_identifier(edge_get_vertex1(edge))][vertex_get_identifier(
			edge_get_vertex2(edge))] = 1;
}

void graph_bridges(graph_t graph, linked_list_t bridges)
{
	/*
	 * This algorithm is based on observation : an edge is a bridge if and only if
	 * it's not part of a simple cycle in given graph_t.
	 */
	linked_list_t cycles;
	linked_list_iterator_t it_list, it;
	unsigned int i, j, n;
	int **_bridges;

	LOGGER("[graph bridges] graph %p, bridges %p\n", graph, bridges);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(bridges, ==, NULL, NULL_POINTER,);

	cycles = linked_list_new();
	n = vector_get_size(graph->vertices);
	_bridges = (int **) _new(n * sizeof(int *));

	for (i = 0; i < n; i++)
	{
		_bridges[i] = (int *) _new(n * sizeof(int));
		for (j = 0; j < n; j++)
			_bridges[i][j] = 0;
	}

	// This function guarantees O(E) complexity
	graph->implementation->iterate_edges(graph->graph,
			_graph_bridges_edges_handler, _bridges);

	graph_cycles(graph, cycles);

	/*
	 * 1. For-each cycle execute :
	 * 	2. For-each edge (u, v) from current cycle remove (u, v) from bridges list.
	 */
	for (it_list = linked_list_get_begin(cycles); it_list != NULL; it_list
			= linked_list_iterator_get_next(it_list))
	{
		i = (unsigned int) linked_list_iterator_get_key(linked_list_get_begin(
				((linked_list_t) linked_list_iterator_get_key(it_list))));
		j = (unsigned int) linked_list_iterator_get_key(linked_list_get_end(
				((linked_list_t) linked_list_iterator_get_key(it_list))));
		_bridges[i][j] = _bridges[j][i] = 0;

		for (it = linked_list_get_begin(
				((linked_list_t) linked_list_iterator_get_key(it_list))); linked_list_iterator_get_next(
				it) != NULL;)
		{
			i = (unsigned int) linked_list_iterator_get_key(it);
			it = linked_list_iterator_get_next(it);
			j = (unsigned int) linked_list_iterator_get_key(it);
			_bridges[i][j] = _bridges[j][i] = 0;
		}
		linked_list_delete(linked_list_iterator_get_key(it_list));
	}
	linked_list_delete(cycles);

	for (i = 0; i < n - 1; i++)
	{
		for (j = i + 1; j < n; j++)
		{
			if (_bridges[i][j])
				linked_list_push_back(bridges, pair_new((void *) i, (void *) j));
		}
		_delete(_bridges[i]);
	}
	_delete(_bridges[n - 1]);
	_delete(_bridges);
}

void graph_biconex_components(graph_t graph, linked_list_t biconex_components)
{
	/*
	 * The algorithm chosen for finding the biconex components is:
	 * 	1. Find the articulation points.
	 * 	2. Remove the articulation points from the graph.
	 * 	3. Find the connected components of the graph_t and put them into the given variable.
	 *  4. Build the biconex components by adding the articulation points to the
	 *  connected components calculated above. Also, between two articulation points there is
	 *  a biconex component.
	 */

	linked_list_t cut_vertex, connected_components;
	linked_list_iterator_t it, it_cc, it_cv;
	vertex_t vertex;
	void *copy, *context;

	LOGGER("[graph biconex components] graph %p, biconex components %p\n",
			graph, biconex_components);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(biconex_components, ==, NULL, NULL_POINTER,);

	cut_vertex = linked_list_new();
	graph_articulation_points(graph, cut_vertex);

	// Make a safe copy of initial adjacency matrix.
	copy = graph->implementation->store(graph->graph);

	// Remove cut vertices from graph_t.
	for (it = linked_list_get_begin(cut_vertex); it != NULL; it
			= linked_list_iterator_get_next(it))
	{
		vertex = graph->implementation->first_vertex(graph->graph,
				(unsigned int) linked_list_iterator_get_key(it), &context);

		while (1)
		{
			if (vertex == NULL)
				break;

			graph_remove_edge(graph,
					(unsigned int) linked_list_iterator_get_key(it),
					vertex_get_identifier(vertex));
			graph_remove_edge(graph, vertex_get_identifier(vertex),
					(unsigned int) linked_list_iterator_get_key(it));

			vertex = graph->implementation->next_vertex(graph->graph,
					(unsigned int) linked_list_iterator_get_key(it), &context);
		}
	}

	connected_components = linked_list_new();
	graph_connected_components(graph, connected_components, 0);

	for (it = linked_list_get_begin(connected_components); it != NULL; it
			= linked_list_iterator_get_next(it))
	{
		// linked_list_iterator_get_key(NULL, it, 0) represents a connected component.
		// it_cc = iterator on connected component nodes.
		// it_cv = iterator on cut vertices.

		// Add articulation points.
		for (it_cc = linked_list_get_begin(
				((linked_list_t) linked_list_iterator_get_key(it))); it_cc
				!= NULL; it_cc = linked_list_iterator_get_next(it_cc))
		{
			for (it_cv = linked_list_get_begin(cut_vertex); it_cv != NULL; it_cv
					= linked_list_iterator_get_next(it_cv))
				if (graph->implementation->get_edge(copy,
						(unsigned int) linked_list_iterator_get_key(it_cc),
						(unsigned int) linked_list_iterator_get_key(it_cv))
						&& linked_list_iterator_get_key(it_cc)
								!= linked_list_iterator_get_key(it_cv)
						&& !linked_list_search_key(
								linked_list_iterator_get_key(it),
								linked_list_iterator_get_key(it_cv),
								_compare_nodes_unsigned, NULL))
					linked_list_push_front(linked_list_iterator_get_key(it),
							linked_list_iterator_get_key(it_cv));
		}

		linked_list_push_back(biconex_components, linked_list_iterator_get_key(
				it));
	}

	graph->implementation->delete_g(graph->graph);
	graph->graph = copy;
	linked_list_delete(connected_components);
	linked_list_delete(cut_vertex);
}

void graph_cycles(graph_t graph, linked_list_t cycles)
{
	unsigned int i, n, *parent, current_node = 0;
	int *colour, *visited;

	LOGGER("[graph cycles] graph %p, cycles %p\n", graph, cycles);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(cycles, ==, NULL, NULL_POINTER,);

	n = vector_get_size(graph->vertices);

	parent = (unsigned int *) _new(n * sizeof(unsigned int));
	colour = (int *) _new(n * sizeof(int));
	visited = (int *) _new(n * sizeof(int));

	for (i = 0; i < n; i++)
	{
		parent[i] = (unsigned int) -1;
		colour[i] = WHITE;
		visited[i] = 0;
	}

	while (current_node != (unsigned int) -1)
	{
		_cycles_travel(graph, current_node, cycles, parent, colour, visited);

		current_node = (unsigned int) -1;
		// Find the first unvisited vertex and start new DFS travel from it.
		for (i = 0; i < n; i++)
		{
			if (!visited[i])
			{
				current_node = i;
				break;
			}
		}
	}

	_delete(parent);
	_delete(colour);
	_delete(visited);
}

void graph_dijkstra(graph_t graph, unsigned int source, vector_t distances,
		vector_t parents)
{
	heap_t heap;
	unsigned int i, j, n;
	int *visited;
	double *edge1, *edge2, edge3;
	edge_t m_edge;
	void *context;

	LOGGER("[graph dijkstra] graph %p, source %u, distances %p, parents %p\n",
			graph, source, distances, parents);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(source, >= , graph->size, INVALID_INPUT,);
	_ASSERT(distances, ==, NULL, NULL_POINTER,);
	_ASSERT(parents, ==, NULL, NULL_POINTER,);

	n = vector_get_size(graph->vertices);
	visited = (int *) _new(n * sizeof(int));

	for (i = 0; i < n; i++)
	{
		*(double *) vector_get_key_at(distances, i) = TEMELIA_INFINITY;
		visited[i] = 0;
	}

	*(double *) vector_get_key_at(distances, source) = 0;

	heap = heap_new(n);

	for (i = 0; i < n; i++)
		heap_insert(heap, (void *) i, _compare_dijkstra, distances);

	while (!heap_is_empty(heap))
	{
		i = (unsigned int) heap_get_min_key(heap);
		heap_remove_min_key(heap, _compare_dijkstra, distances);
		visited[i] = 1;

		m_edge = graph->implementation->first_edge(graph->graph, i, &context);
		while (1)
		{
			if (m_edge == NULL)
				break;

			j = vertex_get_identifier(edge_get_vertex2(m_edge));
			edge1 = vector_get_key_at(distances, j);
			edge2 = vector_get_key_at(distances, i);
			edge3 = edge_get_cost(m_edge);

			if (i != j && (*edge1 > *edge2 + edge3))
			{
				*edge1 = *edge2 + edge3;
				vector_set_key_at(parents, j, (void *) i);
				heap_change_key_by_value(heap, (void *) j, (void *) j,
						_compare_dijkstra, distances);
			}
			m_edge
					= graph->implementation->next_edge(graph->graph, i,
							&context);
		}
	}

	heap_delete(heap);
	_delete(visited);
}

int graph_bellman_ford(graph_t graph, unsigned int source, vector_t distances,
		vector_t parents)
{
	unsigned int i, j, k, n;
	double *edge1, *edge2, edge3;

	LOGGER(
			"[graph bellman ford] graph %p, source %u, distances %p, parents %p\n",
			graph, source, distances, parents);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(distances, ==, NULL, NULL_POINTER, -1);
	_ASSERT(parents, ==, NULL, NULL_POINTER, -1);

	n = vector_get_size(graph->vertices);

	for (i = 0; i < n; i++)
	{
		vector_set_key_at(parents, i, (void *) -1);
		*(double *) vector_get_key_at(distances, i) = TEMELIA_INFINITY;
	}

	*(double *) vector_get_key_at(distances, source) = 0;

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			for (k = 0; k < n; k++)
			{
				if (i == j)
					continue;

				edge1 = vector_get_key_at(distances, k);
				edge2 = vector_get_key_at(distances, j);
				edge3 = edge_get_cost(graph_get_edge(graph, j, k));

				if (*edge1 > *edge2 + edge3)
				{
					*edge1 = *edge2 + edge3;
					vector_set_key_at(parents, k, (void *) j);
				}
			}
		}
	}

	// If there exists an edge (i, j) such that distances[j] > distances[i] + graph_t[i][j]
	// then, in the graph_t, is a negative cycle.
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (graph_is_edge(graph, i, j))
			{
				if (*(double *) vector_get_key_at(distances, j)
						> *(double *) vector_get_key_at(distances, i)
								+ edge_get_cost(graph_get_edge(graph, i, j)))
					return -1;
			}
		}
	}

	return 0;
}

void graph_floyd_warshall(graph_t graph, matrix_t distances, matrix_t parents)
{
	unsigned int i, j, k, n;
	double *edge1, *edge2, *edge3;

	LOGGER("[graph floyd warshall] graph %p, distances %p, parents %p\n",
			graph, distances, parents);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(distances, ==, NULL, NULL_POINTER,);
	_ASSERT(parents, ==, NULL, NULL_POINTER,);

	n = vector_get_size(graph->vertices);

	// The initial distance matrix is equal with the graph_t cost matrix.
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (i == j || !graph_is_edge(graph, i, j))
			{
				matrix_set_key_at(parents, i, j, (void *) -1);
				if (i != j)
					*(double *) matrix_get_key_at(distances, i, j)
							= TEMELIA_INFINITY;
				else
					*(double *) matrix_get_key_at(distances, i, j) = 0;
			}
			else
			{
				matrix_set_key_at(parents, i, j, (void *) i);
				*(double *) matrix_get_key_at(distances, i, j) = edge_get_cost(
						graph_get_edge(graph, i, j));
			}
		}
	}

	// Dynamic programming over k.
	for (k = 0; k < n; k++)
	{
		// For-each edge, relax it and adjust : distances and parents.
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				if (i != j)
				{
					edge1 = matrix_get_key_at(distances, i, j);
					edge2 = matrix_get_key_at(distances, i, k);
					edge3 = matrix_get_key_at(distances, k, j);

					if (*edge2 != TEMELIA_INFINITY && *edge3
							!= TEMELIA_INFINITY)
					{
						if (*edge1 > *edge2 + *edge3)
						{
							*edge1 = *edge2 + *edge3;
							matrix_set_key_at(parents, i, j, matrix_get_key_at(
									parents, k, j));
						}
					}
				}
			}
		}
	}
}

int graph_johnson(graph_t graph, matrix_t distances, matrix_t parents)
{
	/*
	 * The Johnson algorithm computes the minimum distances between all the vertices in the graph_t.
	 * 		1. First, a new node Q is added to the graph_t, connected by zero-weight edge to each other node.
	 * 		2. Second, the Bellman-Ford algorithm is used, starting from the new vertex Q, to find for-each
	 * vertex v the least weight h(v) of a path from Q to v. If this step detects a negative cycle, the
	 * algorithm is terminated.
	 * 		3. The next edges of original graph_t are reweighted using the values computed by the Bellman-Ford
	 * algorithm : an edge from u to v, having length w(u,v), is given the new length w(u,v) + h(u) - h(v).
	 * (graph_t becomes normalized).
	 * 		4. Finally, for each node s, Dijkstra's algorithm is used to find the shortest paths from s to
	 * each other vertex in reweighted graph_t.
	 * 		5. For-each edge (u,v) add h(v) - h(u) to obtain the minimum distance.
	 * (graph_t becomes unnormalized).
	 */

	unsigned int i, j, n, q;
	vector_t bf_h, bf_p, v_distances, v_parents;
	edge_t edge;
	void *context;

	LOGGER("[graph johnson] graph %p, distances %p, parents %p\n", graph,
			distances, parents);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(distances, ==, NULL, NULL_POINTER, -1);
	_ASSERT(matrix_get_rows_number(distances), !=, matrix_get_columns_number(distances), INVALID_INPUT, -1);
	_ASSERT(parents, ==, NULL, NULL_POINTER, -1);
	_ASSERT(matrix_get_rows_number(parents), !=, matrix_get_columns_number(parents), INVALID_INPUT, -1);

	n = graph_get_size(graph);

	q = graph_add_vertex(graph, NULL, NULL);

	_ASSERT(q, ==, -1, FULL, -1);

	for (i = 0; i < n; i++)
		graph_add_edge(graph, q, i, 0, NULL, NULL);

	bf_p = vector_new(n + 1);
	bf_h = vector_new(n + 1);

	for (i = 0; i < n + 1; i++)
		vector_push_back(bf_h, _new(sizeof(double)));

	_ASSERT(graph_bellman_ford(graph, q, bf_h, bf_p), ==, -1, INVALID_INPUT, -1);

	// Normalize graph_t.
	for (i = 0; i < n; i++)
	{
		edge = graph->implementation->first_edge(graph->graph, i, &context);
		while (1)
		{
			if (edge == NULL)
				break;

			j = vertex_get_identifier(edge_get_vertex2(edge));

			if (i != j)
				edge_set_cost(edge, edge_get_cost(edge)
						+ *(double *) vector_get_key_at(bf_h, i)
						- *(double *) vector_get_key_at(bf_h, j));
			matrix_set_key_at(parents, i, j, (void *) -1);
			*(double *) matrix_get_key_at(distances, i, j) = TEMELIA_INFINITY;

			edge = graph->implementation->next_edge(graph->graph, i, &context);
		}
	}

	v_distances = vector_new(n + 1);
	v_parents = vector_new(n + 1);

	for (i = 0; i < n + 1; i++)
	{
		vector_push_back(v_distances, _new(sizeof(double)));
		vector_push_back(v_parents, (void *) -1);
	}

	// Apply Dijkstra's algorithm for each vertex in graph
	for (i = 0; i < n; i++)
	{
		graph_dijkstra(graph, i, v_distances, v_parents);

		for (j = 0; j < n; j++)
		{
			matrix_set_key_at(parents, i, j, (void *) vector_get_key_at(
					v_parents, j));
			*(double *) matrix_get_key_at(distances, i, j)
					= *(double *) vector_get_key_at(v_distances, j)
							+ *(double *) vector_get_key_at(bf_h, j)
							- *(double *) vector_get_key_at(bf_h, i);
		}
	}

	// Re normalize
	for (i = 0; i < n; i++)
	{
		edge = graph->implementation->first_edge(graph->graph, i, &context);
		while (1)
		{
			if (edge == NULL)
				break;

			j = vertex_get_identifier(edge_get_vertex2(edge));

			if (i != j)
				edge_set_cost(edge, edge_get_cost(edge)
						+ *(double *) vector_get_key_at(bf_h, j)
						- *(double *) vector_get_key_at(bf_h, i));

			edge = graph->implementation->next_edge(graph->graph, i, &context);
		}
	}

	for (i = 0; i < n + 1; i++)
	{
		_delete(vector_get_key_at(bf_h, i));
		_delete(vector_get_key_at(v_distances, i));
	}

	vector_delete(bf_h);
	vector_delete(bf_p);
	vector_delete(v_distances);
	vector_delete(v_parents);

	return 0;
}

double graph_prim(graph_t graph, unsigned int start_vertex_identifier,
		linked_list_t minimum_spanning_tree)
{
	/*
	 * Prim's algorithm finds the minimum spanning tree for connected weighted graph_t.
	 * 	1. Put all vertices in queue Q.
	 * 	2. For-each vertex u in graph_t, make key[u] <- INFINITY.
	 * 	3. key[root] <- 0, parent[root] <- NIL.
	 * 	4. while queue Q is not empty execute :
	 * 		5. extract the vertex with minimum key, let it be u.
	 * 		6. for-each vertex v such that v is neighbor with u execute :
	 * 			7. if v is in queue Q and weight(u, v) < key[v] execute :
	 * 				8. parent[v] <- u, key[v] <- weight(u, v).
	 */
	heap_t queue;

	unsigned int i, j, n, *parents;
	double *keys, cost;
	int *visited;
	edge_t m_edge;
	void *context;

	LOGGER(
			"[graph prim] graph %p, start vertex %u, minimum spanning tree %p\n",
			graph, start_vertex_identifier, minimum_spanning_tree);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(minimum_spanning_tree, ==, NULL, INVALID_INPUT, -1);

	n = vector_get_size(graph->vertices);

	_ASSERT(start_vertex_identifier, >=, n, INVALID_INPUT, -1);

	queue = heap_new(n);

	keys = (double *) _new(n * sizeof(double));
	parents = (unsigned int *) _new(n * sizeof(unsigned int));
	visited = (int *) _new(n * sizeof(int));

	for (i = 0; i < n; i++)
	{
		keys[i] = TEMELIA_INFINITY;
		visited[i] = 0;
		parents[i] = (unsigned int) -1;
	}

	keys[start_vertex_identifier] = 0;

	for (i = 0; i < n; i++)
		heap_insert(queue, (void *) i, _compare_prim, keys);

	while (!heap_is_empty(queue))
	{
		i = (unsigned int) heap_get_min_key(queue);
		visited[i] = 1;
		heap_remove_min_key(queue, _compare_prim, keys);

		m_edge = graph->implementation->first_edge(graph->graph, i, &context);

		while (1)
		{
			if (m_edge == NULL)
				break;

			j = vertex_get_identifier(edge_get_vertex2(m_edge));

			if (!visited[j] && edge_get_cost(m_edge) < keys[j])
			{
				edge_debug(m_edge, NULL);
				parents[j] = i;
				keys[j] = edge_get_cost(m_edge);
				heap_change_key_by_value(queue, (void *) j, (void *) j,
						_compare_prim, keys);
			}

			m_edge
					= graph->implementation->next_edge(graph->graph, i,
							&context);
		}
	}

	cost = 0;
	for (i = 0; i < n; i++)
	{
		cost += keys[i];
		linked_list_push_back(minimum_spanning_tree, pair_new((void *) i,
				(void *) parents[i]));
	}

	heap_delete(queue);
	_delete(keys);
	_delete(parents);
	_delete(visited);

	return cost;
}

double graph_kruskal(graph_t graph, unsigned int start_vertex_identifier,
		linked_list_t *minimum_spanning_tree)
{
	/*
	 * Kruskal's algorithm finds a minimum spanning tree for a connected weighted graph_t.
	 * 1. create a forest F (a set of trees), where each vertex in the graph_t is a separate tree
	 * 2. create a set S containing all the edges in the graph
	 * 3. while S is nonempty
	 * 		4. remove an edge with minimum weight from S
	 * 		5. if that edge connects two different trees, then add it to the forest,
	 * 			combining two trees into a single tree
	 * 		6. otherwise discard that edge
	 */

	unsigned int i, j, k, n, k1, k2;
	linked_list_t edges;
	linked_list_iterator_t it;
	linked_list_t *partial_trees;
	int ok;
	double cost;
	edge_t m_edge;
	void *context;

	LOGGER(
			"[graph kruskal] graph %p, start vertex %u, minimum spanning tree %p\n",
			graph, start_vertex_identifier, minimum_spanning_tree);

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(minimum_spanning_tree, ==, NULL, NULL_POINTER, -1);

	n = vector_get_size(graph->vertices);

	_ASSERT(start_vertex_identifier, >=, n, INVALID_INPUT, -1);

	edges = linked_list_new();
	partial_trees = (linked_list_t *) _new(n * sizeof(linked_list_t));
	for (i = 0; i < n; i++)
		partial_trees[i] = linked_list_new();

	linked_list_push_back(partial_trees[0], NULL);

	// Add all the graph_t's edges in the list and sort it.
	for (i = 0; i < n - 1; i++)
	{
		m_edge = graph->implementation->first_edge(graph->graph, i, &context);

		while (1)
		{
			if (m_edge == NULL)
				break;

			j = vertex_get_identifier(edge_get_vertex2(m_edge));

			if (j > i)
			{
				if (edge_get_cost(m_edge) < TEMELIA_INFINITY)
					linked_list_push_back(edges, m_edge);
			}

			m_edge
					= graph->implementation->next_edge(graph->graph, i,
							&context);
		}
		linked_list_push_back(partial_trees[i + 1], (void *) (i + 1));
	}

	// Sort edges by their cost.
	linked_list_sort(edges, _compare_edges_kruskal, NULL);

	cost = 0;

	for (it = linked_list_get_begin(edges); it != NULL; it
			= linked_list_iterator_get_next(it))
	{
		i = vertex_get_identifier(edge_get_vertex1(
				linked_list_iterator_get_key(it)));
		j = vertex_get_identifier(edge_get_vertex2(
				linked_list_iterator_get_key(it)));

		ok = 1;

		k1 = k2 = -1;

		for (k = 0; k < n; k++)
		{
			if (!partial_trees[k])
				continue;

			if (linked_list_search_key(partial_trees[k], (void *) i,
					_compare_nodes_kruskal, NULL) == NULL
					&& linked_list_search_key(partial_trees[k], (void *) j,
							_compare_nodes_kruskal, NULL) != NULL)
				k1 = k;

			if (linked_list_search_key(partial_trees[k], (void *) j,
					_compare_nodes_kruskal, NULL) == NULL
					&& linked_list_search_key(partial_trees[k], (void *) i,
							_compare_nodes_kruskal, NULL) != NULL)
				k2 = k;

			if (linked_list_search_key(partial_trees[k], (void *) i,
					_compare_nodes_kruskal, NULL) != NULL
					&& linked_list_search_key(partial_trees[k], (void *) j,
							_compare_nodes_kruskal, NULL) != NULL)
			{
				ok = 0;
				break;
			}
		}

		if (ok)
		{
			cost += edge_get_cost(graph_get_edge(graph, i, j));

			linked_list_iterator_set_next(
					linked_list_get_end(partial_trees[k1]),
					linked_list_get_begin(partial_trees[k2]));

			linked_list_set_end(partial_trees[k1], linked_list_get_end(
					partial_trees[k2]));

			_delete(partial_trees[k2]);
			partial_trees[k2] = NULL;
		}
	}

	for (i = 0; i < n; i++)
		if (partial_trees[i] != NULL)
			*minimum_spanning_tree = partial_trees[i];

	_delete(partial_trees);
	linked_list_delete(edges);

	return cost;
}

double graph_ford_fulkerson(graph_t graph, unsigned int source,
		unsigned int destination, matrix_t max_flow)
{
	unsigned int n = vector_get_size(graph->vertices);
	linked_list_t path;
	double _max_flow, _min_flow;

	LOGGER(
			"[graph ford fulkerson] graph %u, source %u, destination %u, flow matrix %p\n",
			graph, source, destination, max_flow);

	_ASSERT(graph, ==, NULL, NULL_POINTER, 0);
	_ASSERT(source, >=, n, INVALID_INPUT, 0);
	_ASSERT(destination, >=, n, INVALID_INPUT, 0);
	_ASSERT(max_flow, ==, NULL, NULL_POINTER, 0);
	_ASSERT(matrix_get_columns_number(max_flow), !=, matrix_get_rows_number(max_flow), INVALID_INPUT, 0);

	// Initialize the flow matrix with 0 value.
	_init_flow(max_flow);

	// Initial max flow is 0.
	_max_flow = 0;

	/*
	 * The Ford Fulkerson algorithm is :
	 * 		1. while there is a path from source to destination,
	 * 		such that the flow on that path may increase execute :
	 * 			2. increase the flow on computed path at step 1.
	 * For finding a "good" path, i use DFS search.
	 */
	while (1)
	{
		// Initialization for DFS.
		path = linked_list_new();
		_graph_reset_vertices(graph);

		// Find a valid path from source to destination.
		_flow_dfs(graph, source, destination, path, max_flow);

		// End the algorithm if no path is found.
		if (linked_list_get_size(path) == 0)
		{
			linked_list_delete(path);
			break;
		}

		// Compute the min flow on this path
		_min_flow = _min_flow_path(graph, max_flow, path);

		// Add the min flow calculated above to the max_flow matrix
		_add_flow_on_path(max_flow, path, _min_flow);

		// Reset variables: vertices and path list
		_graph_reset_vertices(graph);
		linked_list_delete(path);

		// Add the min-flow to max-flow, in order to return the desired result
		_max_flow += _min_flow;
	}

	return _max_flow;
}

double graph_edmonds_karp(graph_t graph, unsigned int source,
		unsigned int destination, matrix_t max_flow)
{
	unsigned int n = vector_get_size(graph->vertices);
	linked_list_t path;
	double _max_flow, _min_flow;

	LOGGER(
			"[graph ford fulkerson] graph %u, source %u, destination %u, flow matrix %p\n",
			graph, source, destination, max_flow);

	_ASSERT(graph, ==, NULL, NULL_POINTER, 0);
	_ASSERT(source, >=, n, INVALID_INPUT, 0);
	_ASSERT(destination, >=, n, INVALID_INPUT, 0);
	_ASSERT(max_flow, ==, NULL, NULL_POINTER, 0);
	_ASSERT(matrix_get_columns_number(max_flow), !=, matrix_get_rows_number(max_flow), INVALID_INPUT, 0);

	// Initialize the flow matrix with 0 value.
	_init_flow(max_flow);

	// Initial max flow is 0.
	_max_flow = 0;

	/*
	 * The Edmonds-Karp algorithm is :
	 * 		1. while there is a path from source to destination,
	 * 		such that the flow on that path may increase execute :
	 * 			2. increase the flow on computed path at step 1.
	 * For finding a "good" path, i use BFS search.
	 */
	while (1)
	{
		// Initialization for BFS.
		path = linked_list_new();
		_graph_reset_vertices(graph);

		// Find a valid path from source to destination.
		_flow_bfs(graph, source, destination, path, max_flow);

		// End the algorithm if no path is found : path contains only
		// the destination vertex.
		if (linked_list_get_size(path) <= 1)
		{
			linked_list_delete(path);
			break;
		}

		// Compute the min flow on this path
		_min_flow = _min_flow_path(graph, max_flow, path);

		// If there is no flow, return.
		// Actually, the algorithm should never execute this break,
		// because _flow_BFS guarantees a "good" path; I wrote this
		// statement "just in case"
		if (_min_flow == 0)
			break;

		// Add the min flow calculated above to the max_flow matrix
		_add_flow_on_path(max_flow, path, _min_flow);

		// Reset variables: vertices and path list
		_graph_reset_vertices(graph);
		linked_list_delete(path);

		// Add the min-flow to max-flow, in order to return the desired result
		_max_flow += _min_flow;
	}

	return _max_flow;
}

// === Private functions implementation ===
static void _graph_dfs(graph_t graph, unsigned int node)
{
	unsigned int node_next, nodes_number;
	vertex_t vertex = vector_get_key_at(graph->vertices, node), vertex_next;
	void *context;

	// Return is the current node is not white or visited
	if (vertex_get_color(vertex) != WHITE || vertex_get_visited(vertex))
		return;

	// Change vertex color to GRAY.
	vertex_set_color(vertex, GRAY);

	// Visit the node by setting visited variable accordingly
	vertex_set_visited(vertex, 1);

	// Set the time current node was discovered.
	vertex_set_time_start(vertex, current_time++);

	nodes_number = vector_get_size(graph->vertices);

	vertex_next = graph->implementation->first_vertex(graph->graph, node,
			&context);

	while (1)
	{
		// No more neighbors
		if (vertex_next == NULL)
			break;

		node_next = vertex_get_identifier(vertex_next);

		// If 1, 2, 3 and 4 are true then next_node is a valid neighbor, from DFS point of view,
		// I continue the travel from it.
		//		1. node_next is a valid node in graph
		//		2. it's color is white
		//		3. it's not visited yet
		//		4. there is an edge between node and node next
		if (vertex_get_color(vertex_next) == WHITE && !vertex_get_visited(
				vertex_next))
		{
			vertex_set_parent_identifier(vertex_next, node);
			_graph_dfs(graph, node_next);
		}

		vertex_next = graph->implementation->next_vertex(graph->graph, node,
				&context);
	}

	// Finished traveling this node, set it's time stop and it's color to black
	vertex_set_time_stop(vertex, current_time++);

	// Set it's color to black (DFS finished visiting this node)
	vertex_set_color(vertex, BLACK);
}

static void _graph_bfs(graph_t graph, unsigned int node)
{
	unsigned int nodes_number;
	void *context;
	queue_t queue;
	vertex_t vertex, vertex_next;

	vertex = vector_get_key_at(graph->vertices, node);

	// Returns if current node isn't white or visited
	if (vertex_get_color(vertex) != WHITE || vertex_get_visited(vertex))
		return;

	nodes_number = vector_get_size(graph->vertices);

	// Vertices queue can have maximum of nodes_number keys
	queue = queue_new(nodes_number);

	// In BFS cost represents the distance from root to current vertex
	// Root vertex has 0 cost and parent -1
	vertex_set_color(vertex, GRAY);
	vertex_set_cost(vertex, 0);
	vertex_set_parent_identifier(vertex, -1);
	vertex_set_visited(vertex, 1);

	// Put the first vertex in the queue.
	queue_push_back(queue, vertex);

	// 0. while queue is not empty execute
	//		1. extract a node from queue
	//		2. for each unvisited node, adjacent  with extracted node, do :
	//			3. set new vertex parameters
	//			4. insert neighbor in queue
	while (!queue_is_empty(queue))
	{
		vertex = queue_get_front(queue);
		node = vertex_get_identifier(vertex);
		queue_pop_front(queue);

		vertex_set_time_start(vertex, current_time++);
		vertex_next = graph->implementation->first_vertex(graph->graph, node,
				&context);

		while (1)
		{
			if (vertex_next == NULL)
				break;

			// If the vertex exists, there is an edge from current node to it,
			// it's color is white and was not visited, then is eligible
			// to pushing back in the bfs travel queue.
			if (vertex_get_color(vertex_next) == WHITE && !vertex_get_visited(
					vertex_next))
			{
				// Push back in queue the next vertex
				queue_push_back(queue, vertex_next);

				// Set next vertex color to gray
				vertex_set_color(vertex_next, GRAY);

				// Set cost as 1 + cost(parent).
				vertex_set_cost(vertex_next, 1 + vertex_get_cost(vertex));

				// Set a link between vertex_next and vertex, by setting
				// vertex_next parent's identifier
				vertex_set_parent_identifier(vertex_next,
						vertex_get_identifier(vertex));

				// Set vertex as visited.
				vertex_set_visited(vertex_next, 1);
			}
			vertex_next = graph->implementation->next_vertex(graph->graph,
					node, &context);
		}

		// Finish BFS travel on this node.
		vertex_set_color(vertex, BLACK);
		vertex_set_time_stop(vertex, current_time++);
	}

	// Free the queue used by BFS.
	queue_delete(queue);
}

static void _graph_reset_vertices(graph_t graph)
{
	unsigned int node, nodes_number;
	vertex_t vertex;

	nodes_number = vector_get_size(graph->vertices);
	for (node = 0; node < nodes_number; node++)
	{
		// For-each vertex in graph_t set their parameters to default value.
		vertex = vector_get_key_at(graph->vertices, node);
		vertex_set_color(vertex, WHITE);
		vertex_set_parent_identifier(vertex, -1);
		vertex_set_time_start(vertex, 0);
		vertex_set_time_stop(vertex, 0);
		vertex_set_visited(vertex, 0);
	}
}

unsigned int _articulation_points_travel(graph_t graph, unsigned int u,
		int *color, unsigned int *start, unsigned int *low,
		unsigned int *parent, int *cut_vertex)
{
	unsigned int subtrees = 0, v;
	vertex_t vertex;
	void *context;

	color[u] = GRAY;
	start[u] = ++current_time;
	low[u] = start[u];

	vertex = graph->implementation->first_vertex(graph->graph, u, &context);

	while (1)
	{
		if (vertex == NULL)
			break;

		v = vertex_get_identifier(vertex);
		if (color[v] == WHITE)
		{
			parent[v] = u;
			_articulation_points_travel(graph, v, color, start, low, parent,
					cut_vertex);
			subtrees++;

			if (low[v] < low[u])
				low[u] = low[v];

			if (low[v] >= start[u])
				cut_vertex[u] = 1;
		}
		else if (color[v] == GRAY)
		{
			if (start[v] < low[u])
				low[u] = start[v];
		}

		vertex = graph->implementation->next_vertex(graph->graph, u, &context);
	}

	color[u] = BLACK;
	return subtrees;
}

static void _cycles_travel(graph_t graph, unsigned int current_node,
		linked_list_t current_cycles, unsigned int *parent, int *color,
		int *visited)
{
	unsigned int next_node, n;
	linked_list_t small_cycle;
	vertex_t vertex;
	void *context;

	color[current_node] = GRAY;
	visited[current_node] = 1;

	n = vector_get_size(graph->vertices);

	vertex = graph->implementation->first_vertex(graph->graph, current_node,
			&context);
	while (1)
	{
		if (vertex == NULL)
			break;

		next_node = vertex_get_identifier(vertex);

		/*
		 * If there are two vertices u and v such that :
		 * 		1. u and v are neighbors.
		 * 		2. u isn't the parent of v
		 * 		3. v is the next node in DFS travel, after visiting u.
		 * 		4. v is already visited.
		 * Then u and v close a cycles.
		 * Rebuild the path and add the new cycle to cycles list.
		 */
		if (visited[next_node] && color[next_node] == GRAY && parent[next_node]
				!= current_node)
		{
			small_cycle = linked_list_new();
			_rebuild_cycle(current_node, next_node, parent, small_cycle);
			if (linked_list_get_size(small_cycle) > 2)
				linked_list_push_back(current_cycles, small_cycle);
			else
				linked_list_delete(small_cycle);
		}

		vertex = graph->implementation->next_vertex(graph->graph, current_node,
				&context);
	}

	vertex = graph->implementation->first_vertex(graph->graph, current_node,
			&context);
	while (1)
	{
		if (vertex == NULL)
			break;

		next_node = vertex_get_identifier(vertex);

		if (color[next_node] == WHITE && !visited[next_node])
		{
			parent[next_node] = current_node;
			_cycles_travel(graph, next_node, current_cycles, parent, color,
					visited);
		}

		vertex = graph->implementation->next_vertex(graph->graph, current_node,
				&context);
	}

	color[current_node] = BLACK;
}

static void _rebuild_cycle(unsigned int current_node, unsigned int next_node,
		unsigned int *parent, linked_list_t small_cycle)
{
	if (current_node == next_node)
	{
		linked_list_push_back(small_cycle, (void *) current_node);
		return;
	}

	_rebuild_cycle(parent[current_node], next_node, parent, small_cycle);
	linked_list_push_back(small_cycle, (void *) current_node);
}

static int _compare_nodes_unsigned(void *x, void *y, void *context)
{
	return (int) ((unsigned long) x - (unsigned long) y);
}

static int _int_compare(void *x, void *y, void *context)
{
	return (unsigned int) x - (unsigned int) y;
}

static int _compare_nodes_strongly_connected_components(void *x, void *y,
		void *context)
{

	// Compare the two vertices after their t_stop parameter.
	// The context (vector of vertices) is stored in the global variable.
	return vertex_get_time_stop(vector_get_key_at((vector_t) context,
			(unsigned int) y)) - vertex_get_time_stop(vector_get_key_at(
			(vector_t) context, (unsigned int) x));
}

static int _compare_dijkstra(void *x, void *y, void *context)
{
	vector_t distances = context;

	double *a = (double *) vector_get_key_at(distances, (unsigned int) x);
	double *b = (double *) vector_get_key_at(distances, (unsigned int) y);

	if (*a < *b)
		return -1;
	else if (*a > *b)
		return +1;

	// If the vertices have the same distance from source then
	// i compare them after their identifiers.
	return (unsigned int) x - (unsigned int) y;
}

static int _compare_prim(void *x, void *y, void *context)
{
	double *distances = context;
	unsigned int v1, v2;

	v1 = (unsigned int) x;
	v2 = (unsigned int) y;
	if (distances[v1] < distances[v2])
		return -1;
	else if (distances[v1] > distances[v2])
		return 1;

	// If the vertices have the same distance from source then
	// i compare them after their identifiers.
	return v1 - v2;
}

static int _compare_edges_kruskal(void *x, void *y, void *context)
{
	edge_t edge1, edge2;
	double a, b;
	edge1 = x;
	edge2 = y;

	a = edge_get_cost(edge1);
	b = edge_get_cost(edge2);

	if (a < b)
		return -1;
	if (a > b)
		return 1;
	return 0;
}

static int _compare_nodes_kruskal(void *x, void *y, void *context)
{
	return (int) ((unsigned long) x - (unsigned long) y);
}

static void _init_flow(matrix_t flow)
{
	unsigned int i, j, n;

	n = matrix_get_columns_number(flow);

	// For-each key in the matrix, set it's value to 0.
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			*(double *) matrix_get_key_at(flow, i, j) = 0;
}

static void _flow_dfs(graph_t graph, unsigned int current_node,
		unsigned int destination, linked_list_t path, matrix_t max_flow)
{
	/*
	 * 	Basically, the current function has the same idea as ordinary DFS travel.
	 * The main difference is that this method adds flow constrains on links
	 * between vertices.
	 * 	For example, if an edge is saturated (flow = capacity) then the vertices
	 * aren't neighbors; in ordinary DFS they are.
	 * 	With other words, _flow_dfs works with function cost equals to edge_capacity - edge_flow;
	 * and DFS works with edge_flow as 0 identity function.
	 */

	vertex_t u = vector_get_key_at(graph->vertices, current_node);
	unsigned int next_node, nodes_number;
	double capacity;

	nodes_number = vector_get_size(graph->vertices);

	if (vertex_get_visited(u))
		return;

	vertex_set_visited(u, 1);
	linked_list_push_back(path, (void *) current_node);

	if (current_node == destination)
		return;

	for (next_node = 0; next_node < nodes_number; next_node++)
		/* Travel the next_node only if :
		 * 		1. destination isn't visited
		 * 		2. next_node isn't visited.
		 */
		if (!vertex_get_visited(vector_get_key_at(graph->vertices, destination))
				&& !vertex_get_visited(vector_get_key_at(graph->vertices,
						next_node)))
		{
			/*
			 * 		1. If there is an edge between current_node and next_node
			 * 			then continue only if the flow is smaller then the cost (capacity).
			 *
			 * 		2. If there isn't an edge between current_node and next_node
			 * 			then consider the capacity 0 and go on if the flow is negative.
			 */
			if (graph_is_edge(graph, current_node, next_node))
				capacity = edge_get_cost(graph_get_edge(graph, current_node,
						next_node));
			else
				capacity = 0;

			if (*(double *) matrix_get_key_at(max_flow, current_node, next_node)
					< capacity)
				_flow_dfs(graph, next_node, destination, path, max_flow);
		}

	if (!vertex_get_visited(vector_get_key_at(graph->vertices, destination)))
	{
		linked_list_remove_key(path, (void *) current_node, _int_compare, NULL,
				1);
		vertex_set_visited(vector_get_key_at(graph->vertices, current_node), 0);
	}
}

static void _flow_bfs(graph_t graph, unsigned int source,
		unsigned int destination, linked_list_t path, matrix_t max_flow)
{
	queue_t queue;
	vertex_t vertex, current_vertex;
	unsigned int next_node, current_node, nodes_number;
	void *context;

	/*
	 * 	Basically, this function has the same idea as ordinary BFS function.
	 * 	The main difference is that this method adds flow constrains on links
	 * between vertices.
	 * 	See _flow_dfs for more details about the last statement.
	 */
	nodes_number = vector_get_size(graph->vertices);

	vertex = vector_get_key_at(graph->vertices, source);
	vertex_set_visited(vertex, 1);
	vertex_set_parent_identifier(vertex, (unsigned int) -1);

	queue = queue_new(nodes_number);
	queue_push_back(queue, vertex);

	while (!queue_is_empty(queue))
	{
		current_vertex = queue_get_front(queue);
		current_node = vertex_get_identifier(current_vertex);
		queue_pop_front(queue);

		vertex = graph->implementation->first_vertex(graph->graph,
				current_node, &context);

		while (1)
		{
			if (vertex == NULL)
				break;

			next_node = vertex_get_identifier(vertex);

			if ((CAPACITY(graph, current_node, next_node)) > (FLOW(max_flow,
					current_node, next_node)) && !vertex_get_visited(vertex))
			{
				vertex_set_visited(vertex, 1);
				vertex_set_parent_identifier(vertex, current_node);
				queue_push_back(queue, vertex);
			}

			vertex = graph->implementation->next_vertex(graph->graph,
					current_node, &context);
		}
	}

	// After the BFS modified travel ended, i compute the path between
	// destination and source, analyzing each vertex parent.
	current_node = destination;

	while (current_node != (unsigned int) -1)
	{
		linked_list_push_front(path, (void *) current_node);
		current_node = vertex_get_parent_identifier(vector_get_key_at(
				graph->vertices, current_node));
	}

	// Free the queue used.
	queue_delete(queue);
}

static double _min_flow_path(graph_t graph, matrix_t max_flow,
		linked_list_t path)
{
	double min_flow, aux;
	unsigned i, j, k, n;
	linked_list_iterator_t it;

	/*
	 * Finds the minimum flow for a given path : a(0), a(1) .... a(N).
	 * a - list of vertices.
	 * The algorithm is trivial :
	 * 		1. for-each a(K) and a(K+1), K from 0 to N-1 execute :
	 * 			2. if the current min_flow is greater the flow from a(K) to a(K+1),
	 * 			then actualize current min_flow to the smaller flow value.
	 * 		3. return the min_flow.
	 */

	it = linked_list_get_begin(path);

	i = (unsigned int) linked_list_iterator_get_key(it);
	it = linked_list_iterator_get_next(it);
	j = (unsigned int) linked_list_iterator_get_key(it);
	it = linked_list_iterator_get_next(it);

	min_flow = CAPACITY(graph, i, j) - FLOW(max_flow, i, j);
	n = linked_list_get_size(path);

	for (k = 1; k < n - 1; k++)
	{
		i = j;
		j = (unsigned int) linked_list_iterator_get_key(it);
		it = linked_list_iterator_get_next(it);

		aux = CAPACITY(graph, i, j) - FLOW(max_flow, i, j);
		if (aux < min_flow)
			min_flow = aux;
	}

	return min_flow;
}

static void _add_flow_on_path(matrix_t max_flow, linked_list_t path,
		double min_flow)
{
	unsigned i, j, k, n;
	linked_list_iterator_t it;

	/*
	 * Increases the flow from a given path : a(0), a(1) .... a(N).
	 * a - list of vertices.
	 * The algorithm is trivial :
	 * 		1.for-each a(K) and a(K+1), increase the flow with min_flow value.
	 * 		2.for-each a(K+1) and a(K), decrease the flow with min_flow value.
	 * The second statement is used because flow(u,v) = -flow(v,u).
	 */

	it = linked_list_get_begin(path);
	i = (unsigned int) linked_list_iterator_get_key(it);
	it = linked_list_iterator_get_next(it);
	j = (unsigned int) linked_list_iterator_get_key(it);
	it = linked_list_iterator_get_next(it);

	(*(double *) matrix_get_key_at(max_flow, i, j)) += min_flow;
	(*(double *) matrix_get_key_at(max_flow, j, i)) -= min_flow;

	n = linked_list_get_size(path);

	for (k = 1; k < n - 1; k++)
	{
		i = j;
		j = (unsigned int) linked_list_iterator_get_key(it);
		it = linked_list_iterator_get_next(it);

		(*(double *) matrix_get_key_at(max_flow, i, j)) += min_flow;
		(*(double *) matrix_get_key_at(max_flow, j, i)) -= min_flow;
	}
}

INLINE static double CAPACITY(graph_t graph, unsigned int i, unsigned int j)
{
	if (!graph_is_edge(graph, i, j))
		return 0;
	return edge_get_cost(graph_get_edge(graph, i, j));
}

INLINE static double FLOW(matrix_t max_flow, unsigned int i, unsigned int j)
{
	return *(double *) matrix_get_key_at(max_flow, i, j);
}

// === End ===