Head's Up! These forums are read-only. All users and content have migrated. Please join us at community.neo4j.com.
03-08-2021 03:43 PM
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();
All the sessions of the conference are now available online