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