search

mojaie / MolecularGraph.jl

Graph-based molecule modeling toolkit for cheminformatics
MIT License
192 stars 28 forks source link

outerplanarity test failure on Julia 1.6 #44

Closed timholy closed 3 years ago

timholy commented 3 years ago

With #42 on its way to being fixed, the next failure is here:

Julia 1.5:

julia> Graph.outerplanaritytest(laddergraph(20))
true

Julia 1.6:

julia> Graph.outerplanaritytest(laddergraph(20))
false

In case it's useful, here's the output measured on each with verbose=true.

Julia 1.5 ```julia julia> Graph.outerplanaritytest(laddergraph(20); verbose=true) MolecularGraph.Graph.DFSState(PlainGraph([Dict(98 => 41,3 => 3,1 => 2), Dict(4 => 4,63 => 41,1 => 1), Dict(2 => 4,3 => 1,6 => 5,85 => 41), Dict(7 => 6,4 => 2,83 => 41,2 => 3), Dict(9 => 7,87 => 41,5 => 6,6 => 3), Dict(7 => 4,10 => 8,81 => 41,5 => 5), Dict(9 => 5,69 => 41,8 => 8,12 => 9), Dict(13 => 10,10 => 6,8 => 7,79 => 41), Dict(11 => 10,70 => 41,15 => 11,12 => 7), Dict(13 => 8,72 => 41,16 => 12,11 => 9), Dict(14 => 12,66 => 41,15 => 9,18 => 13), Dict(14 => 11,16 => 10,19 => 14,97 => 41), Dict(17 => 14,21 => 15,91 => 41,18 => 11), Dict(92 => 41,19 => 12,17 => 13,22 => 16), Dict(24 => 17,21 => 13,96 => 41,20 => 16), Dict(25 => 18,65 => 41,22 => 14,20 => 15), Dict(23 => 18,78 => 41,27 => 19,24 => 15), Dict(23 => 17,25 => 16,28 => 20,59 => 41), Dict(26 => 20,77 => 41,27 => 17,30 => 21), Dict(26 => 19,31 => 22,89 => 41,28 => 18), Dict(29 => 22,67 => 41,33 => 23,30 => 19), Dict(31 => 20,34 => 24,29 => 21,80 => 41), Dict(32 => 24,36 => 25,33 => 21,90 => 41), Dict(37 => 26,32 => 23,34 => 22,82 => 41), Dict(71 => 41,35 => 26,36 => 23,39 => 27), Dict(37 => 24,35 => 25,40 => 28,73 => 41), Dict(42 => 29,94 => 41,38 => 28,39 => 25), Dict(43 => 30,86 => 41,40 => 26,38 => 27), Dict(42 => 27,74 => 41,41 => 30,45 => 31), Dict(43 => 28,60 => 41,41 => 29,46 => 32), Dict(93 => 41,48 => 33,44 => 32,45 => 29), Dict(62 => 41,49 => 34,44 => 31,46 => 30), Dict(47 => 34,61 => 41,48 => 31,51 => 35), Dict(47 => 33,75 => 41,49 => 32,52 => 36), Dict(54 => 37,50 => 36,51 => 33,76 => 41), Dict(50 => 35,55 => 38,95 => 41,52 => 34), Dict(54 => 35,53 => 38,57 => 39,84 => 41), Dict(55 => 36,53 => 37,58 => 40,88 => 41), Dict(68 => 41,56 => 40,57 => 37), Dict(58 => 38,64 => 41,56 => 39), Dict(68 => 39,77 => 19,69 => 7,80 => 22,81 => 6,89 => 20,62 => 32,98 => 1,96 => 15,82 => 24,85 => 3,91 => 13,75 => 34,60 => 30,66 => 11,83 => 4,64 => 40,59 => 18,65 => 16,87 => 5,84 => 37,73 => 26,88 => 38,92 => 14,61 => 33,72 => 10,74 => 29,95 => 36,79 => 8,90 => 23,71 => 25,63 => 2,78 => 17,86 => 28,67 => 21,93 => 31,70 => 9,76 => 35,94 => 27,97 => 12)], [(1, 2), (3, 4), (1, 3), (2, 4), (5, 6), (3, 5), (4, 6), (7, 8), (5, 7), (6, 8), (9, 10), (7, 9), (8, 10), (11, 12), (9, 11), (10, 12), (13, 14), (11, 13), (12, 14), (15, 16), (13, 15), (14, 16), (17, 18), (15, 17), (16, 18), (19, 20), (17, 19), (18, 20), (21, 22), (19, 21), (20, 22), (23, 24), (21, 23), (22, 24), (25, 26), (23, 25), (24, 26), (27, 28), (25, 27), (26, 28), (29, 30), (27, 29), (28, 30), (31, 32), (29, 31), (30, 32), (33, 34), (31, 33), (32, 34), (35, 36), (33, 35), (34, 36), (37, 38), (35, 37), (36, 38), (39, 40), (37, 39), (38, 40), (41, 18), (41, 30), (41, 33), (41, 32), (41, 2), (41, 40), (41, 16), (41, 11), (41, 21), (41, 39), (41, 7), (41, 9), (41, 25), (41, 10), (41, 26), (41, 29), (41, 34), (41, 35), (41, 19), (41, 17), (41, 8), (41, 22), (41, 6), (41, 24), (41, 4), (41, 37), (41, 3), (41, 28), (41, 5), (41, 38), (41, 20), (41, 23), (41, 13), (41, 14), (41, 31), (41, 27), (41, 36), (41, 15), (41, 12), (41, 1)], Dict{Symbol,Any}()), Dict(30 => 17,1 => 31,12 => 35,32 => 12,15 => 41,2 => 30,40 => 5,16 => 40,11 => 36,39 => 4,21 => 22,26 => 18,7 => 26,25 => 21,35 => 8,34 => 11,29 => 14,10 => 34,9 => 37,19 => 25,17 => 2,8 => 33,22 => 23,6 => 28,24 => 19,37 => 9,4 => 29,3 => 32,28 => 16,5 => 27,38 => 6,20 => 24,23 => 20,31 => 13,13 => 38,14 => 39,27 => 15,36 => 7,41 => 3,33 => 10,18 => 1), Dict(1 => 1,12 => 16,15 => 20,32 => 49,2 => 4,40 => 56,16 => 22,11 => 14,39 => 68,21 => 33,26 => 40,7 => 69,25 => 36,35 => 50,34 => 47,29 => 45,10 => 13,9 => 15,19 => 26,17 => 23,8 => 10,22 => 29,6 => 5,24 => 37,37 => 54,4 => 7,3 => 3,28 => 38,5 => 9,38 => 58,20 => 31,23 => 32,31 => 44,13 => 18,14 => 17,27 => 42,36 => 55,41 => 78,33 => 51,30 => 43), Dict{Int64,Bool}(68 => 1,2 => 0,89 => 0,11 => 0,39 => 0,46 => 0,85 => 0,25 => 0,55 => 1,42 => 1,29 => 1,58 => 1,66 => 0,59 => 0,8 => 0,74 => 0,95 => 0,57 => 0,90 => 0,20 => 1,31 => 1,14 => 1,78 => 1,70 => 0,52 => 0,33 => 1,18 => 1,69 => 1,96 => 0,26 => 1,35 => 0,83 => 0,64 => 0,65 => 0,17 => 1,49 => 1,84 => 0,44 => 1,37 => 1,4 => 1,45 => 1,13 => 1,86 => 0,67 => 0,93 => 0,94 => 0,30 => 0,1 => 1,54 => 1,47 => 1,32 => 1,77 => 0,80 => 0,40 => 1,50 => 1,82 => 0,91 => 0,43 => 1,7 => 1,75 => 0,60 => 0,34 => 0,9 => 1,87 => 0,3 => 1,61 => 0,79 => 0,38 => 1,71 => 0,48 => 0,36 => 1,76 => 0,12 => 0,98 => 0,81 => 0,16 => 1,62 => 0,21 => 0,10 => 1,19 => 0,51 => 1,22 => 1,88 => 0,73 => 0,6 => 0,24 => 0,92 => 0,53 => 0,72 => 0,28 => 0,5 => 1,23 => 0,63 => 0,27 => 0,56 => 1,97 => 0,41 => 0,15 => 1), Dict(68 => 3,2 => 32,89 => 24,11 => 37,39 => 21,46 => 17,85 => 32,25 => 40,55 => 6,42 => 14,29 => 22,58 => 5,66 => 36,59 => 3,8 => 33,74 => 14,95 => 7,57 => 9,90 => 20,20 => 40,78 => 2,31 => 23,14 => 35,70 => 37,33 => 20,52 => 11,18 => 36,69 => 3,96 => 41,26 => 24,35 => 21,83 => 29,64 => 5,17 => 38,65 => 40,49 => 11,84 => 9,44 => 12,37 => 18,4 => 29,45 => 13,13 => 33,86 => 16,67 => 22,93 => 13,94 => 15,30 => 25,1 => 30,54 => 8,47 => 10,50 => 7,32 => 19,77 => 25,40 => 16,80 => 23,82 => 19,91 => 38,43 => 16,9 => 26,75 => 11,60 => 17,34 => 23,7 => 28,87 => 27,3 => 31,61 => 10,79 => 33,38 => 15,71 => 21,48 => 13,36 => 20,76 => 8,12 => 37,98 => 31,81 => 28,16 => 34,62 => 12,21 => 41,10 => 28,19 => 39,51 => 8,22 => 39,88 => 6,73 => 18,6 => 32,24 => 41,92 => 39,53 => 9,72 => 34,28 => 24,5 => 27,23 => 1,63 => 30,27 => 25,56 => 4,97 => 35,41 => 17,15 => 36), Dict(18 => [17, 91],54 => [84, 57, 53],47 => [49, 75, 52],32 => [33, 90, 36],50 => [51, 76, 54],68 => [56],40 => [37, 73],69 => [9],16 => [14, 97],43 => [60, 46, 41],26 => [27, 77, 30],7 => [83, 4],55 => [50, 95],42 => [38, 94],29 => [31, 80, 34],58 => [55, 88],10 => [13, 79, 8],9 => [5, 87],17 => [22, 92, 19],49 => [44, 62],51 => [47, 61],44 => [45, 93, 48],22 => [25, 20, 65],37 => [32, 82],4 => [63, 1],3 => [85, 6, 2],5 => [10, 81, 7],38 => [40, 86, 43],45 => [42, 74],20 => [24, 96, 21],23 => [78],31 => [28, 26, 89],14 => [18, 66, 15],13 => [16, 72],78 => [59, 68, 69],36 => [71, 39, 35],56 => [58, 64],15 => [70, 12, 11],33 => [29, 67],1 => [98, 3]), Dict(2 => 29,89 => 3,11 => 34,39 => 15,46 => 12,85 => 3,25 => 1,66 => 3,59 => 1,8 => 26,74 => 3,95 => 3,57 => 4,90 => 3,70 => 3,52 => 7,96 => 3,35 => 18,83 => 3,64 => 3,65 => 3,84 => 3,86 => 3,67 => 3,93 => 3,94 => 3,30 => 22,77 => 3,80 => 3,82 => 3,91 => 3,75 => 3,60 => 3,34 => 19,87 => 3,61 => 3,79 => 3,71 => 3,48 => 10,76 => 3,12 => 26,98 => 3,81 => 3,62 => 3,21 => 38,19 => 35,88 => 3,73 => 3,6 => 27,24 => 2,92 => 3,53 => 6,72 => 3,28 => 1,63 => 3,27 => 2,97 => 3,41 => 14), [23, 78, 68, 56, 58, 55, 50, 54, 51, 47, 49, 44, 45, 42, 38, 43, 40, 37, 32, 36, 33, 29, 31, 26, 69, 9, 5, 7, 4, 1, 3, 10, 13, 16, 14, 15, 18, 17, 22, 20]) stem: 24, ds: [[[24], Int64[]]] Trunk cells stem: 96, ds: [[[96], Int64[]]] Next cell Next cell stem: 21, ds: [[[21], Int64[]]] Next cell Next cell Next cell inedge: 20, ds: [[[24], Int64[]], [[96], Int64[]], [[21], Int64[]]] finished: Set{Int64}() stem: 25, ds: [[[25], Int64[]]] Trunk cells stem: 20, ds: [[[24], Int64[]], [[96], Int64[]], [[21], Int64[]]] Next cell Next cell stem: 65, ds: [[[65], Int64[]]] Next cell New opposite inedge: 22, ds: [[[25], Int64[]], [[65], [24, 96, 21]]] finished: Set{Int64}() stem: 22, ds: [[[25], Int64[]], [[65], [24, 96, 21]]] Trunk cells stem: 92, ds: [[[92], Int64[]]] Next cell Merge alike stem: 19, ds: [[[19], Int64[]]] Next cell Merge alike inedge: 17, ds: [[[25], Int64[]], [[65, 92, 19], [24, 96, 21]]] finished: Set([21]) stem: 17, ds: [[[25], Int64[]], [[65, 92, 19], [24, 96]]] Trunk cells stem: 91, ds: [[[91], Int64[]]] Next cell Merge opposite inedge: 18, ds: [[[25], Int64[]], [[65, 92, 19], [24, 96, 91]]] finished: Set{Int64}() stem: 70, ds: [[[70], Int64[]]] Trunk cells stem: 12, ds: [[[12], Int64[]]] Next cell Next cell stem: 11, ds: [[[11], Int64[]]] Next cell Next cell Next cell inedge: 15, ds: [[[70], Int64[]], [[12], Int64[]], [[11], Int64[]]] finished: Set{Int64}() stem: 18, ds: [[[25], Int64[]], [[65, 92, 19], [24, 96, 91]]] Trunk cells stem: 66, ds: [[[66], Int64[]]] Next cell Merge opposite stem: 15, ds: [[[70], Int64[]], [[12], Int64[]], [[11], Int64[]]] Next cell Merge opposite inedge: 14, ds: [[[25], Int64[]], [[65, 92, 19], [24, 96, 91, 66, 70, 12, 11]]] finished: Set([19]) stem: 14, ds: [[[25], Int64[]], [[65, 92], [24, 96, 91, 66, 70, 12, 11]]] Trunk cells stem: 97, ds: [[[97], Int64[]]] Next cell Merge alike inedge: 16, ds: [[[25], Int64[]], [[65, 92, 97], [24, 96, 91, 66, 70, 12, 11]]] finished: Set([11]) stem: 16, ds: [[[25], Int64[]], [[65, 92, 97], [24, 96, 91, 66, 70, 12]]] Trunk cells stem: 72, ds: [[[72], Int64[]]] Next cell Merge alike inedge: 13, ds: [[[25], Int64[]], [[65, 92, 97, 72], [24, 96, 91, 66, 70, 12]]] finished: Set{Int64}() stem: 13, ds: [[[25], Int64[]], [[65, 92, 97, 72], [24, 96, 91, 66, 70, 12]]] Trunk cells stem: 79, ds: [[[79], Int64[]]] Next cell Merge alike stem: 8, ds: [[[8], Int64[]]] Next cell Next cell Next cell inedge: 10, ds: [[[25], Int64[]], [[65, 92, 97, 72, 79], [24, 96, 91, 66, 70, 12]], [[8], Int64[]]] finished: Set{Int64}() stem: 85, ds: [[[85], Int64[]]] Trunk cells stem: 6, ds: [[[6], Int64[]]] Next cell Next cell stem: 2, ds: [[[2], Int64[]]] Next cell Next cell Next cell inedge: 3, ds: [[[85], Int64[]], [[6], Int64[]], [[2], Int64[]]] finished: Set{Int64}() stem: 98, ds: [[[98], Int64[]]] Trunk cells stem: 3, ds: [[[85], Int64[]], [[6], Int64[]], [[2], Int64[]]] Next cell Next cell inedge: 1, ds: [[[98], Int64[]], [[85, 6, 2], Int64[]]] finished: Set{Int64}() stem: 63, ds: [[[63], Int64[]]] Trunk cells stem: 1, ds: [[[98], Int64[]], [[85, 6, 2], Int64[]]] Next cell Next cell inedge: 4, ds: [[[63], Int64[]], [[98, 85, 6, 2], Int64[]]] finished: Set([2]) stem: 83, ds: [[[83], Int64[]]] Trunk cells stem: 4, ds: [[[63], Int64[]], [[98, 85, 6], Int64[]]] Next cell Next cell inedge: 7, ds: [[[83], Int64[]], [[63, 98, 85, 6], Int64[]]] finished: Set{Int64}() stem: 10, ds: [[[25], Int64[]], [[65, 92, 97, 72, 79], [24, 96, 91, 66, 70, 12]], [[8], Int64[]]] Trunk cells stem: 81, ds: [[[81], Int64[]]] Next cell Merge alike stem: 7, ds: [[[83], Int64[]], [[63, 98, 85, 6], Int64[]]] Next cell Merge alike inedge: 5, ds: [[[25], Int64[]], [[65, 92, 97, 72, 79, 81, 83, 63, 98, 85, 6], [24, 96, 91, 66, 70, 12]], [[8], Int64[]]] finished: Set([6]) stem: 5, ds: [[[25], Int64[]], [[65, 92, 97, 72, 79, 81, 83, 63, 98, 85], [24, 96, 91, 66, 70, 12]], [[8], Int64[]]] Trunk cells stem: 87, ds: [[[87], Int64[]]] Next cell Merge alike inedge: 9, ds: [[[25], Int64[]], [[65, 92, 97, 72, 79, 81, 83, 63, 98, 85, 87], [24, 96, 91, 66, 70, 12]], [[8], Int64[]]] finished: Set([8, 12]) stem: 9, ds: [[[25], Int64[]], [[65, 92, 97, 72, 79, 81, 83, 63, 98, 85, 87], [24, 96, 91, 66, 70]]] Trunk cells inedge: 69, ds: [[[25], Int64[]], [[65, 92, 97, 72, 79, 81, 83, 63, 98, 85, 87], [24, 96, 91, 66, 70]]] finished: Set([77, 80, 89, 98, 81, 62, 96, 82, 85, 91, 75, 60, 66, 83, 64, 65, 87, 84, 88, 73, 92, 74, 61, 72, 95, 79, 90, 71, 63, 86, 67, 93, 70, 94, 76, 97]) stem: 27, ds: [[[27], Int64[]]] Trunk cells stem: 77, ds: [[[77], Int64[]]] Next cell Next cell stem: 30, ds: [[[30], Int64[]]] Next cell Next cell Next cell inedge: 26, ds: [[[27], Int64[]], [[77], Int64[]], [[30], Int64[]]] finished: Set{Int64}() stem: 28, ds: [[[28], Int64[]]] Trunk cells stem: 26, ds: [[[27], Int64[]], [[77], Int64[]], [[30], Int64[]]] Next cell Next cell stem: 89, ds: [[[89], Int64[]]] Next cell New opposite inedge: 31, ds: [[[28], Int64[]], [[89], [27, 77, 30]]] finished: Set{Int64}() stem: 31, ds: [[[28], Int64[]], [[89], [27, 77, 30]]] Trunk cells stem: 80, ds: [[[80], Int64[]]] Next cell Merge alike stem: 34, ds: [[[34], Int64[]]] Next cell Merge alike inedge: 29, ds: [[[28], Int64[]], [[89, 80, 34], [27, 77, 30]]] finished: Set([30]) stem: 29, ds: [[[28], Int64[]], [[89, 80, 34], [27, 77]]] Trunk cells stem: 67, ds: [[[67], Int64[]]] Next cell Merge opposite inedge: 33, ds: [[[28], Int64[]], [[89, 80, 34], [27, 77, 67]]] finished: Set{Int64}() stem: 71, ds: [[[71], Int64[]]] Trunk cells stem: 39, ds: [[[39], Int64[]]] Next cell Next cell stem: 35, ds: [[[35], Int64[]]] Next cell Next cell Next cell inedge: 36, ds: [[[71], Int64[]], [[39], Int64[]], [[35], Int64[]]] finished: Set{Int64}() stem: 33, ds: [[[28], Int64[]], [[89, 80, 34], [27, 77, 67]]] Trunk cells stem: 90, ds: [[[90], Int64[]]] Next cell Merge opposite stem: 36, ds: [[[71], Int64[]], [[39], Int64[]], [[35], Int64[]]] Next cell Merge opposite inedge: 32, ds: [[[28], Int64[]], [[89, 80, 34], [27, 77, 67, 90, 71, 39, 35]]] finished: Set([34]) stem: 32, ds: [[[28], Int64[]], [[89, 80], [27, 77, 67, 90, 71, 39, 35]]] Trunk cells stem: 82, ds: [[[82], Int64[]]] Next cell Merge alike inedge: 37, ds: [[[28], Int64[]], [[89, 80, 82], [27, 77, 67, 90, 71, 39, 35]]] finished: Set([35]) stem: 37, ds: [[[28], Int64[]], [[89, 80, 82], [27, 77, 67, 90, 71, 39]]] Trunk cells stem: 73, ds: [[[73], Int64[]]] Next cell Merge alike inedge: 40, ds: [[[28], Int64[]], [[89, 80, 82, 73], [27, 77, 67, 90, 71, 39]]] finished: Set{Int64}() stem: 60, ds: [[[60], Int64[]]] Trunk cells stem: 46, ds: [[[46], Int64[]]] Next cell Next cell stem: 41, ds: [[[41], Int64[]]] Next cell Next cell Next cell inedge: 43, ds: [[[60], Int64[]], [[46], Int64[]], [[41], Int64[]]] finished: Set{Int64}() stem: 40, ds: [[[28], Int64[]], [[89, 80, 82, 73], [27, 77, 67, 90, 71, 39]]] Trunk cells stem: 86, ds: [[[86], Int64[]]] Next cell Merge alike stem: 43, ds: [[[60], Int64[]], [[46], Int64[]], [[41], Int64[]]] Next cell Merge alike inedge: 38, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 46, 41], [27, 77, 67, 90, 71, 39]]] finished: Set([39]) stem: 38, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 46, 41], [27, 77, 67, 90, 71]]] Trunk cells stem: 94, ds: [[[94], Int64[]]] Next cell Merge opposite inedge: 42, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 46, 41], [27, 77, 67, 90, 71, 94]]] finished: Set([41]) stem: 42, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 46], [27, 77, 67, 90, 71, 94]]] Trunk cells stem: 74, ds: [[[74], Int64[]]] Next cell Merge opposite inedge: 45, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 46], [27, 77, 67, 90, 71, 94, 74]]] finished: Set{Int64}() stem: 45, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 46], [27, 77, 67, 90, 71, 94, 74]]] Trunk cells stem: 93, ds: [[[93], Int64[]]] Next cell Merge opposite stem: 48, ds: [[[48], Int64[]]] Next cell Merge opposite inedge: 44, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 46], [27, 77, 67, 90, 71, 94, 74, 93, 48]]] finished: Set([46]) stem: 44, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60], [27, 77, 67, 90, 71, 94, 74, 93, 48]]] Trunk cells stem: 62, ds: [[[62], Int64[]]] Next cell Merge alike inedge: 49, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62], [27, 77, 67, 90, 71, 94, 74, 93, 48]]] finished: Set{Int64}() stem: 49, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62], [27, 77, 67, 90, 71, 94, 74, 93, 48]]] Trunk cells stem: 75, ds: [[[75], Int64[]]] Next cell Merge alike stem: 52, ds: [[[52], Int64[]]] Next cell Merge alike inedge: 47, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 52], [27, 77, 67, 90, 71, 94, 74, 93, 48]]] finished: Set([48]) stem: 47, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 52], [27, 77, 67, 90, 71, 94, 74, 93]]] Trunk cells stem: 61, ds: [[[61], Int64[]]] Next cell Merge opposite inedge: 51, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 52], [27, 77, 67, 90, 71, 94, 74, 93, 61]]] finished: Set{Int64}() stem: 84, ds: [[[84], Int64[]]] Trunk cells stem: 57, ds: [[[57], Int64[]]] Next cell Next cell stem: 53, ds: [[[53], Int64[]]] Next cell Next cell Next cell inedge: 54, ds: [[[84], Int64[]], [[57], Int64[]], [[53], Int64[]]] finished: Set{Int64}() stem: 51, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 52], [27, 77, 67, 90, 71, 94, 74, 93, 61]]] Trunk cells stem: 76, ds: [[[76], Int64[]]] Next cell Merge opposite stem: 54, ds: [[[84], Int64[]], [[57], Int64[]], [[53], Int64[]]] Next cell Merge opposite inedge: 50, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 52], [27, 77, 67, 90, 71, 94, 74, 93, 61, 76, 84, 57, 53]]] finished: Set([52]) stem: 50, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75], [27, 77, 67, 90, 71, 94, 74, 93, 61, 76, 84, 57, 53]]] Trunk cells stem: 95, ds: [[[95], Int64[]]] Next cell Merge alike inedge: 55, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 95], [27, 77, 67, 90, 71, 94, 74, 93, 61, 76, 84, 57, 53]]] finished: Set([53]) stem: 55, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 95], [27, 77, 67, 90, 71, 94, 74, 93, 61, 76, 84, 57]]] Trunk cells stem: 88, ds: [[[88], Int64[]]] Next cell Merge alike inedge: 58, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 95, 88], [27, 77, 67, 90, 71, 94, 74, 93, 61, 76, 84, 57]]] finished: Set{Int64}() stem: 58, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 95, 88], [27, 77, 67, 90, 71, 94, 74, 93, 61, 76, 84, 57]]] Trunk cells stem: 64, ds: [[[64], Int64[]]] Next cell Merge alike inedge: 56, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 95, 88, 64], [27, 77, 67, 90, 71, 94, 74, 93, 61, 76, 84, 57]]] finished: Set([57]) stem: 56, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 95, 88, 64], [27, 77, 67, 90, 71, 94, 74, 93, 61, 76, 84]]] Trunk cells inedge: 68, ds: [[[28], Int64[]], [[89, 80, 82, 73, 86, 60, 62, 75, 95, 88, 64], [27, 77, 67, 90, 71, 94, 74, 93, 61, 76, 84]]] finished: Set([77, 80, 89, 98, 81, 62, 96, 82, 85, 91, 75, 60, 66, 83, 64, 65, 87, 84, 88, 73, 92, 74, 61, 72, 95, 79, 90, 71, 63, 86, 67, 93, 70, 94, 76, 97]) stem: 59, ds: [[[59], Int64[]]] Trunk cells stem: 68, ds: [[[28], Int64[]], [[27], Int64[]]] Next cell Next cell stem: 69, ds: [[[25], Int64[]], [[24], Int64[]]] Next cell New opposite inedge: 78, ds: [[[59], Int64[]], [[25, 24], [28, 27]]] finished: Set([27, 24]) stem: 78, ds: [[[59], Int64[]], [[25], [28]]] Trunk cells inedge: 23, ds: [[[59], Int64[]], [[25], [28]]] finished: Set([25, 28, 59]) true ```
Julia 1.6 ```julia julia> Graph.outerplanaritytest(laddergraph(20); verbose=true) nodes = Set([5, 16, 20, 35, 12, 24, 28, 8, 17, 30, 1, 19, 22, 23, 6, 32, 11, 36, 37, 9, 31, 41, 14, 3, 39, 29, 7, 25, 33, 40, 34, 4, 13, 15, 2, 10, 18, 21, 26, 27, 38]) MolecularGraph.Graph.DFSState(PlainGraph([Dict(69 => 41, 3 => 3, 1 => 2), Dict(4 => 4, 92 => 41, 1 => 1), Dict(6 => 5, 81 => 41, 2 => 4, 3 => 1), Dict(4 => 2, 7 => 6, 2 => 3, 89 => 41), Dict(5 => 6, 59 => 41, 6 => 3, 9 => 7), Dict(5 => 5, 7 => 4, 10 => 8, 73 => 41), Dict(84 => 41, 9 => 5, 12 => 9, 8 => 8), Dict(13 => 10, 10 => 6, 66 => 41, 8 => 7), Dict(78 => 41, 15 => 11, 11 => 10, 12 => 7), Dict(93 => 41, 13 => 8, 16 => 12, 11 => 9), Dict(15 => 9, 18 => 13, 14 => 12, 75 => 41), Dict(16 => 10, 63 => 41, 14 => 11, 19 => 14), Dict(21 => 15, 18 => 11, 90 => 41, 17 => 14), Dict(22 => 16, 17 => 13, 80 => 41, 19 => 12), Dict(20 => 16, 21 => 13, 24 => 17, 91 => 41), Dict(22 => 14, 20 => 15, 25 => 18, 60 => 41), Dict(67 => 41, 27 => 19, 24 => 15, 23 => 18), Dict(94 => 41, 25 => 16, 28 => 20, 23 => 17), Dict(70 => 41, 27 => 17, 26 => 20, 30 => 21), Dict(61 => 41, 26 => 19, 31 => 22, 28 => 18), Dict(29 => 22, 33 => 23, 95 => 41, 30 => 19), Dict(34 => 24, 29 => 21, 31 => 20, 71 => 41), Dict(32 => 24, 33 => 21, 36 => 25, 72 => 41), Dict(32 => 23, 34 => 22, 64 => 41, 37 => 26), Dict(39 => 27, 35 => 26, 36 => 23, 85 => 41), Dict(35 => 25, 37 => 24, 40 => 28, 96 => 41), Dict(39 => 25, 97 => 41, 38 => 28, 42 => 29), Dict(65 => 41, 43 => 30, 38 => 27, 40 => 26), Dict(83 => 41, 41 => 30, 45 => 31, 42 => 27), Dict(41 => 29, 43 => 28, 68 => 41, 46 => 32), Dict(79 => 41, 45 => 29, 44 => 32, 48 => 33), Dict(49 => 34, 44 => 31, 46 => 30, 74 => 41), Dict(51 => 35, 47 => 34, 86 => 41, 48 => 31), Dict(47 => 33, 49 => 32, 52 => 36, 88 => 41), Dict(51 => 33, 50 => 36, 54 => 37, 62 => 41), Dict(50 => 35, 55 => 38, 52 => 34, 76 => 41), Dict(77 => 41, 54 => 35, 57 => 39, 53 => 38), Dict(55 => 36, 58 => 40, 98 => 41, 53 => 37), Dict(56 => 40, 82 => 41, 57 => 37), Dict(56 => 39, 58 => 38, 87 => 41), Dict(78 => 9, 79 => 31, 81 => 3, 60 => 16, 72 => 23, 75 => 11, 83 => 29, 92 => 2, 67 => 17, 69 => 1, 68 => 30, 98 => 38, 73 => 6, 82 => 39, 85 => 25, 74 => 32, 89 => 4, 80 => 14, 96 => 26, 64 => 24, 61 => 20, 77 => 37, 84 => 7, 94 => 18, 95 => 21, 71 => 22, 90 => 13, 66 => 8, 76 => 36, 59 => 5, 70 => 19, 65 => 28, 63 => 12, 86 => 33, 93 => 10, 88 => 34, 97 => 27, 91 => 15, 62 => 35, 87 => 40)], [(1, 2), (3, 4), (1, 3), (2, 4), (5, 6), (3, 5), (4, 6), (7, 8), (5, 7), (6, 8), (9, 10), (7, 9), (8, 10), (11, 12), (9, 11), (10, 12), (13, 14), (11, 13), (12, 14), (15, 16), (13, 15), (14, 16), (17, 18), (15, 17), (16, 18), (19, 20), (17, 19), (18, 20), (21, 22), (19, 21), (20, 22), (23, 24), (21, 23), (22, 24), (25, 26), (23, 25), (24, 26), (27, 28), (25, 27), (26, 28), (29, 30), (27, 29), (28, 30), (31, 32), (29, 31), (30, 32), (33, 34), (31, 33), (32, 34), (35, 36), (33, 35), (34, 36), (37, 38), (35, 37), (36, 38), (39, 40), (37, 39), (38, 40), (41, 5), (41, 16), (41, 20), (41, 35), (41, 12), (41, 24), (41, 28), (41, 8), (41, 17), (41, 30), (41, 1), (41, 19), (41, 22), (41, 23), (41, 6), (41, 32), (41, 11), (41, 36), (41, 37), (41, 9), (41, 31), (41, 14), (41, 3), (41, 39), (41, 29), (41, 7), (41, 25), (41, 33), (41, 40), (41, 34), (41, 4), (41, 13), (41, 15), (41, 2), (41, 10), (41, 18), (41, 21), (41, 26), (41, 27), (41, 38)], Dict{Symbol, Any}()), Dict(5 => 1, 16 => 10, 20 => 17, 35 => 33, 12 => 12, 24 => 22, 28 => 26, 8 => 14, 17 => 19, 30 => 27, 23 => 23, 19 => 18, 22 => 21, 32 => 30, 6 => 2, 41 => 5, 11 => 7, 36 => 34, 37 => 38, 9 => 6, 31 => 29, 1 => 41, 14 => 11, 3 => 40, 39 => 37, 29 => 28, 7 => 15, 25 => 24, 33 => 32, 40 => 36, 34 => 31, 4 => 3, 13 => 8, 15 => 9, 2 => 4, 10 => 13, 18 => 16, 21 => 20, 27 => 25, 38 => 35, 26 => 39), Dict(16 => 20, 20 => 28, 35 => 51, 12 => 19, 24 => 34, 28 => 38, 8 => 13, 17 => 27, 30 => 43, 23 => 32, 19 => 26, 22 => 29, 32 => 44, 6 => 5, 41 => 92, 11 => 15, 36 => 50, 37 => 57, 9 => 78, 31 => 45, 1 => 3, 14 => 22, 3 => 81, 39 => 56, 29 => 41, 7 => 8, 25 => 36, 33 => 47, 40 => 58, 34 => 49, 4 => 7, 13 => 18, 15 => 21, 2 => 4, 10 => 16, 18 => 25, 21 => 30, 27 => 39, 38 => 55, 26 => 40), Dict{Int64, Bool}(5 => 0, 56 => 1, 55 => 1, 35 => 0, 60 => 0, 30 => 1, 32 => 1, 6 => 0, 67 => 0, 45 => 1, 73 => 0, 64 => 0, 90 => 0, 13 => 1, 4 => 1, 63 => 0, 54 => 0, 86 => 0, 91 => 0, 62 => 0, 58 => 1, 52 => 0, 12 => 0, 28 => 1, 75 => 0, 23 => 0, 92 => 1, 41 => 1, 43 => 1, 11 => 0, 68 => 0, 36 => 1, 98 => 0, 69 => 0, 82 => 0, 85 => 0, 84 => 0, 39 => 1, 77 => 0, 95 => 0, 25 => 1, 7 => 1, 71 => 0, 66 => 0, 76 => 0, 93 => 0, 50 => 1, 34 => 1, 59 => 0, 2 => 0, 10 => 0, 27 => 1, 26 => 1, 18 => 1, 87 => 0, 42 => 0, 79 => 0, 16 => 1, 20 => 1, 81 => 1, 19 => 1, 49 => 1, 44 => 1, 9 => 0, 31 => 0, 74 => 0, 61 => 0, 94 => 0, 29 => 1, 46 => 0, 57 => 1, 70 => 0, 21 => 1, 88 => 0, 38 => 1, 78 => 1, 72 => 0, 24 => 0, 8 => 1, 17 => 0, 37 => 0, 1 => 0, 53 => 0, 22 => 1, 83 => 0, 47 => 1, 89 => 0, 14 => 0, 80 => 0, 3 => 1, 96 => 0, 51 => 1, 33 => 0, 40 => 1, 48 => 0, 65 => 0, 15 => 1, 97 => 0), Dict(5 => 1, 56 => 36, 55 => 34, 35 => 39, 60 => 10, 30 => 18, 32 => 22, 6 => 40, 67 => 19, 45 => 28, 73 => 5, 64 => 22, 90 => 8, 4 => 3, 13 => 13, 63 => 12, 54 => 38, 86 => 32, 91 => 9, 62 => 33, 58 => 35, 52 => 34, 12 => 15, 28 => 16, 75 => 7, 23 => 19, 92 => 4, 41 => 27, 43 => 26, 11 => 13, 36 => 23, 68 => 27, 98 => 35, 69 => 41, 82 => 37, 85 => 24, 84 => 15, 39 => 24, 77 => 38, 7 => 2, 25 => 10, 95 => 20, 71 => 21, 66 => 14, 76 => 34, 93 => 13, 34 => 21, 50 => 33, 59 => 5, 2 => 40, 10 => 14, 18 => 7, 26 => 17, 27 => 18, 87 => 36, 42 => 28, 79 => 29, 16 => 12, 20 => 9, 81 => 5, 19 => 11, 49 => 30, 44 => 29, 9 => 15, 31 => 21, 74 => 30, 61 => 17, 94 => 16, 29 => 20, 46 => 30, 57 => 37, 70 => 18, 21 => 8, 38 => 25, 88 => 31, 78 => 5, 72 => 23, 24 => 19, 8 => 14, 17 => 11, 37 => 39, 1 => 41, 53 => 38, 22 => 10, 83 => 28, 47 => 31, 89 => 5, 14 => 12, 80 => 11, 3 => 40, 96 => 39, 51 => 32, 33 => 23, 40 => 26, 48 => 32, 15 => 6, 65 => 26, 97 => 25), Dict(78 => [15], 56 => [82, 57], 16 => [13, 93, 11], 55 => [98, 58], 20 => [22, 60, 25], 58 => [87, 56], 81 => [6, 2, 3], 5 => [7], 30 => [95, 29], 28 => [61, 26], 8 => [9, 84, 12], 19 => [16, 63, 14], 22 => [19, 80, 17], 47 => [86, 51, 48], 49 => [88, 47], 41 => [83, 45, 42], 45 => [79, 44], 44 => [74, 49, 46], 43 => [68, 41], 36 => [85, 39], 32 => [72, 36, 33], 92 => [59, 78, 81, 73, 89], 3 => [1, 69], 51 => [62, 50], 39 => [97, 38], 29 => [71, 34, 31], 7 => [4], 25 => [94, 28], 57 => [77, 54, 53], 40 => [96, 37, 35], 34 => [64, 32], 13 => [8, 10, 66], 50 => [76, 55, 52], 21 => [20, 91], 15 => [18, 75], 27 => [67, 24, 23], 38 => [65, 43, 40], 26 => [70, 27, 30], 18 => [21, 90], 4 => [92]), Dict(35 => 24, 60 => 5, 6 => 1, 67 => 5, 73 => 2, 64 => 5, 90 => 5, 63 => 5, 54 => 33, 86 => 5, 91 => 5, 62 => 5, 52 => 31, 12 => 6, 75 => 5, 23 => 16, 11 => 6, 68 => 5, 69 => 5, 98 => 5, 82 => 5, 85 => 5, 84 => 5, 77 => 5, 95 => 5, 71 => 5, 66 => 5, 76 => 5, 93 => 5, 59 => 1, 2 => 3, 10 => 2, 87 => 5, 42 => 25, 79 => 5, 9 => 1, 31 => 17, 74 => 5, 61 => 5, 94 => 5, 46 => 27, 70 => 5, 88 => 5, 72 => 5, 24 => 9, 17 => 8, 37 => 22, 1 => 4, 53 => 35, 83 => 5, 89 => 3, 14 => 7, 80 => 5, 96 => 5, 33 => 20, 48 => 29, 65 => 5, 97 => 5), [5, 7, 4, 92, 78, 15, 18, 21, 20, 22, 19, 16, 13, 8, 25, 28, 26, 27, 30, 29, 34, 32, 36, 39, 38, 43, 41, 45, 44, 49, 47, 51, 50, 55, 58, 56, 57, 40, 81, 3]) stem: 1, ds: [[[1], Int64[]]] Trunk cells stem: 69, ds: [[[69], Int64[]]] Next cell Next cell inedge: 3, ds: [[[1], Int64[]], [[69], Int64[]]] finished: Set{Int64}() stem: 6, ds: [[[6], Int64[]]] Trunk cells stem: 2, ds: [[[2], Int64[]]] Next cell Next cell stem: 3, ds: [[[1], Int64[]], [[69], Int64[]]] Next cell Next cell Next cell inedge: 81, ds: [[[6], Int64[]], [[2], Int64[]], [[1, 69], Int64[]]] finished: Set([79, 60, 72, 75, 83, 67, 69, 68, 98, 82, 85, 74, 80, 96, 64, 84, 77, 95, 61, 94, 90, 71, 66, 76, 93, 70, 65, 63, 86, 97, 88, 91, 62, 87]) stem: 96, ds: [[[96], Int64[]]] Trunk cells stem: 37, ds: [[[37], Int64[]]] Next cell Next cell stem: 35, ds: [[[35], Int64[]]] Next cell Next cell Next cell inedge: 40, ds: [[[96], Int64[]], [[37], Int64[]], [[35], Int64[]]] finished: Set{Int64}() stem: 77, ds: [[[77], Int64[]]] Trunk cells stem: 54, ds: [[[54], Int64[]]] Next cell Next cell stem: 53, ds: [[[53], Int64[]]] Next cell Next cell Next cell inedge: 57, ds: [[[77], Int64[]], [[54], Int64[]], [[53], Int64[]]] finished: Set{Int64}() stem: 82, ds: [[[82], Int64[]]] Trunk cells stem: 57, ds: [[[77], Int64[]], [[54], Int64[]], [[53], Int64[]]] Next cell Next cell inedge: 56, ds: [[[82], Int64[]], [[77, 54, 53], Int64[]]] finished: Set{Int64}() stem: 87, ds: [[[87], Int64[]]] Trunk cells stem: 56, ds: [[[82], Int64[]], [[77, 54, 53], Int64[]]] Next cell Next cell inedge: 58, ds: [[[87], Int64[]], [[82, 77, 54, 53], Int64[]]] finished: Set([53]) stem: 98, ds: [[[98], Int64[]]] Trunk cells stem: 58, ds: [[[87], Int64[]], [[82, 77, 54], Int64[]]] Next cell Next cell inedge: 55, ds: [[[98], Int64[]], [[87, 82, 77, 54], Int64[]]] finished: Set{Int64}() stem: 76, ds: [[[76], Int64[]]] Trunk cells stem: 55, ds: [[[98], Int64[]], [[87, 82, 77, 54], Int64[]]] Next cell Next cell stem: 52, ds: [[[52], Int64[]]] Next cell New opposite inedge: 50, ds: [[[76], Int64[]], [[52], [98, 87, 82, 77, 54]]] finished: Set([54]) stem: 62, ds: [[[62], Int64[]]] Trunk cells stem: 50, ds: [[[76], Int64[]], [[52], [98, 87, 82, 77]]] Not planer: dichromatic branch found false ```
mojaie commented 3 years ago

Planarity test is a bit complicated so please give me some time. Thank you for catching it!

timholy commented 3 years ago

No rush whatsoever, I just wanted to report it. It's not something I'm actively using right now.

mojaie commented 3 years ago

fixed a659318176228f7a2edfc20418e8f77eac335389

mojaie commented 3 years ago 
julia> using MolecularGraph
julia> using MolecularGraph.Graph
julia> c60 = smilestomol("c12c3c4c5c1c6c7c8c2c9c1c3c2c3c4c4c%10c5c5c6c6c7c7c%11c8c9c8c9c1c2c1c2c3c4c3c4c%10c5c5c6c6c7c7c%11c8c8c9c1c1c2c3c2c4c5c6c3c7c8c1c23")
julia> isplanar(c60)
true
julia> isouterplanar(c60)
false
timholy commented 2 years ago

Thank you! (I've not been checking my notifications for a while, sorry for the delayed acknowledgment.)