Skip to content

Cannot find initial connected bush #25

@finnwiz

Description

@finnwiz

I ran a simple test (test_net.txt and test_trips.txt), which worked and was great (and got the expected result)!

./bin/tap .1 1 test_net.txt test_trip.txt
Nodes, arcs, zones, thrunode: 4 6 2 0
Distance factor, toll factor: 0.000000 0.000000
4 nodes, 6 arcs, and 2 zones
File read and memory allocated.
Forward and reverse star lists generated.
Starting Algorithm B...
Warning: Creating 2 artifical arcs to ensure strong connectivity.
Finalizing network setup
Finalized network setup
Creating Initial bushes
Initializing Algorithm B
Initialized flows
Read matrix 0
Creating batch 0
Finished shortest path bush preds 0
Finished shortest path bush preds 1
Created batch 0
Initialization done in 0.000 s.
Iteration 1: gap 3.534204911719327, obj 248.451103865328, time 0.000, 4 shifts
Iteration 2: gap 0.771018213410878, obj 168.877623226108, time 0.000, 26 shifts
Iteration 3: gap 0.150833572377848, obj 152.910162001144, time 0.000, 48 shifts
Iteration 4: gap 0.020958208823608, obj 150.846825064805, time 0.000, 70 shifts

But when I run my "real" problem (using net.txt and trips.txt), I get an exciting error:

npadon@HO1-PW03D5WL:~/tap-b$ ./bin/tap .1 1 net.txt trips.txt
Nodes, arcs, zones, thrunode: 345843 650887 1504 0
Distance factor, toll factor: 0.000000 0.000000
345843 nodes, 650887 arcs, and 1504 zones
File read and memory allocated.
Forward and reverse star lists generated.
Starting Algorithm B...
Warning: Creating 14677 artifical arcs to ensure strong connectivity.
Finalizing network setup
Finalized network setup
Creating Initial bushes
Initializing Algorithm B
Initialized flows
Read matrix 0
Creating batch 0
Finished shortest path bush preds 0
Fatal error: Cannot find initial connected bush.

I tried with binaries from both make and make parallel. In the full log, I can also see that some of the bush prediction are -1 (ostensibly the value of IS_MISSING and the cost is infinite...). Additionally, I created a different version of net.txt that had fully bi-directional edges (some of the links in the attached net.txt are only one-way) - but got the same error.

I also confirmed that my graph (both the one in net.txt and the crazier one with bi-directional links) is strongly connected (using igraph) so would appreciate any pointers (even if general).

Thanks in advance.

net.txt.gz
test_net.txt
test_trip.txt
trips.txt
full_log.txt.gz

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions