cancel
Showing results for 
Search instead for 
Did you mean: 

Issue of GDS1.5.0 k spanning tree implementation, bug at the compute() method?

Jean
Node Link

Hi all,
I'v checked the source of KSpanningTree.java, and find that there may be a bug at the end of the compute() function.
I think that a k spanning tree shoud be a tree grows from the started node in a serialized way, and couldn't be implemented in a concurrent way, while a whole sapnning tree can. But the algo above just delete the most minimum arcs, and this can't ensure that the result graph is connected with the root, just as the test case shows.
So I write a k spanning tree algo that meets my need by merging KSpanningTree.java and Prim.java together, that needs an aditional parameter of k on the base of SpanningTreeConfig.java, and needs a new configuration interface class(such as MyKSpanningTreeConfig.java) and a class to implement it. Now the problem is that, it seems that there's no way to write such an interface , as there's no way to implement it, I just can't find the source code of org.neo4j.graphalgo.spanningtree.SpanningTreeConfigImpl.java, to have a look. And I can't extend the class to implement my configuration also, as it's a final class.
Is there any solution other than hacking the source code of GDS to add a parameter k on the base of a SpanningTreeConfig?
I'v tested my implementation and the result is O.K. for me, but I think the best way is to implement my configuration class to get the k parameter on the base of the opensource library, instead of hacking the GDS source.
I‘v also posted an issue at the GDS Github project including the source of my implementation.

Best regards
Jean

// remove k-1 relationships
for (int i = 0; i < k - 1 && running(); i++) {
int cutNode = priorityQueue.pop();
parent[cutNode] = -1;
}
// This line just returns the sapnning tree generated by Prim algo directely, ignoring the arcs selection algo above, so the result is incorrect.
this.spanningTree = prim.getSpanningTree();
0 REPLIES 0
Nodes 2022
Nodes
NODES 2022, Neo4j Online Education Summit

On November 16 and 17 for 24 hours across all timezones, you’ll learn about best practices for beginners and experts alike.