graph.py

import numpy as np
import time
np.random.seed(281)


def generate_graph(n, p, k):
    G = (np.random.rand(n, n) <= p).astype(np.int32)
    G[np.triu_indices(n)] = 0
    # Random integer weighing scheme
    for x in np.nditer(G, op_flags=['writeonly']):
        if x > 0:
            x *= np.random.randint(1, k+1)
    # Non-repeating integer weighing scheme
    # weight = 1
    # for x in np.nditer(G, op_flags=['writeonly']):
    #     if x > 0:
    #         x *= weight
    #         weight += 1
    G += G.T
    return G


def generate_graph_2(n, p):
    G = (np.random.rand(n, n) <= p).astype(np.float)
    G[np.triu_indices(n)] = 0
    for x in np.nditer(G, op_flags=['writeonly']):
        if x > 0:
            x *= np.random.rand()
    G += G.T
    return G


def total_matching_weight(G, m):
    total = 0
    it = np.nditer(m, flags=['f_index'])
    for e in it:
        if e != -1 and it.index < e:
            total += G[it.index, e]
    return total


def check_matching_validity(m):
    it = np.nditer(m, flags=['f_index'])
    for e in it:
        if e != -1:
            f = m[e]
            if m[f] != e:
                return False
    return True


def greedy(G):
    s = np.full(G.shape[0], -1)
    it = np.nditer(G, flags=['multi_index'])
    # e = [(x+0, it.multi_index) for x in it if x != 0 and it.multi_index[0] < it.multi_index[1]]
    e = []
    for x in it:
        if x != 0 and it.multi_index[0] < it.multi_index[1]:
            e.append((x+0, -sum(it.multi_index), it.multi_index))
    e.sort(key=lambda x: (x[0], x[1]), reverse=True)
    for _, _, (u, v) in e:
        if (s[u] == -1) and (s[v] == -1):
            s[u] = v
            s[v] = u
    return s


def suitor(G):
    s = np.full(G.shape[0], -1)
    for u in range(G.shape[0]):
        while u != -1:
            v = -1
            heaviest = 0
            for x in range(G.shape[0]):
                if (G[u, x] == 0):
                    continue
                if (s[x] == -1) or (G[u, x] > G[x, s[x]]) or ((G[u, x] == G[x, s[x]]) and (u < s[x])):
                    if G[u, x] > heaviest:
                        heaviest = G[u, x]
                        v = x
            t = u
            u = s[v] if v != -1 else -1
            if v != -1:
                s[v] = t
    return s


def pga(G):
    s = np.full(G.shape[0], -1)
    visited = np.full(G.shape[0], False)
    for u in range(G.shape[0]):
        if visited[u]:
            continue
        P = []
        V = [u]
        visited[u] = True
        while True:
            heaviest = 0
            v = -1
            for x in range(G.shape[0]):
                if (G[u, x] == 0) or visited[x]:
                    continue
                if G[u, x] > heaviest:
                    heaviest = G[u, x]
                    v = x
            if v == -1:
                break
            P.append(G[u, v])
            V.append(v)
            u = v
            visited[u] = True
        if sum(P[1::2]) > sum(P[0::2]):
            for i in range(1, len(V)-1, 2):
                s[V[i]] = V[i+1]
                s[V[i+1]] = V[i]
        else:
            for i in range(0, len(V)-1, 2):
                s[V[i]] = V[i+1]
                s[V[i+1]] = V[i]
    return s


if __name__ == '__main__':
    # import networkx as nx
    # import pylab as plt
    G = generate_graph(9, 0.25, 35)
    # print(G)
    # nx.draw(nx.from_numpy_matrix(G), with_labels=True)
    # plt.show()
    t = time.time()
    m1 = greedy(G)
    print(time.time() - t)
    print(total_matching_weight(G, m1))
    t = time.time()
    m2 = pga(G)
    print(check_matching_validity(m2))
    print(time.time() - t)
    # assert total_matching_weight(G, m1) == total_matching_weight(G, m2)
    # check_matching_validity(m2)
    print(total_matching_weight(G, m2))

main.py

from graph import generate_graph_2, suitor, pga, total_matching_weight
import pylab as plt
import time

W = []
X = range(1, 201)
for n in X:
    print(n)
    w1 = 0
    w2 = 0
    for _ in range(3):
        G = generate_graph_2(n, 0.5)
        m1 = suitor(G)
        m2 = pga(G)
        # w1 += (m1[m1 != -1]).size
        # w2 += (m2[m2 != -1]).size
        w1 += total_matching_weight(G, m1)
        w2 += total_matching_weight(G, m2)
    w1 += 1e-3
    w2 += 1e-3
    W.append(w1/w2)
    

fig, ax = plt.subplots()
# line1, = ax.plot(X, t10, label="p = 0.1")
# line2, = ax.plot(X, t50, label="p = 0.5")
ax.scatter(X, W, s=2, color='black')
ax.plot(X, [1 for i in range(len(X))], linestyle='--', color='orange')
ax.legend()
plt.show()