free(): invalid next size (fast)

[vlarmet]

Hi,

First, thank you for this repo, there are so few Algorithm B implementations on the web.
I'm trying to implement Algorithm B in C++ and I want to include it in the R library cppRouting.
I want to try your sequential implementation with a pretty large graph (>200k nodes, 600k edges) with a small OD matrix (9 origins, 9 destinations).
So I run :
bin/tap 0.01 1 <network_file> <demand_file>

After only one iteration and a small gap achieved, here is the message I got :

free(): invalid next size (fast) Aborted (core dumped)

Something is going wrong because the resulting flows are inconsistent : zero flow coming from an origin node.
I precise that :

• all OD pairs described in demand file are connected and feasible
• I set a fixed capacity of 2000 for all roads.
• your implementation work very well with smaller networks like SiouxFalls or Chicago

I attach a zip containing the two files describing network and demand, plus the result of your implementation and the result coming from my implementation of BFW algorithm with a gap set to 0.01.

Thank you very much for your help !

issues_tap.zip

[sboyles]

Thanks so much for pointing out this issue. I will try to take an in-depth look over the next week.

I took a quick look at your files, one possible issue is that in the TNTP network format all centroids (origins + destinations) have to be numbered consecutively starting from 1. Your network does this with the origins (nodes 1-9) but your trips file has higher-numbered destinations (e.g. 8975, 696). Does the issue persist if the nodes are re-numbered so that both origins and destinations have the lowest numbers (and the tag set to the largest of these)?

Again I will try to take a closer look to confirm that this is the issue (and regardless our code should issue an error indicating destinations which are "out of range").

[vlarmet]

Thank you for your answer!

I have tried this option : rename the destination nodes from 10 to 18 in the network and trip files, and it seems to work.