MultiLML (Issue #57)

[Fanderman]

Added a function for creating multiplications and a function for checking fairness of created graph. The function for multiplications will return the first 'fair' multiplication it finds or a nil if it wont find any.

Multiplications are created by iterating through all possible legal connections, therefore the creation time goes to extremely long for 8 or more players (or a lot of connections in each node).

It is worth noting that it is possible that there doesn't exist a fair multiplication for given node, a simple example: MultiplyLML({{1, 'LOCAL', 2}, {2, 'LOCAL, 3}, {3 'LOCAL', 4}}, 3), you can easily see that it is impossible to create a 'fair' multiplication for 3 players with such a node.

I also only assumed what it means that a connection is 'fair', therefore feel free to tell me if I got it wrong and give me an example where current rules wont find an 'unfair' connection.

[acatai]

OK, I've moved files to the direction I initially proposed and added Grapviz drawing (call mlml.draw.lua from the main directory).

Function checkFairness seems working OK as far as I've tested it. Although by the description in point 3 I was interested why 'types' of these connections are not checked and only amounts. Does point 4 fully cover these cases?

The MultiplyLML also works OK.

Although speed is a huge problem there, that seems obvious now. Checking is fast enough, issue is within the greedy matching. Question is can we significantly reduce the number of checks? Now it goes adding edges for each player and node 'separately'. But - when we add connection between node X and Y labeled a-b, then every other non-X node also should have such connection. So we should search looping through all other players and for each of them find the target reached by the set a-b label. We should be able to reduce #players*#edges complexity tu just #players in this moment. Is it understandable and do you think it will work correctly?

[Fanderman]

the point about checking for if the connected types are ok is resolved in the 'Connect' function itself in the huge 'if'. I see your point about making connections for all players at the same time and will try to write it and check the results.

[acatai]

the point about checking for if the connected types are ok is resolved in the 'Connect' function itself in the huge 'if'.

I know, I sketched through the code. That reduces unnecessary fairness-checking and makes some early-cutoffs for sure.

I see your point about making connections for all players at the same time and will try to write it and check the results.

Yeah, I may describe it a little vaguely but hope you got the idea. That's great, let see if that helps - maybe you'll find some more improvements on the way.

[acatai]

Przejrzałem tę formułkę w ifie odpowiadającym za cutoff. Założenie było takie, że LOCAL może się łączyć ze wszystkim, a jeśli jest inny typ (po ostatnich zmianach możemy powiedzieć że inny to zawsze będzie BUFFER) to może tylko z innym buforem o takim samym poziomie.

Przykładowo:

Test('t1', {{1, 'LOCAL', 2},{2, 'BUFFER', 3}}, 3)

Nie przechodzi a chcielibyśmy żeby przechodził.

[Fanderman]

Przejrzałem tę formułkę w ifie odpowiadającym za cutoff. Założenie było takie, że LOCAL może się łączyć ze wszystkim, a jeśli jest inny typ (po ostatnich zmianach możemy powiedzieć że inny to zawsze będzie BUFFER) to może tylko z innym buforem o takim samym poziomie. Przykładowo: Test('t1', {{1, 'LOCAL', 2},{2, 'BUFFER', 3}}, 3) Nie przechodzi a chcielibyśmy żeby przechodził

Fixed.