dsatur.py
1 """!
2 
3 @brief Graph coloring algorithm: DSATUR
4 @details Implementation based on paper @cite article::gcolor::dsatur::1.
5 
6 @authors Andrei Novikov (pyclustering@yandex.ru)
7 @date 2014-2019
8 @copyright GNU Public License
9 
10 @cond GNU_PUBLIC_LICENSE
11  PyClustering is free software: you can redistribute it and/or modify
12  it under the terms of the GNU General Public License as published by
13  the Free Software Foundation, either version 3 of the License, or
14  (at your option) any later version.
15 
16  PyClustering is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  GNU General Public License for more details.
20 
21  You should have received a copy of the GNU General Public License
22  along with this program. If not, see <http://www.gnu.org/licenses/>.
23 @endcond
24 
25 """
26 
27 class dsatur:
28  """!
29  @brief Represents DSATUR algorithm for graph coloring problem that uses greedy strategy.
30 
31  """
32 
33  def __init__(self, data):
34  """!
35  @brief Constructor of DSATUR algorithm.
36 
37  @param[in] data (list): Matrix graph representation.
38 
39  """
40  if (len(data[0]) != len(data)):
41  raise NameError('Only matrix graph representation is available.');
42 
43  self.__data_pointer = data;
44  self.__colors = [];
45  self.__coloring = None;
46 
47  def process(self):
48  """!
49  @brief Perform graph coloring using DSATUR algorithm.
50 
51  @see get_colors()
52 
53  """
54  color_counter = 1;
55 
56  degrees = list();
57  saturation_degrees = [0] * len(self.__data_pointer);
58 
59  self.__coloring = [0] * len(self.__data_pointer);
60  uncolored_vertices = set(range(len(self.__data_pointer)));
61 
62  index_maximum_degree = 0;
63  maximum_degree = 0;
64  for index_node in range(len(self.__data_pointer)):
65  # Fill degree of nodes in the input graph
66  degrees.append( ( sum(self.__data_pointer[index_node]), index_node ) );
67 
68  # And find node with maximal degree at the same time.
69  if (degrees[index_node][0] > maximum_degree):
70  (maximum_degree, node_index) = degrees[index_node];
71  index_maximum_degree = index_node;
72 
73  # Update saturation
74  neighbors = self.__get_neighbors(index_maximum_degree);
75  for index_neighbor in neighbors:
76  saturation_degrees[index_neighbor] += 1;
77 
78  # Coloring the first node
79  self.__coloring[index_maximum_degree] = color_counter;
80  uncolored_vertices.remove(index_maximum_degree);
81 
82  while(len(uncolored_vertices) > 0):
83  # Get maximum saturation degree
84  maximum_satur_degree = -1;
85  for index in uncolored_vertices:
86  if (saturation_degrees[index] > maximum_satur_degree):
87  maximum_satur_degree = saturation_degrees[index];
88 
89  # Get list of indexes with maximum saturation degree
90  indexes_maximum_satur_degree = [index for index in uncolored_vertices if saturation_degrees[index] == maximum_satur_degree];
91 
92  coloring_index = indexes_maximum_satur_degree[0];
93  if (len(indexes_maximum_satur_degree) > 1): # There are more then one node with maximum saturation
94  # Find node with maximum degree
95  maximum_degree = -1;
96  for index in indexes_maximum_satur_degree:
97  (degree, node_index) = degrees[index];
98  if (degree > maximum_degree):
99  coloring_index = node_index;
100  maximum_degree = degree;
101 
102  # Coloring
103  node_index_neighbors = self.__get_neighbors(coloring_index);
104  for number_color in range(1, color_counter + 1, 1):
105  if (self.__get_amount_color(node_index_neighbors, number_color) == 0):
106  self.__coloring[coloring_index] = number_color;
107  break;
108 
109  # If it has not been colored then
110  if (self.__coloring[coloring_index] == 0):
111  color_counter += 1; # Add new color
112  self.__coloring[coloring_index] = color_counter;
113 
114  # Remove node from uncolored set
115  uncolored_vertices.remove(coloring_index);
116 
117 
118  # Update degree of saturation
119  for index_neighbor in node_index_neighbors:
120  subneighbors = self.__get_neighbors(index_neighbor);
121 
122  if (self.__get_amount_color(subneighbors, self.__coloring[coloring_index]) == 1):
123  saturation_degrees[index_neighbor] += 1;
124 
125  def get_colors(self):
126  """!
127  @brief Returns results of graph coloring.
128 
129  @return (list) list with assigned colors where each element corresponds
130  to node in the graph, for example [1, 2, 2, 1, 3, 4, 1].
131 
132  @see process()
133 
134  """
135 
136  return self.__coloring;
137 
138  def __get_amount_color(self, node_indexes, color_number):
139  """!
140  @brief Countes how many nodes has color 'color_number'.
141 
142  @param[in] node_indexes (list): Indexes of graph nodes for checking.
143  @param[in] color_number (uint): Number of color that is searched in nodes.
144 
145  @return (uint) Number found nodes with the specified color 'color_number'.
146 
147  """
148 
149  color_counter = 0;
150  for index in node_indexes:
151  if (self.__coloring[index] == color_number):
152  color_counter += 1;
153 
154  return color_counter;
155 
156 
157  def __get_neighbors(self, node_index):
158  """!
159  @brief Returns indexes of neighbors of the specified node.
160 
161  @param[in] node_index (uint):
162 
163  @return (list) Neighbors of the specified node.
164 
165  """
166 
167  return [ index for index in range(len(self.__data_pointer[node_index])) if self.__data_pointer[node_index][index] != 0 ];
168 
def __init__(self, data)
Constructor of DSATUR algorithm.
Definition: dsatur.py:33
def process(self)
Perform graph coloring using DSATUR algorithm.
Definition: dsatur.py:47
def get_colors(self)
Returns results of graph coloring.
Definition: dsatur.py:125
def __get_amount_color(self, node_indexes, color_number)
Countes how many nodes has color &#39;color_number&#39;.
Definition: dsatur.py:138
def __get_neighbors(self, node_index)
Returns indexes of neighbors of the specified node.
Definition: dsatur.py:157
Represents DSATUR algorithm for graph coloring problem that uses greedy strategy. ...
Definition: dsatur.py:27