Monday, August 22, 2016

Overview of what was done

My project has been extending the functionality of SageMath in a matroid direction.
As part of my application, and before the summer officially started, I worked on two tickets: and 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 functionshas_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.

Here is the list of all the functions and the status of each of them. Most of them are supporting functions, with the exception of relink1, typing, relink2, and hypopath from section 4 of the paper, squeeze and update from section 5, and is_graphic from section 6.


get_named_edge(self, f)
set_f(self, int n)
s_path(self, P)
is_cycle(self, P)
_T(self, P, Z=*)
This will correctly give the T value when self is a leaf of the reduced arborescence. It does not correctly compute the T value otherwise.
__relink1(self, Z=*, WQ=*)
__relink2(self, Z=*, WQ=*)
set_T(self, int T)


relink1(self, Q, Z=*, WQ=*)
get_D_hat(self, P)
T(self, N, P, T)
This is not done. It needs to be fixed so that it takes into account the types of the children of self.
__typing(self, P, pi)
This is not tested as it relies on T. There are, however, no known deficiencies with the algorithm.
__relink2(Q, Z=*, WQ=*)
__hypopath(self, P)
This is not tested as it relies on __typing. The assigning of u_1 and u_2 needs to be fixed.
__squeeze(self, N, L)
__update(self, P, C)
This is not tested as it relies on __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.
This is not done. G2 and G3 need to be written, and it needs to be tested. This cannot happen until the rest of the problems are fixed.
merge_with_parent(self, N, N_vertex=*, P_vertex=*)
This is done, but it doesn't use the f is N_vertex and P_vertex are undefined. This should probably be changed.
merge_branch(self, N, P)
This is written, but in order to insure that the intersection of P with this graph is always a path if possible, P should be replaced with P_0, and the parent markers of children that intersect P should be added to P_0 initially, and removed, in turn, when that child is merged with N.
__add_cycle(self, cycle)
This is done, but it should be changed so that it can take a sub tree of self.arborescence as an input, and give pi on the reduced decomposition.
branch(self, N)
get_parent(self, N)

No comments:

Post a Comment