Graph Week

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.

My solution to both challenges is up at my GitHub.

The next challenge gives you the edges of a directed graph. It asks you to find the radius and the diameter of the graph.

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.

Here is my Floyd-Warshall solution. Here is my breadth-first search solution. Both are up at my GitHub.

The last challenge posed by /r/DailyProgrammer gives you the number of vertices in an undirected graph and the graph’s edges. It asks you to find a maximum clique in the graph.

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.

My solution to the last challenge is up at my GitHub.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s