dsatur.process() - Code Metrics - Inspection of "[refactoring] ant_colony params [phase 2 - final]" - annoviko/pyclustering - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( a63a82...61f52c )

unknown

created 2016-04-12 15:26 UTC

dsatur.process() F

↳ Parent: dsatur

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Metric	Value
cc	17
dl	0
loc	77
rs	2.2335

How to fix Long Method Complexity

"""!

@brief Graph coloring algorithm: DSATUR
@details Based on article description:
         - D.Brelaz. New Methods to color the vertices of a graph. 1979.

@authors Andrei Novikov ([email protected])
@date 2014-2016
@copyright GNU Public License

@cond GNU_PUBLIC_LICENSE
    PyClustering is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
    
    PyClustering is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
@endcond

"""

class dsatur:
    """!
    @brief Represents DSATUR algorithm for graph coloring problem that uses greedy strategy.
    
    """
    
    __data_pointer = None;
    __coloring = None;
    
    def __init__(self, data):
        """!
        @brief Constructor of DSATUR algorithm.
        
        @param[in] data (list): Matrix graph representation.
        
        """
        if (len(data[0]) != len(data)):
            raise NameError('Only matrix graph representation is available.');
    
        self.__data_pointer = data;
        self.__colors = [];
        
    def process(self):
        """!
        @brief Perform graph coloring using DSATUR algorithm.
        
        @see get_colors()
        
        """        
        color_counter = 1;
        
        degrees = list();
        saturation_degrees = [0] * len(self.__data_pointer);
        
        self.__coloring = [0] * len(self.__data_pointer);
        uncolored_vertices = set(range(len(self.__data_pointer)));
        
        index_maximum_degree = 0;
        maximum_degree = 0;
        for index_node in range(len(self.__data_pointer)):
            # Fill degree of nodes in the input graph
            degrees.append( ( sum(self.__data_pointer[index_node]), index_node ) );
            
            # And find node with maximal degree at the same time.
            if (degrees[index_node][0] > maximum_degree):
                (maximum_degree, node_index) = degrees[index_node];
                index_maximum_degree = index_node;
            
        # Update saturation
        neighbors = self.__get_neighbors(index_maximum_degree);
        for index_neighbor in neighbors:
            saturation_degrees[index_neighbor] += 1;
        
        # Coloring the first node
        self.__coloring[index_maximum_degree] = color_counter;
        uncolored_vertices.remove(index_maximum_degree);
        
        while(len(uncolored_vertices) > 0):
            # Get maximum saturation degree
            maximum_satur_degree = -1;
            for index in uncolored_vertices:
                if (saturation_degrees[index] > maximum_satur_degree):
                    maximum_satur_degree = saturation_degrees[index];
            
            # Get list of indexes with maximum saturation degree
            indexes_maximum_satur_degree = [index for index in uncolored_vertices if saturation_degrees[index] == maximum_satur_degree];           
    
            coloring_index = indexes_maximum_satur_degree[0];
            if (len(indexes_maximum_satur_degree) > 1): # There are more then one node with maximum saturation
                # Find node with maximum degree
                maximum_degree = -1;
                for index in indexes_maximum_satur_degree:
                    (degree, node_index) = degrees[index];
                    if (degree > maximum_degree):
                        coloring_index = node_index;
                        maximum_degree = degree;
            
            # Coloring
            node_index_neighbors = self.__get_neighbors(coloring_index);
            for number_color in range(1, color_counter + 1, 1):
                if (self.__get_amount_color(node_index_neighbors, number_color) == 0):
                    self.__coloring[coloring_index] = number_color;
                    break;
                    
            # If it has not been colored then
            if (self.__coloring[coloring_index] == 0):
                color_counter += 1;     # Add new color
                self.__coloring[coloring_index] = color_counter;
            
            # Remove node from uncolored set
            uncolored_vertices.remove(coloring_index);
            
            
            # Update degree of saturation
            for index_neighbor in node_index_neighbors:
                subneighbors = self.__get_neighbors(index_neighbor);
                
                if (self.__get_amount_color(subneighbors, self.__coloring[coloring_index]) == 1):
                    saturation_degrees[index_neighbor] += 1;     
    
    def get_colors(self):
        """!
        @brief Returns results of graph coloring.
        
        @return (list) list with assigned colors where each element corresponds 
                to node in the graph, for example [1, 2, 2, 1, 3, 4, 1].
                
        @see process()
        
        """
    
        return self.__coloring;
    
    def __get_amount_color(self, node_indexes, color_number):
        """!
        @brief Countes how many nodes has color 'color_number'.
        
        @param[in] node_indexes (list): Indexes of graph nodes for checking.
        @param[in] color_number (uint): Number of color that is searched in nodes.
        
        @return (uint) Number found nodes with the specified color 'color_number'.
        
        """
        
        color_counter = 0;  
        for index in node_indexes:
            if (self.__coloring[index] == color_number):
                color_counter += 1;
        
        return color_counter;
    
    
    def __get_neighbors(self, node_index):
        """!
        @brief Returns indexes of neighbors of the specified node.
        
        @param[in] node_index (uint):
        
        @return (list) Neighbors of the specified node.
        
        """
        
        return [ index for index in range(len(self.__data_pointer[node_index])) if self.__data_pointer[node_index][index] != 0 ]; 
    

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

annoviko / pyclustering

Push — master ( a63a82...61f52c )

dsatur.process() F

Complexity

Size

Duplication

How to fix Long Method Complexity

Long Method

Complexity

Duplication Side-by-Side

Filter issues like