3 @brief Graph coloring algorithm based on Sync Oscillatory Network 4 @details Implementation based on paper @cite article::gcolor::sync::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/>. 34 @brief Analyser of output dynamic of the oscillatory network syncgcolor. 38 def __init__(self, phase, time, pointer_sync_analyser):
40 @brief Constructor of the analyser. 42 @param[in] phase (list): Output dynamic of the oscillatory network, where one iteration consists of all phases of oscillators. 43 @param[in] time (list): Simulation time. 44 @param[in] pointer_sync_analyser (POINTER): Pointer to CCORE analyser, if specified then other arguments can be omitted. 48 super().
__init__(phase, time, pointer_sync_analyser);
53 @brief Allocates clusters, when one cluster defines only one color. 55 @param[in] tolerance (double): Defines maximum deviation between phases. 57 @return (list) Clusters [vertices with color 1], [vertices with color 2], ..., [vertices with color n]. 66 @brief Allocates coloring map for graph that has been processed. 68 @param[in] tolerance (double): Defines maximum deviation between phases. 70 @return (list) Colors for each node (index of node in graph), for example [color1, color2, color2, ...]. 75 number_oscillators = len(self.
_dynamic[0]);
77 coloring_map = [0] * number_oscillators;
79 for color_index
in range(len(clusters)):
80 for node_index
in clusters[color_index]:
81 coloring_map[node_index] = color_index;
88 @brief Oscillatory network based on Kuramoto model with negative and positive connections for graph coloring problem. 92 def __init__(self, graph_matrix, positive_weight, negative_weight, reduction = None):
94 @brief Constructor of the oscillatory network syncgcolor for graph coloring problem. 96 @param[in] graph_matrix (list): Graph represented by matrix. 97 @param[in] positive_weight (double): Value of weight of positive connections. 98 @param[in] negative_weight (double): Value of weight of negative connections. 99 @param[in] reduction (bool): Inverse degree of the processed graph. 102 number_oscillators = len(graph_matrix);
103 super().
__init__(number_oscillators, type_conn = conn_type.DYNAMIC, ccore =
False);
105 if (reduction ==
None):
116 def _create_connections(self, graph_matrix):
118 @brief Creates connection in the network in line with graph. 120 @param[in] graph_matrix (list): Matrix representation of the graph. 124 for row
in range(0, len(graph_matrix)):
125 for column
in range (0, len(graph_matrix[row])):
126 if (graph_matrix[row][column] > 0):
130 def _phase_kuramoto(self, teta, t, argv):
132 @brief Returns result of phase calculation for oscillator in the network. 134 @param[in] teta (double): Value of phase of the oscillator with index argv in the network. 135 @param[in] t (double): Unused, can be ignored. 136 @param[in] argv (uint): Index of the oscillator in the network. 138 @return (double) New value of phase for oscillator with index argv. 154 def process(self, order = 0.998, solution = solve_type.FAST, collect_dynamic = False):
156 @brief Performs simulation of the network (performs solving of graph coloring problem). 158 @param[in] order (double): Defines when process of synchronization in the network is over, range from 0 to 1. 159 @param[in] solution (solve_type): defines type (method) of solving diff. equation. 160 @param[in] collect_dynamic (bool): If True - return full dynamic of the network, otherwise - last state of phases. 162 @return (syncnet_analyser) Returns analyser of results of coloring. def simulate_dynamic(self, order=0.998, solution=solve_type.FAST, collect_dynamic=False, step=0.1, int_step=0.01, threshold_changes=0.0000001)
Performs dynamic simulation of the network until stop condition is not reached.
def allocate_color_clusters(self, tolerance=0.1)
Allocates clusters, when one cluster defines only one color.
Represents output dynamic of Sync.
def __init__(self, graph_matrix, positive_weight, negative_weight, reduction=None)
Constructor of the oscillatory network syncgcolor for graph coloring problem.
def allocate_sync_ensembles(self, tolerance=0.01, indexes=None, iteration=None)
Allocate clusters in line with ensembles of synchronous oscillators where each synchronous ensemble c...
def set_connection(self, i, j)
Couples two specified oscillators in the network with dynamic connections.
Analyser of output dynamic of the oscillatory network syncgcolor.
def has_connection(self, i, j)
Returns True if there is connection between i and j oscillators and False - if connection doesn't exi...
Neural Network: Oscillatory Neural Network based on Kuramoto model.
def _create_connections(self, graph_matrix)
Creates connection in the network in line with graph.
Oscillatory network based on Kuramoto model with negative and positive connections for graph coloring...
def process(self, order=0.998, solution=solve_type.FAST, collect_dynamic=False)
Performs simulation of the network (performs solving of graph coloring problem).
def __init__(self, phase, time, pointer_sync_analyser)
Constructor of the analyser.
def allocate_map_coloring(self, tolerance=0.1)
Allocates coloring map for graph that has been processed.
Neural and oscillatory network module.
Model of oscillatory network that is based on the Kuramoto model of synchronization.