Graph property recognition algorithms

[Luis-Varona]

I'd like to add the following graph property recognition algorithms to Graphs.jl:

• is_cartesian_product (Imrich and Peterin 2007)
• is_chordal (Tarjan and Yannakakis 1984)
• is_chordal_bipartite + is_strongly_chordal (Spinrad 1993)
• is_cograph(Habib and Paul 2005)
• is_outerplanar (Wiegers 1986)
• is_planar (de Fraysseix and Rosenstiehl 1982)

All of these are algorithms implemented in SageMath that I regularly use in my research, and which I typically have to reimplement from scratch or use my own FFI with sage to access from Julia. Given that Graphs.jl already includes functions such as is_bipartite, is_cyclic, is_strongly_connected, etc., I think (at least some of) these algorithms would be well-suited for inclusion.

Should the maintainers deem these additions appropriate, I believe each item listed above merits its own separate PR to avoid overloading any single review.

[Krastanov]

Please go ahead, no need to ask for permission. These additions will be appreciated. Review might be somewhat slow, so anything you can do to simplify that step would be useful (check the dev docs, have easy to understand tests, run code autoformatting, etc). Thank you for spending some of your time on improving the library!

[Krastanov]

of note, check whether NautyGraphs, VNGraphs, or IGraphs implements any of these features. Using them as a cross check in the unit tests can be very valuable.

[simonschoelly]

Please go ahead, no need to ask for permission. These additions will be appreciated. Review might be somewhat slow, so anything you can do to simplify that step would be useful (check the dev docs, have easy to understand tests, run code autoformatting, etc). Thank you for spending some of your time on improving the library!

From CONTRIBUTING.MD

If you want to introduce a new feature, open an issue to discuss a feature before you start coding (this maximizes the likelihood of patch acceptance).

It is always good to ask first as it can be frustrating for contributors as well as us maintainers having to say no when something has already been implemented. And we can also give directions so that less things have to be changed afterwards.

[simonschoelly]

Planarity is especially something that we want for a long time. It is possible that there are already existing PRs on that where we did not have the time to review them yet (we are quite short staffed). The only other thing I am familiar with is chordiality, but I think all these features are welcome.

As these features are non-trivial to review I would strongly suggest to create a different PR for each feature. EDIT: After re-reading your comment I realized that you already thought of that.

[Luis-Varona]

Planarity is especially something that we want for a long time. It is possible that there are already existing PRs on that where we did not have the time to review them yet (we are quite short staffed). The only other thing I am familiar with is chordiality, but I think all these features are welcome.

As these features are non-trivial to review I would strongly suggest to create a different PR for each feature. EDIT: After re-reading your comment I realized that you already thought of that.

@simonschoelly I've checked—there is indeed one very old PR from June 2023 introducing planarity in which there are now merge conflicts due to updates in the main branch. Every other algorithm I proposed is not implemented in Graphs.jl, though. If you want, I can start with planarity and outerplanarity. Do you want me to split that up into two PRs as well, or are the groupings in my original Issue post okay?

The nice thing also is that all of these are implemented in SageMath, so it saves me trouble having to write everything with no concrete implementation reference whatsoever and could (potentially) be another source of reference for reviewers.

[Luis-Varona]

of note, check whether NautyGraphs, VNGraphs, or IGraphs implements any of these features. Using them as a cross check in the unit tests can be very valuable.

@Krastanov will do!

[Luis-Varona]

PS: Probably best to add the enhancements label to this Issue?

[Luis-Varona]

If you want, I can start with planarity and outerplanarity. Do you want me to split that up into two PRs as well, or are the groupings in my original Issue post okay?

On second thought, @simonschoelly, I'll probably just split up is_planar and is_outerplanar into two separate PRs. I was originally planning to just make is_outerplanar a decorator of is_planar (testing the graph join $K_1 + G$ for planarity is equivalent to testing the graph $G$ for outerplanarity), but I might just implement Wiegers 1986 instead with less overhead. I'll be using de Fraysseix and Rosenstiehl 1982, on the other hand, to test for planarity; given your feedback, I'll prioritize that first.

[Luis-Varona]

@Krastanov @simonschoelly, would it be appropriate to place is_planar in src/core.jl, or should I make a new file [src/planarity.jl] for both is_planar and (in a separate PR) is_outerplanar? Alternatively, do you recommend the creation of a new subfolder entirely, in the spirit of the already existing src/traversals/?

[Krastanov]

I am leaning towards avoiding core.jl -- it does not fit semantically there too well. We can modify this towards the end of your PR review, but right now sticking this in a new planarity.jl seems clean and simple enough.

[Luis-Varona]

I am leaning towards avoiding core.jl -- it does not fit semantically there too well. We can modify this towards the end of your PR review, but right now sticking this in a new planarity.jl seems clean and simple enough.

Would it make sense to include both is_planar and is_outerplanar in src/planarity.jl? (I still plan to do a separate PR for each, though.)

[simonschoelly]

Totally agree - there is probably already too much in core.jl. And we export all symbols - so it is not a breaking change to move stuff around later. Planarity deserves its own file so src/planarity.jl is a perfect location.