GraphAlgorithms/partition_refinement.py at master · Bazch/GraphAlgorithms · 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
from graph_io import *


def color_refinement(G: Graph, C: Graph = None):
    partition = {}
    rho = {}
    for vertex in G.vertices:
        if vertex.label not in partition:
            partition[vertex.label] = [vertex]
        else:
            partition[vertex.label].append(vertex)

    for vertex in C.vertices:
        if vertex.label not in partition:
            partition[vertex.label] = [vertex]
        else:
            partition[vertex.label].append(vertex)

    for label in partition:
        isEqual = is_equal_vertices(G, partition[label])
        if not isEqual:
            return 0, partition
        if len(partition[label]) > 2:
            refine_partition(G, partition[label])

    for vertex in G.vertices:
        if hasattr(vertex, 'newlabel'):
            vertex.label = vertex.newlabel
            delattr(vertex, 'newlabel')
        if vertex.label not in rho:
            rho[vertex.label] = [vertex]
        else:
            rho[vertex.label].append(vertex)

    for vertex in C.vertices:
        if hasattr(vertex, 'newlabel'):
            vertex.label = vertex.newlabel
            delattr(vertex, 'newlabel')
        if vertex.label not in rho:
            rho[vertex.label] = [vertex]
        else:
            rho[vertex.label].append(vertex)

    if rho == partition:
        count = 0
        for label in rho:
            count += 1
        if count == len(G.vertices):
            return 1, partition
        return -1, partition

    return None, partition


def is_equal_vertices(G: Graph, vertices: list):
    count_g = 0
    count_c = 0
    for vertex in vertices:
        if vertex.graph == G:
            count_g += 1
        else:
            count_c += 1
    if count_g == count_c:
        return True
    else:
        return False


def refine_partition(G: Graph, vertices: list):
    neighbour_set = {}
    for i, vertex in enumerate(vertices):
        neighbours = []
        for neighbour in vertex.neighbours:
            neighbours.append(neighbour.label)
        neighbours.sort()
        neighbours_str = str(neighbours)
        if i == 0:
            neighbour_set[neighbours_str] = vertex
        elif neighbours_str not in neighbour_set:
            G.increase_highest_vertex()
            vertex.newlabel = G.highest_vertex
            neighbour_set[neighbours_str] = vertex
        else:
            same_vertex = neighbour_set.get(neighbours_str)
            if hasattr(same_vertex, 'newlabel'):
                vertex.newlabel = same_vertex.newlabel
            else:
                vertex.newlabel = same_vertex.label