tag:blogger.com,1999:blog-35348174900446132732018-03-06T09:57:03.792-08:00Extending Matroid Functionality Google Summer of Code 2016Tarahttp://www.blogger.com/profile/03187790486376807341noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3534817490044613273.post-10793020885104271462016-08-22T07:18:00.002-07:002016-08-23T05:39:37.107-07:00Overview of what was doneMy project has been extending the functionality of SageMath in a matroid direction.<br />As part of my application, and before the summer officially started, I worked on two tickets: <a href="https://trac.sagemath.org/ticket/20290">https://trac.sagemath.org/ticket/20290</a> and <a href="https://trac.sagemath.org/ticket/14666">https://trac.sagemath.org/ticket/14666</a>. 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 <span style="background-color: white; color: #212121; font-family: wf_segoe-ui_normal, "Segoe UI", "Segoe WP", Tahoma, Arial, sans-serif; font-size: 15px;">official release version of SageMath</span>.<br /><br />At the beginning of the summer, I was focused on adding certificates to the pre written algorithms <a href="https://trac.sagemath.org/ticket/20660">is_isomorphic()</a>, <a href="https://trac.sagemath.org/ticket/20696">chordal functions</a>, <a href="https://trac.sagemath.org/ticket/20689">has_minor()</a>, and <a href="https://trac.sagemath.org/ticket/20778">has_line_minor()</a>. 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.<br /><br />The bulk of my project has been working on implementing <a href="http://www.jstor.org/stable/3689867?seq=1#page_scan_tab_contents" target=""><i>An Almost Linear-Time Algorithm</i></a> 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 <a href="https://trac.sagemath.org/ticket/20834">here</a>. 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.<br /><br />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.<br /><br />A node contains a graph, a parent marker edge, and a parent marker vertex. The latter is one of the <span style="background-color: white; color: #212121; font-family: wf_segoe-ui_normal, "Segoe UI", "Segoe WP", Tahoma, Arial, sans-serif; font-size: 15px;">vertices</span> 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.<br /><br />The flow structure of the main functions is given below. Each function is a decomposition function.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-5xvyY925m5Q/V7sIsmAheUI/AAAAAAAABG0/O0RUUuz6o-A4POAGtIuIyD9DXH4iT5e0QCLcB/s1600/Diagram.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://3.bp.blogspot.com/-5xvyY925m5Q/V7sIsmAheUI/AAAAAAAABG0/O0RUUuz6o-A4POAGtIuIyD9DXH4iT5e0QCLcB/s320/Diagram.png" width="280" /></a></div><br /><br /><div style="line-height: 100%; margin-bottom: 0in;">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 <b>relink1</b>, <b>typing</b>, <b>relink2</b>, and <b>hypopath</b> from section 4 of the paper, <b>squeeze</b> and <b>update</b> from section 5, and <b>is_graphic</b> from section 6.</div><div style="line-height: 100%; margin-bottom: 0in;"><br /></div><div style="line-height: 100%; margin-bottom: 0in;"><span style="font-size: large;">Nodes</span></div><div style="line-height: 100%; margin-bottom: 0in;"><br /></div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_graph(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_parent_marker(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_named_edge(self, f)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_parent_marker_edge(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_f(self) </b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>set_f(self, int n)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>is_polygon(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>s_path(self, P)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>is_cycle(self, P)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>_T(self, P, Z=*)</b></div><div style="line-height: 100%; margin-bottom: 0in;">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.</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__relink1(self, Z=*, WQ=*)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__relink2(self, Z=*, WQ=*)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_T(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>set_T(self, int T)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><br /></div><div style="line-height: 100%; margin-bottom: 0in;"><br /></div><div style="line-height: 100%; margin-bottom: 0in;"><br /></div><div style="line-height: 100%; margin-bottom: 0in;"><span style="font-size: large;">CunninghamEdmondsDecomposition</span></div><div style="line-height: 100%; margin-bottom: 0in;"><br /></div><div style="line-height: 100%; margin-bottom: 0in;"><b>relink1(self, Q, Z=*, WQ=*)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_D_hat(self, P)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>T(self, N, P, T)</b></div><div style="line-height: 100%; margin-bottom: 0in;">This is not done. It needs to be fixed so that it takes into account the types of the children of self.</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__typing(self, P, pi)</b></div><div style="line-height: 100%; margin-bottom: 0in;">This is not tested as it relies on T. There are, however, no known deficiencies with the algorithm.</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__relink2(Q, Z=*, WQ=*)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__hypopath(self, P)</b></div><div style="line-height: 100%; margin-bottom: 0in;">This is not tested as it relies on <b>__typing</b>. The assigning of u_1 and u_2 needs to be fixed.</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__squeeze(self, N, L)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__update(self, P, C)</b></div><div style="line-height: 100%; margin-bottom: 0in;">This is not tested as it relies on <b>__hypopath</b>. 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.</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__is_graphic(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">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.</div><div style="line-height: 100%; margin-bottom: 0in;"><b>merge_with_parent(self, N, N_vertex=*, P_vertex=*)</b></div><div style="line-height: 100%; margin-bottom: 0in;">This is done, but it doesn't use the f is N_vertex and P_vertex are undefined. This should probably be changed.</div><div style="line-height: 100%; margin-bottom: 0in;"><b>merge_branch(self, N, P)</b></div><div style="line-height: 100%; margin-bottom: 0in;">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.</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__add_cycle(self, cycle)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_arborescence(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_nodes(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_root(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>__get_pi(self)</b></div><div style="line-height: 100%; margin-bottom: 0in;">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.</div><div style="line-height: 100%; margin-bottom: 0in;"><b>branch(self, N)</b></div><div style="line-height: 100%; margin-bottom: 0in;">Done</div><div style="line-height: 100%; margin-bottom: 0in;"><b>get_parent(self, N)</b></div><div style="line-height: 100%; margin-bottom: 0in;"> Done</div>Tarahttp://www.blogger.com/profile/03187790486376807341noreply@blogger.com0tag:blogger.com,1999:blog-3534817490044613273.post-38284326547879848902016-06-27T10:41:00.001-07:002016-06-27T11:39:17.597-07:00Midterm ishMy summer of code is broken up into several projects. There were a lot of small ones, a couple medium ones, and one large one. Right now, I'm in the midst of working on the large project. Basically, we want to feed Sage a collection of subsets of an edge set E, and have Sage tell us if there is a graph that has cycles which correspond to the subsets of E, and if so, to give a corresponding. This boils down to asking if a matroid is <a href="https://en.wikipedia.org/wiki/Graphic_matroid" target="_blank">graphic</a>, and asking for a graph that realizes the matroid.<br /><br />For instance, if we give have E = {1, 2, 3, 4}, and our collection of sets is any three element subset of E, then we can't get an appropriate graph. To see this, we start constructing a graph. Our first cycle is {1, 2, 3}, There is only one graph on three elements that has this cycle, namely a triangle. To add the edge 4, we need to have a cycle {1, 2, 4}. But this means that we have to add 4 in parallel to the edge 3. This is a problem, because then {1, 3, 4}, in particular, is not a cycle of our graph.<br /><br />This example illustrates a key idea of the algorithm. The set {1, 2} is a maximal set that is not contained in a cylce, so we skipped over those elements, and started with 3. We then added 3 and any needed elements of {1, 2} to our partial graph. And we kept adding elements till we either had a problem, or till we added all of the elements.<br /><br />In our case, we didn't get so complicated of a graph that we had a choice about which graph to use for our partial graph. In general, this is not the case. It would be troublesome to check if we could add the new element to every graphs that realizes the already added elements, so we use a decomposition made possible by <a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190040106/pdf" target="_blank">Whitney's 2 isomorphism theorem</a> to check all of the graphs options at once. This of course makes the code more complicated. The algorithm that we are following comes from a <a href="http://www.jstor.org/stable/3689867?seq=1#page_scan_tab_contents" target="_blank">paper</a> by Ronald Bixby and Donald Wagner.<br /><br />The tricky part, so far, has been trying to get information in and out of graphs. graph theorists care a lot about the vertices of a graph and much less about the edges of the graph. That is, they store their edges as a list of the two vertices that they are incident with, and a possible label. matroid theorists, however, care a lot more about the edges of a graph. This is true in general, and is true in particular for this project.Tarahttp://www.blogger.com/profile/03187790486376807341noreply@blogger.com0tag:blogger.com,1999:blog-3534817490044613273.post-41682778568823026492016-06-02T17:30:00.003-07:002016-06-02T17:30:39.549-07:00First Week or soBefore coding started, I spent some time on <a href="http://www.codecademy.com/" target="_blank">code academy</a> getting more familiar with the syntax of Python. I was impressed with the setup that they had (I would recommend it to my mom), and it helped me to learn python in a systematic way.<br /><br />Since the 23rd I've been working on adding certificated (proof that we gave the right answer to a yes-no question) to some of the functions in the matroid part of Sage. For the first two days, I spent a lot of time trying to get Sage to compile. For a while, the problem was an error in a new release, and then I had some type of trouble on my end. I've also spent a good amount of time figuring out the ins and outs of documentation practices.Tarahttp://www.blogger.com/profile/03187790486376807341noreply@blogger.com0tag:blogger.com,1999:blog-3534817490044613273.post-52988108818794002922016-05-09T10:29:00.001-07:002016-05-09T10:29:25.999-07:00Getting StartedI first heard about Google Summer of Code a little over a year ago. It was something that I wanted to do for several reasons. I only had a chance to take a couple of programing classes in undergrad. (I didn't realized that I liked it till part way through my Junior year.) Since then, I've wanted to grow the length and complexity of projects that I was capable of successfully working on. Secondly, I like the idea of open source resources, because its free, and that lets poor college students use cool resources.<br /><br />My project is building and expanding tools in <a href="http://www.sagemath.org/">Sage</a> to be used by people studying matroid theory. A <a href="https://www.math.lsu.edu/~oxley/survey4.pdf">matroid</a> is a notion of independence that generalizes the independence structure that is found in vector spaces and that comes from looking at cycleless subgraphs of <a href="https://en.wikipedia.org/wiki/Graph_theory">graphs</a>. Sage already has a lot of <a href="http://doc.sagemath.org/html/en/reference/matroids/index.html">tools</a> that let people work with matroids, mostly created by Stefan van Zwam and Rudi Pendavingh. My <a href="https://summerofcode.withgoogle.com/projects/#4830375092158464">project</a> focuses on a small collection of new tools.<br /><br />I'll be working with Stefan and Michael on this project.Tarahttp://www.blogger.com/profile/03187790486376807341noreply@blogger.com0