algovault/code_library/python/graph_matching.py at master · sgtlaugh/algovault · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
"""
General Graph Matching

maximum_matching(edges, mod): size of a maximum matching of a simple undirected graph, by the Tutte matrix rank,
wrong with probability at most n / mod

Complexity: O(n^3) for n vertices, even on sparse graphs
"""

import itertools
from random import randint

_DEFAULT_PRIME = 1073750017


def maximum_matching(edges, mod=_DEFAULT_PRIME):
    """
    Returns the maximum cardinality matching of any simple graph (undirected, unweighted, no self-loops)
    Uses a randomized algorithm to compute the rank of the Tutte matrix
    The rank of the Tutte matrix is equal to twice the size of the maximum matching with high probability
    The probability for error is not more than n/mod

    Complexity: O(n ^ 3), even on sparse graphs

    :param edges: a list of edges, assume nodes can be anything numbered from 0 to max number in edges
    :param mod: optional, a large random prime
    :return: the maximum cardinality matching of the graph
    """

    if not edges:
        return 0

    n = max(itertools.chain(*edges)) + 1
    matrix = _get_tutte_matrix(n, edges, mod)
    return _gauss(n, matrix, mod) // 2


def _get_tutte_matrix(n, edges, mod):
    matrix = [[0] * n for _ in range(n)]

    for u, v in edges:
        val = randint(1, mod - 1)
        matrix[u][v], matrix[v][u] = val, mod - val

    return matrix


def _gauss(n, matrix, mod):
    r = 0
    for j in range(n):
        k = r
        while k < n and not matrix[k][j]:
            k += 1

        if k == n:
            continue

        inv = pow(matrix[k][j], mod - 2, mod)
        for i in range(n):
            matrix[k][i] = inv * matrix[k][i] % mod
        matrix[k], matrix[r] = matrix[r], matrix[k]

        for u in range(r + 1, n):
            # reducing indexing costs to gain performance boost for the next loop
            matrix_u, matrix_r = matrix[u], matrix[r]
            if matrix_u[j]:
                for v in range(j + 1, n):
                    if matrix_r[v]:
                        matrix_u[v] = (matrix_u[v] - matrix_r[v] * matrix_u[j]) % mod

        r += 1

    return r


def main():
    edges = []
    assert maximum_matching(edges) == 0

    for e in [(0, 1), (1, 2), (2, 0)]:
        edges.append(e)
        assert maximum_matching(edges) == 1

    for e in [(2, 3), (3, 4)]:
        edges.append(e)
        assert maximum_matching(edges) == 2

    for e in [(4, 5), (5, 6)]:
        edges.append(e)
        assert maximum_matching(edges) == 3

    for e in [(7, 8), (7, 9), (7, 10)]:
        edges.append(e)
        assert maximum_matching(edges) == 4

    edges.append((4, 10))
    assert maximum_matching(edges) == 5

    for e in [(9, 11), (8, 11)]:
        edges.append(e)
        assert maximum_matching(edges) == 6


if __name__ == '__main__':
    main()