Le vendredi 2 mars 2018 22:55:27 UTC+1, Sai Harsh Tondomker a écrit : > > Thanks for your response. I would like to go with recoding the method with > documentation. > > I have installed OGDF and sage on my system, using OGDF implementation as > a reference, I am implementing Find Triconnected Components > <http://www.dtic.mil/dtic/tr/fulltext/u2/746856.pdf> in a graph for sage. > Code link is given below. >
Before starting to code, you must read "Gutwenger, Carsten; Mutzel, Petra (2001), "A linear time implementation of SPQR-trees", Proc. 8th International Symposium on Graph Drawing (GD 2000), Lecture Notes in Computer Science, 1984, Springer-Verlag, pp. 77–90, doi:10.1007/3-540-44541-2_8" It corrects the Hopcroft-Tarjan algorithm. > > I have been working on an implementation of the Triconnected components > algorithm in the research paper in python. The algorithm requires a lot of > DFS function calls, corresponding to it. I made some design decisions which > I needed to get reviewed. > > 1. I have stored all the arrays in a class (array_info) such that I > can access them in any other classes/functions. > > a. The advantage of this approach is that there is no > need to send all the parameters(arrays) to the functions again and again. > > b. The demerit is that if a function needs only a few > lists from array_info, all the lists in the array_info will be initialized. > Why using an extra class array_info instead of including all arrays in the class Search ? This way you can initialize the arrays only if you need them. > > 2. For DFS to avoid passing graph at each function call, I stored > the graph in a parameter of a class (search). > OK > > I am currently implementing the remaining code required for finding > triconnected components. I needed some review of these design decisions and > suggestions if any changes I needed to make for better performance. > In your code, please add sufficient amount of comments. This is very important. You can look at the code of the graph module of sagemath. You will see that the amount of comments is huge. > > Code: link <https://github.com/SaiHarsh/Triconnected-Component> > > Thanks, > Harsh > > > -- 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.
