Posts with #GSoC

The VF2++ algorithm
The last and final post discussing the VF2++ helpers can be found here. Now that we’ve figured out how to solve all the sub-problems that VF2++ consists of, we are ready to combine our implemented functionalities to create the final solver for the Graph Isomorphism problem. Introduction We should quickly review the individual functionalities used in the VF2++ algorithm: Node ordering which finds the optimal order to access the nodes, such that those that are more likely to match are placed first in the order.
ISO Feasibility & Candidates
The previous post can be found here, be sure to check it out so you can follow the process step by step. Since then, another two very significant features of the algorithm have been implemented and tested: node pair candidate selection and feasibility checks. Introduction As previously described, in the ISO problem we are basically trying to create a mapping such that, every node from the first graph is matched to a node from the second graph.
Updates on VF2++
This post includes all the major updates since the last post about VF2++. Each section is dedicated to a different sub-problem and presents the progress on it so far. General progress, milestones and related issues can be found here. Node ordering The node ordering is one major modification that VF2++ proposes. Basically, the nodes are examined in an order that makes the matching faster by first examining nodes that are more likely to match.
GSoC 2022: NetworkX VF2++ Implementation
Intro I got accepted as a GSoC contributor, and I am so excited to spend the summer working on such an incredibly interesting project. The mentors are very welcoming, communicative, fun to be around, and I really look forward to collaborating with them. My application for GSoC 2022 can be found here. About me My name is Konstantinos Petridis, and I am an Electrical Engineering student at the Aristotle University of Thessaloniki.
GSoC'21: Final Report
Matplotlib: Revisiting Text/Font Handling To kick things off for the final report, here’s a meme to nudge about the previous blogs. About Matplotlib Matplotlib is a comprehensive library for creating static, animated, and interactive visualizations, which has become a de-facto Python plotting library. Much of the implementation behind its font manager is inspired by W3C compliant algorithms, allowing users to interact with font properties like font-size, font-weight, font-family, etc. However, the way Matplotlib handled fonts and general text layout was not ideal, which is what Summer 2021 was all about.
GSoC'21: Quarter Progress
“Matplotlib, I want 多个汉字 in between my text.” Let’s say you asked Matplotlib to render a plot with some label containing 多个汉字 (multiple Chinese characters) in between your English text. Or conversely, let’s say you use a Chinese font with Matplotlib, but you had English text in between (which is quite common). Assumption: the Chinese font doesn’t have those English glyphs, and vice versa With this short writeup, I’ll talk about how does a migration from a font-first to a text-first approach in Matplotlib looks like, which ideally solves the above problem.
GSoC'21: Pre-Quarter Progress
“Well? Did you get it working?!” Before I answer that question, if you’re missing the context, check out my previous blog’s last few lines.. promise it won’t take you more than 30 seconds to get the whole problem! With this short writeup, I intend to talk about what we did and why we did, what we did. XD Ostrich Algorithm Ring any bells? Remember OS (Operating Systems)? It’s one of the core CS subjects which I bunked then and regret now.
GSoC'21: Mid-Term Progress
"Aitik, how is your GSoC going?" Well, it’s been a while since I last wrote. But I wasn’t spending time watching Loki either! (that’s a lie.) During this period the project took on some interesting (and stressful) curves, which I intend to talk about in this small writeup. New Mentor! The first week of coding period, and I met one of my new mentors, Jouni. Without him, along with Tom and Antony, the project wouldn’t have moved an inch.
Aitik Gupta joins as a Student Developer under GSoC'21
The day of result, was a very, very long day. With this small writeup, I intend to talk about everything before that day, my experiences, my journey, and the role of Matplotlib throughout! About Me I am a third-year undergraduate student currently pursuing a Dual Degree (B.Tech + M.Tech) in Information Technology at Indian Institute of Information Technology, Gwalior. During my sophomore year, my interests started expanding in the domain of Machine Learning, where I learnt about various amazing open-source libraries like NumPy, SciPy, pandas, and Matplotlib!
GSoC 2020 Work Product - Baseline Images Problem
Google Summer of Code 2020 is completed. Hurray!! This post discusses about the progress so far in the three months of the coding period from 1 June to 24 August 2020 regarding the project Baseline Images Problem under matplotlib organisation under the umbrella of NumFOCUS organization. Project Details: This project helps with the difficulty in adding/modifying tests which require a baseline image. Baseline images are problematic because Baseline images cause the repo size to grow rather quickly.
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\).
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.
GSoC Coding Phase 2 Blog 1
Google Summer of Code 2020’s first evaluation is completed. I passed!!! Hurray! Now we are in the mid way of the second evaluation. This post discusses about the progress so far in the first two weeks of the second coding period from 30 June to 12 July 2020. Completion of the matplotlib_baseline_images package We successfully created the matplotlib_baseline_images package. It contains the matplotlib and the matplotlib toolkit baseline images. Symlinking is done for the baseline images, related changes for Travis, appvoyer, azure pipelines etc.
Finalizing the Held-Karp Relaxation
This should be my final post about the Held-Karp relaxation! Since my last post titled Implementing The Held Karp Relaxation, I have been testing both the ascent method as well as the branch and bound method. My first test was to use a truly asymmetric graph rather than a directed graph where the cost in each direction happened to be the same. In order to create such a test, I needed to know the solution to any such proposed graphs.
Implementing the Held-Karp Relaxation
I have now completed my implementation of the ascent and the branch and bound method detailed in the 1970 paper The Traveling-Salesman Problem and Minimum Spanning Trees by Micheal Held and Richard M. Karp. In my last post, titled Understanding the Ascent Method, I completed the first iteration of the ascent method and found an important bug in the find_epsilon() method and found a more efficient way to determine substitutes in the graph.
GSoC Coding Phase 1 Blog 2
Google Summer of Code 2020’s first evaluation is about to complete. This post discusses about the progress so far in the last two weeks of the first coding period from 15 June to 30 June 2020. Completion of the demo package We successfully created the demo app and uploaded it to the test.pypi. It contains the main and the secondary package. The main package is analogous to the matplotlib and secondary package is analogous to the matplotlib_baseline_images package as discussed in the previous blog.
Understanding the Ascent Method
It has been far longer than I would have preferred since I wrote a blog post. As I expected in my original GSoC proposal, the Held-Karp relaxation is proving to be quite difficult to implement. My mentors and I agreed that the branch and bound method discussed in Held and Karp’s 1970 paper The Traveling-Salesman Problem and Minimum Spanning Trees which first required the implementation of the ascent method because it is used in the branch and bound method.
implementing the Iterators
We are coming into the end of the first week of coding for the Summer of Code, and I have implemented two new, but related, features in NetworkX. In this post, I will discuss how I implemented them, some of the challenges and how I tested them. Those two new features are a spanning tree iterator and a spanning arborescence iterator. The arborescence iterator is the feature that I will be using directly in my GSoC project, but I though that it was a good idea to implement the spanning tree iterator first as it would be easier and I could directly refer back to the research paper as needed.
GSoC Coding Phase 1 Blog 1
I Sidharth Bansal, was waiting for the coding period to start from the March end so that I can make my hands dirty with the code. Finally, coding period has started. Two weeks have passed. This blog contains information about the progress so far from 1 June to 14 June 2020. Movement from mpl-test and mpl packages to mpl and mpl-baseline-images packages Initially, we thought of creating a mpl-test and mpl package.
Finding all Minimum Arborescences
There is only one thing that I need to figure out before the first coding period for GSoC starts on Monday: how to find all of the minimum arborescences of a graph. This is the set \(K(\pi)\) in the Held and Karp paper from 1970 which can be refined down to \(K(\pi, d)\) or \(K_{X, Y}(\pi)\) as needed. For more information as to why I need to do this, please see my last post here.
A Closer Look at the Held-Karp Relaxation
After talking with my GSoC mentors about what we all believe to be the most difficult part of the Asadpour algorithm, the Held-Karp relaxation, we came to several conclusions: The Asadpour paper recommends using the ellipsoid method so that their algorithm runs in polynomial time. We do not need a polynomial time, just an algorithm with reasonable execution time. An example of this would be the ellipsoid algorithm versus the simplex algorithm.
NetworkX Function Stubs
Now that my porposal was accepted by NetworkX for the 2021 Google Summer of Code (GSoC), I can get more into the technical details of how I plan to implement the Asadpour algorithm within NetworkX. In this post I am going to outline my thought process for the control scheme of my implementation and create function stubs according to my GSoC proposal. Most of the work for this project will happen in netowrkx.
Held-Karp Separation Oracle
Continuing the theme of my last post, we know that the Held-Karp relaxation in the Asadpour Asymmetric Traveling Salesman Problem cannot be practically written into the standard matrix form of a linear program. Thus, we need a different method to solve the relaxation, which is where the ellipsoid method comes into play. The ellipsoid method can be used to solve semi-infinite linear programs, which is what the Held-Karp relaxation is.
Sidharth Bansal joined as GSoC'20 intern
When I, Sidharth Bansal, heard I got selected in Google Summer of Code(GSOC) 2020 with Matplotlib under Numfocus, I was jumping and dancing. In this post, I talk about my past experiences, how I got selected for GSOC with Matplotlib, and my project details. I am grateful to the community :) About me: I am currently pursuing a Bachelor’s in Technology in Software Engineering at Delhi Technological University, Delhi, India. I started my journey of open source with Public Lab, an open-source organization as a full-stack Ruby on Rails web developer.
Held-Karp Relaxation
In linear programming, we sometimes need to take what would be a integer program and ‘relax’ it, or unbound the values of the variables so that they are continuous. One particular application of this process is Held-Karp relaxation used the first part of the Asadpour algorithm for the Asymmetric Traveling Salesman Problem, where we find the lower bound of the approximation. Normally the relaxation is written as follows. \[ \begin{array}{c l l} \text{min} & \sum_{a} c(a)x_a \\\ \text{s.