ChompingTheBit

Another week of class, another week of algorithms. This week we covered some more complex topics about graph traversal, which is something I’m a little less familiar with.

One of the tasks we had was to implement a method for traversing a directed acyclic graph according to Khan’s algorithm. This was a new topic to me and presented a fun challenge as I worked to solve the problem.

While I was working on my solution, I had two main issues.

My first issue was a little embarrassing, because I hadn’t considered cases where vertexes and edges were not presorted. This was easy enough to fix, but it presented another issue of maintaining the order that were added to the queue to be visited.

My issue was that priority for vertexes with zero in-degrees was given to minimum values, without keeping track of the order that vertexes were decremented to have zero in-degrees.

To solve this problem, I combined the two methods that I had previously tried using to follow Khan’s algorithm.

I ended up using both a queue and a priority queue to implement a system of batching that kept track of which zero in-degree vertexes should be visited first. Using this batching system, the program was able to successfully visit vertexes according to the order they were made zero in-degree, as well as their numerical value.