Generating tournament brackets / Finding subgraphs

Question

I'm trying to make a bracket generator similar to the Swiss style, but drawing games in batches of 2 rounds unlike Swiss which requires the results of the most recent round to generate the next round of games.

I decided to try using some kind of rating system (Glicko, elo, whatever...) for the seeding - every player starts with the default rating (so initial matches are random), and then matches are drawn such that the sum of squares of rating differences is minimal and after each batch of matches, the ratings are updated with the results. However, I must also prevent 2 players from playing more than once (especially in the same round).

I thought about representing each round as a graph - all of the "possible" matches would be the edges and each vertex would be a player, so the possible matches would be the complete graph of n vertices (then I can set repeat matchups from previous rounds to have a very high "distance" so they never get picked). The problem then becomes finding the right subgraph such that each vertex is connected exactly twice and the sum of squares of distances is minimized.

This sounds a bit similar to the traveling salesman problem but the matches can be completely "disjoint" - if we have:

1 vs 2
2 vs 3
3 vs 1

4 vs 5
5 vs 6
6 vs 4

when we represent this as a graph, the two groups of 3 are disconnected.

I haven't been able to come up with an efficient algorithm for this, nor find an analogous problem that has been solved.

Answer 1

I implemented a Swiss-like tournament pairing algorithm using networkx.min_weight_matching.

The logic of the pairing is in methods tournament.dist, which defines the "penalty" of pairing together two players who don't have the same number of wins; and tournament.get_next_round.

SOS (sum of opponents' numbers of wins) and SOSOS (sum of opponents' sos) are used as tie-breakers.

I did not implement a method to remove players for a round or to add a bye-player in case the number of players is odd.

from networkx import Graph, min_weight_matching

class Player:
    def __init__(self, name, nwins=0):
        self.name = name
        self.nwins = 0
        self.sos = 0
        self.sosos = 0

class DoubleSwissTournament:
    def __init__(self, list_of_player_names=()):
        self.n_players = len(list_of_player_names)
        self.player_list = [Player(name) for name in list_of_player_names]
        self.prev_matches = {i: set() for i in range(self.n_players)}
        self.rounds = []
        self.coeffs = {'nwins':100, 'sos':10, 'sosos':1}
    def add_player(self, name, nwins=0):
        self.player_list.append(Player(name,nwins=nwins))
        self.prev_matches[self.n_players] = set()
        self.n_players += 1
    def recompute_sos(self):
        for p,opponents in self.prev_matches.items():
            self.player_list[p].sos = sum(self.player_list[q].nwins for q in opponents)
    def recompute_sosos(self):
        for p,opponents in self.prev_matches.items():
            self.player_list[p].sosos = sum(self.player_list[q].sos for q in opponents)
    def dist(self, p, q):
        x,y = self.player_list[p], self.player_list[q]
        return sum(coeff * (getattr(x,score) - getattr(y,score))**2
                   for score,coeff in self.coeffs.items())
    def gen_next_round(self):
        g = Graph()
        g.add_nodes_from(range(self.n_players))
        g.add_weighted_edges_from(
            (p, q, self.dist(p,q))
            for p,opponents in self.prev_matches.items()
            for q in set(range(p)).difference(opponents)
        )
        m1 = min_weight_matching(g)
        g.remove_edges_from(m1)
        m2 = min_weight_matching(g)
        round = m1.union(m2)
        self.rounds.append(round)
        return round
    def add_results(self, results):
        for p,q, winner in results:
            self.prev_matches[p].add(q)
            self.prev_matches[q].add(p)
            self.player_list[winner].nwins += 1
        self.recompute_sos()
        self.recompute_sosos()
    def get_standings(self):
        players = sorted(self.player_list, key=lambda p:(p.nwins,p.sos,p.sosos), reverse=True)
        ranks = list(range(1,len(players)+1))
        for i in range(1,len(players)):
            if ((players[i].nwins,players[i].sos,players[i].sosos)
             == (players[i-1].nwins,players[i-1].sos,players[i-1].sosos)):
                ranks[i] = ranks[i-1]
        return [(r,p.name,p.nwins,p.sos,p.sosos) for r,p in zip(ranks,players)]
    def str_standings(self):
        l = self.get_standings()
        l = [('','name','wins','sos','sosos')] + l
        maxlen = max(len(name) for _,name,_,_,_ in l)
        return '\n'.join('{:2}. {:{width}}  {:>4} {:>4} {:>4}'.format(*x, width=maxlen) for x in l)

from random import choice

def main():
    player_names = ['Alice', 'Bob', 'Chen', 'David', 'Elena', 'Fanfan', 'Gregory', 'Han', 'Irma', 'Jan', 'Kim', 'Lili', 'Mehdi', 'Noah', 'Oskar', 'Penelope']
    tournament = DoubleSwissTournament(player_names)
    print('STANDINGS BEFORE ROUND 1')
    print(tournament.str_standings())
    for round_number in (1,2,3):
        print('\nROUND {}: PAIRINGS'.format(round_number))
        round = tournament.gen_next_round()
        print([(tournament.player_list[p].name,tournament.player_list[q].name)
               for p,q in round])
        print('\nROUND {}: RESULTS'.format(round_number))
        results = [(p,q,choice((p,q))) for p,q in round]
        print(['{} {}-{} {}'.format(tournament.player_list[p].name,int(p==w),int(q==w),tournament.player_list[q].name)
               for p,q,w in results])
        tournament.add_results(results)
        print('\nSTANDINGS AFTER ROUND {}'.format(round_number))
        print(tournament.str_standings())
    return tournament

if __name__ == '__main__':
    tournament = main()

Output:

STANDINGS BEFORE ROUND 1
  . name      wins  sos sosos
 1. Alice        0    0    0
 1. Bob          0    0    0
 1. Chen         0    0    0
 1. David        0    0    0
 1. Elena        0    0    0
 1. Fanfan       0    0    0
 1. Gregory      0    0    0
 1. Han          0    0    0
 1. Irma         0    0    0
 1. Jan          0    0    0
 1. Kim          0    0    0
 1. Lili         0    0    0
 1. Mehdi        0    0    0
 1. Noah         0    0    0
 1. Oskar        0    0    0
 1. Penelope     0    0    0

ROUND 1: PAIRINGS
[('Kim', 'Fanfan'), ('Oskar', 'Bob'), ('Irma', 'Han'), ('Jan', 'Gregory'), ('Kim', 'Elena'), ('Penelope', 'Bob'), ('Mehdi', 'David'), ('Oskar', 'Alice'), ('Noah', 'David'), ('Penelope', 'Alice'), ('Mehdi', 'Chen'), ('Lili', 'Fanfan'), ('Irma', 'Gregory'), ('Noah', 'Chen'), ('Jan', 'Han'), ('Lili', 'Elena')]

ROUND 1: RESULTS
['Kim 0-1 Fanfan', 'Oskar 1-0 Bob', 'Irma 1-0 Han', 'Jan 1-0 Gregory', 'Kim 0-1 Elena', 'Penelope 1-0 Bob', 'Mehdi 1-0 David', 'Oskar 0-1 Alice', 'Noah 1-0 David', 'Penelope 0-1 Alice', 'Mehdi 0-1 Chen', 'Lili 1-0 Fanfan', 'Irma 1-0 Gregory', 'Noah 1-0 Chen', 'Jan 0-1 Han', 'Lili 1-0 Elena']

STANDINGS AFTER ROUND 1
  . name      wins  sos sosos
 1. Alice        2    2    4
 1. Lili         2    2    4
 3. Irma         2    1    6
 3. Noah         2    1    6
 5. Chen         1    3    2
 5. Han          1    3    2
 7. Elena        1    2    4
 7. Fanfan       1    2    4
 7. Oskar        1    2    4
 7. Penelope     1    2    4
11. Jan          1    1    6
11. Mehdi        1    1    6
13. David        0    3    2
13. Gregory      0    3    2
15. Bob          0    2    4
15. Kim          0    2    4

ROUND 2: PAIRINGS
[('Noah', 'Irma'), ('Lili', 'Alice'), ('Penelope', 'Elena'), ('Lili', 'Noah'), ('Gregory', 'Bob'), ('Kim', 'Bob'), ('Elena', 'Mehdi'), ('Penelope', 'Han'), ('Mehdi', 'Jan'), ('Oskar', 'Jan'), ('Han', 'Chen'), ('Kim', 'David'), ('Alice', 'Irma'), ('Gregory', 'David'), ('Oskar', 'Fanfan'), ('Fanfan', 'Chen')]

ROUND 2: RESULTS
['Noah 1-0 Irma', 'Lili 0-1 Alice', 'Penelope 1-0 Elena', 'Lili 1-0 Noah', 'Gregory 1-0 Bob', 'Kim 0-1 Bob', 'Elena 1-0 Mehdi', 'Penelope 0-1 Han', 'Mehdi 1-0 Jan', 'Oskar 0-1 Jan', 'Han 1-0 Chen', 'Kim 0-1 David', 'Alice 0-1 Irma', 'Gregory 0-1 David', 'Oskar 1-0 Fanfan', 'Fanfan 0-1 Chen']

STANDINGS AFTER ROUND 2
  . name      wins  sos sosos
 1. Irma         3   10   37
 2. Alice        3   10   35
 3. Noah         3   10   34
 4. Han          3    9   36
 5. Lili         3    9   34
 6. Chen         2    9   34
 7. Penelope     2    9   31
 8. Jan          2    8   32
 9. Mehdi        2    8   30
10. Elena        2    7   32
11. Oskar        2    7   30
12. David        2    6   32
13. Gregory      1    8   29
14. Fanfan       1    7   31
15. Bob          1    5   30
16. Kim          0    6   25

ROUND 3: PAIRINGS
[('Lili', 'Han'), ('Elena', 'David'), ('Elena', 'Jan'), ('Chen', 'Alice'), ('Noah', 'Alice'), ('Fanfan', 'Bob'), ('Oskar', 'Kim'), ('Han', 'Noah'), ('Gregory', 'Kim'), ('Fanfan', 'Gregory'), ('Penelope', 'Jan'), ('Oskar', 'Mehdi'), ('Penelope', 'Mehdi'), ('Bob', 'David'), ('Irma', 'Lili'), ('Chen', 'Irma')]

ROUND 3: RESULTS
['Lili 0-1 Han', 'Elena 0-1 David', 'Elena 0-1 Jan', 'Chen 0-1 Alice', 'Noah 0-1 Alice', 'Fanfan 0-1 Bob', 'Oskar 1-0 Kim', 'Han 0-1 Noah', 'Gregory 1-0 Kim', 'Fanfan 0-1 Gregory', 'Penelope 0-1 Jan', 'Oskar 1-0 Mehdi', 'Penelope 0-1 Mehdi', 'Bob 0-1 David', 'Irma 0-1 Lili', 'Chen 1-0 Irma']

STANDINGS AFTER ROUND 3
  . name      wins  sos sosos
 1. Alice        5   20  120
 2. Noah         4   23  116
 3. Han          4   20  123
 4. Lili         4   19  119
 5. Jan          4   18  105
 6. Oskar        4   15  103
 7. David        4   14  103
 8. Irma         3   23  116
 9. Chen         3   20  121
10. Mehdi        3   19  104
11. Gregory      3   14  101
12. Penelope     2   20  108
13. Elena        2   17  106
14. Bob          2   14   95
15. Fanfan       1   16   98
16. Kim          0   16   90