Week #11: On Biedged Graphs and Cacti

As you may remember from last week's post, the algorithm presented in the paper by Benedict Paten et al. used a Biedged Graph, that is a graph with two types of edges (black and gray), such that each vertex is incident with at most one black edge. This is in contrast with Handlegraphs (as defined here) which, while sharing some similarities to Biedged Graphs, made it difficult to re-implement the algorithm in a straightforward manner. The main objective for this week was to find a way to implement the Cactus Graph creation algorithm Rust, while making sure that any change to the underlying data structure did preserve its correctness.

My first idea was to take a look at how vg implements the Handlegraph to Cactus Graph conversion. This is done in the cactus.cpp file, which I started re-implementing in Rust. However, soon after that, I noticed that some types referenced in that file were missing from the .hpp as well, with the include statements referencing a library called sonLib. I then found the github repo for sonLib, but there was no reference to Cacti either. Finally, I found PinchesAndCacti, which is the library the actually implements Cactus Graphs. Needless to say, I started re-implementing that as well, but after figuring that it would take too much time, I changed my mind. As a last attempt, I also tried using corrode, an automated C to Rust code translator, but after trying to use it unsuccesfully for a few hours, I gave up.

Since trying to replicate vg wasn't really working out well, I had to change my approach completely: I decided to create my own Cactus Graph Rust library, called rs-cactusgraph. The idea was to follow the paper step-by-step, while trying to create a general library for handling Cactus graphs in Rust. I decided to use Petgraph, a well-known Rust library for all kinds of graph, as a "back-end" for my implementation. 

Since the algorithm uses a Biedged Graph as a input, the first thing I had to do was creating a function to convert HandleGraphs into Biedged Graphs. This procedure is rather straightforward: 

• each node (in the Handlegraph) is divided into two nodes; these two nodes are connected by a black edge
• each edge (in the Handlegraph) is converted into a gray edge; since for each node in the Handlegraph there are now two nodes, it is necessary to decide which nodes to use (depending on which sides were connected to the edge).

A Handlegraph (above) and the equivalent Biedged Graph. The gray edges have been represented as red to make them easier to see.

My library features multiple multiple operations on Biedged Graphs, such as edge contraction (that will be used in the algorithm). It also allows for storing Biedged Graphs in Dot format, which can be converted in an image format by using tools such as graphviz.

A Biedged Graph created from a Handlegraph. Black edges are labelled with B, gray edges with G; the numbers represent the original NodeIds.

Next week I'll work on actually implementing the algorithm. There are also some concerns that Petgraph may not be the best library for larger graphs, so maybe Handlegraph could still be used instead as the "back-end" library for storing the graph.