3 @brief Graph coloring algorithm: Algorithm based on Hysteresis Oscillatory Network 4 @details Implementation based on paper @cite article::gcolor::hysteresis::1. 6 @authors Andrei Novikov (pyclustering@yandex.ru) 8 @copyright GNU Public License 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. 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. 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/>. 33 @brief Performs analysis of output dynamic of the hysteresis oscillatory network to extract information about clusters or color allocation. 39 @brief Constructor of the analyser. 41 @param[in] amplitudes (list): Output dynamic of the hysteresis oscillatory network, where one iteration consists of all amplitudes of oscillators. 42 @param[in] time (list): Simulation time (timestamps of simulation steps) when amplitudes are stored. 50 @brief Returns list of clusters in line with state of ocillators (phases). 52 @param[in] tolerance (double): Maximum error for allocation of synchronous ensemble oscillators. 53 @param[in] threshold_steps (uint): Number of steps from the end of simulation that should be analysed for ensemble allocation. 54 If amount of simulation steps has been less than threshold steps than amount of steps will be reduced to amount 57 @remark Results can be obtained only after network simulation (graph processing by the network). 59 @return (list) List of clusters, for example [ [cluster1], [cluster2], ... ]. 61 @see allocate_map_coloring() 69 @brief Returns list of color indexes that are assigned to each object from input data space accordingly. 71 @param[in] tolerance (double): Tolerance level that define maximal difference between outputs of oscillators in one synchronous ensemble. 72 @param[in] threshold_steps (uint): Number of steps from the end of simulation that should be analysed for ensemble allocation. 73 If amount of simulation steps has been less than threshold steps than amount of steps will be reduced to amount 76 @remark Results can be obtained only after network simulation (graph processing by the network). 78 @return (list) Color indexes that are assigned to each object from input data space accordingly. 80 @see allocate_clusters() 85 coloring_map = [0] * len(self.
_dynamic[0])
87 for color_index
in range(len(clusters)):
88 for node_index
in clusters[color_index]:
89 coloring_map[node_index] = color_index
96 @brief Class represents graph coloring algorithm based on hysteresis oscillatory network. 97 This is bio-inspired algorithm where the network uses relaxation oscillators that is 98 regarded as a multi-vibrator. Each ensemble of synchronous oscillators corresponds to 103 # import required modules 104 from pyclustering.nnet.hysteresis import hysteresis_visualizer; 106 from pyclustering.gcolor.hysteresis import hysteresisgcolor; 108 from pyclustering.utils.graph import read_graph, draw_graph; 110 # load graph from a file 111 graph = read_graph(filename); 113 # create oscillatory network for solving graph coloring problem 114 network = hysteresisgcolor(graph.data, alpha, eps); 116 # perform simulation of the network 117 output_dynamic = network.simulate(2000, 20); 119 # show dynamic of the network 120 hysteresis_visualizer.show_output_dynamic(output_dynamic); 122 # obtain results of graph coloring and display results 123 coloring_map = hysteresis_visualizer.allocate_map_coloring(); 124 draw_graph(graph, coloring_map); 131 @brief Constructor of hysteresis oscillatory network for graph coloring. 133 @param[in] graph_matrix (list): Matrix representation of a graph. 134 @param[in] alpha (double): Positive constant (affect weight between two oscillators w[i][j]). 135 @param[in] eps (double): Positive constant (affect feedback to itself (i = j) of each oscillator w[i][j] = -alpha - eps). 138 number_oscillators = len(graph_matrix)
140 super().
__init__(number_oscillators)
156 self.
_weight[row][col] = -alpha * (graph_matrix[row][col]) / sum(graph_matrix[row])
158 self.
_weight[row][col] = -alpha - eps
161 def process(self, steps, time, collect_dynamic=True):
163 @brief Peforms graph coloring analysis using simulation of the oscillatory network. 165 @param[in] steps (uint): Number steps of simulations during simulation. 166 @param[in] time (double): Time of simulation. 167 @param[in] collect_dynamic (bool): Specified requirement to collect whole dynamic of the network. 169 @return (hysteresis_analyser) Returns analyser of results of clustering. 173 output_dynamic = super().
simulate(steps, time, collect_dynamic=collect_dynamic)
Neural Network: Hysteresis Oscillatory Network.
Hysteresis oscillatory network that uses relaxation oscillators that are represented by objective hys...
Represents output dynamic of hysteresis oscillatory network.
def allocate_sync_ensembles(self, tolerance=0.1, threshold_steps=1)
Allocate clusters in line with ensembles of synchronous oscillators where each synchronous ensemble c...
def allocate_clusters(self, tolerance=0.1, threshold_steps=10)
Returns list of clusters in line with state of ocillators (phases).
def __init__(self, graph_matrix, alpha, eps)
Constructor of hysteresis oscillatory network for graph coloring.
def simulate(self, steps, time, solution=solve_type.RK4, collect_dynamic=True)
Performs static simulation of hysteresis oscillatory network.
def allocate_map_coloring(self, tolerance, threshold_steps=10)
Returns list of color indexes that are assigned to each object from input data space accordingly...
Class represents graph coloring algorithm based on hysteresis oscillatory network.
def process(self, steps, time, collect_dynamic=True)
Peforms graph coloring analysis using simulation of the oscillatory network.
Performs analysis of output dynamic of the hysteresis oscillatory network to extract information abou...
def __init__(self, amplitudes, time)
Constructor of the analyser.