temelia/release/include/graph_matrix.h

/*!
 Temelia - Graph interface implementation with adjacency matrix

 Copyright (C) 2008, 2009 Ceata (http://cod.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.
 */

#ifndef GRAPH_MATRIX_H_
#define GRAPH_MATRIX_H_

#include "platform.h"
#include "vertex.h"
#include "edge.h"

/*!
 * @brief Singleton containing structure filled with corresponding
 * pointers to functions.
 */
DECLSPEC graph_implementation_t graph_matrix_get_implementation();

/*!
 * @brief Returns new empty graph represented with adjacency matrix.
 * @param Number of vertices
 */
DECLSPEC void *graph_matrix_new(int size);

/*!
 * @brief Frees the memory occupied by this graph representation.
 * Complexity O(1)
 *
 * @param Graph representation reference
 */
DECLSPEC void graph_matrix_delete(void *graph);

/*!
 * @brief Resizes current graph representation to new size.
 * Complexity O(V * V)
 *
 * @param Graph representation reference
 * @param New size - should be greater than current size
 */
DECLSPEC void graph_matrix_resize(void *graph, int size);

/*!
 * @brief Adds new edge to adjacency matrix; edge is identified
 * by vertices and attributes.
 * Complexity O(1)
 *
 * @param Graph representation reference
 * @param Edge
 */
DECLSPEC void graph_matrix_add_edge(void *graph, unsigned int src, unsigned int dest,
		edge_t edge);

/*!
 * @brief Removes an edge identified by vertices and returns
 * the reference.
 * Complexity O(1)
 *
 * @param Graph representation reference
 * @param Vertex 1
 * @param Vertex 2
 * @return Edge between vertex 1 and vertex 2
 */
DECLSPEC edge_t graph_matrix_remove_edge(void *graph, unsigned int vertex1,
		unsigned int vertex2);

/*
 * @see graph_matrix_remove_edge
 */
DECLSPEC edge_t graph_matrix_get_edge(void *graph, unsigned int vertex1,
		unsigned int vertex2);

/*!
 * @brief Returns the first neighbor vertex of given vertex.
 * Context is set up because of the iteration property.
 * Complexity O(V)
 *
 * @param Graph representation reference
 * @param Vertex
 * @param Context reference, where iteration information is stored.
 * In this implementation, you must pass a valid (unsigned int *)
 */
DECLSPEC vertex_t graph_matrix_first_vertex(void *graph, unsigned int vertex,
		void **context);

/*!
 * @brief Deletes allocated context for iterating, by graph_matrix_first_vertex.
 * Notice that it is automatically called when the iterating process is over
 *
 * @param Context
 */
DECLSPEC void graph_matrix_delete_vertex_context(void **context);

/*!
 * @brief Returns the next neighbor vertex of given vertex.
 * Context is used to find out the last visited neighbor.
 * Complexity O(V)
 *
 * @param Graph representation reference
 * @param Vertex
 * @param Context reference, where iteration information is stored.
 */
DECLSPEC vertex_t graph_matrix_next_vertex(void *graph, unsigned int vertex,
		void **context);

/*!
 * @brief Returns the first edge with a neighbor vertex of given vertex.
 * Context is set up because of the iteration property.
 * Complexity O(V)
 *
 * @param Graph representation reference
 * @param Vertex
 * @param Context reference, where iteration information is stored.
 * In this implementation, you must pass a valid (unsigned int *)
 */
DECLSPEC edge_t graph_matrix_first_edge(void *graph, unsigned int vertex, void **context);

/*!
 * @brief Deletes allocated context for iterating, by graph_matrix_first_edge.
 * Notice that it is automatically called when the iterating process is over
 *
 * @param Context
 */
DECLSPEC void graph_matrix_delete_edge_context(void **context);

/*!
 * @brief Returns the edge to the next neighbor.
 * Context is used to find out the last visited edge.
 * Complexity O(V)
 *
 * @param Graph representation reference
 * @param Vertex
 * @param Context reference, where iteration information is stored.
 */
DECLSPEC edge_t graph_matrix_next_edge(void *graph, unsigned int vertex,
		void **context);

/*!
 * @brief Iterates over the edges of current graph and calls
 * the callback function for-each record.
 *
 * Complexity O(V*V)
 *
 * If you want to pretty debug the graph, then see the examples
 * in temelia_samples. Basically, it uses a static variable to
 * count current edge id and when id is equal to the number of vertices
 * it emits a newline and resets id to 0.
 *
 * @param Graph
 * @param Iterating callback function
 */
DECLSPEC void graph_matrix_iterate(void *graph, void(*iterate)(vertex_t src,
		vertex_t dest, double cost, char *label, void *key, char type));

/*!
 * @brief Iterates over the edge of graph.
 * Complexity O(V*V)
 *
 * @see graph_matrix_iterate
 */
DECLSPEC void graph_matrix_iterate_edges(void *graph, void edge_handler(edge_t e,
		void *context), void *context);

/*!
 * @brief Transposes graph.
 * Complexity O(V*V)
 *
 * @param Graph
 */
DECLSPEC void graph_matrix_transpose(void *graph);

/*!
 * @brief Computes degree, in degree and out degree of graph.
 * Complexity O(V)
 *
 * @param Graph
 * @param Vertex identifier
 */
DECLSPEC unsigned int graph_matrix_vertex_degree(void *graph, unsigned int vertex);
DECLSPEC unsigned int graph_matrix_vertex_in_degree(void *graph, unsigned int vertex);
DECLSPEC unsigned int graph_matrix_vertex_out_degree(void *graph, unsigned int vertex);

/*!
 * @brief Computes graph's dimension - number of edges.
 * Complexity O(V*V)
 *
 * @param Graph
 */
DECLSPEC unsigned int graph_matrix_dimension(void *graph);

/*!
 * @brief Removes and deletes the edges from/in vertex.
 * Complexity O(V)
 *
 * @param Graph
 * @param Vertex identifier
 * @param Edge destructor
 */
DECLSPEC void graph_matrix_delete_vertex_edges(void *graph, unsigned int vertex,
		void(*edge_delete)(edge_t edge));

#endif /* GRAPH_MATRIX_H_ */