1import itertools
2
3__all__ = ["greedy_coloring_with_interchange"]
4
5
6class Node:
7
8    __slots__ = ["node_id", "color", "adj_list", "adj_color"]
9
10    def __init__(self, node_id, n):
11        self.node_id = node_id
12        self.color = -1
13        self.adj_list = None
14        self.adj_color = [None for _ in range(n)]
15
16    def __repr__(self):
17        return (
18            f"Node_id: {self.node_id}, Color: {self.color}, "
19            f"Adj_list: ({self.adj_list}), adj_color: ({self.adj_color})"
20        )
21
22    def assign_color(self, adj_entry, color):
23        adj_entry.col_prev = None
24        adj_entry.col_next = self.adj_color[color]
25        self.adj_color[color] = adj_entry
26        if adj_entry.col_next is not None:
27            adj_entry.col_next.col_prev = adj_entry
28
29    def clear_color(self, adj_entry, color):
30        if adj_entry.col_prev is None:
31            self.adj_color[color] = adj_entry.col_next
32        else:
33            adj_entry.col_prev.col_next = adj_entry.col_next
34        if adj_entry.col_next is not None:
35            adj_entry.col_next.col_prev = adj_entry.col_prev
36
37    def iter_neighbors(self):
38        adj_node = self.adj_list
39        while adj_node is not None:
40            yield adj_node
41            adj_node = adj_node.next
42
43    def iter_neighbors_color(self, color):
44        adj_color_node = self.adj_color[color]
45        while adj_color_node is not None:
46            yield adj_color_node.node_id
47            adj_color_node = adj_color_node.col_next
48
49
50class AdjEntry:
51
52    __slots__ = ["node_id", "next", "mate", "col_next", "col_prev"]
53
54    def __init__(self, node_id):
55        self.node_id = node_id
56        self.next = None
57        self.mate = None
58        self.col_next = None
59        self.col_prev = None
60
61    def __repr__(self):
62        col_next = None if self.col_next is None else self.col_next.node_id
63        col_prev = None if self.col_prev is None else self.col_prev.node_id
64        return (
65            f"Node_id: {self.node_id}, Next: ({self.next}), "
66            f"Mate: ({self.mate.node_id}), "
67            f"col_next: ({col_next}), col_prev: ({col_prev})"
68        )
69
70
71def greedy_coloring_with_interchange(original_graph, nodes):
72    """
73        This procedure is an adaption of the algorithm described by [1]_,
74        and is an implementation of coloring with interchange. Please be
75        advised, that the datastructures used are rather complex because
76        they are optimized to minimize the time spent identifying
77        subcomponents of the graph, which are possible candidates for color
78        interchange.
79
80    References
81    ----------
82    .. [1] Maciej M. Syslo, Marsingh Deo, Janusz S. Kowalik,
83       Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983.
84       ISBN 0-486-45353-7.
85    """
86    n = len(original_graph)
87
88    graph = {node_id: Node(node_id, n) for node_id in original_graph}
89
90    for (node1, node2) in original_graph.edges():
91        adj_entry1 = AdjEntry(node2)
92        adj_entry2 = AdjEntry(node1)
93        adj_entry1.mate = adj_entry2
94        adj_entry2.mate = adj_entry1
95        node1_head = graph[node1].adj_list
96        adj_entry1.next = node1_head
97        graph[node1].adj_list = adj_entry1
98        node2_head = graph[node2].adj_list
99        adj_entry2.next = node2_head
100        graph[node2].adj_list = adj_entry2
101
102    k = 0
103    for node in nodes:
104        # Find the smallest possible, unused color
105        neighbors = graph[node].iter_neighbors()
106        col_used = {graph[adj_node.node_id].color for adj_node in neighbors}
107        col_used.discard(-1)
108        k1 = next(itertools.dropwhile(lambda x: x in col_used, itertools.count()))
109
110        # k1 is now the lowest available color
111        if k1 > k:
112            connected = True
113            visited = set()
114            col1 = -1
115            col2 = -1
116            while connected and col1 < k:
117                col1 += 1
118                neighbor_cols = graph[node].iter_neighbors_color(col1)
119                col1_adj = [it for it in neighbor_cols]
120
121                col2 = col1
122                while connected and col2 < k:
123                    col2 += 1
124                    visited = set(col1_adj)
125                    frontier = list(col1_adj)
126                    i = 0
127                    while i < len(frontier):
128                        search_node = frontier[i]
129                        i += 1
130                        col_opp = col2 if graph[search_node].color == col1 else col1
131                        neighbor_cols = graph[search_node].iter_neighbors_color(col_opp)
132
133                        for neighbor in neighbor_cols:
134                            if neighbor not in visited:
135                                visited.add(neighbor)
136                                frontier.append(neighbor)
137
138                    # Search if node is not adj to any col2 vertex
139                    connected = (
140                        len(
141                            visited.intersection(graph[node].iter_neighbors_color(col2))
142                        )
143                        > 0
144                    )
145
146            # If connected is false then we can swap !!!
147            if not connected:
148                # Update all the nodes in the component
149                for search_node in visited:
150                    graph[search_node].color = (
151                        col2 if graph[search_node].color == col1 else col1
152                    )
153                    col2_adj = graph[search_node].adj_color[col2]
154                    graph[search_node].adj_color[col2] = graph[search_node].adj_color[
155                        col1
156                    ]
157                    graph[search_node].adj_color[col1] = col2_adj
158
159                # Update all the neighboring nodes
160                for search_node in visited:
161                    col = graph[search_node].color
162                    col_opp = col1 if col == col2 else col2
163                    for adj_node in graph[search_node].iter_neighbors():
164                        if graph[adj_node.node_id].color != col_opp:
165                            # Direct reference to entry
166                            adj_mate = adj_node.mate
167                            graph[adj_node.node_id].clear_color(adj_mate, col_opp)
168                            graph[adj_node.node_id].assign_color(adj_mate, col)
169                k1 = col1
170
171        # We can color this node color k1
172        graph[node].color = k1
173        k = max(k1, k)
174
175        # Update the neighbors of this node
176        for adj_node in graph[node].iter_neighbors():
177            adj_mate = adj_node.mate
178            graph[adj_node.node_id].assign_color(adj_mate, k1)
179
180    return {node.node_id: node.color for node in graph.values()}
181