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.
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.
Nodes
get_graph(self)
Done
get_parent_marker(self)
Done
get_named_edge(self,
f)
Done
get_parent_marker_edge(self)
Done
get_f(self)
Done
set_f(self, int n)
Done
is_polygon(self)
Done
s_path(self, P)
Done
is_cycle(self, P)
Done
_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=*)
Done
__relink2(self, Z=*,
WQ=*)
Done
get_T(self)
Done
set_T(self, int T)
Done
CunninghamEdmondsDecomposition
relink1(self, Q,
Z=*, WQ=*)
Done
get_D_hat(self, P)
Done
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=*)
Done
__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)
Done
__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.
__is_graphic(self)
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)
Done
get_arborescence(self)
Done
get_nodes(self)
Done
get_root(self)
Done
__get_pi(self)
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)
Done
get_parent(self, N)
Done
No comments:
Post a Comment