Hi Serafeim,
Thank you for your reply. However, that’s not what I need. First, I am looking for the largest independent set, which is not necessarily the maximal independent set. Second, “maximal_independent_vertex_sets()” outputs a longer list than the “largest_independent_vertex_sets()”, which takes even longer computation time. Maybe I did not make myself clear, but I just need one tuple representing the largest independent set instead of a list of tuples in the output. Do you know how to deal with it? Best regards, Yu Xiang From: igraph-help <[email protected]> On Behalf Of serafim loukas Sent: Wednesday, July 17, 2019 9:51 AM To: Help for igraph users <[email protected]> Subject: Re: [igraph] largest independent vertex sets Hi, I believe you need another function. If you need only the maximal independent vertex set use “maximal_independent_vertex_sets()” function. https://igraph.org/python/doc/igraph.GraphBase-class.html#maximal_independe nt_vertex_sets Bests, Serafeim On 17 Jul 2019, at 15:43, [email protected] <mailto:[email protected]> 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: [email protected] <mailto:[email protected]> Phone: (518) 833-4710 _______________________________________________ igraph-help mailing list [email protected] <mailto:[email protected]> https://lists.nongnu.org/mailman/listinfo/igraph-help
<<attachment: winmail.dat>>
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
