Skip to content
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

Add support for induced bipartite subgraph #145

Open
Codsilla opened this issue Jun 13, 2022 · 3 comments
Open

Add support for induced bipartite subgraph #145

Codsilla opened this issue Jun 13, 2022 · 3 comments
Labels
enhancement New feature or request

Comments

@Codsilla
Copy link

As part of a project, I had to use bipartite induced subgraphs of a graph.

Let $G=(V,E) $ be a graph and let $X,Y\subseteq V$ such that $X \cap Y = \emptyset$. The bipartite subgraph of G induced by $X$ and $Y$ is $$(X \cup Y, X \times Y \cap E) $$
In other words, it's the bipartite subgraph made of all the edges of $G$ that are between $X$ and $Y$.
Such a construction is useful in, for example, the search of vertex separators.

I've made a simple implementation (30 lines or so) for it and I think it might be worth including it.
Before making a pull request, I wanted to see if this is something people might find interesting to have in the package.

@etiennedeg
Copy link
Member

A function which more generally returns the induced subgraph of a set of vertices could be useful. It could also be a good idea to define views on graphs where we could filter the edges and vertices (by filtering vertices, we would get the induced subgraph), see #128 (comment).

@gdalle gdalle added the enhancement New feature or request label Jun 19, 2022
@gdalle
Copy link
Member

gdalle commented Jun 19, 2022

I agree that it would be useful functionality. @Codsilla do you want to get started on a PR so we can help?

@Codsilla
Copy link
Author

A function which more generally returns the induced subgraph of a set of vertices could be useful.

The function induced_subgraph does just that :)
Views would be nice but are not exactly in the scope of what is proposed.

I agree that it would be useful functionality. @Codsilla do you want to get started on a PR so we can help?

Just did!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

3 participants