temelia/release/include/graph.h

/*!
 Temelia - Generic graph interface.
 This source file contains the implementation of the most known
 algorithms on graphs. Graph uses another layer consisting of the
 internal representation: adjacency matrix, adjacency list etc
 The representation can be user defined, see graph_matrix.h and
 graph_list.h for additional information.

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

 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_H_
#define GRAPH_H_

#include "common.h"
#include "vertex.h"
#include "edge.h"
#include "linked_list.h"
#include "vector.h"
#include "matrix.h"

/*!
 * @brief Common interface for graph implementation.
 * It contains pointers to functions; you may initialize
 * them with the values you want to hook in the library's
 * graph algorithms.
 *
 * Graph algorithms uses this interface to build generic
 * solution, instead of depending on the graph implementation.
 *
 * Temelia comes with two default implementations: adjacency matrix
 * and adjancency list. You can define your own implementation by
 * implementing the functions in this interface - look at
 * current solutions for details.
 *
 * The core concept is that at the upper layer I want to
 * work with unsigned int, instead of vertex_t; thus, the library
 * should automatically box/unbox unsigned int from/to vertex_t
 */
struct _graph_implementation_t
{
	// Returns an empty graph with given size
	void *(*new)(int size);

	// Frees the memory occupied by graph
	void (*delete)(void *graph);

	// Actualizes graph's size
	void (*resize)(void *graph, int size);

	/*!
	 * @brief Loads source graph into destination graph.
	 * The load operation should consists of edge references duplication.
	 * Notice that this operation does not require any memory allocation.
	 * @param Source graph
	 * @param Destination graph
	 */
	void (*load)(void *graph_src, void *graph_dest);

	/*!
	 * @brief Duplicates source graph and returns the clone. In a common example,
	 * the returned value, graph_dest, will be used to with load(graph_src, graph_dest).
	 * @param Source graph
	 */
	void *(*store)(void *graph_src);

	// Adds new edge to graph
	void (*add_edge)(void *graph, unsigned int vertex1, unsigned int vertex2,
			edge_t edge);

	// Removes edge from graph
	edge_t (*remove_edge)(void *graph, unsigned int vertex1,
			unsigned int vertex2);

	// Retrives the reference of edge from graph
	edge_t (*get_edge)(void *graph, unsigned int vertex1, unsigned int vertex2);

	// === [Start] Iterator over vertice's neighbors ===
	/*!
	 * @brief Returns the first neighbor vertex of given vertex in graph
	 * @param Graph implementation
	 * @param Vertex
	 * @param Pointer to context; here your implementation
	 * may save a context (what's the current vertex, other references etc)
	 */
	vertex_t (*first_vertex)(void *graph, unsigned int vertex, void **context);

	/*!
	 * @brief Deteles the allocated context for iterating on neighbors;
	 * you should call this function if you don't want full neighbors iterating.
	 * At the end of iterating, next_vertex returns NULL, this function is automatically
	 * called.
	 * @param Context
	 */
	void (*delete_vertex_context)(void **context);

	/*!
	 * @brief Returns the next neighbor vertex of given vertex in graph
	 * @param Graph implementation
	 * @param Vertex
	 * @param Pointer to context; information about the last visited
	 * neighbor should be here and it may be actualized
	 */
	vertex_t (*next_vertex)(void *graph, unsigned int vertex, void **context);
	// === [Stop] Iterator over vertice's neighbors ===

	// === [Start] Iterator over vertice's out edges ===
	/*!
	 * @brief Returns the first out edge of given vertex in graph
	 * @param Graph implementation
	 * @param Vertex
	 * @param Pointer to context; here your implementation
	 * may save a context (what's the current vertex, other references etc)
	 */
	edge_t (*first_edge)(void *graph, unsigned int vertex, void **context);

	/*!
	 * @brief Deteles the allocated context for iterating on neighbors;
	 * you should call this function if you don't want full neighbors iterating.
	 * At the end of iterating, next_vertex returns NULL, this function is automatically
	 * called.
	 * @param Context
	 */
	void (*delete_edge_context)(void **context);

	/*!
	 * @brief Returns the next out edge of given vertex in graph
	 * @param Graph implementation
	 * @param Vertex
	 * @param Pointer to context; information about the last visited
	 * neighbor should be here and it may be actualized
	 */
	edge_t (*next_edge)(void *graph, unsigned int vertex, void **context);
	// === [Stop] Iterator over out edge's ===

	/*!
	 * @brief Iterates over the edges of graph
	 * @param Graph
	 * @param Edge iterating function
	 * @param Iterating context
	 */
	void (*iterate_edges)(void *graph, void edge_handler(edge_t e,
			void *context), void *context);

	/*!
	 * @brief Transposes graph
	 * @param Graph
	 */
	void (*transpose)(void *graph);

	// == [Start] [Optimization] Optional functions ==
	/*!
	 * Generic graph implementation computes, the results of
	 * the following functions, if NULL pointers are in the structure.
	 * Saving non-NULL pointers in the structure makes the library
	 * call those functions, instead of the default implementation.
	 */
	/*!
	 * @brief Computes degree, in degree or out degree of a vertex
	 * in graph.
	 *
	 * in degree(u) = count{ v | (v, u) is an edge}
	 *
	 * out degree(u) = count{ v | (u, v) is an edge}
	 *
	 * degree = in degree + out degree
	 *
	 * @param Graph
	 * @param Vertex identifier
	 */
	unsigned int (*vertex_degree)(void *graph, unsigned int vertex);
	unsigned int (*vertex_in_degree)(void *graph, unsigned int vertex);
	unsigned int (*vertex_out_degree)(void *graph, unsigned int vertex);

	/*!
	 * @brief Computes the dimension of the graph - number of edges
	 * @param Graph
	 */
	unsigned int (*dimension)(void *graph);

	/*!
	 * @brief Removes and deletes all the edges containing vertex
	 * @param Graph
	 * @param Vertex identifier
	 * @param Edge destructor
	 */
	void (*delete_vertex_edges)(void *graph, unsigned int vertex,
			void(*edge_delete)(edge_t edge));
// == [Stop] [Optimization] Optional functions ==
};

typedef struct _graph_implementation_t *graph_implementation_t;

struct _graph_t;
typedef struct _graph_t *graph_t;

/*!
 * @brief Constructor - returns an empty graph_t with maximum size.
 * Complexity O(1)
 *
 * @param Maximum vertices number
 * @param Implementation layer
 * @param Vertex destructor; if you pass NULL then vertex_delete will
 * be used
 * @param Edge destructor; if you pass NULL then edge_delete will be
 * used
 */
DECLSPEC graph_t graph_new(unsigned int max, graph_implementation_t implementation,
		void(*m_vertex_delete)(vertex_t), void(*m_edge_delete)(edge_t));

/*!
 * @brief Frees the memory occupied by graph_t. Remember it only frees the pointers allocated
 * by the library, none of your pointers, please free them in order to avoid memory leaks.
 * Complexity O(V + E)
 *
 * @param Graph
 */
DECLSPEC void graph_delete(graph_t graph);

/*!
 * @brief Adds new vertex with a given label.
 * Complexity O(V)
 *
 * @param Graph
 * @param Vertex label
 * @param Key stored in the label
 * @return Vertex identifier. In the future, use this instead of vertex label
 */
DECLSPEC unsigned int graph_add_vertex(graph_t graph, char *label, void *key);

/*!
 * @brief Removes vertex from graph_t by giving it's identifier.
 * Complexity O(1)
 *
 * @param Graph
 * @param Vertex identifier
 * @return Pointer to removed vertex; it's your job to free the memory occupied
 * by the container and by it's content: label and key
 */
DECLSPEC vertex_t graph_remove_vertex(graph_t graph, unsigned int identifier);

/*!
 * @brief Verifies if vertex given by it's identifier is in graph.
 * Complexity O(1)
 *
 * @param Graph
 * @param Vertex identifier
 * @return 1 if it's in the graph_t and 0 if not; -1 if an error occurred.
 */
DECLSPEC int graph_is_vertex(graph_t graph, unsigned int identifier);

/*!
 * @brief Returns the vertex structure associated with identifier.
 * Complexity O(1)
 *
 * @param Graph
 * @param Vertex identifier
 */
DECLSPEC vertex_t graph_get_vertex(graph_t graph, unsigned int identifier);

/*!
 * @brief Adds an edge between two vertices given by their identifiers.
 * Complexity depends on the graph implementation; it may be O(V) or O(1)
 *
 * @param Graph
 * @param First vertex identifier
 * @param Second vertex identifier
 * @param Edge cost
 * @param Edge label
 * @param Key stored in edge
 */
DECLSPEC void graph_add_edge(graph_t graph, unsigned int vertex, unsigned int vertex2,
		double cost, char *label, void *key);

/*!
 * @brief Removes an edge from graph.
 * Complexity depends on the graph implementation; it may be O(V) or O(1)
 *
 * @param Graph
 * @param First vertex
 * @param Second vertex
 * @return Pointer to removed edge; it's you job the free the memory allocated for the edge,
 * and for it's content: label and key
 */
DECLSPEC edge_t graph_remove_edge(graph_t graph, unsigned int vertex1,
		unsigned int vertex2);

/*!
 * @brief Verifies if there is an edge between two vertices.
 * Complexity depends on the graph implementation; it may be O(V) or O(1)
 *
 * @param Graph
 * @param First vertex identifier
 * @param Second vertex identifier
 * @return 1 if there exists an edge between vertices, 0 if not or -1 if an error occurred
 */
DECLSPEC int graph_is_edge(graph_t graph, unsigned int vertex1, unsigned int vertex2);

/*!
 * @brief Returns the edge structure associated with pair of identifiers.
 * Complexity depends on the graph implementation; it may be O(1) or O(V)
 *
 * @param Graph
 * @param Vertex1 identifier
 * @param Vertex2 identifier
 */
DECLSPEC edge_t graph_get_edge(graph_t graph, unsigned int identifier1,
		unsigned int identifier2);

/*!
 * @brief Verifies is graph_t is empty: it contains 0 vertices.
 * Complexity O(1)
 *
 * @param Graph
 * @return 1 if it's empty, 0 if not or -1 an error occurred
 */
DECLSPEC int graph_is_empty(graph_t graph);

/*!
 * @brief Returns graph's size (order): number of nodes.
 * Complexity O(1)
 *
 * @param Graph
 */
DECLSPEC unsigned int graph_get_size(graph_t graph);

/*!
 * @brief Returns graph's dimension : number of edges.
 * Complexity depends on the graph implementation; it may be O(E) or O(V*V)
 *
 * @param Graph
 */
DECLSPEC unsigned int graph_get_dimension(graph_t graph);

/*!
 * @brief Returns the degree of vertex given by it's identifier.
 * Complex O(V)
 *
 * @param Graph
 * @param Vertex identifier
 * @return Number of neighbors
 */
DECLSPEC unsigned int graph_vertex_degree(graph_t graph, unsigned int identifier);

/*!
 * @brief Returns the out degree of vertex given by it's identifier.
 * Complexity O(V)
 *
 * @param Graph
 * @param Vertex identifier
 * @return Number of edges from vertex to it's neighbors
 */
DECLSPEC unsigned int graph_vertex_out_degree(graph_t graph, unsigned int identifier);

/*!
 * @brief Returns the in degree of vertex given by it's identifier.
 * Complexity O(V)
 *
 * @param Graph
 * @param Vertex identifier
 * @return Number of edges from neighbors to vertex
 */
DECLSPEC unsigned int graph_vertex_in_degree(graph_t graph, unsigned int identifier);

/*!
 * @brief Iterates over graph's vertices and call the callback function for each entity.
 * Complexity O(V)
 *
 * @param Graph
 * @param Iterating function
 * @param Iterating context
 */
DECLSPEC void graph_iterate_vertices(graph_t graph, void vertex_handler(vertex_t vertex,
		void *context), void *context);

/*!
 * @brief Iterates over graph's edges and call the callback function for each entity.
 * Complexity depends on the graph implementation; it may be O(E) or O(V*V).
 *
 * @param Graph
 * @param Iterating function
 * @param Iterating context
 */
DECLSPEC void graph_iterate_edges(graph_t graph, void edge_handler(edge_t edge,
		void *context), void *context);

/*!
 * @brief Transposes the graph.
 * Complexity depends on the graph implementation; in general,
 * it's O(V*V)
 *
 * @param Graph
 */
DECLSPEC void graph_transpose_graph(graph_t graph);

/*!
 * @brief Synchronization methods. Get and sets the value of current time.
 */
DECLSPEC void graph_set_current_time(unsigned int time);
DECLSPEC int graph_get_current_time();

/*!
 * @brief Checks if graph is undirected. User should know that his graph is directed or undirected
 * and should not access this function directly. It is used as an assert on algorithms applied
 * only to directed graphs, if the user wants this.
 * Complexity O(V*V)
 *
 * @param Graph
 */
DECLSPEC int graph_is_undirected(graph_t graph);

/*!
 * @brief Adjusts vertices parameters values by depth-first-search traveling this graph,
 * starting from start vertex, given by it's identifier. If the start vertex is -1
 * then the function does a complete DFS travel. The algorithm is picking nodes is lexicographic order, by
 * identifiers. The variable changing is the vector of vertices.
 * Complexity O(E) if vertex = -1 and O(V) is vertex is a valid identifier
 *
 * @param Graph
 * @param Start vertex
 */
DECLSPEC void graph_dfs(graph_t graph, unsigned int start_vertex_identifier);

/*!
 * @brief Adjusts vertices parameters values by breadth-first-search traveling this graph,
 * starting from start vertex, given by it's identifier. If the start vertex is -1
 * then the function does a complete DFS travel. The algorithm is picking nodes is lexicographic order, by
 * identifiers. The variable changing is the vector of vertices.
 * Complexity O(E) if vertex = -1 and O(V) is vertex is a valid identifier
 *
 * @param Graph
 * @param Start vertex
 */
DECLSPEC void graph_bfs(graph_t graph, unsigned int start_vertex_identifier);

/*!
 * @brief Classifies edges from DFS point of view.
 * Complexity O(E)
 *
 * @param Graph
 */
DECLSPEC void graph_dfs_edges_classification(graph_t graph);

/*!
 * @brief Classifies edges from BFS point of view.
 * Complexity O(E)
 *
 * @param Graph
 */
DECLSPEC void graph_bfs_edges_classification(graph_t graph);

/*!
 * @brief Reset vertices parameters to default values : unvisited, colored with white, not discovered,
 * travel not ended and parent nil (-1).
 * Complexity O(V)
 *
 * @param Graph
 */
DECLSPEC void graph_reset_vertices(graph_t graph);

/*!
 * @brief Checks if graph is bipartite : exists subgraphs A and B , A has nothing in common
 * with B, such that A U B = G. You should call this function with empty linked lists
 * as parameters because there is stored the result.
 * @param Graph
 * @param Pointer to first vertices set
 * @param Pointer to second vertices set
 * @return 0 if the graph_t is bipartite, 1 if not and -1 if an error occurred
 */
DECLSPEC int graph_bipartite(graph_t graph, linked_list_t first_set,
		linked_list_t second_set);

/*!
 * @brief Returns the diameter of graph.
 * @param Graph
 * @param Pointer to first node; here the function will store first node of diameter
 * @param Pointer to second node; here the function will store second node of diameter
 */
DECLSPEC unsigned int graph_diameter(graph_t graph, unsigned int *first_node,
		unsigned int *second_node);

/*!
 * @brief Calculates the articulation points.
 * @param Graph
 * @param Articulation points list
 */
DECLSPEC void
graph_articulation_points(graph_t graph, linked_list_t articulation_points);

/*!
 * @brief Computes the bridges from graph. Each key of bridges is a pair of unsigned int, unsigned int.
 * @param Graph
 * @param Bridges list
 */
DECLSPEC void graph_bridges(graph_t graph, linked_list_t bridges);

/*!
 * @brief Computes the biconex components from graph. Each key of biconex_components is a
 * linked list of unsigned int.
 * @param Graph
 * @param Biconex components list
 */
DECLSPEC void graph_biconex_components(graph_t graph, linked_list_t biconex_components);

/*!
 * @brief Finds the simple cycles from graph.
 * @param Graph
 * @param Cycles list; each key of list is a linked list containing vertices identifiers
 * as keys
 */
DECLSPEC void graph_cycles(graph_t graph, linked_list_t cycles);

/*!
 * @brief Finds the connected components from graph. Depends on the last parameter, the function
 * will check is the given graph is undirected. After the function finishes the vertices parameters
 * will be reseted, because it's doing DFS travels for each unvisited vertices.
 * @param Graph
 * @param Linked list, which will contain the connected components; a connected component
 * is a linked list with vertices' identifiers as keys
 * @param 1 if you want to check the graph it's undirected and 0 if you know this in advance;
 * pay attention, this function works correctly only for undirected graphs
 */
DECLSPEC void graph_connected_components(graph_t graph,
		linked_list_t connected_components, char check);

/*!
 * @brief Finds the strongly connected components from graph
 * @param Graph
 * @param Linked list which will contain the result
 * @see graph_connected_components
 */
DECLSPEC void graph_strongly_connected_components(graph_t graph,
		linked_list_t strongly_connected_components);

/*!
 * @brief Sorts in topological order the keys of graph
 * and returns a linked list containing vertices in sorted order.
 * Your graph should be acyclic and direct (DAG - direct acyclic graph)
 * @param Graph
 * @param Linked list which will store the result
 * @return 0 if graph can be sorted this way and -1 if not
 */
DECLSPEC char graph_topological_sort(graph_t graph, linked_list_t sort);

/*!
 * @brief Executes Dijkstra's algorithm for computing minimum distance vector of graph
 * @param Graph
 * @param Source vertex
 * @param Minimum distances vector
 * @param Parents vector
 */
DECLSPEC void graph_dijkstra(graph_t graph, unsigned int source, vector_t distances,
		vector_t parents);

/*!
 * @brief Executes Bellman-Ford algorithm for computing minimum distance vector of graph
 * @param Pointer to graph
 * @param Source vertex
 * @param Reference to minimum distances vector
 * @param Reference to parents vector
 * @return 1 if success, 0 if not and -1 if an error occurred, negative
 * cycle detected for example
 */
DECLSPEC int graph_bellman_ford(graph_t graph, unsigned int source, vector_t distances,
		vector_t parents);

/*!
 * @brief Executes Floyd-Warshall algorithm for computing minimum distance matrix of graph
 * @param Graph
 * @param Reference to minimum distances matrix. Each key should be a valid double *
 * @param Reference to parents matrix
 */
DECLSPEC void graph_floyd_warshall(graph_t graph, matrix_t distances, matrix_t parents);

/*!
 * @brief Executes Johnson algorithm for computing minimum distance matrix of graph
 * @param Graph
 * @param Minimum distances matrix
 * @param Parents matrix
 * @return 1 if success, 0 if not and -1 if an error occurred - negative
 * cycle detected for example
 */
DECLSPEC int graph_johnson(graph_t graph, matrix_t distances, matrix_t parents);

/*!
 * @brief Executes Prim's algorithm for computing minimum spanning tree of graph
 * @param Graph
 * @param Starting vertex
 * @param Minimum spanning tree. The function will store here a linked list
 * of edges (pair of vertices).
 * @return The cost of the minimum spanning tree - the sum of edges cost.
 */
DECLSPEC double graph_prim(graph_t graph, unsigned int start_vertex_identifier,
		linked_list_t minimum_spanning_tree);

/*!
 * @brief Executes Kruskal's algorithm for computing minimum spanning tree of graph.
 * Minimum spanning tree is a linked list of vertices identifiers, where two
 * consecutive vertices form an edge. For example u1, u2, u3 => [u1, u2], [u2, u3]
 * @see graph_prim for more details
 */
DECLSPEC double graph_kruskal(graph_t graph, unsigned int start_vertex_identifier,
		linked_list_t *minimum_spanning_tree);

/*!
 * @brief Executes Ford-Fulkerson algorithm for computing max-flow in graph
 * It uses DFS travel for exploring possible flow increasing paths.
 * @param Graph
 * @param Source vertex
 * @param Destination vertex
 * @param Flow matrix where the result is written; the matrix should have allocated double pointers
 * @return Maximum flow in graph between source and destination
 */
DECLSPEC double graph_ford_fulkerson(graph_t graph, unsigned int source,
		unsigned int destination, matrix_t max_flow);

/*!
 * @brief Executes Edmonds-Karp algorithm for computing max-flow in graph.
 * It uses BFS travel for exploring possible flow increasing paths
 * @param Graph
 * @param Source vertex
 * @param Destination vertex
 * @param Reference to flow matrix, where the result is written
 * @return Maximum flow in graph_t between source and destination
 */
DECLSPEC double graph_edmonds_karp(graph_t graph, unsigned int source,
		unsigned int destination, matrix_t max_flow);

#endif /* GRAPH_H_ */