#ifndef __UNDIGRAPH_H__ #define __UNDIGRAPH_H__ #include #include struct undigraph; typedef struct undigraph undigraph; undigraph *undigraph_create(); /** * Destroy a provided graph * * @param g a pointer to an undigraph, non NULL * * Expected runtime: O(V + E) */ void undigraph_destroy(undigraph *g); /** * Returns whether a vertex exists in the given graph * * @param g a pointer to an undigraph, non NULL * @param name the vertex in question * @return whether or not the vertex is present in g * * Expected runtime: O(1) */ bool undigraph_has_vertex(undigraph *g, char *name); /** * Returns whether an edge exists in the given graph * * @param g a pointer to an undigraph, non NULL * @param a the first vertex of the edge to be queried * @param b the second vertex of the edge to be queried * @return whether or not the edge is present in g * * Expected runtime: O(1) */ bool undigraph_has_edge(undigraph *g, char *a, char *b); /** * Adds an edge to a given graph. * * @param g a pointer to an undigraph, non NULL * @param a the first vertex of the edge to be added * @param b the second vertex of the edge to be added * @return whether or not the addition was succcessful * * If the edge a, b is already present in g, the return * value should be false. Vertices a and b may or may not * already be present in g, and vertex a may not be the same * as vertex b. * * Expected runtime: O(1) */ bool undigraph_add_edge(undigraph *g, char *a, char *b); /** * Returns the length of the shortest minimum path * between two vertices in the supplied graph. * * @param g a pointer to an undigraph, non NULL * @param start the first vertex of the query * @param target the second vertex of the query * @return the length of the shortest minimum path, or * 0 if there does not exist a path between the two vertices. * * The parameters start and target cannot be equal as determined by strcmp, and both start * and target are guaranteed to be present in the graph. * * Expected runtime: O(V + E) */ size_t undigraph_bfs_distance(undigraph *g, char *start, char *target); /** * Returns all common neighbors to two vertices in the supplied graph * * @param g a pointer to an undigraph, non NULL * @param a the first vertex of the query * @param b the second vertex of the query * @param count the number of neighbors common to both a and b, initialized to 0 by the caller * @param successful_query the truthiness of whether or not the query succeeded * without any memory issues, initialized to false by the caller * @return an array of pointers to unsorted names, each of which having been copied. * Ownership of these copied names and the containing array is transferred to the caller. * * Both a and b are guaranteed to be present in g. NULL is returned in two cases: * 1) there was an allocation error or 2) there are no common neighbors. * If NULL is returned and successful_query is false, a memory issue occurred. * If NULL is returned otherwise, no memory issue occurred. * * Expected runtime: O(D' * S' + D'' * S''), although it is a precondition that no string * may have length greater than 20, collapsing the bound to O(D' + D'') */ char **undigraph_common_neighbors(undigraph *g, char *a, char *b, size_t *count, bool *is_valid_query); #endif