update graph_algorithm for API changes in igraph 0.10

[szhorvat]

This PR is intended to help with updating HAL for the API changes in igraph 0.10.

The basics are there, and it should work, but I would like to ask for a HAL developer to take over and finalize this PR. I hope this is useful, but feel free to do with it as you please.

Changes:

• Updates code for igraph 0.10
• Fixed memory leak when creating graph (edges vector was not destroyed).
• Replaces FindIGraph.cmake with igraph's native CMake support

TODO:

• [ ] Update install_dependencies.sh.
• [ ] Decide whether communities_multilevel should be re-enabled

[szhorvat]

I thought a bit about this, and I would not recommend trying to write code which is compatible both with igraph 0.9 and 0.10. The API has changed significantly in 0.10. Previous versions used the double type for indexing (because igraph was originally an R package, and R has no support for 64-bit integers to this day—it just uses doubles). igraph 0.10 received a major internal cleanup and now uses a proper integer type to represent all index-like quantities. It also has proper 64-bit support. Since this was a major breaking change that affected nearly all functions, we took the opportunity to make many other breaking changes wherever it was useful. This is all part of the journey towards a 1.0 release with a stable, and hopefully much cleaner API.

All this means that it's not practical to use #ifdefs to write code that is compatible with both 0.10 and 0.9, not to mention very old versions like 0.7. HAL's usage of igraph is fairly simple, so it could be done if we really wanted to, but it would be a mess ...

My recommendation is to delay merging this PR until you are ready to bump the requirements for HAL.

It seems reasonable that at some point people have to either upgrade their operating system, or accept that they are stuck with using older software (including an older version of HAL). I'm in this situation too as I still use macOS 10.14 due to needing to use some 32-bit programs. Thus I'm stuck with older versions of most non-free software I use, and also some of the free software.

It's up to you to decide when the time is ripe to start requiring newer versions of depdencies. You are right that Ubuntu 20.04 is still more popular than 22.04.

---

Some potential solutions for Ubuntu 20.04:

Ubuntu comes with snap pre-installed since 16.04, and installing a recent CMake is very easy with a single command: snap install --classic cmake. Snaps are available for many platforms, including x86_64, aarch64, ppc64le, s390x, so no one will be left out. Those users who are averse of snap can also use https://apt.kitware.com/

Once the CMake problem is solved, there's still the issue of current Ubuntu versions not having igraph 0.10. To make the life of your users easy, you might choose to bundle igraph as a git submodule, like in cmake-project-2 here: https://github.com/igraph/igraph-example If a compatible version of igraph is present on the system, you can use that, and otherwise fall back to the bundled version.

We use a similar approach in igraph: all non-optional dependencies are bundled, and so are some of the optional ones. If an external version of the dependency is not found, the internal copy is used. The target audience of igraph is mainly researchers, not programmers, and we wanted to make it as easy as possible for them to install it.

Of course igraph is not a small package, so you might consider it too heavy for bundling ... what some packages do is that they auto-download dependencies when they are not present on the system (e.g. ccache does this).

[joern274]

@szhorvat your ideas about the best way how to integrate igraph under Ubuntu 20.04 are well thought out and very convincing. I have only two comments to add:

1. You are right that using #ifdefs to support both igraph 0.10 and older versions will violate best practice rules (aka "mess"). However, it will be very easy to do the cleanup the moment we drop support for old Ubuntu versions in years to come. In my eyes this option is not completely off the table although I understand it is ugly.

2. I agree that installing packages via snap is very easy even for the unexperienced user. However, instead of offering CMake in order to compile the igraph 0.10 submodule we should offer a ready-to-use HAL binary with the latest igraph version already included, don't you think so?

[szhorvat]

@joern274 I'm sorry about the late response. Unfortunately I'm overwhelmed at the moment and wouldn't have time to make such as #ifdef based solution work and ensure that it works with all versions between 0.7 and 0.10. 0.7 is extremely ancient, from before when I got involved with igraph in 2015. I would still not recommend this solution, as it seems to be that the differences are great enough that it would lead to two almost entirely separate implementations for <= 0.9 and >= 0.10 anyway. The move to representing indices with igraph_integer_t affects almost every function.

Unfortunately from here on I need to leave it to you do use this PR now or use it as a reference at a later time. I hope it'll be useful for upgrading the code to igraph 0.10 whenever you choose to make that move. If you have any igraph specific questions, feel free to ask.

---

2. we should offer a ready-to-use HAL binary with the latest igraph version already included

That's definitely easiest for users (and what I prefer in the role of a user 🙂 ), but for producing ready-to-use binaries, moving to an igraph version not included in Ubuntu 20.04 is not a problem, since you are in full control of the machine where binaries are produced. Or am I misunderstanding what you mean?

[SJulianS]

will (finally) be solved in feature/latest_igraph by rewriting / cleaning up the entire plugin

[szhorvat]

Let me know if you want feedback on the update / igraph API use.

Note that igraph 1.0 is coming in a few months, and will bring more breaking changes. These changes will be mostly localized to specific functions, an adapting using #ifdefs should be feasible. They probably won't affect the most-used part of the igraph API.