/usr/lib/python2.7/dist-packages/networkx/algorithms/coloring/greedy_coloring_with_interchange.py is in python-networkx 1.11-1ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 | import networkx as nx
import itertools
__all__ = ['greedy_coloring_with_interchange']
class Node(object):
__slots__ = ['node_id', 'color', 'adj_list', 'adj_color']
def __init__(self, node_id, n):
self.node_id = node_id
self.color = -1
self.adj_list = None
self.adj_color = [None for _ in range(n)]
def __repr__(self):
return "Node_id: {0}, Color: {1}, Adj_list: ({2}), \
adj_color: ({3})".format(
self.node_id, self.color, self.adj_list, self.adj_color)
def assign_color(self, adj_entry, color):
adj_entry.col_prev = None
adj_entry.col_next = self.adj_color[color]
self.adj_color[color] = adj_entry
if adj_entry.col_next != None:
adj_entry.col_next.col_prev = adj_entry
def clear_color(self, adj_entry, color):
if adj_entry.col_prev == None:
self.adj_color[color] = adj_entry.col_next
else:
adj_entry.col_prev.col_next = adj_entry.col_next
if adj_entry.col_next != None:
adj_entry.col_next.col_prev = adj_entry.col_prev
def iter_neighbors(self):
adj_node = self.adj_list
while adj_node != None:
yield adj_node
adj_node = adj_node.next
def iter_neighbors_color(self, color):
adj_color_node = self.adj_color[color]
while adj_color_node != None:
yield adj_color_node.node_id
adj_color_node = adj_color_node.col_next
class AdjEntry(object):
__slots__ = ['node_id', 'next', 'mate', 'col_next', 'col_prev']
def __init__(self, node_id):
self.node_id = node_id
self.next = None
self.mate = None
self.col_next = None
self.col_prev = None
def __repr__(self):
return "Node_id: {0}, Next: ({1}), Mate: ({2}), \
col_next: ({3}), col_prev: ({4})".format(
self.node_id,
self.next,
self.mate.node_id,
None if self.col_next == None else self.col_next.node_id,
None if self.col_prev == None else self.col_prev.node_id
)
def greedy_coloring_with_interchange(original_graph, nodes):
"""
This procedure is an adaption of the algorithm described by [1]_,
and is an implementation of coloring with interchange. Please be
advised, that the datastructures used are rather complex because
they are optimized to minimize the time spent identifying
subcomponents of the graph, which are possible candidates for color
interchange.
References
----------
.. [1] Maciej M. Syslo, Marsingh Deo, Janusz S. Kowalik,
Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983.
ISBN 0-486-45353-7.
"""
n = len(original_graph)
graph = {node_id: Node(node_id, n) for node_id in original_graph}
for (node1, node2) in original_graph.edges_iter():
adj_entry1 = AdjEntry(node2)
adj_entry2 = AdjEntry(node1)
adj_entry1.mate = adj_entry2
adj_entry2.mate = adj_entry1
node1_head = graph[node1].adj_list
adj_entry1.next = node1_head
graph[node1].adj_list = adj_entry1
node2_head = graph[node2].adj_list
adj_entry2.next = node2_head
graph[node2].adj_list = adj_entry2
k = 0
for node in nodes:
# Find the smallest possible, unused color
neighbors = graph[node].iter_neighbors()
col_used = {graph[adj_node.node_id].color for adj_node in neighbors}
col_used.discard(-1)
k1 = next(itertools.dropwhile(
lambda x: x in col_used, itertools.count()))
# k1 is now the lowest available color
if k1 > k:
connected = True
visited = set()
col1 = -1
col2 = -1
while connected and col1 < k:
col1 += 1
neighbor_cols = (
graph[node].iter_neighbors_color(col1))
col1_adj = [it for it in neighbor_cols]
col2 = col1
while connected and col2 < k:
col2 += 1
visited = set(col1_adj)
frontier = list(col1_adj)
i = 0
while i < len(frontier):
search_node = frontier[i]
i += 1
col_opp = (
col2 if graph[search_node].color == col1 else col1)
neighbor_cols = (
graph[search_node].iter_neighbors_color(col_opp))
for neighbor in neighbor_cols:
if neighbor not in visited:
visited.add(neighbor)
frontier.append(neighbor)
# Search if node is not adj to any col2 vertex
connected = len(visited.intersection(
graph[node].iter_neighbors_color(col2))) > 0
# If connected is false then we can swap !!!
if not connected:
# Update all the nodes in the component
for search_node in visited:
graph[search_node].color = (
col2 if graph[search_node].color == col1 else col1)
col2_adj = graph[search_node].adj_color[col2]
graph[search_node].adj_color[col2] = (
graph[search_node].adj_color[col1])
graph[search_node].adj_color[col1] = col2_adj
# Update all the neighboring nodes
for search_node in visited:
col = graph[search_node].color
col_opp = col1 if col == col2 else col2
for adj_node in graph[search_node].iter_neighbors():
if graph[adj_node.node_id].color != col_opp:
# Direct reference to entry
adj_mate = adj_node.mate
graph[adj_node.node_id].clear_color(
adj_mate, col_opp)
graph[adj_node.node_id].assign_color(adj_mate, col)
k1 = col1
# We can color this node color k1
graph[node].color = k1
k = max(k1, k)
# Update the neighbors of this node
for adj_node in graph[node].iter_neighbors():
adj_mate = adj_node.mate
graph[adj_node.node_id].assign_color(adj_mate, k1)
return {node.node_id: node.color for node in graph.values()}
|