Open SeaSlug10 opened 4 years ago
The library will return "False", if the graph is not a bipartite graph. So maybe you need to check if your graph is really a bipartite graph.
Well I found that having the same name for nodes on different sides does not work, so I changed that, now using the below graph, but I dont know what else could be wrong? I have a set of nodes 0o-9o on one side now and another set 0-9 on the other and they are all connected by a weighted edge. Does using a complete bipartite graph affect this at all? Also, when I changed the matching type to max instead of min I didnt get a False return right away, rather the program appeared to run indefinitely (I let it run for 40 minutes before stopping it) and it looks like it was running the algorithm ok at least, if taking awhile
{ '0o': {'0': 0.0, '1': 51.61395, '2': 127.12199, '3': 364.85751, '4': 451.00998, '5': 516.0, '6': 572.00087, '7': 668.71892, '8': 768.21091, '9': 813.13836}, '1o': {'0': 64.19502, '1': 33.30165, '2': 64.2573, '3': 300.66593, '4': 387.00517, '5': 452.02765, '6': 508.03543, '7': 604.55934, '8': 704.12002, '9': 749.06675}, '2o': {'0': 143.03147, '1': 104.54664, '2': 31.40064, '3': 222.09232, '4': 308.0, '5': 373.01206, '6': 429.01865, '7': 525.74614, '8': 625.17997, '9': 670.10745}, '3o': {'0': 393.0, '1': 352.27972, '2': 270.45332, '3': 38.28838, '4': 58.07753, '5': 123.0, '6': 179.00279, '7': 276.74176, '8': 375.43175, '9': 420.26777}, '4o': {'0': 486.01646, '1': 445.2999, '2': 363.41161, '3': 125.39936, '4': 35.69314, '5': 30.26549, '6': 86.05231, '7': 185.33483, '8': 282.85685, '9': 327.55152}, '5o': {'0': 516.0, '1': 474.94842, '2': 392.99873, '3': 154.0422, '4': 65.06919, '5': 0.0, '6': 56.00893, '7': 155.12898, '8': 252.64204, '9': 297.37855}, '6o': {'0': 572.00087, '1': 530.90583, '2': 448.93763, '3': 209.6187, '4': 121.0661, '5': 56.00893, '6': 0.0, '7': 101.19289, '8': 196.91876, '9': 241.53054}, '7o': {'0': 689.01161, '1': 647.5222, '2': 565.5095, '3': 325.67775, '4': 238.0021, '5': 173.04624, '6': 117.10679, '7': 34.20526, '8': 80.23092, '9': 124.48695}, '8o': {'0': 791.01011, '1': 749.7713, '2': 667.76717, '3': 427.98364, '4': 340.07205, '5': 275.02909, '6': 219.02055, '7': 127.88276, '8': 31.82766, '9': 29.06888}, '9o': {'0': 835.00958, '1': 793.72854, '2': 711.71975, '3': 471.89194, '4': 384.0638, '5': 319.02508, '6': 263.01711, '7': 170.62825, '8': 70.5195, '9': 29.06888} }
It seems like the algorithm does not always find a match for some reason based on the input, even if it is a bipartite graph. for example, I run this code to create a random 3x3 graph: G = {} for i in range(3): edges = {} for b in range(3): edges['#'+str(b)] = random.randint(0,10) G['Operator'+str(i)] = edges
When this produces the following graph: {'Operator0': {'#0': 2, '#1': 8, '#2': 7}, 'Operator1': {'#0': 10, '#1': 4, '#2': 2}, 'Operator2': {'#0': 2, '#1': 10, '#2': 5}} I get a matching return of [(('Operator1', '#1'), 4), (('Operator0', '#0'), 2), (('Operator2', '#2'), 5)]
However when it produces this graph instead {'Operator0': {'#0': 10, '#1': 6, '#2': 0}, 'Operator1': {'#0': 6, '#1': 1, '#2': 9}, 'Operator2': {'#0': 8, '#1': 6, '#2': 2}} I get a return value of False. Im not sure if this could be because if the matching isnt solved after the first attempt it returns or maybe some other reason but it seems like it will not always find a match
@SeaSlug10 Strange... can you share all of your code? I've just run:
from hungarian_algorithm import algorithm
G = {
'Operator0': {'#0': 10, '#1': 6, '#2': 0},
'Operator1': {'#0': 6, '#1': 1, '#2': 9},
'Operator2': {'#0': 8, '#1': 6, '#2': 2}
}
print(algorithm.find_matching(G));
And got [(('Operator1', '#2'), 9), (('Operator2', '#1'), 6), (('Operator0', '#0'), 10)]
.
As for your previous example with 20 vertices, I'm also experiencing the failure to return. I'll look into this...
@benchaplin Thanks for getting back to me, the code i ran was
from hungarian import algorithm
G = {}
for i in range(3):
edges = {}
for b in range(3):
edges['#'+str(b)] = random.randint(0,10)
G['Operator'+str(i)] = edges
print(G)
print(algorithm.find_matching(G,matching_type='min')
I was only running the tests with the matching type of min while I was testing them because that was what i was originally trying to do. I checked the two graphs again by manually setting G to them and got the same result that I posted in my previous comment
@SeaSlug10 Ok, I think I've identified the issue. It seems there is a fundamental problem with how the algorithm works on edges of weight 0 when matching_type='min'
.
I will work to fix it soon, but for now, a temporary workaround is to set all edges of weight 0 to 0.0001, or something.
@benchaplin So I changed the 20 vertice graph to G={ '0o': {'0': 0.01, '1': 51.61395, '2': 127.12199, '3': 364.85751, '4': 451.00998, '5': 516.0, '6': 572.00087, '7': 668.71892, '8': 768.21091, '9': 813.13836}, '1o': {'0': 64.19502, '1': 33.30165, '2': 64.2573, '3': 300.66593, '4': 387.00517, '5': 452.02765, '6': 508.03543, '7': 604.55934, '8': 704.12002, '9': 749.06675}, '2o': {'0': 143.03147, '1': 104.54664, '2': 31.40064, '3': 222.09232, '4': 308.0, '5': 373.01206, '6': 429.01865, '7': 525.74614, '8': 625.17997, '9': 670.10745}, '3o': {'0': 393.0, '1': 352.27972, '2': 270.45332, '3': 38.28838, '4': 58.07753, '5': 123.0, '6': 179.00279, '7': 276.74176, '8': 375.43175, '9': 420.26777}, '4o': {'0': 486.01646, '1': 445.2999, '2': 363.41161, '3': 125.39936, '4': 35.69314, '5': 30.26549, '6': 86.05231, '7': 185.33483, '8': 282.85685, '9': 327.55152}, '5o': {'0': 516.0, '1': 474.94842, '2': 392.99873, '3': 154.0422, '4': 65.06919, '5': 0.01, '6': 56.00893, '7': 155.12898, '8': 252.64204, '9': 297.37855}, '6o': {'0': 572.00087, '1': 530.90583, '2': 448.93763, '3': 209.6187, '4': 121.0661, '5': 56.00893, '6': 0.01, '7': 101.19289, '8': 196.91876, '9': 241.53054}, '7o': {'0': 689.01161, '1': 647.5222, '2': 565.5095, '3': 325.67775, '4': 238.0021, '5': 173.04624, '6': 117.10679, '7': 34.20526, '8': 80.23092, '9': 124.48695}, '8o': {'0': 791.01011, '1': 749.7713, '2': 667.76717, '3': 427.98364, '4': 340.07205, '5': 275.02909, '6': 219.02055, '7': 127.88276, '8': 31.82766, '9': 29.06888}, '9o': {'0': 835.00958, '1': 793.72854, '2': 711.71975, '3': 471.89194, '4': 384.0638, '5': 319.02508, '6': 263.01711, '7': 170.62825, '8': 70.5195, '9': 29.06888} }
and now Im getting a runtime error of
File "C:\Users\cmaddox\Anaconda3\lib\site-packages\hungarian_algorithm\algorithm.py", line 352, in vertex_saturated if v == e.vertices[0]:
AttributeError: 'bool' object has no attribute 'vertices'
after a couple quick tests it looks like I get this error any time an edge is set to something less than one, as setting them to .9999 still produced the error but once they were set to one it went away. In this case it shouldnt affect me because these small edges are still smaller than the others, but I just wanted update this to say it doesnt seem to be only when equal to zero but when edges are less than one, at least for this graph. I did try it with the 6 vertice graph and .01 seemed to work so maybe something with the size of the graph is affecting it?
Im having another problem pertaining to the values in the graph now actually, I'm trying to run a larger bipartite graph and getting a runtime error of
File "C:\Users\cmaddox\Anaconda3\lib\site-packages\hungarian_algorithm\algorithm.py", line 447, in find_matching y = list(S_nbs - T)[0]
IndexError: list index out of range
when I run the following graph; {'0o': {'0': 1.0, '1': 51.61395, '2': 127.12199, '3': 364.85751, '4': 451.00998, '5': 516.0, '6': 572.00087, '7': 668.71892, '8': 768.21091, '9': 813.13836, '10': 838.46765, '11': 600.14082, '12': 905.92825, '13': 185.06485, '14': 240.86926, '15': 707.59452, '16': 110.05908, '17': 473.51135, '18': 83.81527}, '1o': {'0': 64.19502, '1': 33.30165, '2': 64.2573, '3': 300.66593, '4': 387.00517, '5': 452.02765, '6': 508.03543, '7': 604.55934, '8': 704.12002, '9': 749.06675, '10': 774.34166, '11': 536.0597, '12': 841.77016, '13': 122.06556, '14': 177.12425, '15': 643.44774, '16': 57.42822, '17': 409.35315, '18': 44.18144}, '2o': {'0': 143.03147, '1': 104.54664, '2': 31.40064, '3': 222.09232, '4': 308.0, '5': 373.01206, '6': 429.01865, '7': 525.74614, '8': 625.17997, '9': 670.10745, '10': 695.44949, '11': 457.1094, '12': 762.94692, '13': 54.48853, '14': 102.15674, '15': 564.59897, '16': 67.20863, '17': 330.54652, '18': 87.98295}, '3o': {'0': 393.0, '1': 352.27972, '2': 270.45332, '3': 38.28838, '4': 58.07753, '5': 123.0, '6': 179.00279, '7': 276.74176, '8': 375.43175, '9': 420.26777, '10': 445.88003, '11': 207.40781, '12': 513.63898, '13': 217.29703, '14': 161.8178, '15': 315.33633, '16': 300.53286, '17': 82.96987, '18': 328.67309}, '4o': {'0': 486.01646, '1': 445.2999, '2': 363.41161, '3': 125.39936, '4': 35.69314, '5': 30.26549, '6': 86.05231, '7': 185.33483, '8': 282.85685, '9': 327.55152, '10': 353.45155, '11': 115.26057, '12': 421.40954, '13': 309.58844, '14': 253.39692, '15': 223.45022, '16': 393.01018, '17': 29.06888, '18': 421.34665}, '5o': {'0': 516.0, '1': 474.94842, '2': 392.99873, '3': 154.0422, '4': 65.06919, '5': 1.0, '6': 56.00893, '7': 155.12898, '8': 252.64204, '9': 297.37855, '10': 323.2151, '11': 85.0, '12': 391.1547, '13': 338.74031, '14': 282.29417, '15': 193.18903, '16': 422.2144, '17': 48.30114, '18': 450.67172}, '6o': {'0': 572.00087, '1': 530.90583, '2': 448.93763, '3': 209.6187, '4': 121.0661, '5': 56.00893, '6': 1.0, '7': 101.19289, '8': 196.91876, '9': 241.53054, '10': 267.57616, '11': 31.30495, '12': 335.6382, '13': 394.46166, '14': 337.8772, '15': 138.29317, '16': 477.9477, '17': 101.63661, '18': 506.47409}, '7o': {'0': 689.01161, '1': 647.5222, '2': 565.5095, '3': 325.67775, '4': 238.0021, '5': 173.04624, '6': 117.10679, '7': 34.20526, '8': 80.23092, '9': 124.48695, '10': 150.92051, '11': 89.4539, '12': 219.14607, '13': 510.49192, '14': 453.6794, '15': 30.80584, '16': 593.94276, '17': 216.7487, '18': 622.6283}, '8o': {'0': 791.01011, '1': 749.7713, '2': 667.76717, '3': 427.98364, '4': 340.07205, '5': 275.02909, '6': 219.02055, '7': 127.88276, '8': 31.82766, '9': 29.06888, '10': 56.85948, '11': 191.75505, '12': 122.56019, '13': 612.80503, '14': 555.99011, '15': 90.24965, '16': 696.2557, '17': 319.06112, '18': 724.94}, '9o': {'0': 835.00958, '1': 793.72854, '2': 711.71975, '3': 471.89194, '4': 384.0638, '5': 319.02508, '6': 263.01711, '7': 170.62825, '8': 70.5195, '9': 29.06888, '10': 32.14032, '11': 235.61409, '12': 83.21658, '13': 656.68409, '14': 599.84415, '15': 132.18548, '16': 740.12161, '17': 362.9325, '18': 768.82898}, '10o': {'0': 860.00233, '1': 818.47908, '2': 736.4591, '3': 496.53298, '4': 409.00122, '5': 344.00581, '6': 288.01562, '7': 194.17775, '8': 93.38094, '9': 48.76474, '10': 34.05877, '11': 260.23259, '12': 59.5483, '13': 681.23491, '14': 624.34766, '15': 155.36409, '16': 764.63651, '17': 387.51645, '18': 793.39335}, '11o': {'0': 600.14082, '1': 558.2589, '2': 476.23629, '3': 236.30489, '4': 149.33519, '5': 85.0, '6': 31.30495, '7': 70.34202, '8': 168.07439, '9': 213.00939, '10': 238.47222, '11': 1.0, '12': 306.28255, '13': 421.07007, '14': 364.23756, '15': 108.18965, '16': 504.50966, '17': 127.3185, '18': 533.21665}, '12o': {'0': 929.12109, '1': 887.12682, '2': 805.10496, '3': 565.08849, '4': 478.1506, '5': 413.27231, '6': 357.35836, '7': 261.48996, '8': 161.02795, '9': 116.0, '10': 91.92388, '11': 329.00608, '12': 35.38361, '13': 749.52318, '14': 692.56624, '15': 222.441, '16': 832.82231, '17': 456.05372, '18': 861.67105}, '13o': {'0': 200.99751, '1': 158.31614, '2': 76.41989, '3': 164.0762, '4': 251.57504, '5': 316.63228, '6': 372.59227, '7': 468.12926, '8': 568.00352, '9': 613.02039, '10': 638.05015, '11': 400.06125, '12': 705.3127, '13': 30.4795, '14': 43.56604, '15': 507.07988, '16': 107.85639, '17': 273.00733, '18': 135.14807}, '14o': {'0': 257.56164, '1': 215.39266, '2': 133.45411, '3': 107.29865, '4': 194.5045, '5': 259.55732, '6': 315.51387, '7': 411.23837, '8': 511.00098, '9': 556.0036, '10': 581.10412, '11': 343.02332, '12': 648.44429, '13': 81.27115, '14': 32.80244, '15': 450.15997, '16': 163.78339, '17': 216.05786, '18': 191.68985}, '15o': {'0': 707.59452, '1': 665.00075, '2': 583.00086, '3': 343.02332, '4': 257.31693, '5': 193.18903, '6': 138.29317, '7': 39.05125, '8': 61.98387, '9': 106.92053, '10': 131.00382, '11': 108.18965, '12': 198.3633, '13': 527.18593, '14': 470.20846, '15': 1.0, '16': 610.43345, '17': 234.10468, '18': 639.31291}, '16o': {'0': 119.85408, '1': 75.10659, '2': 7.28011, '3': 247.00202, '4': 334.79098, '5': 399.84622, '6': 455.80039, '7': 551.02269, '8': 651.04915, '9': 696.08692, '10': 721.00277, '11': 483.17492, '12': 788.14275, '13': 65.25335, '14': 121.19818, '15': 590.00763, '16': 32.80244, '17': 356.02247, '18': 54.12947}, '17o': {'0': 473.51135, '1': 431.07424, '2': 349.05157, '3': 109.04128, '4': 29.06888, '5': 48.30114, '6': 101.63661, '7': 195.20758, '8': 295.02712, '9': 340.07205, '10': 365.04931, '11': 127.3185, '12': 432.41762, '13': 293.7516, '14': 236.93248, '15': 234.10468, '16': 377.19491, '17': 1.0, '18': 405.899}, '18o': {'0': 90.24965, '1': 45.39824, '2': 37.21559, '3': 277.00181, '4': 364.60527, '5': 429.6708, '6': 485.6439, '7': 581.04217, '8': 681.02643, '9': 726.05578, '10': 751.01065, '11': 513.11792, '12': 818.17663, '13': 94.92102, '14': 151.19854, '15': 620.02016, '16': 29.73214, '17': 386.00518, '18': 31.40064}}
when I remove the final node (the one labeled '18'/'18o') or replace it with a different one the program then runs fine so it seems like something about its specific values is messing it up, im just not sure what
@SeaSlug10 Ok, thanks for providing me with these examples. I'll let you know when I find the problem...
any updates or should we look for different libraries?
I also get a value of False for this input, which is a bipartite graph:
{'one_p': {'one_g': 372.42309516064086, 'two_g': 148.61294304217748, 'three_g': 25.28233776454882, 'four_g': 399.5749071470076}, 'two_p': {'one_g': 50.45393247396498, 'two_g': 422.0035376798201, 'three_g': 320.8134870679795, 'four_g': 542.9268686389967}, 'three_p': {'one_g': 457.9124259929159, 'two_g': 12.95405752046296, 'three_g': 167.81989076281263, 'four_g': 340.6892682197605}, 'four_p': {'one_g': 549.2944736018247, 'two_g': 341.3927595675478, 'three_g': 397.5525286603245, 'four_g': 0.0}}
It seems like the problem happens when one of the weights is exactly 0.0. If in my example I manually set 'four_p' - 'four_g' to 0.001, then everything works fine.
Yes there are some Python float issues to deal with here. I've taken a couple tries at fixing this issue, but have not found success yet.
I do not have much time to work on this library. If anyone needs a more reliable implementation, see here.
First, thank you for this library when i run the find_matching method with the following bipartite graph it returns a value of False. Is there something wrong with the dictionary I'm using or something written into the algorithm that would make it return this value? Thank you
{'0': {'0': 0.0, '1': 51.61395, '2': 127.12199, '3': 364.85751, '4': 451.00998, '5': 516.0, '6': 572.00087, '7': 668.71892, '8': 768.21091, '9': 813.13836, '10': 838.46765, '11': 600.14082, '12': 905.92825, '13': 185.06485, '14': 240.86926, '15': 707.59452, '16': 110.05908, '17': 473.51135, '18': 83.81527, '19': 312.00641}, '1': {'0': 64.19502, '1': 33.30165, '2': 64.2573, '3': 300.66593, '4': 387.00517, '5': 452.02765, '6': 508.03543, '7': 604.55934, '8': 704.12002, '9': 749.06675, '10': 774.34166, '11': 536.0597, '12': 841.77016, '13': 122.06556, '14': 177.12425, '15': 643.44774, '16': 57.42822, '17': 409.35315, '18': 44.18144, '19': 248.01814}, '2': {'0': 143.03147, '1': 104.54664, '2': 31.40064, '3': 222.09232, '4': 308.0, '5': 373.01206, '6': 429.01865, '7': 525.74614, '8': 625.17997, '9': 670.10745, '10': 695.44949, '11': 457.1094, '12': 762.94692, '13': 54.48853, '14': 102.15674, '15': 564.59897, '16': 67.20863, '17': 330.54652, '18': 87.98295, '19': 169.00296}, '3': {'0': 393.0, '1': 352.27972, '2': 270.45332, '3': 38.28838, '4': 58.07753, '5': 123.0, '6': 179.00279, '7': 276.74176, '8': 375.43175, '9': 420.26777, '10': 445.88003, '11': 207.40781, '12': 513.63898, '13': 217.29703, '14': 161.8178, '15': 315.33633, '16': 300.53286, '17': 82.96987, '18': 328.67309, '19': 81.02469}, '4': {'0': 486.01646, '1': 445.2999, '2': 363.41161, '3': 125.39936, '4': 35.69314, '5': 30.26549, '6': 86.05231, '7': 185.33483, '8': 282.85685, '9': 327.55152, '10': 353.45155, '11': 115.26057, '12': 421.40954, '13': 309.58844, '14': 253.39692, '15': 223.45022, '16': 393.01018, '17': 29.06888, '18': 421.34665, '19': 174.10342}, '5': {'0': 516.0, '1': 474.94842, '2': 392.99873, '3': 154.0422, '4': 65.06919, '5': 0.0, '6': 56.00893, '7': 155.12898, '8': 252.64204, '9': 297.37855, '10': 323.2151, '11': 85.0, '12': 391.1547, '13': 338.74031, '14': 282.29417, '15': 193.18903, '16': 422.2144, '17': 48.30114, '18': 450.67172, '19': 204.0098}, '6': {'0': 572.00087, '1': 530.90583, '2': 448.93763, '3': 209.6187, '4': 121.0661, '5': 56.00893, '6': 0.0, '7': 101.19289, '8': 196.91876, '9': 241.53054, '10': 267.57616, '11': 31.30495, '12': 335.6382, '13': 394.46166, '14': 337.8772, '15': 138.29317, '16': 477.9477, '17': 101.63661, '18': 506.47409, '19': 260.01731}, '7': {'0': 689.01161, '1': 647.5222, '2': 565.5095, '3': 325.67775, '4': 238.0021, '5': 173.04624, '6': 117.10679, '7': 34.20526, '8': 80.23092, '9': 124.48695, '10': 150.92051, '11': 89.4539, '12': 219.14607, '13': 510.49192, '14': 453.6794, '15': 30.80584, '16': 593.94276, '17': 216.7487, '18': 622.6283, '19': 377.00531}, '8': {'0': 791.01011, '1': 749.7713, '2': 667.76717, '3': 427.98364, '4': 340.07205, '5': 275.02909, '6': 219.02055, '7': 127.88276, '8': 31.82766, '9': 29.06888, '10': 56.85948, '11': 191.75505, '12': 122.56019, '13': 612.80503, '14': 555.99011, '15': 90.24965, '16': 696.2557, '17': 319.06112, '18': 724.94, '19': 479.03758}, '9': {'0': 835.00958, '1': 793.72854, '2': 711.71975, '3': 471.89194, '4': 384.0638, '5': 319.02508, '6': 263.01711, '7': 170.62825, '8': 70.5195, '9': 29.06888, '10': 32.14032, '11': 235.61409, '12': 83.21658, '13': 656.68409, '14': 599.84415, '15': 132.18548, '16': 740.12161, '17': 362.9325, '18': 768.82898, '19': 523.03442}, '10': {'0': 860.00233, '1': 818.47908, '2': 736.4591, '3': 496.53298, '4': 409.00122, '5': 344.00581, '6': 288.01562, '7': 194.17775, '8': 93.38094, '9': 48.76474, '10': 34.05877, '11': 260.23259, '12': 59.5483, '13': 681.23491, '14': 624.34766, '15': 155.36409, '16': 764.63651, '17': 387.51645, '18': 793.39335, '19': 548.0}, '11': {'0': 600.14082, '1': 558.2589, '2': 476.23629, '3': 236.30489, '4': 149.33519, '5': 85.0, '6': 31.30495, '7': 70.34202, '8': 168.07439, '9': 213.00939, '10': 238.47222, '11': 0.0, '12': 306.28255, '13': 421.07007, '14': 364.23756, '15': 108.18965, '16': 504.50966, '17': 127.3185, '18': 533.21665, '19': 288.20999}, '12': {'0': 929.12109, '1': 887.12682, '2': 805.10496, '3': 565.08849, '4': 478.1506, '5': 413.27231, '6': 357.35836, '7': 261.48996, '8': 161.02795, '9': 116.0, '10': 91.92388, '11': 329.00608, '12': 35.38361, '13': 749.52318, '14': 692.56624, '15': 222.441, '16': 832.82231, '17': 456.05372, '18': 861.67105, '19': 617.13694}, '13': {'0': 200.99751, '1': 158.31614, '2': 76.41989, '3': 164.0762, '4': 251.57504, '5': 316.63228, '6': 372.59227, '7': 468.12926, '8': 568.00352, '9': 613.02039, '10': 638.05015, '11': 400.06125, '12': 705.3127, '13': 30.4795, '14': 43.56604, '15': 507.07988, '16': 107.85639, '17': 273.00733, '18': 135.14807, '19': 113.43721}, '14': {'0': 257.56164, '1': 215.39266, '2': 133.45411, '3': 107.29865, '4': 194.5045, '5': 259.55732, '6': 315.51387, '7': 411.23837, '8': 511.00098, '9': 556.0036, '10': 581.10412, '11': 343.02332, '12': 648.44429, '13': 81.27115, '14': 32.80244, '15': 450.15997, '16': 163.78339, '17': 216.05786, '18': 191.68985, '19': 57.00877}, '15': {'0': 707.59452, '1': 665.00075, '2': 583.00086, '3': 343.02332, '4': 257.31693, '5': 193.18903, '6': 138.29317, '7': 39.05125, '8': 61.98387, '9': 106.92053, '10': 131.00382, '11': 108.18965, '12': 198.3633, '13': 527.18593, '14': 470.20846, '15': 0.0, '16': 610.43345, '17': 234.10468, '18': 639.31291, '19': 395.92171}, '16': {'0': 119.85408, '1': 75.10659, '2': 7.28011, '3': 247.00202, '4': 334.79098, '5': 399.84622, '6': 455.80039, '7': 551.02269, '8': 651.04915, '9': 696.08692, '10': 721.00277, '11': 483.17492, '12': 788.14275, '13': 65.25335, '14': 121.19818, '15': 590.00763, '16': 32.80244, '17': 356.02247, '18': 54.12947, '19': 196.47137}, '17': {'0': 473.51135, '1': 431.07424, '2': 349.05157, '3': 109.04128, '4': 29.06888, '5': 48.30114, '6': 101.63661, '7': 195.20758, '8': 295.02712, '9': 340.07205, '10': 365.04931, '11': 127.3185, '12': 432.41762, '13': 293.7516, '14': 236.93248, '15': 234.10468, '16': 377.19491, '17': 0.0, '18': 405.899, '19': 162.23748}, '18': {'0': 90.24965, '1': 45.39824, '2': 37.21559, '3': 277.00181, '4': 364.60527, '5': 429.6708, '6': 485.6439, '7': 581.04217, '8': 681.02643, '9': 726.05578, '10': 751.01065, '11': 513.11792, '12': 818.17663, '13': 94.92102, '14': 151.19854, '15': 620.02016, '16': 29.73214, '17': 386.00518, '18': 31.40064, '19': 226.073}, '19': {'0': 336.25288, '1': 293.00171, '2': 211.00237, '3': 29.27456, '4': 118.87809, '5': 183.30848, '6': 238.89119, '7': 333.00601, '8': 433.1397, '9': 478.20498, '10': 503.00099, '11': 265.48258, '12': 570.1263, '13': 155.63097, '14': 98.99495, '15': 372.0, '16': 239.10876, '17': 138.17742, '18': 267.74802, '19': 35.4683}}