#ifndef __LUGRAPH_H__ #define __LUGRAPH_H__ #include typedef struct lugraph lugraph; typedef struct lug_search lug_search; /** * Creates a new undirected graph with the given number of vertices. The * vertices will be numbered 0, ..., n-1. * * @param n a nonnegative integer * @return a pointer to the new graph */ lugraph *lugraph_create(int n); /** * Returns the number of vertices in the given graph. * * @param g a pointer to an undirected graph, non-NULL * @return the number of vertices in that graph */ int lugraph_size(const lugraph *g); /** * Adds an undirected edge between the given pair of vertices to * the given undirected graph. The behavior is undefined if the edge * already exists. * * @param g a pointer to an undirected graph, non-NULL * @param v1 the index of a vertex in the given graph * @param v2 the index of a vertex in the given graph, not equal to from */ void lugraph_add_edge(lugraph *g, int v1, int v2); /** * Determines if the given undirected graph contains an edge between * the given vertices. * * @param g a pointer to an undirected graph, non-NULL * @param v1 the index of a vertex in the given graph * @param v2 the index of a vertex in the given graph, not equal to from * @return true if and only if the edge exists */ bool lugraph_has_edge(const lugraph *g, int v1, int v2); /** * Returns the degree of the given vertex in the given graph. * * @param g a pointer to an undirected graph, non-NULL * @param v the index of a vertex in the given graph * @return the degree of v */ int lugraph_degree(const lugraph *g, int v); /** * Returns the result of running breadth-first search on the given * graph starting with the given vertex. When the search arrives * at a vertex, its neighbors are considered in the order the * corresponding edges were added to the graph. The result is returned * as a pointer to a lug_search that must subsequently be passed to * lugraph_search_destroy. * * @param g a pointer to an undirected graph, non-NULL * @param from the index of a vertex in the given graph * @return a pointer to the result of the search */ lug_search *lugraph_bfs(const lugraph *g, int from); /** * Determines if the two given vertices are connected by some path * in the given graph. * * @param g a pointer to an undirected graph, non-NULL * @param v1 the index of a vertex in the given graph * @param v2 the index of a vertex in the given graph * @return true if the two vertices are connected in the graph, false otherwise */ bool lugraph_connected(const lugraph *g, int v1, int v2); /** * Destroys the given undirected graph. * * @param g a pointer to a undirected graph, non-NULL */ void lugraph_destroy(lugraph *g); /** * Returns the path from the staring point of the given search to the * given vertex. The returned path starts with the origin of the * search and ends with the to vertex. If no such path exists then * the return value is NULL and the length is -1. The integer pointed * to by len is set to the length of (number of edges on) the path. * It is the caller's responsibility to free the returned array. * * @param s a pointer to a search result, non-NULL * @param to a vertex in the graph the search was performed in * @param len a pointer to an int, non-NULL * @return an array containing the vertices on the path, or NULL if there * is no such path */ int *lug_search_path(const lug_search *s, int to, int *len); /** * Returns the distance from the source to the given vertex after the * given search. If the vertex was not reached then then return value is * -1. * * @param s a pointer to a search result, non-NULL * @param to a vertex in the graph the search was performed in * @return the distance from the source of the search to that vertex, or -1 */ int lug_search_distance(const lug_search *s, int to); /** * Destroys the given search result. * * @param s a pointer to a search result, non-NULL */ void lug_search_destroy(lug_search *s); #endif