ioftools / networkxMiCe / networkxmaster / networkx / algorithms / coloring / greedy_coloring_with_interchange.py @ 5cef0f13
History  View  Annotate  Download (6.5 KB)
1 
import itertools 

2  
3 
__all__ = ['greedy_coloring_with_interchange']

4  
5  
6 
class Node(object): 
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 "Node_id: {0}, Color: {1}, Adj_list: ({2}), \ 
18 
adj_color: ({3})".format(

19 
self.node_id, self.color, self.adj_list, self.adj_color) 
20  
21 
def assign_color(self, adj_entry, color): 
22 
adj_entry.col_prev = None

23 
adj_entry.col_next = self.adj_color[color]

24 
self.adj_color[color] = adj_entry

25 
if adj_entry.col_next is not None: 
26 
adj_entry.col_next.col_prev = adj_entry 
27  
28 
def clear_color(self, adj_entry, color): 
29 
if adj_entry.col_prev is None: 
30 
self.adj_color[color] = adj_entry.col_next

31 
else:

32 
adj_entry.col_prev.col_next = adj_entry.col_next 
33 
if adj_entry.col_next is not None: 
34 
adj_entry.col_next.col_prev = adj_entry.col_prev 
35  
36 
def iter_neighbors(self): 
37 
adj_node = self.adj_list

38 
while adj_node is not None: 
39 
yield adj_node

40 
adj_node = adj_node.next 
41  
42 
def iter_neighbors_color(self, color): 
43 
adj_color_node = self.adj_color[color]

44 
while adj_color_node is not None: 
45 
yield adj_color_node.node_id

46 
adj_color_node = adj_color_node.col_next 
47  
48  
49 
class AdjEntry(object): 
50  
51 
__slots__ = ['node_id', 'next', 'mate', 'col_next', 'col_prev'] 
52  
53 
def __init__(self, node_id): 
54 
self.node_id = node_id

55 
self.next = None 
56 
self.mate = None 
57 
self.col_next = None 
58 
self.col_prev = None 
59  
60 
def __repr__(self): 
61 
return "Node_id: {0}, Next: ({1}), Mate: ({2}), \ 
62 
col_next: ({3}), col_prev: ({4})".format(

63 
self.node_id,

64 
self.next,

65 
self.mate.node_id,

66 
None if self.col_next is None else self.col_next.node_id, 
67 
None if self.col_prev is None else self.col_prev.node_id 
68 
) 
69  
70  
71 
def 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, 415424, 1983.

84 
ISBN 0486453537.

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(

109 
lambda x: x in col_used, itertools.count())) 
110  
111 
# k1 is now the lowest available color

112 
if k1 > k:

113 
connected = True

114 
visited = set()

115 
col1 = 1

116 
col2 = 1

117 
while connected and col1 < k: 
118 
col1 += 1

119 
neighbor_cols = ( 
120 
graph[node].iter_neighbors_color(col1)) 
121 
col1_adj = [it for it in neighbor_cols] 
122  
123 
col2 = col1 
124 
while connected and col2 < k: 
125 
col2 += 1

126 
visited = set(col1_adj)

127 
frontier = list(col1_adj)

128 
i = 0

129 
while i < len(frontier): 
130 
search_node = frontier[i] 
131 
i += 1

132 
col_opp = ( 
133 
col2 if graph[search_node].color == col1 else col1) 
134 
neighbor_cols = ( 
135 
graph[search_node].iter_neighbors_color(col_opp)) 
136  
137 
for neighbor in neighbor_cols: 
138 
if neighbor not in visited: 
139 
visited.add(neighbor) 
140 
frontier.append(neighbor) 
141  
142 
# Search if node is not adj to any col2 vertex

143 
connected = len(visited.intersection(

144 
graph[node].iter_neighbors_color(col2))) > 0

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 
col2_adj = graph[search_node].adj_color[col2] 
153 
graph[search_node].adj_color[col2] = ( 
154 
graph[search_node].adj_color[col1]) 
155 
graph[search_node].adj_color[col1] = col2_adj 
156  
157 
# Update all the neighboring nodes

158 
for search_node in visited: 
159 
col = graph[search_node].color 
160 
col_opp = col1 if col == col2 else col2 
161 
for adj_node in graph[search_node].iter_neighbors(): 
162 
if graph[adj_node.node_id].color != col_opp:

163 
# Direct reference to entry

164 
adj_mate = adj_node.mate 
165 
graph[adj_node.node_id].clear_color( 
166 
adj_mate, col_opp) 
167 
graph[adj_node.node_id].assign_color(adj_mate, col) 
168 
k1 = col1 
169  
170 
# We can color this node color k1

171 
graph[node].color = k1 
172 
k = max(k1, k)

173  
174 
# Update the neighbors of this node

175 
for adj_node in graph[node].iter_neighbors(): 
176 
adj_mate = adj_node.mate 
177 
graph[adj_node.node_id].assign_color(adj_mate, k1) 
178  
179 
return {node.node_id: node.color for node in graph.values()} 