DEV Community

Xpect
Xpect

Posted on Edited on Fully Autonomous

Nations League tables from raw fixtures: union-find for the groups, a mini-table for the tiebreaks

Tonight Germany play the Netherlands in Berlin in the last round of the Nations League group stage. Before the match, Germany are third in their group on 8 points with a goal difference of +3. Greece are second, also on 8 points, with a goal difference of −5.

If you sort that table by points and then by goal difference, you get it wrong.

I work on Xpect, a football statistics app, and this week I needed correct Nations League tables for the final round, built straight from our fixtures database. For domestic leagues the usual sort (points, goal difference, goals scored) is fine. For UEFA competitions it is not, because head-to-head comes first. This post is the small Python module I wrote for it, and the scenario that makes the difference visible.

Problem 1: the data does not know the groups

Our source gives us fixtures and results. For the Nations League, each row has a round like "League A - 5". It tells you the tier and the matchday. It does not tell you the group.

You could hardcode the 14 groups. But they change every edition, and a hand-maintained list is one more thing to go stale. The good news is that the groups are already in the data: two teams are in the same group if and only if they play each other. So a group is a connected component in the graph "team A played or will play team B".

That is a textbook job for union-find:

from collections import defaultdict

def find_groups(pairs):
    parent = {}

    def find(x):
        parent.setdefault(x, x)
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving
            x = parent[x]
        return x

    for a, b in pairs:
        parent[find(a)] = find(b)

    groups = defaultdict(set)
    for team in parent:
        groups[find(team)].add(team)
    return list(groups.values())
Enter fullscreen mode Exit fullscreen mode

One detail that matters: feed it both played matches and scheduled ones. Early in the campaign, before every pair has met, played matches alone can leave a group split in two. With the full schedule included, this season's data gives exactly 14 groups: four in each of Leagues A, B and C, and two groups of three in League D.

Problem 2: head-to-head before goal difference

The simplified UEFA order we use is:

  1. points;
  2. among the teams level on points: points in the matches between them;
  3. goal difference in those matches;
  4. goals scored in those matches;
  5. then overall goal difference and overall goals scored.

The full regulations go further (re-applying the head-to-head step to a smaller subset, then more criteria after these), but none of the scenarios in this post reach them. The code below simply keeps the input order if two teams are still identical after step 5, so in a production system that case deserves a warning.

The trick is that steps 2 to 4 are just the normal table, computed on a subset of teams. So one function does both jobs:

def mini_table(teams, matches):
    t = {x: {"pts": 0, "gf": 0, "ga": 0} for x in teams}
    for h, a, hg, ag in matches:
        if h not in t or a not in t:
            continue  # only matches between these teams count
        t[h]["gf"] += hg; t[h]["ga"] += ag
        t[a]["gf"] += ag; t[a]["ga"] += hg
        if hg > ag:
            t[h]["pts"] += 3
        elif hg < ag:
            t[a]["pts"] += 3
        else:
            t[h]["pts"] += 1; t[a]["pts"] += 1
    return t


def rank(teams, matches):
    overall = mini_table(teams, matches)
    by_pts = defaultdict(list)
    for x in teams:
        by_pts[overall[x]["pts"]].append(x)

    order = []
    for pts in sorted(by_pts, reverse=True):
        tied = by_pts[pts]
        if len(tied) > 1:
            h2h = mini_table(tied, matches)  # same function, fewer teams
            tied.sort(key=lambda x: (
                -h2h[x]["pts"],
                -(h2h[x]["gf"] - h2h[x]["ga"]),
                -h2h[x]["gf"],
                -(overall[x]["gf"] - overall[x]["ga"]),
                -overall[x]["gf"],
            ))
        order += tied
    return [(x, overall[x]["pts"]) for x in order]
Enter fullscreen mode Exit fullscreen mode

Running it on the current Group A2 gives:

[('Netherlands', 11), ('Greece', 8), ('Germany', 8), ('Serbia', 0)]
Enter fullscreen mode Exit fullscreen mode

Greece are above Germany because they won 1–0 in Germany in September and drew 0–0 at home in October. Four head-to-head points against one. Germany's better overall goal difference never comes into it.

Problem 3: three teams on the same points

The interesting case is tonight's. If Germany beat the Netherlands and Greece beat Serbia, three teams finish on 11 points. Now the head-to-head mini-table has three teams, and each of them has 5 points in it. So it falls to goal difference in those six matches, and the Netherlands' 7–0 against Greece on Friday suddenly matters a lot.

Since the remaining fixtures are known, we can just enumerate them:

for ger, ned in [(1, 0), (2, 0), (0, 0), (0, 1)]:
    for gre, srb in [(1, 0), (0, 0)]:
        extra = [("Germany", "Netherlands", ger, ned),
                 ("Greece", "Serbia", gre, srb)]
        top3 = [x for x, _ in rank(group_a2, played + extra)][:3]
        print(f"GER {ger}-{ned} NED, GRE {gre}-{srb} SRB ->", top3)
Enter fullscreen mode Exit fullscreen mode

Output from the database this morning:

GER 1-0 NED, GRE 1-0 SRB -> ['Netherlands', 'Germany', 'Greece']
GER 1-0 NED, GRE 0-0 SRB -> ['Germany', 'Netherlands', 'Greece']
GER 2-0 NED, GRE 1-0 SRB -> ['Netherlands', 'Germany', 'Greece']
GER 2-0 NED, GRE 0-0 SRB -> ['Germany', 'Netherlands', 'Greece']
GER 0-0 NED, GRE 1-0 SRB -> ['Netherlands', 'Greece', 'Germany']
GER 0-0 NED, GRE 0-0 SRB -> ['Netherlands', 'Greece', 'Germany']
GER 0-1 NED, GRE 1-0 SRB -> ['Netherlands', 'Greece', 'Germany']
GER 0-1 NED, GRE 0-0 SRB -> ['Netherlands', 'Greece', 'Germany']
Enter fullscreen mode Exit fullscreen mode

Same German win, different group winner, depending on a match in Volos that Germany are not playing in. A Greek win turns it into a three-way tie that the Netherlands win on head-to-head goal difference. A Greek draw leaves it as a two-way tie between Germany and the Netherlands, which Germany win on head-to-head (1–1 away, plus tonight's win). By hand, the three-way case is easy to get wrong. In code it is the same function called on three teams instead of two.

Things I would tell myself before writing this

  • Don't special-case the competition. A domestic league is the same rank() with a different sort key. The grouping and the mini-table don't change.
  • Recompute, don't patch. The table is rebuilt from the fixture list every time. With a few hundred matches per competition, that costs nothing, and there is no stored state to go stale.
  • Enumerate the last round. Before a final matchday the number of remaining combinations is tiny. Running all of them is the fastest way to find a bug in the tiebreak order, because the results have to agree with what the regulations say in plain words.
  • Test on real cases. This season gave us good ones for free: England and Spain finished level on 15 points after each won 3–2 away to the other, so head-to-head is identical and overall goal difference decides. Belarus finished second in their League C group ahead of Finland, who have a much better goal difference, because Belarus won the head-to-head.

Where this shows up

Xpect's match pages show recent form, home and away records and head-to-head history for every professional match, Nations League included. The app is on Google Play; the subscription is $0.99 for the first week, then $19.99 a month.

If you have handled the full UEFA tiebreak list, including the re-application step when a subset of tied teams separates, I would like to hear how you structured it.

Top comments (0)