WIP: Add an `is_chordal` algorithm

[Luis-Varona]

We implement Tarjan and Yannakakis (1984)'s MCS algorithm, taking inspiration from the existing NetworkX implementation. Everything is done except for example doctests in src/chordality.jl and unit tests in test/chordality.jl. (This PR is part of a new suite of algorithms outlined in issue #431.)

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 0% with 23 lines in your changes missing coverage. Please review.

Project coverage is 97.09%. Comparing base (c001dab) to head (eeb10f4). Report is 5 commits behind head on master.

Files with missing lines	Patch %	Lines
src/chordality.jl	0.00%	23 Missing :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #434      +/-   ##
==========================================
- Coverage   97.41%   97.09%   -0.32%     
==========================================
  Files         120      121       +1     
  Lines        6953     6982      +29     
==========================================
+ Hits         6773     6779       +6     
- Misses        180      203      +23     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[simonschoelly]

Do you by any change know where I could find a public accessible version of that paper? My usual methods did not help.

[Krastanov]

out.pdf

The paper is attached here, courtesy of the UMass library.

[Luis-Varona]

out.pdf

The paper is attached here, courtesy of the UMass library.

Wonderful, @Krastanov, thanks!

[Luis-Varona]

@simonschoelly, just wanted to let you know I certainly haven't abandoned this PR. I was busy with work this past week and I'm at a conference this weekend, but I'll get back to it shortly. I've looked over your comments and it shouldn't be many more changes at all anyway, hehe.

[Luis-Varona]

@simonschoelly, just changed the input type from AbstractSimpleGraph to AbstractGraph. Anything else you'd like me to change before I get around to adding tests?

[Luis-Varona]

Wait—I just remembered your comment about induced subgraphs. I'll think about that and get back to you I was largely just porting over networkx's implementation, which does do this, but it probably really isn't optimal.

[simonschoelly]

@simonschoelly, just wanted to let you know I certainly haven't abandoned this PR. I was busy with work this past week and I'm at a conference this weekend, but I'll get back to it shortly. I've looked over your comments and it shouldn't be many more changes at all anyway, hehe.

Don't worry - we are quite slow with reviewing PRs here :D

[Luis-Varona]

@simonschoelly @Krastanov I've fixed the issue regarding unnecessary allocations with induced_subgraph, instead having the _induces_clique helper take in a vertex subset and, in the context of the original graph, confirm that all possible edges exist. @simonschoelly, is there anything else I should change before I start on unit tests and docstring examples?

[Luis-Varona]

Hi @simonschoelly, just following up. Is everything good enough for me to conclude my work on the actual logic and start on the docstring and unit tests? 🙂

[Luis-Varona]

What do you think, @Krastanov? 🙂

[Krastanov]

Thanks, @Luis-Varona ! No need to wait for anything else to be finished before adding tests on my end. I actually frequently refuse to review PRs before the tests are added, as I judge quality first by the tests and documentation.

I am adding some quality of life improvements to IGraphs.jl that should make it easy to test against their implementation as well. I will post it here shortly.

[Krastanov]

Just to clarify: while I might have a particular style of review, that style is not shared by everyone, and please do not hesitate to request me approaching this differently.

[Krastanov]

IGraphs.jl just got a new release in which you can use the following in order to test your implementation against the ones in the igraph C library https://igraph.org/c/html/latest/igraph-Structural.html#igraph_is_chordal

the_graph = random_regular_graph(10,5)
LibIGraph.is_chordal(IGraph(the_graph), IGNull(), IGNull(), IGNull(), IGNull())

I frequently use random sampling over appropriate ensembles as a way to test that two implementations give the same result. This can be useful here as well.

It can also be fun to compare performance (just make sure to not count the time to convert the graph from one format to the other).

[simonschoelly]

There is also https://github.com/wangjie212/ChordalGraph

[simonschoelly]

You resolved that conversation but might have overlooked what I wrote there about using the IsDirected trait.

[Luis-Varona]

Thanks for the info, @Krastanov!

You resolved that conversation but might have overlooked what I wrote there about using the IsDirected trait.

So I did, @simonschoelly. Sorry—I must've overlooked that. I expect that sort of fix shouldn't take long, anyway, so I'll try to take a crack at it later this week.

I suppose regardless of the internal workings of our version of is_chordal, I can also start right away on the test suite. Testing against only one of the two libraries suggested above (i.e., ChordalGraphs.jl or IGraphs.jl, not both) should be sufficient, right?

Edit: Certainly, benchmarking our implementation against both of the above would be useful, but I'm thinking I'll leave that to the benchmark/ folder and just use one or the other as a point of comparison in the actual test suite in test/.

[Krastanov]

Yes, no need to test against multiple other libraries. Your own correctness tests are probably most important -- testing against another library with a bunch of random samples just provides a bit more certainty that we are not missing anything.

[Luis-Varona]

Hi @Krastanov and @simonschoelly, sorry for the long silence—I plan to return to this issue sometime next week. IIRC, all that's left is just a test suite, and maybe a docs fix. 🙂

[Krastanov]

Thanks @Luis-Varona

[samuelsonric]

@Luis-Varona @Krastanov @simonschoelly I have an extremely performant implementation of this function here, if that is of any interest. In particular, the MCS algorithm is best implemented using a bucket queue: see here.

[Krastanov]

@samuelsonric , thanks for the heads up! It would be great to have access to both implementations from Graphs.jl -- this also makes testing much easier as we can just do random tests against each other.

If you or anyone else has the bandwidth, my suggestion would be to do

is_chordal(graph) which dispatches to is_cordal(graph, alg::GraphsMCSAlg) which is the algorithm implemented here and then in CliqueTrees.jl import Graphs; Graphs.is_cordal(graph, alg::CliqueTreesMCSAlg). The reason I am suggesting the extension happening in CliqueTrees is because CliqueTrees already depends on Graphs. The reason I am suggesting keeping both options is because it is valuable to keep the Graphs dependencies as minimal as possible.

As for is_chordal vs ischordal, it seems we mostly use the underscore notation for public functions:

[samuelsonric]

@Krastanov,

I am happy to do this. I can probably implement is_cograph as well.

[Krastanov]

Thanks, Richard!