This week /r/DailyProgrammer posed a series of challenges related to graph theory.
The first challenge gives you the number of vertices of an undirected graph and the graph’s edges. It asks you to find the degree of each vertex. The bonus challenge asks you to construct the adjacency matrix of the graph. I solved both problems, and I combined my solutions into one solution.
Each vertex i corresponds to a row in the adjacency matrix. For each column j in the matrix, if there is an edge between vertex i and vertex j, then the matrix entry i,j is equal to 1, and 0 otherwise. So, to find the number of edges for a vertex in an undirected graph, you can just construct the adjacency matrix and then sum all of the entries of the corresponding row.
The eccentricity of a vertex is the greatest distance from that vertex to any other vertex. So, to find the radius and the diameter of a graph, you can find the eccentricity of each vertex. Then the radius is the smallest eccentricity, and the diameter is the largest eccentricity.
Because I find the eccentricity of each vertex, I find the distances between all pairs of vertices in the graph. So, my first thought was to apply the Floyd-Warshall algorithm. However, one of the given graphs has a cycle, and I mistakenly believed that Floyd-Warshall only applies to directed acyclic graphs. So, instead of using Floyd-Warshall, I designed a solution around breadth-first search. When I discovered that Floyd-Warshall only fails on graphs that have negative cycles, I implemented a solution that employs Floyd-Warshall.
Even though the challenge is advertised as hard, I found it to be very easy. You can just recursively construct cliques and determine whether they are maximum. Although this is an exhaustive search, you can’t really solve the problem any faster than that, because the maximum clique problem is NP-complete. Fortunately, the size of the given problem instance is small enough for brute force to quickly yield a solution.