On Saturday, March 25, 2017 at 9:59:03 PM UTC, Lokesh Jain wrote: > > 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. >
Do you have any other commitments for the summer, which might interfere with GSoC? > > 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.
