runeksvendsen/bellman-ford

Haskell translation of Sedgewick & Wayne's Bellman-Ford implementation

bellman-ford's Issues

Don't use `System.Random.Shuffle.shuffleM` in `IO` to avoid non-determinism

Make the shuffling depend on the seed so failing test cases can be reproduced

Test suite failure for `/multiplicative (positive weights).QuickCheck/`

multiplicative (positive weights)
        SmallCheck: OK
          190 tests completed
        QuickCheck: FAIL (0.10s)
          *** Failed! (after 50 tests and 2 shrinks):
          Exception:
            distTo source /= zero
            CallStack (from HasCallStack):
              error, called at src/Data/Graph/BellmanFord.hs:316:13 in bellman-ford-0.1.0.0-inplace:Data.Graph.BellmanFord
          [TestEdge {getFrom = "=d7oh\92566\ETBt\DC3k\992320\ACKN*[\1003745r\38120y\NAKIty\ACKY\SO", getTo = "eTme t\rpR[x\NAK\USD", getWeight = 16.8},TestEdge {getFrom = "cA8\FSvY{G\GSIC4G=\ENQs\994057n\50237QUIdijT\832[72](https://github.com/runeksvendsen/bellman-ford/actions/runs/6182991083/job/16783808837#step:9:73)\DEL\SOH]2\50735#l6!?\111150", getTo = "\n@l\169580gl9\63647\CANn!\DLE\r\NULwhX\175293Y9 \SO\4698\69383\&3RS\1016403t\1066628L\15537U\v47\v\28100\ETX\158902\FSQ", getWeight = 21.678571428571427},TestEdge {getFrom = "\140430\1046479\ESC\1088417\"\v\FS\SO", getTo = "RZ[\DC4", getWeight = 5.0},TestEdge {getFrom = "\SUB\1069004g\197646\DC1\DLE\FSr$\189369)% (\151881\SUBQn1\ENQ\118903M\4407\t\EM\18918\RS}", getTo = "C6H\60800\33337h@Gk\1107295_\EOTuO/!}\1086438", getWeight = 0.45454545454545453},TestEdge {getFrom = "lYY]\42616~\GS\146858ad-8ZK\198542C7gZ7jJ\1066915\1045393Q\SYNA!\135837u>\US(\DC4\1018793I\170049DK\1101109\DC3L", getTo = "3\ETX\95887#m\70516=\142433qA\123641\153829\126256u\1036397\141588QK\54604\SI{\60299\194856\&1(-\SOu", getWeight = 10.0},TestEdge {getFrom = "\83494\1008691\DC3\1035230AM\1106845F-\DC2Fk,#8y\154046f;G\b\1093513'sel\120017o=\123620s=pn\998647V\NUL9Q\160559:RF*\26576\1021151s", getTo = "~\NAK\154013>\ETX)\61352\"\NULR", getWeight = 14.0},TestEdge {getFrom = "\NAK\n\CANb\190898\SO\ETB\1017546}lE*\1028491o^\1111972@\36147&\151571f\ESC^b0\1050735\148218\RSP{\US\SID\1113109k\f\1055319\998304\r\1063893\ACK\999031,`9", getTo = "X9\145154FC5!", getWeight = 19.0},TestEdge {getFrom = "\97569\DC3 \DC4\1013772Vq\ACKi\1080353EC\US%\18662\"", getTo = "rZ|)}hh\42943\ESCm1\GS\96087\154457V\a\1031509ef,5\SOH", getWeight = 0.5714285714285714},TestEdge {getFrom = "-M\nO[\STX\176838D\FSZ\CAN)\ACK\10636z", getTo = "!bp\STX\RS\SO\EOT\US\DC2\1048366\4187\SO\158140\f\1094977xJpgJ\1047955\1001192zU\127247\160928\1110610 9w\1050367\&7O\DC3h\94503P\DLE+B {1", getWeight = 28.53846153846154},TestEdge {getFrom = "\987433vP\GS\21725\60515\&5\1065815T\1015508w`.%\1037161\&8\n\164271\1061566\&7t\EOTJ\1099883\STX;\"\999016\64724D\SUB\USMj\5878t\DEL\1055129Ew(\b\ESC\NAKHX\150114", getTo = "\1086145WY!\991635[r\1064496P\61101v\NAKmG\26827\21230c\DC3\1099423\1018267B\b[$}\23124\b\1044557\176571\EOT\ACK", getWeight = 44.27906976744186},TestEdge {getFrom = "\DC1rD\1021885\24430\SO#\1091437\177623Q\1111098\1036701dZR\EM\DC4-\983599U]bt\n\fx0", getTo = "x", getWeight = 0.7214833819108236},TestEdge {getFrom = "", getTo = "", getWeight = 0.5},TestEdge {getFrom = "\1000130@(\STX\1080701\r\ETX\83128\\l\r;\SOH%:\168514T\DC3vT\ACK\SYN\99702\1037838\62955\111353~\1007298\FS\186647\153605\DC4/d\FSJ=", getTo = "Y[\60683\51052`p\GS|\1100093y\1011467\27440\1022686u]\144103\1016317\a\12526", getWeight = 22.56},TestEdge {getFrom = "JwY]", getTo = "\1034193]\SO\DLEB;\EOTj\8145<\v\NUL\NAK+\CANj\CANWi$\25386\n'`7\28526\DC4\152864V\NUL\169634\1054096\SI\CAN\176301\1006606K5\SO\25699\\\"_\ETB/", getWeight = 0.7590380331428749},TestEdge {getFrom = "3\175752qv\USwc\6924\72121\992029\1072781\99085\1085011t9\STX\1077127\1075153Y\1094458\66624o;\96187\r\FS-n@\nzG\DEL\ESC\135614\&8S", getTo = "i\DC18;;W\171033uBS\1077794VK\138735~>_n$\1016917Jbk\DC2\\{|\STX\1111390", getWeight = 31.72972972972973},TestEdge {getFrom = "\990124U\998830JM2T\RS\EML\1107111.\DEL\ETB\tHbf\67410[Wa\SOev\989435\986330\2130{1%2{4$\tY3Zr", getTo = "\EOT~\EOT+<G\144690\1072418]\v\SUByn-\1016612\15628s>Q", getWeight = 16.0},TestEdge {getFrom = "&Q\1081159\f\170586q5:Y", getTo = "\1079595", getWeight = 32.56},TestEdge {getFrom = "\DLE\1012529b~2M\120625\fS\1054110j\131476\186875\173348zA&\1027764bdV\996038\a)I\1010726\\\146558\FS6\DEL\ETB\39348rO;\nSsI", getTo = "\DC1Q", getWeight = 0.7147901925189171},TestEdge {getFrom = "\187748\148581\STXz<')", getTo = "UcbB9\ESC\1051043n\FS(\1110727\rQ|\"\997276\178363\1030605y\NAKGk\1006338E]o\NUL\1110275\GS\STXPnK\25319um8\fb\97123j\1032757z\US", getWeight = 47.21052631578947},TestEdge {getFrom = "b\FS\14186!", getTo = "er\23736!$\1009042Zae\65769 \FSzQ[s\DC3lo\DLE{\120482=\DEL6\ENQC#)", getWeight = 0.375},TestEdge {getFrom = "\153\1025345\fq\vD\1021597\DC2\97290j\DELgst\1043200\FSC7\GS`\t", getTo = "\FSb\171787\ACK)e\SYN\22512\12723}U\SI\177485gCwn\FS\38761J~\145876y\1078037\1026845$\SOHDR3r", getWeight = 0.3333333333333333},TestEdge {getFrom = "Q\ETX\FS\DEL<\DC38FWK\9496=\CAN\994436)\SYN\f_B\137633\FS\1107859$\37757Rd,\\69&\EM", getTo = "3~=n\DC4+K\ETBK7\1035437\33429\1019306D:)T0\987443?H\SO\\\164330\DEL0Qk{\1000227R\1039402\SUBY", getWeight = 29.0},TestEdge {getFrom = "\ENQ\\\984437\34820b01b_\STX+r|\DC4%q\991836\1743GtXF\1061330b\171088\DC4I\33601\134831\&4s\\\994610\a\DC42I", getTo = "Q\"PN\127524\32933-\NAK;\1004068yGT;\1000436a\1008622", getWeight = 26.413793103448278},TestEdge {getFrom = "\SI\150160\GS\STX\29195c\DC4`\24044,\ETBJ&[;DM1\ESC*\37183\59721;\30910\STXY\fuLj\14234rt\1094712\tc\62713\&7N\t.Kd<-1\1043501Fn", getTo = "\59368\FSNx\vK\FS\761\987318\184744F\STX\ESC\DC3\RSOW7\1010068\96526\b,wtufT\57973", getWeight = 42.0},TestEdge {getFrom = "\ENQ]Z\29417\&6(p%\EOT#\\\r4\136734$<\175090\CANE\74059i6\182722\&0yTII\149399fdf\996398\1070583:t\SI\DC3\1112748\SOZ\CANS", getTo = "\990310\187689\32868G\49721\&4\42308O\998956s\1042630\\\132500ONk1>%\987894TLJkP", getWeight = 0.43231868809891094}]
          Use --quickcheck-replay=130492 to reproduce.
          Use -p '/multiplicative (positive weights).QuickCheck/' to rerun this test only.

Input test data (list of edges):

[ TestEdge {getFrom = "=d7oh\92566\ETBt\DC3k\992320\ACKN*[\1003745r\38120y\NAKIty\ACKY\SO", getTo = "eTme t\rpR[x\NAK\USD", getWeight = 16.8}
, TestEdge {getFrom = "cA8\FSvY{G\GSIC4G=\ENQs\994057n\50237QUIdijT\832[72](https://github.com/runeksvendsen/bellman-ford/actions/runs/6182991083/job/16783808837#step:9:73)\DEL\SOH]2\50735#l6!?\111150", getTo = "\n@l\169580gl9\63647\CANn!\DLE\r\NULwhX\175293Y9 \SO\4698\69383\&3RS\1016403t\1066628L\15537U\v47\v\28100\ETX\158902\FSQ", getWeight = 21.678571428571427}
, TestEdge {getFrom = "\140430\1046479\ESC\1088417\"\v\FS\SO", getTo = "RZ[\DC4", getWeight = 5.0}
, TestEdge {getFrom = "\SUB\1069004g\197646\DC1\DLE\FSr$\189369)% (\151881\SUBQn1\ENQ\118903M\4407\t\EM\18918\RS}", getTo = "C6H\60800\33337h@Gk\1107295_\EOTuO/!}\1086438", getWeight = 0.45454545454545453}
, TestEdge {getFrom = "lYY]\42616~\GS\146858ad-8ZK\198542C7gZ7jJ\1066915\1045393Q\SYNA!\135837u>\US(\DC4\1018793I\170049DK\1101109\DC3L", getTo = "3\ETX\95887#m\70516=\142433qA\123641\153829\126256u\1036397\141588QK\54604\SI{\60299\194856\&1(-\SOu", getWeight = 10.0}
, TestEdge {getFrom = "\83494\1008691\DC3\1035230AM\1106845F-\DC2Fk,#8y\154046f;G\b\1093513'sel\120017o=\123620s=pn\998647V\NUL9Q\160559:RF*\26576\1021151s", getTo = "~\NAK\154013>\ETX)\61352\"\NULR", getWeight = 14.0}
, TestEdge {getFrom = "\NAK\n\CANb\190898\SO\ETB\1017546}lE*\1028491o^\1111972@\36147&\151571f\ESC^b0\1050735\148218\RSP{\US\SID\1113109k\f\1055319\998304\r\1063893\ACK\999031,`9", getTo = "X9\145154FC5!", getWeight = 19.0}
, TestEdge {getFrom = "\97569\DC3 \DC4\1013772Vq\ACKi\1080353EC\US%\18662\"", getTo = "rZ|)}hh\42943\ESCm1\GS\96087\154457V\a\1031509ef,5\SOH", getWeight = 0.5714285714285714}
, TestEdge {getFrom = "-M\nO[\STX\176838D\FSZ\CAN)\ACK\10636z", getTo = "!bp\STX\RS\SO\EOT\US\DC2\1048366\4187\SO\158140\f\1094977xJpgJ\1047955\1001192zU\127247\160928\1110610 9w\1050367\&7O\DC3h\94503P\DLE+B {1", getWeight = 28.53846153846154}
, TestEdge {getFrom = "\987433vP\GS\21725\60515\&5\1065815T\1015508w`.%\1037161\&8\n\164271\1061566\&7t\EOTJ\1099883\STX;\"\999016\64724D\SUB\USMj\5878t\DEL\1055129Ew(\b\ESC\NAKHX\150114", getTo = "\1086145WY!\991635[r\1064496P\61101v\NAKmG\26827\21230c\DC3\1099423\1018267B\b[$}\23124\b\1044557\176571\EOT\ACK", getWeight = 44.27906976744186}
, TestEdge {getFrom = "\DC1rD\1021885\24430\SO#\1091437\177623Q\1111098\1036701dZR\EM\DC4-\983599U]bt\n\fx0", getTo = "x", getWeight = 0.7214833819108236}
, TestEdge {getFrom = "", getTo = "", getWeight = 0.5}
, TestEdge {getFrom = "\1000130@(\STX\1080701\r\ETX\83128\\l\r;\SOH%:\168514T\DC3vT\ACK\SYN\99702\1037838\62955\111353~\1007298\FS\186647\153605\DC4/d\FSJ=", getTo = "Y[\60683\51052`p\GS|\1100093y\1011467\27440\1022686u]\144103\1016317\a\12526", getWeight = 22.56}
, TestEdge {getFrom = "JwY]", getTo = "\1034193]\SO\DLEB;\EOTj\8145<\v\NUL\NAK+\CANj\CANWi$\25386\n'`7\28526\DC4\152864V\NUL\169634\1054096\SI\CAN\176301\1006606K5\SO\25699\\\"_\ETB/", getWeight = 0.7590380331428749}
, TestEdge {getFrom = "3\175752qv\USwc\6924\72121\992029\1072781\99085\1085011t9\STX\1077127\1075153Y\1094458\66624o;\96187\r\FS-n@\nzG\DEL\ESC\135614\&8S", getTo = "i\DC18;;W\171033uBS\1077794VK\138735~>_n$\1016917Jbk\DC2\\{|\STX\1111390", getWeight = 31.72972972972973}
, TestEdge {getFrom = "\990124U\998830JM2T\RS\EML\1107111.\DEL\ETB\tHbf\67410[Wa\SOev\989435\986330\2130{1%2{4$\tY3Zr", getTo = "\EOT~\EOT+<G\144690\1072418]\v\SUByn-\1016612\15628s>Q", getWeight = 16.0}
, TestEdge {getFrom = "&Q\1081159\f\170586q5:Y", getTo = "\1079595", getWeight = 32.56}
, TestEdge {getFrom = "\DLE\1012529b~2M\120625\fS\1054110j\131476\186875\173348zA&\1027764bdV\996038\a)I\1010726\\\146558\FS6\DEL\ETB\39348rO;\nSsI", getTo = "\DC1Q", getWeight = 0.7147901925189171}
, TestEdge {getFrom = "\187748\148581\STXz<')", getTo = "UcbB9\ESC\1051043n\FS(\1110727\rQ|\"\997276\178363\1030605y\NAKGk\1006338E]o\NUL\1110275\GS\STXPnK\25319um8\fb\97123j\1032757z\US", getWeight = 47.21052631578947}
, TestEdge {getFrom = "b\FS\14186!", getTo = "er\23736!$\1009042Zae\65769 \FSzQ[s\DC3lo\DLE{\120482=\DEL6\ENQC#)", getWeight = 0.375}
, TestEdge {getFrom = "\153\1025345\fq\vD\1021597\DC2\97290j\DELgst\1043200\FSC7\GS`\t", getTo = "\FSb\171787\ACK)e\SYN\22512\12723}U\SI\177485gCwn\FS\38761J~\145876y\1078037\1026845$\SOHDR3r", getWeight = 0.3333333333333333}
, TestEdge {getFrom = "Q\ETX\FS\DEL<\DC38FWK\9496=\CAN\994436)\SYN\f_B\137633\FS\1107859$\37757Rd,\\69&\EM", getTo = "3~=n\DC4+K\ETBK7\1035437\33429\1019306D:)T0\987443?H\SO\\\164330\DEL0Qk{\1000227R\1039402\SUBY", getWeight = 29.0}
, TestEdge {getFrom = "\ENQ\\\984437\34820b01b_\STX+r|\DC4%q\991836\1743GtXF\1061330b\171088\DC4I\33601\134831\&4s\\\994610\a\DC42I", getTo = "Q\"PN\127524\32933-\NAK;\1004068yGT;\1000436a\1008622", getWeight = 26.413793103448278}
, TestEdge {getFrom = "\SI\150160\GS\STX\29195c\DC4`\24044,\ETBJ&[;DM1\ESC*\37183\59721;\30910\STXY\fuLj\14234rt\1094712\tc\62713\&7N\t.Kd<-1\1043501Fn", getTo = "\59368\FSNx\vK\FS\761\987318\184744F\STX\ESC\DC3\RSOW7\1010068\96526\b,wtufT\57973", getWeight = 42.0}
, TestEdge {getFrom = "\ENQ]Z\29417\&6(p%\EOT#\\\r4\136734$<\175090\CANE\74059i6\182722\&0yTII\149399fdf\996398\1070583:t\SI\DC3\1112748\SOZ\CANS", getTo = "\990310\187689\32868G\49721\&4\42308O\998956s\1042630\\\132500ONk1>%\987894TLJkP", getWeight = 0.43231868809891094}]

CI run: https://github.com/runeksvendsen/bellman-ford/actions/runs/6182991083/job/16783808837

Not reproducible locally (on M1 MacBook):

$ git checkout 40f8754

HEAD is now at 40f8754 Update README.md (spelling)
$ cabal run test-suite:bellman-ford-test -- --quickcheck-replay=130492 -p '/multiplicative (positive weights).QuickCheck/'
Properties
  BellmanFord
    passes 'check'
      multiplicative (positive weights)
        QuickCheck: OK (0.71s)
          +++ OK, passed 200 tests.

All 1 tests passed (0.71s)

Test suite failure for `Properties.BellmanFord.finds negative cycle.with no other edges in the graph.QuickCheck`

With Test.Tasty.QuickCheck.QuickCheckTests set to 2000.

Command to reproduce (after modifying test/Spec.hs to set QuickCheckTests to 2000):

cabal run test-suite:bellman-ford-test -- --hide-successes --quickcheck-verbose --quickcheck-replay=91682 -p '/with no other edges in the graph.QuickCheck/'

          Failed:
          NegativeCycle {getNegativeCycle = TestEdge {getFrom = "\110717.\3567\124938", getTo = "&{c\DEL", getWeight = 2.0} :| [TestEdge {getFrom = "&{c\DEL", getTo = "\SO~R", getWeight = -3.3333333333333335},TestEdge {getFrom = "\SO~R", getTo = "\110717.\3567\124938", getWeight = 1.3333333333333333}]}
          
          *** Failed! (after 1105 tests):
          no cycle found.
          expected: TestEdge {getFrom = "\110717.\3567\124938", getTo = "&{c\DEL", getWeight = 2.0} :| [TestEdge {getFrom = "&{c\DEL", getTo = "\SO~R", getWeight = -3.3333333333333335},TestEdge {getFrom = "\SO~R", getTo = "\110717.\3567\124938", getWeight = 1.3333333333333333}]
          positive edges: []
          NegativeCycle {getNegativeCycle = TestEdge {getFrom = "\110717.\3567\124938", getTo = "&{c\DEL", getWeight = 2.0} :| [TestEdge {getFrom = "&{c\DEL", getTo = "\SO~R", getWeight = -3.3333333333333335},TestEdge {getFrom = "\SO~R", getTo = "\110717.\3567\124938", getWeight = 1.3333333333333333}]}
          Use --quickcheck-replay=91682 to reproduce.
          Use -p '/with no other edges in the graph.QuickCheck/' to rerun this test only.

1 out of 30 tests failed (44.53s)