Le vendredi 9 mars 2018 09:03:07 UTC+1, Meghana.M Reddy a écrit : > > 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 agree that as soon as we will get an efficient implementation of SPQR tree available, and so a decomposition into 3-connected components, we should use it. For instance, we can use it as pre-processing for Hamiltonian cycle and other standard optimization problems. We can implement the linear time algorithms you mentioned. Dynamic version should be considered only after. 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. > It might be better to code SPQR tree using Cython to have better performances. So knowing Python and C/C++ is useful. > 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>. > I'm already following this ticket. It's a good training for you. Best, David. -- 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.
