1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
"""!
@brief Graph coloring algorithm based on Sync Oscillatory Network
@details Implementation based on paper @cite article::gcolor::sync::1.
@authors Andrei Novikov (pyclustering@yandex.ru)
@date 2014-2020
@copyright BSD-3-Clause
"""
from pyclustering.nnet import *
from pyclustering.nnet.sync import sync_network
from pyclustering.nnet.sync import sync_dynamic
class syncgcolor_analyser(sync_dynamic):
"""!
@brief Analyser of output dynamic of the oscillatory network syncgcolor.
"""
def __init__(self, phase, time, pointer_sync_analyser):
"""!
@brief Constructor of the analyser.
@param[in] phase (list): Output dynamic of the oscillatory network, where one iteration consists of all phases of oscillators.
@param[in] time (list): Simulation time.
@param[in] pointer_sync_analyser (POINTER): Pointer to CCORE analyser, if specified then other arguments can be omitted.
"""
super().__init__(phase, time, pointer_sync_analyser);
def allocate_color_clusters(self, tolerance = 0.1):
"""!
@brief Allocates clusters, when one cluster defines only one color.
@param[in] tolerance (double): Defines maximum deviation between phases.
@return (list) Clusters [vertices with color 1], [vertices with color 2], ..., [vertices with color n].
"""
return self.allocate_sync_ensembles(tolerance);
def allocate_map_coloring(self, tolerance = 0.1):
"""!
@brief Allocates coloring map for graph that has been processed.
@param[in] tolerance (double): Defines maximum deviation between phases.
@return (list) Colors for each node (index of node in graph), for example [color1, color2, color2, ...].
"""
clusters = self.allocate_color_clusters(tolerance);
number_oscillators = len(self._dynamic[0]);
coloring_map = [0] * number_oscillators;
for color_index in range(len(clusters)):
for node_index in clusters[color_index]:
coloring_map[node_index] = color_index;
return coloring_map;
class syncgcolor(sync_network):
"""!
@brief Oscillatory network based on Kuramoto model with negative and positive connections for graph coloring problem.
"""
def __init__(self, graph_matrix, positive_weight, negative_weight, reduction = None):
"""!
@brief Constructor of the oscillatory network syncgcolor for graph coloring problem.
@param[in] graph_matrix (list): Graph represented by matrix.
@param[in] positive_weight (double): Value of weight of positive connections.
@param[in] negative_weight (double): Value of weight of negative connections.
@param[in] reduction (bool): Inverse degree of the processed graph.
"""
number_oscillators = len(graph_matrix);
super().__init__(number_oscillators, type_conn = conn_type.DYNAMIC, ccore = False);
if (reduction == None):
self._reduction = self._num_osc;
else:
self._reduction = reduction;
self._positive_weight = positive_weight;
self._negative_weight = negative_weight;
self._create_connections(graph_matrix);
def _create_connections(self, graph_matrix):
"""!
@brief Creates connection in the network in line with graph.
@param[in] graph_matrix (list): Matrix representation of the graph.
"""
for row in range(0, len(graph_matrix)):
for column in range (0, len(graph_matrix[row])):
if (graph_matrix[row][column] > 0):
self.set_connection(row, column);
def _phase_kuramoto(self, teta, t, argv):
"""!
@brief Returns result of phase calculation for oscillator in the network.
@param[in] teta (double): Value of phase of the oscillator with index argv in the network.
@param[in] t (double): Unused, can be ignored.
@param[in] argv (uint): Index of the oscillator in the network.
@return (double) New value of phase for oscillator with index argv.
"""
index = argv;
phase = 0;
for k in range(0, self._num_osc):
if (self.has_connection(index, k) == True):
phase += self._negative_weight * math.sin(self._phases[k] - teta);
else:
phase += self._positive_weight * math.sin(self._phases[k] - teta);
return ( phase / self._reduction );
def process(self, order = 0.998, solution = solve_type.FAST, collect_dynamic = False):
"""!
@brief Performs simulation of the network (performs solving of graph coloring problem).
@param[in] order (double): Defines when process of synchronization in the network is over, range from 0 to 1.
@param[in] solution (solve_type): defines type (method) of solving diff. equation.
@param[in] collect_dynamic (bool): If True - return full dynamic of the network, otherwise - last state of phases.
@return (syncnet_analyser) Returns analyser of results of coloring.
"""
analyser = self.simulate_dynamic(order, solution, collect_dynamic);
return syncgcolor_analyser(analyser.output, analyser.time, None);
|
