3 @brief Graph coloring algorithm: DSATUR
4 @details Implementation based on paper @cite article::gcolor::dsatur::1.
6 @authors Andrei Novikov (pyclustering@yandex.ru)
8 @copyright BSD-3-Clause
14 @brief Represents DSATUR algorithm for graph coloring problem that uses greedy strategy.
20 @brief Constructor of DSATUR algorithm.
22 @param[in] data (list): Matrix graph representation.
25 if (len(data[0]) != len(data)):
26 raise NameError(
'Only matrix graph representation is available.');
34 @brief Perform graph coloring using DSATUR algorithm.
47 index_maximum_degree = 0;
51 degrees.append( ( sum(self.
__data_pointer[index_node]), index_node ) );
54 if (degrees[index_node][0] > maximum_degree):
55 (maximum_degree, node_index) = degrees[index_node];
56 index_maximum_degree = index_node;
60 for index_neighbor
in neighbors:
61 saturation_degrees[index_neighbor] += 1;
64 self.
__coloring[index_maximum_degree] = color_counter;
65 uncolored_vertices.remove(index_maximum_degree);
67 while(len(uncolored_vertices) > 0):
69 maximum_satur_degree = -1;
70 for index
in uncolored_vertices:
71 if (saturation_degrees[index] > maximum_satur_degree):
72 maximum_satur_degree = saturation_degrees[index];
75 indexes_maximum_satur_degree = [index
for index
in uncolored_vertices
if saturation_degrees[index] == maximum_satur_degree];
77 coloring_index = indexes_maximum_satur_degree[0];
78 if (len(indexes_maximum_satur_degree) > 1):
81 for index
in indexes_maximum_satur_degree:
82 (degree, node_index) = degrees[index];
83 if (degree > maximum_degree):
84 coloring_index = node_index;
85 maximum_degree = degree;
89 for number_color
in range(1, color_counter + 1, 1):
91 self.
__coloring[coloring_index] = number_color;
97 self.
__coloring[coloring_index] = color_counter;
100 uncolored_vertices.remove(coloring_index);
104 for index_neighbor
in node_index_neighbors:
108 saturation_degrees[index_neighbor] += 1;
112 @brief Returns results of graph coloring.
114 @return (list) list with assigned colors where each element corresponds
115 to node in the graph, for example [1, 2, 2, 1, 3, 4, 1].
123 def __get_amount_color(self, node_indexes, color_number):
125 @brief Countes how many nodes has color 'color_number'.
127 @param[in] node_indexes (list): Indexes of graph nodes for checking.
128 @param[in] color_number (uint): Number of color that is searched in nodes.
130 @return (uint) Number found nodes with the specified color 'color_number'.
135 for index
in node_indexes:
139 return color_counter;
142 def __get_neighbors(self, node_index):
144 @brief Returns indexes of neighbors of the specified node.
146 @param[in] node_index (uint):
148 @return (list) Neighbors of the specified node.