Hi I have shared a draft with you on GSOC website. I have also included the link to my code over there. Can you please review it? I am working on completing the full implementation. Currently I am working on refining trees using the active edges of nodes in the graph. I will keep you updated on my progress.
Thanks Lokesh On Friday, March 17, 2017 at 2:17:53 AM UTC+5:30, Dima Pasechnik wrote: > > > > On Wednesday, March 15, 2017 at 5:13:00 PM UTC, Lokesh Jain wrote: >> >> Hi >> >> I have been working on an implementation of the linear time algorithm in >> the research paper. The algorithm requires a lot of computations involving >> formation of induced graphs. Corresponding to this I made some design >> decisions which I needed to get reviewed. >> >> 1. I do not store the induced graph entirely in memory. For an >> induced graph I create a set and a list which contains all the vertices >> of >> the induced graph. The edges corresponding to vertices in the induced >> graph >> is not stored and need to be used from the original graph itself. >> >> > yes, this looks very reasonable - I think that's the usual way to > implement induced subgraphs. > > >> >> - The advantage of this approach is it saves memory and computations >> required to create the induced graph. This would be useful for large >> graphs >> where number of edges can be of order O(n^2). >> - The demerit is that if I have to traverse through the edges of a >> vertex in the induced graph it would require me to traverse all the >> edges >> of that vertex in the original graph itself. >> >> do not worry about this - especially I think it's extremely unlikely that > you can get linear complexity if you fully create induced subgraphs rather > than represent them as you currently do. > > >> >> - >> - The set and list can be combined into a single data structure >> using C++ set implementation as it allows to iterate through the >> elements >> of the set. I have currently implemented everything using C. >> >> no need to go into C++ here, I think. > >> >> 1. For set implementation I am using bits to represent whether a node >> is present in the graph or not. This reduces the memory required by a >> factor of 32. But this approach assumes that the nodes are numbered from >> 0 >> or 1 and that too in a contiguous manner. >> >> I think bit representation is a minor detail, that can always be added > later on. > Do not optimise your code too early. > > >> I am currently implementing the code required for recursive >> factorization. I needed some review on these design decisions and changes I >> need to make for better performance. >> > > better get a complete working implementation first, and optimise later. > > > >> >> Thanks >> Lokesh >> >> >> >> >> >> On Tuesday, March 7, 2017 at 11:03:12 PM UTC+5:30, Dima Pasechnik wrote: >>> >>> >>> >>> On Tuesday, March 7, 2017 at 4:26:52 PM UTC, Lokesh Jain wrote: >>>> >>>> Hi >>>> >>>> I am M.Sc.(Hons.) Mathematics and B.E.(Hons.) Computer Science student >>>> at BITS Pilani, Pilani Campus. I am currently interning with the Apache >>>> Hadoop YARN team in Hortonworks. I am very interested in Graph Theory and >>>> look forward to implement the Modular Decomposition of Graphs algorithm as >>>> a GSOC project. I have found a research paper "Simpler Linear-Time >>>> Modular Decomposition via Recursive Factorizing Permutations >>>> <http://www.google.com/url?q=http%3A%2F%2Fwww.cs.toronto.edu%2F~mtedder%2FTedderModular.pdf&sa=D&sntz=1&usg=AFQjCNHs-Rq8h6w_TDvK0THTze8wUZCgEQ>" >>>> >>>> corresponding to that. It defines a practical linear time algorithm for >>>> modular decomposition of graphs. I wanted to ask whether I should go ahead >>>> with this research paper and try to implement it? >>>> >>> >>> yes, this is one that definitely should implemented (in C or Python). >>> The only implementation I know is in Java, >>> and it's probably quite old too. >>> >>> >>> >>>> >>>> Regards >>>> Lokesh >>>> >>> -- 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.
