My Summer of Code 2021
Welcome! This post is not going to be discussing technical implementation details or theortical work for my Google Summer of Code project, but rather serve as a summary and recap for the work that I did this summer. I am very happy with the work I was able to accomplish and believe that I successfully completed my project. Overview My project was titled NetworkX: Implementing the Asadpour Asymmetric Traveling Salesman Problem Algorithm.
Completing the Asadpour Algorithm
My implementation of asadpour_atsp is now working! Recall that my pseudo code for this function from my last post was def asadpour_tsp Input: A complete graph G with weight being the attribute key for the edge weights. Output: A list of edges which form the approximate ATSP solution. z_star = held_karp(G) # test to see if z_star is a graph or dict if type(z_star) is nx.DiGraph return z_star.edges z_support = nx.
GSoC Coding Phase 3 Blog 1
Google Summer of Code 2020’s second evaluation is completed. I passed!!! Hurray! Now we are in the mid way of the last evaluation. This post discusses about the progress so far in the first two weeks of the third coding period from 26 July to 9 August 2020. Completion of the modification logic for the matplotlib_baseline_images package We successfully created the matplotlib_baseline_image_generation command line flag for baseline image generation for matplotlib and mpl_toolkits in the previous months.
Looking at the Big Picture
Well, we’re finally at the point in this GSoC project where the end is glimmering on the horizon. I have completed the Held Karp relaxation, generating a spanning tree distribution and now sampling from that distribution. That means that it is time to start thinking about how to link these separate components into one algorithm. Recall that from the Asadpour paper the overview of the algorithm is Algorithm 1 An \(O(\log n / \log \log n)\)-approximation algorithm for the ATSP
Sampling a Spanning Tree
The heavy lifting I did in the preliminary post certainly paid off here! In just one day I was able to implement sample_spanning_tree and its two helper functions. krichhoffs This was a very easy function to implement. It followed exactly from the pesudo code and was working with spanning_tree_distribution before I started on sample_spanning_tree. sample_spanning_tree This function was more difficult than I originally anticipated. The code for the main body of the function only needed minor tweaks to work with the specifics of python such as shuffle being in place and returning None and some details about how sets work.
GSoC Coding Phase 2 Blog 2
Google Summer of Code 2020’s second evaluation is about to complete. Now we are about to start with the final coding phase. This post discusses about the progress so far in the last two weeks of the second coding period from 13 July to 26 July 2020. Modular approach towards removal of matplotlib baseline images We have divided the work in two parts as discussed in the previous blog. The first part is the generation of the baseline images discussed below.
Preliminaries for Sampling a Spanning Tree
In order to test the exponential distribution that I generate using spanning_tree_distribution, I need to be able to sample a tree from the distribution. The primary citation used in the Asadpour paper is Generating Random Combinatorial Objects by V. G. Kulkarni (1989). While I was not able to find an online copy of this article, the Michigan Tech library did have a copy that I was able to read. Does the Kulkarni Algorithm work with Asadpour?
The Entropy Distribution
Implementing spanning_tree_distribution proved to have some NetworkX difficulties and one algorithmic difficulty. Recall that the algorithm for creating the distribution is given in the Asadpour paper as Set \(\gamma = \vec{0}\). While there exists an edge \(e\) with \(q_e(\gamma) > (1 + \epsilon) z_e\): Compute \(\delta\) such that if we define \(\gamma’\) as \(\gamma_e’ = \gamma_e - \delta\), and \(\gamma_f’ = \gamma_f\) for all \(f \in E\ \backslash {e}\), then \(q_e(\gamma’) = (1 + \epsilon/2)z_e\).
Elementary Cellular Automata
Cellular automata are discrete models, typically on a grid, which evolve in time. Each grid cell has a finite state, such as 0 or 1, which is updated based on a certain set of rules. A specific cell uses information of the surrounding cells, called it’s neighborhood, to determine what changes should be made. In general cellular automata can be defined in any number of dimensions. A famous two dimensional example is Conway’s Game of Life in which cells “live” and “die”, sometimes producing beautiful patterns.
Entropy Distribution Setup
Finally moving on from the Held Karp relaxation, we arrive at the second step of the Asadpour asymmetric traveling salesman problem algorithm. Referencing the Algorithm 1 from the Asadpour paper, we are now finally on step two. Algorithm 1 An \(O(\log n / \log \log n)\)-approximation algorithm for the ATSP Input: A set \(V\) consisting of \(n\) points and a cost function \(c\ :\ V \times V \rightarrow \mathbb{R}^+\) satisfying the triangle inequality.