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.
