temelia/src/graph_list.c

/*!
 Temelia - Linked list 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_list.h"
#include "include/linked_list.h"
#include "include/vector.h"
#include "include/pair.h"
#include <stdlib.h>

struct _graph_list_t
{
	int size;
	vector_t adjacency_list;
};

typedef struct _graph_list_t *graph_list_t;

void *graph_list_new(int size)
{
	graph_list_t graph;
	int i;

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

	graph = (graph_list_t) _new(sizeof(struct _graph_list_t));

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

	graph->size = size;
	graph->adjacency_list = vector_new(size);

	for (i = 0; i < size; i++)
		vector_push_back(graph->adjacency_list, linked_list_new());

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

	return graph;
}

void graph_list_delete(void *graph)
{
	graph_list_t m_graph = (graph_list_t) graph;
	int i;

	LOGGER("[graph list delete] graph %p, list %p\n", graph,
			m_graph->adjacency_list);

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

	for (i = 0; i < m_graph->size; i++)
		linked_list_delete(vector_get_key_at(m_graph->adjacency_list, i));

	vector_delete(m_graph->adjacency_list);
	_delete(m_graph);
}

void graph_list_resize(void *graph, int size)
{
	graph_list_t m_graph = (graph_list_t) graph;

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

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 0, INVALID_INPUT,);

	vector_set_size(m_graph->adjacency_list, size);
	m_graph->size = size;
}

static int _edge_compare_by_dest(void *key1, void *key2, void *context)
{
	edge_t key;
	unsigned int dest;

	// Choose non-NULL pointer between key1 and key2
	if (key1 == NULL)
		key = key2;
	else
		key = key1;

	dest = *(unsigned int *) context;

	if (vertex_get_identifier(edge_get_vertex2(key)) == dest)
		return 0;
	return -1;
}

void graph_list_add_edge(void *graph, unsigned int src, unsigned int dest,
		edge_t edge)
{
	graph_list_t m_graph = (graph_list_t) graph;
	linked_list_t m_list;

	LOGGER(
			"[graph list 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,);

	m_list = vector_get_key_at(m_graph->adjacency_list, src);

	if (linked_list_search_key(m_list, NULL, _edge_compare_by_dest, &dest)
			== NULL)
		linked_list_push_back(m_list, edge);
}

edge_t graph_list_remove_edge(void *graph, unsigned int vertex1,
		unsigned int vertex2)
{
	graph_list_t m_graph = (graph_list_t) graph;
	linked_list_t m_list;
	linked_list_iterator_t m_it;
	void *m_edge;

	LOGGER("[graph 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);

	m_list = vector_get_key_at(m_graph->adjacency_list, vertex1);
	m_it = linked_list_remove_key(m_list, NULL, _edge_compare_by_dest,
			&vertex2, 0);

	if (m_it == NULL)
		return NULL;

	m_edge = linked_list_iterator_get_key(m_it);
	linked_list_iterator_delete(m_it);
	return m_edge;
}

edge_t graph_list_get_edge(void *graph, unsigned int vertex1,
		unsigned int vertex2)
{
	graph_list_t m_graph = (graph_list_t) graph;
	linked_list_t m_list;
	linked_list_iterator_t m_it;

	LOGGER("[graph list get edge] graph %p, vertex1 %u, vertex2 %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);

	m_list = vector_get_key_at(m_graph->adjacency_list, vertex1);
	m_it
			= linked_list_search_key(m_list, NULL, _edge_compare_by_dest,
					&vertex2);

	if (m_it == NULL)
		return NULL;
	return linked_list_iterator_get_key(m_it);
}

vertex_t graph_list_first_vertex(void *graph, unsigned int vertex,
		void **context)
{
	graph_list_t m_graph = (graph_list_t) graph;
	linked_list_iterator_t it;

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

	it = linked_list_get_begin(vector_get_key_at(m_graph->adjacency_list,
			vertex));

	if (it == NULL)
	{
		*(linked_list_iterator_t *) context = NULL;
		return NULL;
	}

	*(linked_list_iterator_t *) context = linked_list_iterator_get_next(it);
	return edge_get_vertex2(linked_list_iterator_get_key(it));
}

void graph_list_delete_vertex_context(void **context)
{
}

vertex_t graph_list_next_vertex(void *graph, unsigned int vertex_id,
		void **context)
{
	linked_list_iterator_t *p_it = (linked_list_iterator_t *) context;
	linked_list_iterator_t it;
	vertex_t vertex;

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

	it = *p_it;
	if (it)
	{
		vertex = edge_get_vertex2(linked_list_iterator_get_key(it));
		it = linked_list_iterator_get_next(it);
		*(linked_list_iterator_t *) context = it;
		return vertex;
	}
	*(linked_list_iterator_t *) context = NULL;
	return NULL;
}

edge_t graph_list_first_edge(void *graph, unsigned int vertex, void **context)
{
	graph_list_t m_graph = (graph_list_t) graph;
	linked_list_iterator_t it;

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

	it = linked_list_get_begin(vector_get_key_at(m_graph->adjacency_list,
			vertex));

	if (it == NULL)
	{
		*(linked_list_iterator_t *) context = NULL;
		return NULL;
	}

	*(linked_list_iterator_t *) context = linked_list_iterator_get_next(it);
	return linked_list_iterator_get_key(it);
}

void graph_list_delete_edge_context(void **context)
{
}

edge_t graph_list_next_edge(void *graph, unsigned int vertex, void **context)
{
	linked_list_iterator_t *p_it = (linked_list_iterator_t *) context;
	linked_list_iterator_t it;
	edge_t edge;

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

	it = *p_it;
	if (it)
	{
		edge = linked_list_iterator_get_key(it);
		it = linked_list_iterator_get_next(it);
		*(linked_list_iterator_t *) context = it;
		return edge;
	}
	*(linked_list_iterator_t *) context = NULL;
	return NULL;
}

static void _iterate_vertex_key(void *key, void *context)
{
	edge_t edge = (edge_t) key;
	void(*iterate_handler)(vertex_t src, vertex_t dest, double cost,
			char *label, void *key, int type) =
			(void(*)(vertex_t src, vertex_t dest, double cost, char *label,
					void *key, int type)) context;

	iterate_handler(edge_get_vertex1(edge), edge_get_vertex2(edge),
			edge_get_cost(edge), edge_get_label(edge), edge_get_key(edge),
			edge_get_type(edge));
}

static void _iterate_vertex_list(void *key, void *context)
{
	linked_list_iterate(key, _iterate_vertex_key, context, -1);
}

void graph_list_iterate(void *graph, void(*iterate_handler)(vertex_t src,
		vertex_t dest, double cost, char *label, void *key, int type))
{
	graph_list_t m_graph = (graph_list_t) graph;

	LOGGER("[graph list iterate] graph %p, iterate handler %d\n", graph,
			iterate_handler);

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

	vector_iterate(m_graph->adjacency_list, _iterate_vertex_list,
			(void *) iterate_handler);
}

static void _iterate_edge_list(void *key, void *context)
{
	linked_list_t list;
	pair_t pair;

	list = (linked_list_t) key;
	pair = (pair_t) context;

	linked_list_iterate(list, pair_get_key(pair), pair_get_value(pair), -1);
}

void graph_list_iterate_edges(void *graph, void edge_handler(edge_t e,
		void *context), void *context)
{
	graph_list_t m_graph = (graph_list_t) graph;
	pair_t pair;

	LOGGER(
			"[graph list iterate edges] graph %p, edge handler %p, context %p\n",
			graph, edge_handler, context);

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

	pair = pair_new(edge_handler, context);

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

	vector_iterate(m_graph->adjacency_list, _iterate_edge_list, pair);
	pair_delete(pair);
}

void graph_list_transpose(void *graph)
{
	graph_list_t m_graph = (graph_list_t) graph;
	edge_t m_edge;
	vector_t adjacency_list;
	linked_list_t list;
	linked_list_iterator_t it;
	int i;

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

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

	// Initialize new adjacency matrix
	adjacency_list = vector_new(m_graph->size);
	for (i = 0; i < m_graph->size; i++)
		vector_push_back(adjacency_list, linked_list_new());

	for (i = 0; i < m_graph->size; i++)
	{
		list = vector_get_key_at(m_graph->adjacency_list, i);

		for (it = linked_list_get_begin(list); it != NULL; it
				= linked_list_iterator_get_next(it))
		{
			// Aggregate modified edges into auxiliary adjacency list
			m_edge = linked_list_iterator_get_key(it);
			edge_switch_vertices(m_edge);

			linked_list_push_back(vector_get_key_at(adjacency_list,
					vertex_get_identifier(edge_get_vertex1(m_edge))), m_edge);
		}
	}

	// Delete the old adjacency matrix
	for (i = 0; i < m_graph->size; i++)
		linked_list_delete(vector_get_key_at(m_graph->adjacency_list, i));
	vector_delete(m_graph->adjacency_list);

	m_graph->adjacency_list = adjacency_list;
}

unsigned int graph_list_vertex_degree(void *graph, unsigned int vertex)
{
	LOGGER("[graph list vertex degree] graph %p, vertex %u\n", graph, vertex);

	return graph_list_vertex_in_degree(graph, vertex)
			+ graph_list_vertex_out_degree(graph, vertex);
}

unsigned int _vertex_in_degree(linked_list_t list, unsigned int vertex)
{
	linked_list_iterator_t m_it;
	edge_t m_edge;
	unsigned int in_degree;

	_ASSERT(list, ==, NULL, NULL_POINTER, 0);

	m_it = linked_list_get_begin(list);
	in_degree = 0;

	while (m_it)
	{
		m_edge = linked_list_iterator_get_key(m_it);
		if (vertex_get_identifier(edge_get_vertex2(m_edge)) == vertex)
			in_degree++;
		m_it = linked_list_iterator_get_next(m_it);
	}
	return in_degree;
}

unsigned int graph_list_vertex_in_degree(void *graph, unsigned int vertex)
{
	int i;
	unsigned int in_degree;
	graph_list_t m_graph = (graph_list_t) graph;

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

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(vertex, >=, m_graph->size, INVALID_INPUT, -1);

	in_degree = 0;
	for (i = 0; i < m_graph->size; i++)
	{
		if (i != vertex)
			in_degree += _vertex_in_degree(vector_get_key_at(
					m_graph->adjacency_list, i), vertex);
	}
	return in_degree;
}

unsigned int graph_list_vertex_out_degree(void *graph, unsigned int vertex)
{
	graph_list_t m_graph = (graph_list_t) graph;

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

	_ASSERT(graph, ==, NULL, NULL_POINTER, -1);
	_ASSERT(vertex, >=, m_graph->size, INVALID_INPUT, -1);

	return linked_list_get_size(vector_get_key_at(m_graph->adjacency_list,
			vertex));
}

unsigned int graph_list_dimension(void *graph)
{
	int i, size;
	unsigned int dimension;
	linked_list_t list;
	graph_list_t m_graph = (graph_list_t) graph;

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

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

	dimension = 0;
	size = vector_get_size(m_graph->adjacency_list);
	for (i = 0; i < size; i++)
	{
		list = vector_get_key_at(m_graph->adjacency_list, i);
		dimension += linked_list_get_size(list);
	}

	return dimension;
}

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

void graph_list_delete_vertex_edges(void *graph, unsigned int vertex,
		void(*edge_delete)(edge_t edge))
{
	linked_list_t m_list;
	linked_list_iterator_t it;
	graph_list_t m_graph = (graph_list_t) graph;
	int i;

	LOGGER(
			"[graph list delete vertex edges] graph %p, vertex %u, edge delete %p\n",
			graph, vertex, edge_delete);

	_ASSERT(graph, ==, NULL, NULL_POINTER,);
	_ASSERT(vertex, >=, m_graph->size, INVALID_INPUT,);
	_ASSERT(edge_delete, ==, NULL, NULL_POINTER,);

	m_list = vector_get_key_at(m_graph->adjacency_list, vertex);

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

	linked_list_iterate(m_list, _delete_vertex_edges, edge_delete, 1);
	linked_list_delete(m_list);
	vector_set_key_at(m_graph->adjacency_list, vertex, linked_list_new());

	for (i = 0; i < m_graph->size; i++)
	{
		if (i != vertex)
		{
			m_list = vector_get_key_at(m_graph->adjacency_list, i);
			it = linked_list_remove_key(m_list, NULL, _edge_compare_by_dest,
					&vertex, 0);
			edge_delete(linked_list_iterator_get_key(it));
			linked_list_iterator_delete(it);
		}
	}
}

void graph_list_load(void *graph_src, void *graph_dest)
{
	graph_list_t m_graph_src = (graph_list_t) graph_src;
	graph_list_t m_graph_dest = (graph_list_t) graph_dest;
	linked_list_t list_src, list_dest;
	linked_list_iterator_t it_src, it_dest;
	int i, 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++)
	{
		list_src = vector_get_key_at(m_graph_src->adjacency_list, i);
		it_src = linked_list_get_begin(list_src);

		list_dest = vector_get_key_at(m_graph_dest->adjacency_list, i);
		it_dest = linked_list_get_back(list_dest);

		while (it_src)
		{
			linked_list_iterator_set_key(it_dest, linked_list_iterator_get_key(
					it_src));
			it_src = linked_list_iterator_get_next(it_src);
		}
	}
}

static void *_store_linked_list_clone(void *key, void *context)
{
	return linked_list_clone(key, NULL, NULL);
}

void *graph_list_store(void *graph_src)
{
	graph_list_t m_graph = (graph_list_t) graph_src;
	graph_list_t m_clone;

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

	m_clone = (graph_list_t) _new(sizeof(struct _graph_list_t));
	m_clone->size = m_graph->size;
	m_clone->adjacency_list = vector_clone(m_graph->adjacency_list,
			_store_linked_list_clone, NULL);

	return m_clone;
}

void graph_list_debug(void *graph)
{
	graph_list_t m_graph = (graph_list_t) graph;
	linked_list_t list;
	linked_list_iterator_t it;
	int i, n;

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

	n = m_graph->size;

	for (i = 0; i < n; i++)
	{
		list = vector_get_key_at(m_graph->adjacency_list, i);
		it = linked_list_get_begin(list);

		while (1)
		{
			if (it == NULL)
				break;
			edge_debug(linked_list_iterator_get_key(it), NULL);
			it = linked_list_iterator_get_next(it);
		}
	}
}

graph_implementation_t graph_list_get_implementation()
{
	static struct _graph_implementation_t _graph_adjacency_list_implementation;
	_graph_adjacency_list_implementation.new_g = graph_list_new;
	_graph_adjacency_list_implementation.delete_g = graph_list_delete;
	_graph_adjacency_list_implementation.resize = graph_list_resize;
	_graph_adjacency_list_implementation.add_edge = graph_list_add_edge;
	_graph_adjacency_list_implementation.remove_edge = graph_list_remove_edge;
	_graph_adjacency_list_implementation.get_edge = graph_list_get_edge;
	_graph_adjacency_list_implementation.first_vertex = graph_list_first_vertex;
	_graph_adjacency_list_implementation.delete_vertex_context
			= graph_list_delete_vertex_context;
	_graph_adjacency_list_implementation.next_vertex = graph_list_next_vertex;
	_graph_adjacency_list_implementation.first_edge = graph_list_first_edge;
	_graph_adjacency_list_implementation.delete_edge_context
			= graph_list_delete_edge_context;
	_graph_adjacency_list_implementation.next_edge = graph_list_next_edge;
	_graph_adjacency_list_implementation.iterate_edges
			= graph_list_iterate_edges;
	_graph_adjacency_list_implementation.transpose = graph_list_transpose;
	_graph_adjacency_list_implementation.vertex_degree
			= graph_list_vertex_degree;
	_graph_adjacency_list_implementation.vertex_in_degree
			= graph_list_vertex_in_degree;
	_graph_adjacency_list_implementation.vertex_out_degree
			= graph_list_vertex_out_degree;
	_graph_adjacency_list_implementation.dimension = graph_list_dimension;
	_graph_adjacency_list_implementation.delete_vertex_edges
			= graph_list_delete_vertex_edges;
	_graph_adjacency_list_implementation.load = graph_list_load;
	_graph_adjacency_list_implementation.store = graph_list_store;
	_graph_adjacency_list_implementation.debug = graph_list_debug;
	return &_graph_adjacency_list_implementation;
}