temelia/src/graph_sparse_matrix.c

/*!
 Temelia - Sparse matrix implementation structure graph

 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/graph_sparse_matrix.h"
#include "include/sparse_matrix.h"
#include <stdlib.h>

struct _graph_sparse_matrix_t
{
	int size;
	sparse_matrix_t sparse_matrix;
};

typedef struct _graph_sparse_matrix_t *graph_sparse_matrix_t;

void *graph_sparse_matrix_new(int size)
{
	graph_sparse_matrix_t graph;

	LOGGER("[graph sparse matrix new] size %d\n", size);
	_ASSERT(size, <=, 0, NULL_POINTER, NULL);

	graph = (graph_sparse_matrix_t) _new(sizeof(struct _graph_sparse_matrix_t));

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

	graph->size = size;
	graph->sparse_matrix = sparse_matrix_new(size, size, size * size,
			SPARSE_MATRIX_COLUMN_DENSE | SPARSE_MATRIX_ROW_DENSE);

	if (graph->sparse_matrix == NULL)
	{
		_delete(graph);
		return NULL;
	}

	return graph;
}

void graph_sparse_matrix_delete(void *graph)
{
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;

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

	LOGGER("[graph sparse matrix delete] graph %p, matrix %p\n", graph,
			m_graph->sparse_matrix);
	sparse_matrix_delete(m_graph->sparse_matrix);
	_delete(m_graph);
}

void graph_sparse_matrix_resize(void *graph, int size)
{
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;

	LOGGER("[graph sparse matrix resize] graph %p, new size %d\n", graph, size);

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

	sparse_matrix_resize(m_graph->sparse_matrix, size, size, size * size);
}

void graph_sparse_matrix_add_edge(void *graph, unsigned int src,
		unsigned int dest, edge_t edge)
{
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;

	LOGGER(
			"[graph sparse matrix add edge] graph %p, source %u, destination %u, edge %p\n",
			graph, src, dest, edge);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(edge, ==, NULL, NULL_POINTER,);
	_ASSERT(src, >=, (unsigned int) m_graph->size, INVALID_INPUT,);
	_ASSERT(dest, >=, (unsigned int) m_graph->size, INVALID_INPUT,);

	sparse_matrix_set_key_at(m_graph->sparse_matrix, src, dest, edge);
}

edge_t graph_sparse_matrix_remove_edge(void *graph, unsigned int vertex1,
		unsigned int vertex2)
{
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;
	edge_t edge;

	LOGGER(
			"[graph sparse matrix remove edge] graph %p, source %u, destination %u\n",
			graph, vertex1, vertex2);

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

	_ASSERT(vertex1, >=, (unsigned int) m_graph->size, INVALID_INPUT, NULL);
	_ASSERT(vertex2, >=, (unsigned int) m_graph->size, INVALID_INPUT, NULL);

	edge
			= sparse_matrix_get_key_at(m_graph->sparse_matrix, vertex1,
					vertex2, 0);
	sparse_matrix_set_key_at(m_graph->sparse_matrix, vertex1, vertex2, NULL);

	return edge;
}

edge_t graph_sparse_matrix_get_edge(void *graph, unsigned int vertex1,
		unsigned int vertex2)
{
	graph_sparse_matrix_t m_graph;

	LOGGER(
			"[graph sparse matrix get edge] graph %p, source %u, destination %u\n",
			graph, vertex1, vertex2);

	m_graph = (graph_sparse_matrix_t) graph;

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

	return sparse_matrix_get_key_at(m_graph->sparse_matrix, vertex1, vertex2, 0);
}

vertex_t graph_sparse_matrix_first_vertex(void *graph, unsigned int vertex,
		void **context)
{
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;
	sparse_matrix_t m_matrix;
	unsigned int i, size, *init;
	edge_t edge;

	LOGGER(
			"[graph sparse matrix first vertex] graph %p, vertex %u, context %p\n",
			graph, vertex, context);

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

	m_matrix = (sparse_matrix_t) m_graph->sparse_matrix;

	size = m_graph->size;
	init = _new(sizeof(unsigned int));

	for (i = 0; i < size; i++)
	{
		edge = sparse_matrix_get_key_at(m_matrix, vertex, i, 1);
		if (edge)
		{
			*init = i;
			*((unsigned int **) context) = init;
			return edge_get_vertex2(edge);
		}
	}

	_delete(init);
	return NULL;
}

void graph_sparse_matrix_delete_vertex_context(void **context)
{
	unsigned int **m_context = (unsigned int **) context;

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

	_delete(*m_context);
}

vertex_t graph_sparse_matrix_next_vertex(void *graph, unsigned int vertex,
		void **context)
{
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;
	edge_t m_edge;
	unsigned int it;

	LOGGER(
			"[graph sparse matrix next vertex] graph %p, vertex %u, context %p\n",
			graph, vertex, context);

	_ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(vertex, >=, (unsigned int) m_graph->size, NULL_POINTER, NULL);
	_ASSERT(context, ==, NULL, NULL_POINTER, NULL);

	it = **(unsigned int **) context;

	_ASSERT(it, >= , (unsigned int) m_graph->size, INVALID_INPUT, NULL);

	while (++it < (unsigned int) m_graph->size)
	{
		m_edge
				= sparse_matrix_get_key_at(m_graph->sparse_matrix, vertex, it,
						1);
		if (m_edge)
		{
			**(unsigned int **) context = it;
			return edge_get_vertex2(m_edge);
		}
	}

	_delete(*(unsigned int **) context);
	return NULL;
}

edge_t graph_sparse_matrix_first_edge(void *graph, unsigned int vertex,
		void **context)
{
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;
	sparse_matrix_t m_matrix;
	edge_t edge;
	unsigned int i, size, *init;

	LOGGER(
			"[graph sparse matrix first edge] graph %p, vertex %u, context %p\n",
			graph, vertex, context);

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

	m_matrix = (sparse_matrix_t) m_graph->sparse_matrix;
	size = m_graph->size;
	init = _new(sizeof(unsigned int));

	for (i = 0; i < size; i++)
	{
		edge = sparse_matrix_get_key_at(m_matrix, vertex, i, 1);
		if (edge)
		{
			*init = i;
			*((unsigned int **) context) = init;
			return edge;
		}
	}

	_delete(init);
	return NULL;
}

void graph_sparse_matrix_delete_edge_context(void **context)
{
	unsigned int **m_context = (unsigned int **) context;

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

	_delete(*m_context);
}

edge_t graph_sparse_matrix_next_edge(void *graph, unsigned int vertex,
		void **context)
{
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;
	edge_t m_edge;
	unsigned int it;

	LOGGER("[graph sparse matrix next edge] graph %p, vertex %u, context %p\n",
			graph, vertex, context);

	_ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(vertex, >=, (unsigned int) m_graph->size, NULL_POINTER, NULL);
	_ASSERT(context, ==, NULL, NULL_POINTER, NULL);

	it = **(unsigned int **) context;

	_ASSERT(it, >= , (unsigned int) m_graph->size, INVALID_INPUT, NULL);

	while (++it < (unsigned int) m_graph->size)
	{
		m_edge
				= sparse_matrix_get_key_at(m_graph->sparse_matrix, vertex, it,
						1);
		if (m_edge)
		{
			**(unsigned int **) context = it;
			return m_edge;
		}
	}

	_delete(*(unsigned int **) context);
	return NULL;
}

void graph_sparse_matrix_iterate(void *graph, void(*iterate)(vertex_t src,
		vertex_t dest, double cost, char *label, void *key, int type))
{
	int i, j, n;
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;
	edge_t m_edge;

	LOGGER("[graph sparse matrix iterate] graph %p, iterating function %p\n",
			graph, iterate);

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

	n = m_graph->size;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			m_edge = (edge_t) sparse_matrix_get_key_at(m_graph->sparse_matrix,
					i, j, 0);
			if (m_edge)
			{
				iterate(edge_get_vertex1(m_edge), edge_get_vertex2(m_edge),
						edge_get_cost(m_edge), edge_get_label(m_edge),
						edge_get_key(m_edge), edge_get_type(m_edge));
			}
		}
	}
}

void graph_sparse_matrix_iterate_edges(void *graph, void edge_handler(edge_t e,
		void *context), void *context)
{
	int i, j, n;
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;
	edge_t m_edge;

	LOGGER(
			"[graph sparse matrix iterate edges] graph %p, iterating function %p, context %p\n",
			graph, edge_handler, context);

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

	n = m_graph->size;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			m_edge = (edge_t) sparse_matrix_get_key_at(m_graph->sparse_matrix,
					i, j, 0);
			if (m_edge)
				edge_handler(m_edge, context);
		}
	}
}

void graph_sparse_matrix_transpose(void *graph)
{
	int i, j, n;
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;
	edge_t m_edge1, m_edge2;

	LOGGER("[graph sparse matrix transpose] graph %p\n", graph);

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

	n = m_graph->size;
	for (i = 0; i < n; i++)
	{
		for (j = i + 1; j < n; j++)
		{
			// First edge
			m_edge1 = (edge_t) sparse_matrix_get_key_at(m_graph->sparse_matrix,
					i, j, 0);
			edge_switch_vertices(m_edge1);

			// Second edge
			m_edge2 = (edge_t) sparse_matrix_get_key_at(m_graph->sparse_matrix,
					j, i, 0);
			edge_switch_vertices(m_edge2);

			// Swap operation
			sparse_matrix_set_key_at(m_graph->sparse_matrix, i, j, m_edge2);
			sparse_matrix_set_key_at(m_graph->sparse_matrix, j, i, m_edge1);
		}
	}
}

unsigned int graph_sparse_matrix_vertex_degree(void *graph, unsigned int vertex)
{
	int i, n, degree;
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;

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

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

	n = m_graph->size;
	degree = 0;
	for (i = 0; i < n; i++)
	{
		if (sparse_matrix_get_key_at(m_graph->sparse_matrix, vertex, i, 0))
			degree++;

		if (sparse_matrix_get_key_at(m_graph->sparse_matrix, i, vertex, 0))
			degree++;
	}

	return degree;
}

unsigned int graph_sparse_matrix_vertex_in_degree(void *graph,
		unsigned int vertex)
{
	int i, n, in_degree;
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;

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

	n = m_graph->size;
	in_degree = 0;
	for (i = 0; i < n; i++)
	{
		if (sparse_matrix_get_key_at(m_graph->sparse_matrix, i, vertex, 0))
			in_degree++;
	}

	return in_degree;
}

unsigned int graph_sparse_matrix_vertex_out_degree(void *graph,
		unsigned int vertex)
{
	int i, n, out_degree;
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;

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

	n = m_graph->size;
	out_degree = 0;
	for (i = 0; i < n; i++)
	{
		if (sparse_matrix_get_key_at(m_graph->sparse_matrix, vertex, i, 0))
			out_degree++;
	}

	return out_degree;
}

unsigned int graph_sparse_matrix_dimension(void *graph)
{
	int i, j, n, dimension;
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;

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

	n = m_graph->size;
	dimension = 0;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (sparse_matrix_get_key_at(m_graph->sparse_matrix, i, j, 0))
				dimension++;
		}
	}

	return dimension;
}

void graph_sparse_matrix_delete_vertex_edges(void *graph, unsigned int vertex,
		void(*edge_delete)(edge_t edge))
{
	int i, n;
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph;

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(vertex, >=, (unsigned int) m_graph->size, NULL_POINTER,);

	n = m_graph->size;
	for (i = 0; i < n; i++)
	{
		edge_delete(sparse_matrix_get_key_at(m_graph->sparse_matrix, i, vertex,
				0));
		sparse_matrix_set_key_at(m_graph->sparse_matrix, i, vertex, NULL);

		edge_delete(sparse_matrix_get_key_at(m_graph->sparse_matrix, vertex, i,
				0));
		sparse_matrix_set_key_at(m_graph->sparse_matrix, vertex, i, NULL);
	}
}

void graph_sparse_matrix_load(void *graph_src, void *graph_dest)
{
	graph_sparse_matrix_t m_graph_src = (graph_sparse_matrix_t) graph_src;
	graph_sparse_matrix_t m_graph_dest = (graph_sparse_matrix_t) graph_dest;
	int i, j, size;

	_ASSERT(graph_src, ==, NULL, NULL_POINTER,);
	_ASSERT(graph_dest, ==, NULL, NULL_POINTER,);
	_ASSERT(m_graph_src->size, != , m_graph_dest->size, INVALID_INPUT,);

	size = m_graph_src->size;
	for (i = 0; i < size; i++)
	{
		for (j = 0; j < size; j++)
			sparse_matrix_set_key_at(m_graph_dest->sparse_matrix, i, j,
					sparse_matrix_get_key_at(m_graph_src->sparse_matrix, i, j,
							0));
	}
}

void *graph_sparse_matrix_store(void *graph_src)
{
	graph_sparse_matrix_t m_graph = (graph_sparse_matrix_t) graph_src;
	graph_sparse_matrix_t m_clone;

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

	m_clone = (graph_sparse_matrix_t) _new(
			sizeof(struct _graph_sparse_matrix_t));
	m_clone->size = m_graph->size;
	m_clone->sparse_matrix = sparse_matrix_clone(m_graph->sparse_matrix);

	return m_clone;
}

void graph_sparse_matrix_debug(void *graph)
{
}

graph_implementation_t graph_sparse_matrix_get_implementation()
{
	static struct _graph_implementation_t
			_graph_adjacency_sparse_matrix_implementation;
	_graph_adjacency_sparse_matrix_implementation.new_g = graph_sparse_matrix_new;
	_graph_adjacency_sparse_matrix_implementation.delete_g
			= graph_sparse_matrix_delete;
	_graph_adjacency_sparse_matrix_implementation.resize
			= graph_sparse_matrix_resize;
	_graph_adjacency_sparse_matrix_implementation.add_edge
			= graph_sparse_matrix_add_edge;
	_graph_adjacency_sparse_matrix_implementation.remove_edge
			= graph_sparse_matrix_remove_edge;
	_graph_adjacency_sparse_matrix_implementation.get_edge
			= graph_sparse_matrix_get_edge;
	_graph_adjacency_sparse_matrix_implementation.first_vertex
			= graph_sparse_matrix_first_vertex;
	_graph_adjacency_sparse_matrix_implementation.delete_vertex_context
			= graph_sparse_matrix_delete_vertex_context;
	_graph_adjacency_sparse_matrix_implementation.next_vertex
			= graph_sparse_matrix_next_vertex;
	_graph_adjacency_sparse_matrix_implementation.first_edge
			= graph_sparse_matrix_first_edge;
	_graph_adjacency_sparse_matrix_implementation.delete_edge_context
			= graph_sparse_matrix_delete_edge_context;
	_graph_adjacency_sparse_matrix_implementation.next_edge
			= graph_sparse_matrix_next_edge;
	_graph_adjacency_sparse_matrix_implementation.iterate_edges
			= graph_sparse_matrix_iterate_edges;
	_graph_adjacency_sparse_matrix_implementation.transpose
			= graph_sparse_matrix_transpose;
	_graph_adjacency_sparse_matrix_implementation.vertex_degree
			= graph_sparse_matrix_vertex_degree;
	_graph_adjacency_sparse_matrix_implementation.vertex_in_degree
			= graph_sparse_matrix_vertex_in_degree;
	_graph_adjacency_sparse_matrix_implementation.vertex_out_degree
			= graph_sparse_matrix_vertex_out_degree;
	_graph_adjacency_sparse_matrix_implementation.dimension
			= graph_sparse_matrix_dimension;
	_graph_adjacency_sparse_matrix_implementation.delete_vertex_edges
			= graph_sparse_matrix_delete_vertex_edges;
	_graph_adjacency_sparse_matrix_implementation.load
			= graph_sparse_matrix_load;
	_graph_adjacency_sparse_matrix_implementation.store
			= graph_sparse_matrix_store;
	_graph_adjacency_sparse_matrix_implementation.debug
			= graph_sparse_matrix_debug;
	return &_graph_adjacency_sparse_matrix_implementation;
}