Thanks, this is great, and will make it much easier to continue!

Can you please remove the accidentally committed .DS_Store files? Generally, you can look at https://github.com/igraph/igraph/pull/2288/files and check if there are any unintended changes are present.

Codecov Report

❌ Patch coverage is 93.84615% with 12 lines in your changes missing coverage. Please review.
⚠️ Please upload report for BASE (main@251091a). Learn more about missing BASE report.

@@           Coverage Diff           @@
##             main    #2288   +/-   ##
=======================================
  Coverage        ?   84.35%           
=======================================
  Files           ?      381           
  Lines           ?    62412           
  Branches        ?    12252           
=======================================
  Hits            ?    52650           
  Misses          ?     9762           
  Partials        ?        0           

Just wondering if there is any further action to be taken by us.

Just wondering if there is any further action to be taken by us.

Thank you, not at the moment. I also needed to deal with some other PRs. I will try to get back to this in February, but until then I'm overwhelmed.

Could you add the function to src/CMakeLists.txt and the test to tests/CMakelists.txt? Then the tests will run.

Tests you could add:

• A graph with 1 vertex, no edges.
• A graph with a loop connecting a vertex to itself.
• A terminal given multiple times. What should happen?
• CHECK_ERROR on a terminal out of bounds.

K_7_Unit graph test is currently not checked like the others.

review notes: I made a brute forcer, which confirms that the resulting trees in the tests have minimum weights.
I've put it here: https://github.com/GroteGnoom/igraph/tree/feat/steiner.

Comments on the algorithm. These are a bit preliminary, because I don't have a complete overview of how the algorithm works. But I just wanted to write things down things I noticed.

generateSubsets:

• It overflows when 2 ^ terminals > max integer_t. We probably want to add a check for that.
• i = 0 never produces any subsets, so can be skipped.
• The number of subsets generated is the number of 1s in the binary representation of i, so i=1 and i=2 can only produce one subset, so they can also be skipped.
• I also wonder if it might efficient to let j stop based on i. Probably not worth the effort.
• Why do you need to check if a subset already exists?

fetchIndexofMapofSets:

• Why do you add this function instead of using the at or find map methods?

steiner_dreyfus_wagner:

• You are now also checking weights (for negative numbers, etc.) if they are not provided by the user and they are all set to 1. This is not necessary.
• In some algorithms we do + weight[edge] if we have weights, and + 1 otherwise. In other algorithms (including this one) we generate a vector of 1 weights. This does matter for performance, but I don't know what's best here.
• I think we leak memory in the case of no weights and no terminals. The weights are initialized, and then the function returns without destroying them because there's no terminals. The same problem occurs when no_of_terminals == no_of_nodes.
• If negative weights are not supported, I wonder why the paper by Dreyfus and Wagner uses Floyd as a reference to find shortest paths.
• If you don't use negative weights, are nodes that are further away from any terminal than any other terminal ever relevant?

Is the Steiner Tree algorithm available now in March 2023?

The PR is still unmerged; you can try checking out this branch and compiling it on your own if you want to use the code in this PR, but it's not in an official release yet.

I was wondering whether there are more steps that have to be taken from our end for this PR in terms of testing. I was thinking if there's any update about the code review.

Maybe I have time this weekend or the weekend after to take another look.

I checked again, added some tests, and I can't seem to find any inputs where your algorithm goes wrong (if I remember correctly some errors could be handled better). I haven't checked the code itself, so I'll have a talk with my colleagues about merging it like this.

All right 🥳 we will look at the code and the docs to see if it still needs work, but the functionality seems there :) So thank you for all your work, and we'll take it from here to get it merged!

@GroteGnoom ask me for a review when you are done with this and I'll have a final look before it is merged.

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 14 days if no further activity occurs. Thank you for your contributions.

hi, rechecking on this. if we have to do any work