does threshold work with bidirectional elementary=true direction=both

[mgalati13]

I have an example that finds -15 with maxtime=60 seconds.

If I then set threshold=-0.1 and maxtime=60 seconds, it stops on time at 60 seconds and still gives -15. If I then set threshold=-0.1 and maxtime=80 seconds, it stops on time at 80 seconds and still gives -15.

When I look at checkValidLabel, all the labels it is checking against threshold have weight=0, so it won't stop on threshold.

Is this a known issue? It is a bit complicated to create an independent test case since my data is big. So, I wanted to check if this is a known issue first.

[mgalati13]

I am attaching some debug log I added after running for 10 seconds. Even after just 10 seconds it finds -15, but does not stop on threshold. I print out the intermediate_label (which is what is checked against threshold) and current_label at each step. I also print out the final label.

Source=71 Sink=83

I am not sure where the final label came from after the join: Label(node=83, weight= -15.7627, res[0]=2, partial_path=[71,9,79,62,13,83,])

I do see in the current_label: Label(node=62, weight= 127.048, res[0]=27, partial_path=[83,13,62,])

But, I don't see anything forward with 71,9 debug.txt .

[torressa]

Thanks again @mgalati13! Labels are not merged until the very end, so unless a full Source-Sink path is found that fulfills the bound condition, the search will not stop. So that behavior is expected.

To debug that final label, you can print the labels before they are merged so you can see exactly which ones are being picked. Print fwd_label and bwd_label just before this call https://github.com/torressa/cspy/blob/1c25c1064cd492e997d053e1248caf81646f995a/src/cc/bidirectional.cc#L656

To fix this, one could merge forward and backward labels if/when they reach an adjacent node, however, this may make performance go down (?). I have no plans of implementing this, but feel free to look into it. Labels for each direction are in separate Search objects and they are indexed by node, at efficient_labels. So if:

1. you have a new label say forward at node i
2. there's an edge i->j
3. and, efficient_labels[j] is not empty in the backward direction

then the labels in may be eligible for merging.

Using the members of https://github.com/torressa/cspy/blob/beb3cb829f3932bf07bf3951eb82aeba5a560a5d/src/cc/bidirectional.h#L150

If 1. 2. and 3. is true, then fwd_search_ptr_->efficient_labels[i] may be joined with bwd_search_ptr_->efficient_labels[j] and we could have a candidate label for termination.

[torressa]

Added this, also there was a bug in the Python interface. Still remains to test if it is actually helpful.