As part of my application, and before the summer officially started, I worked on two tickets: https://trac.sagemath.org/ticket/20290 and https://trac.sagemath.org/ticket/14666. The first was fixing a typo (and learning how to use the interface), and the second one modified the code to find a maximum weighted basis of a matroid so that a user could also see if there was exactly one maximum weighted basis. These are both currently incorporated into official release version of SageMath.

At the beginning of the summer, I was focused on adding certificates to the pre written algorithms is_isomorphic(), chordal functions, has_minor(), and has_line_minor(). All of these are closed tickets except the last one, which had a merge conflict. This also enabled me to get a feel for the documentation culture of my organization.

The bulk of my project has been working on implementing

*An Almost Linear-Time Algorithm*for Graph Realization by Robert Bixby and Donald Wagner. This algorithm was written with data structures that didn't exactly match the code base that I was incorporating the function into, so some changes were made there, and some simple (but not necessarily easy) supporting functions were added. There are still some bugs in the code, whose current version can be found here. Much of the rest of this post will be devoted to explaining the data structures that we used for the algorithm. It is aimed mostly at whoever (hopefully future me) is going to finish this function.

We used two new data structures Node, and Decomposition. The decomposition is composed of nodes and relations between them. In particular, it contains a directed tree, where each vertex corresponds to a node. A decomposition also stores information which is useful to the functions that need it. The root of the tree is stored, as are the nodes which contain the first and last verticies of the hypopath along with these verticies. Also stored are integers to makes sure that we don't double name two verticies or two edges the same thing.

A node contains a graph, a parent marker edge, and a parent marker vertex. The latter is one of the vertices of the parent marker edge, and is manipulated so that it is the edge which will end up being included in the path that comes from the hypopath. It also stores an integer T, which depends on the iteration of adding edges, and is stored after being computed.

The flow structure of the main functions is given below. Each function is a decomposition function.

**relink1**,

**typing**,

**relink2**, and

**hypopath**from section 4 of the paper,

**squeeze**and

**update**from section 5, and

**is_graphic**from section 6.

**get_graph(self)**

**get_parent_marker(self)**

**get_named_edge(self, f)**

**get_parent_marker_edge(self)**

**get_f(self)**

**set_f(self, int n)**

**is_polygon(self)**

**s_path(self, P)**

**is_cycle(self, P)**

**_T(self, P, Z=*)**

**__relink1(self, Z=*, WQ=*)**

**__relink2(self, Z=*, WQ=*)**

**get_T(self)**

**set_T(self, int T)**

**relink1(self, Q, Z=*, WQ=*)**

**get_D_hat(self, P)**

**T(self, N, P, T)**

**__typing(self, P, pi)**

**__relink2(Q, Z=*, WQ=*)**

**__hypopath(self, P)**

**__typing**. The assigning of u_1 and u_2 needs to be fixed.

**__squeeze(self, N, L)**

**__update(self, P, C)**

**__hypopath**. It is essentially done, except that the variables u_1, u_2, K_1, and K_2 are not necessarily computed correctly, and U2.4 is not written.

**__is_graphic(self)**

**merge_with_parent(self, N, N_vertex=*, P_vertex=*)**

**merge_branch(self, N, P)**

**__add_cycle(self, cycle)**

**get_arborescence(self)**

**get_nodes(self)**

**get_root(self)**

**__get_pi(self)**

**branch(self, N)**

**get_parent(self, N)**