Hi Szabolcs, Thank you for your reply. The lattice I am testing right now is quite small, with about 200 vertices, which already take several minutes. The real case I plan to run has about 10,000 vertices, so I guess it may not be reasonable to keep them in memory.
Yu Xiang -----Original Message----- From: igraph-help <igraph-help-bounces+yux1991=gmail....@nongnu.org> On Behalf Of Szabolcs Horvát Sent: Wednesday, July 17, 2019 12:13 PM To: Help for igraph users <igraph-help@nongnu.org> Subject: Re: [igraph] largest independent vertex sets Hello Yu, How big is your lattice? Is it reasonable to keep the complement graph in memory? Szabolcs On Wed, 17 Jul 2019 at 15:46, <yux1...@gmail.com> wrote: > > Hi, > > > > I am trying to find out a largest independent vertex set for a graph that > represents a randomly generated crystal lattice, then I came across igraph. > My program is written with Python. I managed to get a list of the largest > independent vertex sets using the largest_independent_vertex_sets() method of > the Graph class. However, that’s not quite what I want. All I need is just a > single largest independent vertex set, instead of a list of all > possibilities. There are thousands of vertices in my graph, therefore it > takes a very long time to calculate the complete list. I know it is a > NP-complete problem, but I think generating just one such set instead of > generating the complete list and then taking one from it would cut down the > runtime significantly. I looked at the source code written in C but was kind > of getting lost there. I am not sure whether this can be easily done by > modifying the source code. Could anybody help me with this issue? > > > > Best regards, > > > > Yu Xiang > > PhD Candidate > > Dept. of Physics, Applied Physics & Astronomy > > Rensselaer Polytechnic Institute > > Jonsson-Rowland Science Center 2W19 > > Email: xia...@rpi.edu > > Phone: (518) 833-4710 > > > > _______________________________________________ > igraph-help mailing list > igraph-help@nongnu.org > https://lists.nongnu.org/mailman/listinfo/igraph-help _______________________________________________ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help _______________________________________________ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help