/usr/lib/python2.7/dist-packages/networkx/algorithms/coloring/greedy_coloring.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 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 | # -*- coding: utf-8 -*-
"""
Greedy graph coloring using various strategies.
"""
# Copyright (C) 2014 by
# Christian Olsson <chro@itu.dk>
# Jan Aagaard Meier <jmei@itu.dk>
# Henrik Haugbølle <hhau@itu.dk>
# All rights reserved.
# BSD license.
import networkx as nx
import random
import itertools
from . import greedy_coloring_with_interchange as _interchange
__author__ = "\n".join(["Christian Olsson <chro@itu.dk>",
"Jan Aagaard Meier <jmei@itu.dk>",
"Henrik Haugbølle <hhau@itu.dk>"])
__all__ = [
'greedy_color',
'strategy_largest_first',
'strategy_random_sequential',
'strategy_smallest_last',
'strategy_independent_set',
'strategy_connected_sequential',
'strategy_connected_sequential_dfs',
'strategy_connected_sequential_bfs',
'strategy_saturation_largest_first'
]
def min_degree_node(G):
return min(G, key=G.degree)
def max_degree_node(G):
return max(G, key=G.degree)
def strategy_largest_first(G, colors):
"""
Largest first (lf) ordering. Ordering the nodes by largest degree
first.
"""
nodes = G.nodes()
nodes.sort(key=lambda node: -G.degree(node))
return nodes
def strategy_random_sequential(G, colors):
"""
Random sequential (RS) ordering. Scrambles nodes into random ordering.
"""
nodes = G.nodes()
random.shuffle(nodes)
return nodes
def strategy_smallest_last(G, colors):
"""
Smallest last (sl). Picking the node with smallest degree first,
subtracting it from the graph, and starting over with the new smallest
degree node. When the graph is empty, the reverse ordering of the one
built is returned.
"""
len_g = len(G)
available_g = G.copy()
nodes = [None] * len_g
for i in range(len_g):
node = min_degree_node(available_g)
available_g.remove_node(node)
nodes[len_g - i - 1] = node
return nodes
def strategy_independent_set(G, colors):
"""
Greedy independent set ordering (GIS). Generates a maximal independent
set of nodes, and assigns color C to all nodes in this set. This set
of nodes is now removed from the graph, and the algorithm runs again.
"""
len_g = len(G)
no_colored = 0
k = 0
uncolored_g = G.copy()
while no_colored < len_g: # While there are uncolored nodes
available_g = uncolored_g.copy()
while len(available_g): # While there are still nodes available
node = min_degree_node(available_g)
colors[node] = k # assign color to values
no_colored += 1
uncolored_g.remove_node(node)
# Remove node and its neighbors from available
available_g.remove_nodes_from(available_g.neighbors(node) + [node])
k += 1
return None
def strategy_connected_sequential_bfs(G, colors):
"""
Connected sequential ordering (CS). Yield nodes in such an order, that
each node, except the first one, has at least one neighbour in the
preceeding sequence. The sequence is generated using BFS)
"""
return strategy_connected_sequential(G, colors, 'bfs')
def strategy_connected_sequential_dfs(G, colors):
"""
Connected sequential ordering (CS). Yield nodes in such an order, that
each node, except the first one, has at least one neighbour in the
preceeding sequence. The sequence is generated using DFS)
"""
return strategy_connected_sequential(G, colors, 'dfs')
def strategy_connected_sequential(G, colors, traversal='bfs'):
"""
Connected sequential ordering (CS). Yield nodes in such an order, that
each node, except the first one, has at least one neighbour in the
preceeding sequence. The sequence can be generated using both BFS and
DFS search (using the strategy_connected_sequential_bfs and
strategy_connected_sequential_dfs method). The default is bfs.
"""
for component_graph in nx.connected_component_subgraphs(G):
source = component_graph.nodes()[0]
yield source # Pick the first node as source
if traversal == 'bfs':
tree = nx.bfs_edges(component_graph, source)
elif traversal == 'dfs':
tree = nx.dfs_edges(component_graph, source)
else:
raise nx.NetworkXError(
'Please specify bfs or dfs for connected sequential ordering')
for (_, end) in tree:
# Then yield nodes in the order traversed by either BFS or DFS
yield end
def strategy_saturation_largest_first(G, colors):
"""
Saturation largest first (SLF). Also known as degree saturation (DSATUR).
"""
len_g = len(G)
no_colored = 0
distinct_colors = {}
for node in G.nodes_iter():
distinct_colors[node] = set()
while no_colored != len_g:
if no_colored == 0:
# When sat. for all nodes is 0, yield the node with highest degree
no_colored += 1
node = max_degree_node(G)
yield node
for neighbour in G.neighbors_iter(node):
distinct_colors[neighbour].add(0)
else:
highest_saturation = -1
highest_saturation_nodes = []
for node, distinct in distinct_colors.items():
if node not in colors: # If the node is not already colored
saturation = len(distinct)
if saturation > highest_saturation:
highest_saturation = saturation
highest_saturation_nodes = [node]
elif saturation == highest_saturation:
highest_saturation_nodes.append(node)
if len(highest_saturation_nodes) == 1:
node = highest_saturation_nodes[0]
else:
# Return the node with highest degree
max_degree = -1
max_node = None
for node in highest_saturation_nodes:
degree = G.degree(node)
if degree > max_degree:
max_node = node
max_degree = degree
node = max_node
no_colored += 1
yield node
color = colors[node]
for neighbour in G.neighbors_iter(node):
distinct_colors[neighbour].add(color)
def greedy_color(G, strategy=strategy_largest_first, interchange=False):
"""Color a graph using various strategies of greedy graph coloring.
The strategies are described in [1]_.
Attempts to color a graph using as few colors as possible, where no
neighbours of a node can have same color as the node itself.
Parameters
----------
G : NetworkX graph
strategy : function(G, colors)
A function that provides the coloring strategy, by returning nodes
in the ordering they should be colored. G is the graph, and colors
is a dict of the currently assigned colors, keyed by nodes.
You can pass your own ordering function, or use one of the built in:
* strategy_largest_first
* strategy_random_sequential
* strategy_smallest_last
* strategy_independent_set
* strategy_connected_sequential_bfs
* strategy_connected_sequential_dfs
* strategy_connected_sequential
(alias of strategy_connected_sequential_bfs)
* strategy_saturation_largest_first (also known as DSATUR)
interchange: bool
Will use the color interchange algorithm described by [2]_ if set
to true.
Note that saturation largest first and independent set do not
work with interchange. Furthermore, if you use interchange with
your own strategy function, you cannot rely on the values in the
colors argument.
Returns
-------
A dictionary with keys representing nodes and values representing
corresponding coloring.
Examples
--------
>>> G = nx.cycle_graph(4)
>>> d = nx.coloring.greedy_color(G, strategy=nx.coloring.strategy_largest_first)
>>> d in [{0: 0, 1: 1, 2: 0, 3: 1}, {0: 1, 1: 0, 2: 1, 3: 0}]
True
References
----------
.. [1] Adrian Kosowski, and Krzysztof Manuszewski,
Classical Coloring of Graphs, Graph Colorings, 2-19, 2004.
ISBN 0-8218-3458-4.
.. [2] Maciej M. Syslo, Marsingh Deo, Janusz S. Kowalik,
Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983.
ISBN 0-486-45353-7.
"""
colors = {} # dictionary to keep track of the colors of the nodes
if len(G):
if interchange and (
strategy == strategy_independent_set or
strategy == strategy_saturation_largest_first):
raise nx.NetworkXPointlessConcept(
'Interchange is not applicable for GIS and SLF')
nodes = strategy(G, colors)
if nodes:
if interchange:
return (_interchange
.greedy_coloring_with_interchange(G, nodes))
else:
for node in nodes:
# set to keep track of colors of neighbours
neighbour_colors = set()
for neighbour in G.neighbors_iter(node):
if neighbour in colors:
neighbour_colors.add(colors[neighbour])
for color in itertools.count():
if color not in neighbour_colors:
break
# assign the node the newly found color
colors[node] = color
return colors
|