-
-
Notifications
You must be signed in to change notification settings - Fork 403
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Generator for Kneser graphs and related graphs #1876
Comments
Hi. I would like to work on this issue. I am already a bit familiar with igraph. This seems like a really interesting issue and I think I'll get to learn quite a lot about graph generation (theoretically and implementation-wise)! |
Thank you for your interest in helping us develop igraph further! Here's a short guide for contributors that should help you get started: https://github.com/igraph/igraph/wiki/Quickstart-for-new-contributors I cannot emphasize enough that we really mean that you should start drafting a PR as soon as you are a bit familiar with the topic - it is easier for us to guide you along the way if you have an understanding of what you are working on and how you intend to tackle the problem. As @szhorvat suggested above in the text of the issue, work out the math first, and then feel free to start a PR. Happy coding! :) |
Thank you. After working out the maths part, I'll open a draft PR for the implementation. |
Hi. I tried thinking of ways to generate kneser graphs more efficiently than the direct approach. I also tried searching for existing resources but I haven't made any headway in this. I went through sage's kneser graph generator. They have used the direct approach as well. def KneserGraph(n, k):
# Initialise a graph structure
g = Graph(name="Kneser graph with parameters {},{}".format(n, k))
from sage.combinat.subset import Subsets
# 'Subsets' uses itertools.combinations to generate subsets
# Complexity: nCk
S = Subsets(n, k)
if 2 * k > n:
g.add_vertices(S)
s0 = S.underlying_set() # {1,2,...,n}
# Complexity of outer loop: nCk
for s in S:
# Complexity of inner loop: (n-k)Ck
for t in Subsets(s0.difference(s), k):
g.add_edge(s, t)
return g The time complexity is |
Generally Sage is very good, so if they didn't find a better way, I think we can go ahead. It's always good to leave a comment in the code pointing out the bad complexity, in case someone comes up with a better idea in the future. |
Alright, in that case I'll open a draft PR and will start working on it. As pointed out in the first comment, I'll start with the subset generation iterator.
Sure, I'll do that. What are the constraints on n and k going to be like? |
Sounds good. Just letting you know that there are a number of outstanding PRs from people working on other projects, so it may take a while before we get the chance to look at yours. |
Hi. Sorry for the inactivity. By iterator, are you referring to something similar to vertex iterators such as |
What is the feature or improvement you would like to see?
The vertices of the Kneser graph
K(n,k)
are thek
-element subsets ofn
elements. Two vertices are connected precisely when the subsets are disjoint.This task is a bit more involved than other "good first issue" tasks. Work out the math before you start coding.
Implementation
One possible implementation is the direct one: represent subsets as Boolean vectors
b
of lengthn
, whereb[i]
is true if elementi
is part of the subset. Directly generate allk
-element subsets and compute their intersections. Question: Is there a more efficient way to generate these graphs?If using the direct implementation, first implement a
k
-subset iterator. It may be useful for other parts of igraph as well.The function should return the subsets as well (e.g. as a Boolean matrix).
Related graph families which may be implemented at the same time
K(n, k, s)
: twok
-subsets are connected when they intersect in no more thans
elements.J(n, k)
: twok
-subsets are connected when they intersect in preciselyk-1
elements.Use cases for the feature
This is a well-studied graph family in graph theory.
References
The text was updated successfully, but these errors were encountered: