JuliaGraphs / JuliaGraphs/Graphs.jl
Graph property recognition algorithms
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 538
- Forks
- 128
- Avg merge
- 10h 25m
- Merged PRs (30d)
- 2
Description
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.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reading the existing Graphs.jl predicates such as is_bipartite, is_cyclic, and is_strongly_connected, then consult the cited papers and corresponding SageMath implementations. Treat each requested predicate as a separate PR; done means one selected algorithm is included in Graphs.jl with behavior matching its specification.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- data
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100