More Progress On The Code
Welcome back to the fifth blog in my adventure with graphs.
Last time, I left off with proposing two new features to add to my code: the ability to compute dot products and the ability to compute defects. I am happy to say that I have accomplished both these goals.
The dot product code was relatively simple to implement, as it mostly involved following through on an already well-defined operation. I plan to touch up this code a little to make it more useful when I construct some of my own graphs.
Implementing the code for defects was a much tougher. I spent a majority of time studying different data structures in Python and deciding which ones to use for my project. For example, I decided to reformat the storage of my edges using sets rather than the default tuple returned by Sage. This would make it much easier to compare edges from different facial walks. Once this change in storage was made, writing code for computing the defect became much easier. Below, I compare my storage methods for the faces of the Petersen graph.
Since a graph has polyhedral embedding if and only if it has defect 0, I decided rewrite my code using this fact. Previously, I tested polyhedrality by computing the intersection of facial walks, but my new code does this much better and gives more information about the embeddings.
Moreover, to support testing multiple graphs at once, I wrote some code that parses graphs from an outside file. This is particular helpful as databases like the House of Graphs stores its data as plaintext.
The only thing that worries me now is the runtime of the code. Currently, it takes an entire minute to test a single graph of 18 vertices and around thirty minutes for a graph of 22 vertices. Given that there are over 100,000 snarks with 30 vertices, I can only imagine how long the code will take to run. As such, I will limit my code to testing one graph at a time until I optimize it.
Now that I have code to perform computations, I am planning on leaving the code as is and only optimizing it if I need to. For next week, I will be doing more theoretical work and trying to construct/test different graphs.