BiDirectional in forward direction is faster than both directions

[torressa]

Describe the bug For some reason, the forward direction tends to be faster than the bidirectional version. This can be the case for some problems, but I've experienced it across several problems (Beasley and Christofides, Solomon and Augerat).

To Reproduce Run any of the Beasley and Christofides, Solomon or Augerat instances with direction="forward" and then with direction="both" and see.

The first can be ran

cd tools/dev/
./build -b -s

The Solomon + Augerat can be ran by using vrpy (changing directions in subproblem_cspy.py) and running

python3 -m pytest -k cspy -s -v benchmarks/

Suggestions Starter

• [x] Merge the Search functionality (src/cc/search.h) into BiDirectional. I'm not entirely sure this would work, but I had the same issue when I had this structure in Python.
• [x] Revise joining procedure

Further

• [x] Use a proper graph implementation (#63, unrelated, but can't hurt).
• [ ] Come up with a way of stopping the search early using the threshold (it is easy in the forward direction as paths are fully formed, whereas in both directions, labels have to merged then checked)
• [x] Valgrind

[torressa]

Updated WIP in branch patch66

[torressa]

Finally working as expected. On a solomon instance (for Beasley bencharchmarks, see https://github.com/torressa/cspy/issues/65#issuecomment-824173114) The number of stops is the primary resource. I suspect changing this to match the most restrictive one (e.g. time), will see further improvements.

Table of time in seconds until optimal solution (using vrpy)

# of nodes	both	fwd
2	0.03	0.03
3	0.05	0.05
4	0.05	0.06
5	0.07	0.06
6	0.07	0.07
7	0.15	0.15
8	0.17	0.17
9	0.20	0.24
10	0.35	0.52
11	0.44	0.51
12	0.63	1.07
13	1.60	1.04
14	1.46	1.57
15	1.88	1.95
16	2.27	2.25
17	2.17	2.39
18	1.37	1.64
19	3.43	3.46
20	4.45	4.36
21	4.18	3.70
22	4.16	4.36
23	6.29	5.63
24	5.44	6.92
25	7.27	8.87
average	2.01	2.13