Dear Mr David, Thank you for your prompt response.
As mentioned by you, there are two approaches that can be followed. Creating an interface with ODGF or recoding the algorithm in Sage. However, I suggest we recode the algorithm in Sage with sufficient modularity and documentation, mainly due to the below reasons - 1. Most of the times, it is a better idea to have an in-house implementation, rather than depend on a different library. And since the graph theory module in Sage is very wide with various algorithms implemented, it is a good idea to implement SPQR trees also. 2. SPQR tree is an important data structure in the field of graph algorithms. It is quite possible that new and efficient algorithms for existing problems can be devised using SPQR trees or a modification of SPQR trees. In such cases, the new algorithms can be easily implemented in Sage by re-using the sub modules of SPQR trees. With the above points in mind, I have read the two papers and I understand that the second paper provides a correct and efficient linear time algorithm for computing the SPQR trees in the offline case, i.e., static SPQR trees. Gutwenger's PHD thesis <https://ls11-www.cs.tu-dortmund.de/people/gutweng/diss.pdf> has an extended version of the paper which helps in understanding the algorithm better. The three components of the algorithm - finding separation pairs, using the separation pairs to obtain the split components, and further using the split components to build the SPQR tree have been detailed in the thesis. As the SPQR tree implementation is already available in C++, in my opinion recoding it in Python along with thoroughly testing the code would take about 6-7 weeks. I could use the remaining of the summer by doing one of the following - 1. Wrt SPQR trees, one step before SPQR trees are BC trees for graphs with cut vertices. However, this has already been implemented in Sage as blocks_and_cuts_tree() method in the module generic_graph.py. An extension to this would be to add dynamic BC trees to Sage. ODGF has dynamic BC tree implemented here <https://github.com/ogdf/ogdf/blob/master/src/ogdf/decomposition/DynamicBCTree.cpp> . 2. ODGF also contains a linear time implementation of dynamic SPQR tree <https://github.com/ogdf/ogdf/blob/master/src/ogdf/decomposition/DynamicSPQRTree.cpp> which supports updates to the graph. I would like to continue implementing the dynamic SPQR trees after completing static SPQR tree. 3. I would like to identify a couple of algorithms which use static SPQR trees and implement these algorithms. For example, recognition of chordless graphs and of graphs that do not contain a propeller as a subgraph can be done in linear time using SPQR trees according to this <https://www.sciencedirect.com/science/article/pii/S0166218X17300422> paper. I could not find the full version of the paper and hence could not go through the algorithm but they seem to be using SPQR trees to obtain linear time algorithm. Another paper by Carsten Gutwenger, link here <https://dl.acm.org/citation.cfm?id=1496812>, gives an efficient algorithm using SPQR trees for finding a planar embedding of a graph where a star has to be augmented with minimum crossings. In case the scope of any of the above is too broad to be finished in the summer, I could continue the work after summer and finish the implementations. I have 5 years of experience with both Python and C++ and I am proficient in these languages. I have worked on various projects and libraries built on top of Python and C++. You can find a few of my projects in Python here <https://github.com/meghanamreddy/Face-detection-algorithm>, here <https://github.com/meghanamreddy/Strassens-algorithm> and here <https://github.com/meghanamreddy/Calorie-estimation-from-food-images-OpenCV>; and a few of my C++ projects here <https://github.com/meghanamreddy/Range-trees-and-Interval-Trees> and here <https://github.com/meghanamreddy/Computer-graphics>. My github link - https://github.com/meghanamreddy. I have also been working on graph theory extensively in the course of my masters thesis. Apart from getting an understanding on the project itself, I have familiarized myself with SageMath, Sage trac and git, and I have started working on the graph module of the sage code base. As of now, I will continue to build on ticket #24909 <https://trac.sagemath.org/ticket/24909>. Please let me know your views on the above. Thank you, Meghana M Reddy -- You received this message because you are subscribed to the Google Groups "sage-gsoc" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sage-gsoc. For more options, visit https://groups.google.com/d/optout.
