Opened 11 years ago

Closed 11 years ago

#341 closed defect/bug (fixed)

values from heap in route.c are not monotonic?

Reported by: pavelmachek.livejournal.com Owned by: KaZeR
Priority: major Milestone:
Component: core Version: git master
Severity: Keywords:
Cc:

Description

Ok, so there's an Dijkstra's algorithm there:

p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */

...that means that p_min->value's should come in increasing order, right? Well, after some debugging I found out that they do not; either there's something very wrong with my reasoning, or there's nasty bug hidden in somewhere. I'm getting

end 817 len 266 vs 285 (0x137b84,0x5d57f7)

got smaller than minimum, something is wrong here

...with my debug prints. I'll attach my debugging hacks.

Attachments (1)

delme (2.5 KB) - added by pavelmachek.livejournal.com 11 years ago.
these debug checks show the problem

Download all attachments as: .zip

Change History (3)

Changed 11 years ago by pavelmachek.livejournal.com

these debug checks show the problem

comment:1 Changed 11 years ago by pavelmachek.livejournal.com

AFAICT this shows the problem:

end 547 len 100 vs 605 (0x137b9e,0x5d5774) replace_start p=0x850b038 el=0x8601338 val=547 ### we replace_start with value 547

end 756 len 309 vs 138 (0x137bc2,0x5d57fa)

extract p=0x850b418 free el=0x816f710 min=462, 0x137b9c, 0x5d58f2 ### then extract min=462

begin 1063 len 601 vs 138 (0x137bc2,0x5d57fa)

begin 616 len 154 vs 2147483647 (0x137b5b,0x5d58f6) insert_end p=0x850af18 el=(nil) val=616 el new=0x816f710

end 919 len 457 vs 2147483647 (0x137c59,0x5d58df) insert_start p=0x8503410 el=(nil) val=919 el new=0x83864d8

extract p=0x850b2c0 free el=0x86012e8 min=551, 0x137b17, 0x5d57de ### and now extract should give us 547; but we got 551.

begin 839 len 288 vs 2147483647 (0x137a9f,0x5d57d1) insert_end p=0x850b320 el=(nil) val=839 el new=0x86012e8

end 1163 len 612 vs 2147483647 (0x137b04,0x5d58dd) insert_start p=0x850b380 el=(nil) val=1163 el new=0x8386500

end 817 len 266 vs 285 (0x137b84,0x5d57f7)

*got smaller than minimum, something is wrong here extract p=0x850b038 free el=0x8601338 min=547, 0x137b9e, 0x5d5774 begin 647 len 100 vs 447 (0x137bc9,0x5d5778)

comment:2 Changed 11 years ago by Tinloaf

  • Resolution set to fixed
  • Status changed from new to closed

You were right, seems like either the fibonacci heap implementation (which is not written by us...) had a bug, or our compare function (which I guess is unlikely, since that one was fairly easy). It works now, in revision 2196. Thanks for the hint!

Note: See TracTickets for help on using tickets.