search

JuliaGraphs / Graphs.jl

An optimized graphs package for the Julia programming language
http://juliagraphs.org/Graphs.jl/
Other
451 stars 87 forks source link

Lancichinetti-Fortunato-Radicchi generators #345

Closed fcdimitr closed 4 months ago

fcdimitr commented 5 months ago

Hello! This pull request adds support for generating Lancichinetti-Fortunato-Radicchi graphs.

The function calls the C/C++ generators implemented by the original authors.

simonschoelly commented 5 months ago

Thanks, while such graphs could certainly be interesting, we try to keep the number of dependencies of this package as low as possible. Therefore the only way I see here is either:

codecov[bot] commented 5 months ago

Codecov Report

Attention: Patch coverage is 94.87179% with 2 lines in your changes are missing coverage. Please review.

Project coverage is 97.21%. Comparing base (7133460) to head (5b8572b).

Files Patch % Lines
src/SimpleGraphs/generators/randgraphs.jl 94.87% 2 Missing :warning:
Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #345 +/- ## ========================================== - Coverage 97.28% 97.21% -0.08% ========================================== Files 115 115 Lines 6789 6819 +30 ========================================== + Hits 6605 6629 +24 - Misses 184 190 +6 ```

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

fcdimitr commented 5 months ago

Thank you, @simonschoelly. If I understand correctly, I could create a new package under the JuliaGraphs project, named LFRBenchmarks, for example, and move the codes to that package. How can I prepare and create a new repository under the JuliaGraphs project/organization? Do I need to coordinate with a maintainer?

simonschoelly commented 5 months ago

I think we probably would need to set it up for you, if you wish so.

But maybe it would make sense if we would instead create a package GraphsExtra.jl (or GraphsExtras.jl) for you and then you could push your code there? In the future we can then port some of the code there to Graphs.jl using extensions - but we cannot do that as long as we try to support Julia v1.6.

And eventually we can also carry over some of the code from LightGraphsExtras.jl

What do you think about that? Also quickly checking with @gdalle or anyone else who has an opinion on that.

Btw. your code does not run Julia v1.6 right now.

fcdimitr commented 5 months ago

I saw the "Graphs community calls" in Discourse. There is a meeting this Thursday. I can join, and maybe I can also contribute some other functions/packages that I have developed? Perhaps this is the easiest way to coordinate the best course of action for this "extra" functionality.

Regarding v1.6, I am using the redirect_stdio, which was not available. I can easily switch to redirect_stdout and redirect_stderr. I will make the changes when we migrate this function to the correct package 😄

Thank you!

gdalle commented 5 months ago

Thanks for the ping @simonschoelly :) I definitely agree that Graphs.jl should not take on more dependencies, especially for very specific algorithms.

My recommendation would be to reimplement the LFR sampling procedure in Julia: a quick look at the wikipedia article tells me this should be feasible. I understand the temptation to wrap the original code, but given how it is presented on the authors' website (downloadable archives, not even a repo), I have severe doubts about long term maintenance and reliability. IIRC, there were similar issues with GraphsMatching.jl because it uses an unmaintained wrapper of the Blossom algorithm, where the original implementation is hosted on the author's personal website.

Doing everything in pure Julia is a bit of a hassle at first, but it will make maintenance significantly easier in the future. If you agree to do this, we can definitely help you! Just expect the usual delay in PR review, none of us have lots of time to give JuliaGraphs at the moment.

gdalle commented 5 months ago

There is a meeting this Thursday. I can join, and maybe I can also contribute some other functions/packages that I have developed?

By all means @fcdimitr, you're welcome to join! Excited to meet new contributors. All the info is on the Julia community calendar as well.

gdalle commented 5 months ago

maybe it would make sense if we would instead create a package GraphsExtra.jl (or GraphsExtras.jl) for you and then you could push your code there?

The Graphs.jl already contains various graph generation utilities like ER or SBM, so semantically I think it makes sense to put LFR (in pure Julia) with this bunch.

More generally, the LightGraphsExtras.jl repo was a weird collection of unrelated utilities. Just like I'm trying to move flow and matching code back into Graphs.jl or GraphsOptim.jl, I would love to archive these "extras", or possibly find them a better name

fcdimitr commented 5 months ago

There is a meeting this Thursday. I can join, and maybe I can also contribute some other functions/packages that I have developed?

By all means @fcdimitr, you're welcome to join! Excited to meet new contributors. All the info is on the Julia community calendar as well.

Thank you @gdalle! This functionality was a side-project that emerged while developing some community detection packages in Julia. It makes perfect sense to translate the implementation in pure Julia. I was thinking that until I finish the translation, I could share the wrapper to the C/C++ implementation as a point of comparison.

I can discuss more about it in the meeting and also discuss some other Julia graph analysis packages we have developed over the past couple of years. I would love to be able to contribute additional functionality to community detection and structure identification in networks!

simonschoelly commented 5 months ago

maybe it would make sense if we would instead create a package GraphsExtra.jl (or GraphsExtras.jl) for you and then you could push your code there?

The Graphs.jl already contains various graph generation utilities like ER or SBM, so semantically I think it makes sense to put LFR (in pure Julia) with this bunch.

More generally, the LightGraphsExtras.jl repo was a weird collection of unrelated utilities. Just like I'm trying to move flow and matching code back into Graphs.jl or GraphsOptim.jl, I would love to archive these "extras", or possibly find them a better name

I don't think extra is that weird of a name - people use that fairly often do specify "extra" dependencies. The main reason why we don't have GraphExtras.jl at the moment is that I did not find enough time to get the JuMP dependencies in LightGraphsExtras.jl working. And as mentioned above, in the future we might use the extra dependency mechanism introduced in Julia 1.9.

While I would not say, that we should not wrap code written in other languages (especially if its not in the main Graphs.jl repo) I agree that downloading archives is not something that we should strive for. So I think some kind of repo + clear versioning + clear open source license is something that we should require of all dependencies in the main Julia branch.

And if it is easy, a clear Julia version is of course preferred and then can also life in Graphs.jl - the main issue I see at the moment, is that we won't find much time to review the code - so if it is a non-trivial new algorithm then they often get stuck unmerged for months.

My suggestion here, is to add a Contrib submodule where we have some relaxed standards - but let me outline that in a new issue.

gdalle commented 5 months ago

If there are JuMP dependencies in LightGraphsExtras, can we maybe move those to GraphsOptim? I haven't yet found time to clean it up and register it but I could

fcdimitr commented 4 months ago

As per our discussion, I moved these functions to https://github.com/fcdimitr/LFRBenchmarkGraphs.jl and registered the package https://github.com/JuliaRegistries/General/pull/102043. I am closing this issue. I will reopen it when I have the Julia version of the generators ready for review. Thank you!