Steiner minimum tree not found for the graph with fixed weight on edges.

[Latek]

Did:
I have written a JUnit test that shows the problem of finding Steiner minimum tree.

Please see the attached:
TestFixedTwoHeuristicsSteinerTree.zip

To run the test:

1. Unpack the zip file in the main project directory preserving the directory structure. ( there is only one JAVA file)
2. Download and include in the project path "junit-platform-console-standalone" Jar, for example from the Maven repository.
3. Run the JUnit test src/sl/TestFixedTwoHeuristicsSteinerTree.java

Alternatively, remove the "junit-platform-console-standalone" dependency from the src/sl/TestFixedTwoHeuristicsSteinerTree.java file (import static org.junit.jupiter.api.Assertions.assertTrue;) and assert and run the program in debug mode to see that it doesn't have the path specified in the results.

Happened:
Got missing paths resulting in the Steiner tree being not complete.

The preview of one of the missing paths:

Moreover, the algorithm also doesn't find the paths between other terminals (Steiner vertices).

Expected:
To find the Steiner minimum tree in the test so that the test would end successfully.

[Latek]

Please help me with this issue. When I've omitted the last two commits in the git tree:
d21dd1e made Mathematica output from examples more robust against errors
fe44a27 fixed embarrassing bug

then test ends with the error:
java.lang.UnsupportedOperationException: no more advancement is possible

I don't have deep enough knowledge about the algorithm itself, but something is wrong in the algorithm implementation or I am doing something wrong in the test. Please guide me or try to fix the problem. Any feedback will be appreciated.

[mjwach]

Okay, I'll look into it when next I have time (either tonight or tomorrow morning).

[mjwach]

I got your test running and worked up some drawing logic to help me understand it, but I need to spend more time to find the problem. Sorry, I'm quite busy for the next couple of days!

[Latek]

I got your test running and worked up some drawing logic to help me understand it, but I need to spend more time to find the problem. Sorry, I'm quite busy for the next couple of days!

Ok, good to know it's working and reproducible also on another machine. I'll wait. I really appreciate any help you can provide.

[mjwach]

Okay, I spent some time looking at it and I now partly understand my own code again. :) I think that one problem that's arising here is that the tree-marking algorithm does not gracefully handle edge weights of zero. Zero-weight edges were never needed in my own uses of this code, so I probably never even considered testing them. I apologize for that! It's not a very strange thing to expect to work correctly, and I would prefer that it did work correctly.

Are zero-weight edges essential in your project? If not, the easiest and fastest solution may be for you to replace the zero weights with very small weights. I seem to find that replacing the 0.0 weights in your test case with Float.MIN_NORMAL causes the test to pass. (Float.MIN_VALUE does not work, evidently because it's TOO small. Float.MIN_VALUE * 2 works, though. But it's probably safer not to go that small.) Can you make the test pass on your machine by doing that? And if so, are you satisfied with this solution?

My preference would be for weights of zero to work correctly, but it's tricky to find an elegant way to make that happen. I have an idea of how it could be done, so if you really do require weights of zero, then maybe I can make it work. But it'd be easier not to!

[Latek]

Okay, I spent some time looking at it and I now partly understand my own code again. :) I think that one problem that's arising here is that the tree-marking algorithm does not gracefully handle edge weights of zero. Zero-weight edges were never needed in my own uses of this code, so I probably never even considered testing them. I apologize for that! It's not a very strange thing to expect to work correctly, and I would prefer that it did work correctly.

Are zero-weight edges essential in your project? If not, the easiest and fastest solution may be for you to replace the zero weights with very small weights. I seem to find that replacing the 0.0 weights in your test case with Float.MIN_NORMAL causes the test to pass. (Float.MIN_VALUE does not work, evidently because it's TOO small. Float.MIN_VALUE * 2 works, though. But it's probably safer not to go that small.) Can you make the test pass on your machine by doing that? And if so, are you satisfied with this solution?

Great you have found it! Yes, the test passes on my machine too after replacing zero with Float.MIN_NORMAL. And yes, I'm satisfied. I think it will work for me for now. I got areas (islands) with zero-weight edges that I need to connect together with Steiner minimum tree. But I think I could live with the small, non-zero weight for now. It will probably have a very limited impact on where to leave the island because there probably will still be some edges with higher weights included in paths between those islands.

My preference would be for weights of zero to work correctly, but it's tricky to find an elegant way to make that happen. I have an idea of how it could be done, so if you really do require weights of zero, then maybe I can make it work. But it'd be easier not to!
Ok, but it would be nice to have the limitation at least in the project documentation, and maybe see the solution in the long run. I'll report the issue in the future if I'll find some corner case where it won't work for me.

Thank you for your support!