Re: [igraph] largest independent vertex sets

2019-07-17 Thread yux1991 
Hi Szabolcs,

I saw the new issue. A callback function would definitely solve my problem. 
Thank you so much!

Best regards,

Yu Xiang

-Original Message-
From: igraph-help  On Behalf 
Of Szabolcs Horvát
Sent: Wednesday, July 17, 2019 1:55 PM
To: Help for igraph users 
Subject: Re: [igraph] largest independent vertex sets

I created a new issue with a feature request to solve this:

https://github.com/igraph/igraph/issues/1220

On Wed, 17 Jul 2019 at 15:46,  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

Re: [igraph] largest independent vertex sets

2019-07-17 Thread yux1991 
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  On Behalf 
Of Szabolcs Horvát
Sent: Wednesday, July 17, 2019 12:13 PM
To: Help for igraph users 
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,  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

Re: [igraph] largest independent vertex sets

2019-07-17 Thread Szabolcs Horvát 
I created a new issue with a feature request to solve this:

https://github.com/igraph/igraph/issues/1220

On Wed, 17 Jul 2019 at 15:46,  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

Re: [igraph] largest independent vertex sets

2019-07-17 Thread Szabolcs Horvát 
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,  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

Re: [igraph] largest independent vertex sets

2019-07-17 Thread yux1991 
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  On
Behalf Of serafim loukas
Sent: Wednesday, July 17, 2019 9:51 AM
To: Help for igraph users 
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, yux1...@gmail.com <mailto: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 <mailto:xia...@rpi.edu> 
Phone: (518) 833-4710
 
___
igraph-help mailing list
igraph-help@nongnu.org <mailto: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

Re: [igraph] largest independent vertex sets

2019-07-17 Thread serafim loukas 
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_independent_vertex_sets

Bests,
Serafeim



On 17 Jul 2019, at 15:43, 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] largest independent vertex sets

2019-07-17 Thread yux1991 
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