mjwach / two-steiner-tree-algorithms-in-java Goto Github PK

Did:
Created the EdgeArraysGraph with default options and weighted edges coming from distances of roads in OpenStreetMap roads graph. The graph was created using OSM data from geofabrik.de.
Tried the algorithm on a large graph (> 5000 vertices, > 100 randomly selected terminals).

Happened:
Got exception telling: "no more advancement is possible".

Expected:
To solve the Steiner minimum tree problem without errors.

Note:
I've double-checked the vertices and edges passed to the graph and the path should be found.

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.