sync.py
1 """!
2 
3 @brief Graph coloring algorithm based on Sync Oscillatory Network
4 @details Implementation based on paper @cite article::gcolor::sync::1.
5 
6 @authors Andrei Novikov (pyclustering@yandex.ru)
7 @date 2014-2018
8 @copyright GNU Public License
9 
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.
15 
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.
20 
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/>.
23 @endcond
24 
25 """
26 
27 from pyclustering.nnet import *
28 from pyclustering.nnet.sync import sync_network
29 from pyclustering.nnet.sync import sync_dynamic
30 
31 
33  """!
34  @brief Analyser of output dynamic of the oscillatory network syncgcolor.
35 
36  """
37 
38  def __init__(self, phase, time, pointer_sync_analyser):
39  """!
40  @brief Constructor of the analyser.
41 
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.
45 
46  """
47 
48  super().__init__(phase, time, pointer_sync_analyser);
49 
50 
51  def allocate_color_clusters(self, tolerance = 0.1):
52  """!
53  @brief Allocates clusters, when one cluster defines only one color.
54 
55  @param[in] tolerance (double): Defines maximum deviation between phases.
56 
57  @return (list) Clusters [vertices with color 1], [vertices with color 2], ..., [vertices with color n].
58 
59  """
60 
61  return self.allocate_sync_ensembles(tolerance);
62 
63 
64  def allocate_map_coloring(self, tolerance = 0.1):
65  """!
66  @brief Allocates coloring map for graph that has been processed.
67 
68  @param[in] tolerance (double): Defines maximum deviation between phases.
69 
70  @return (list) Colors for each node (index of node in graph), for example [color1, color2, color2, ...].
71 
72  """
73 
74  clusters = self.allocate_color_clusters(tolerance);
75  number_oscillators = len(self._dynamic[0]);
76 
77  coloring_map = [0] * number_oscillators;
78 
79  for color_index in range(len(clusters)):
80  for node_index in clusters[color_index]:
81  coloring_map[node_index] = color_index;
82 
83  return coloring_map;
84 
85 
87  """!
88  @brief Oscillatory network based on Kuramoto model with negative and positive connections for graph coloring problem.
89 
90  """
91 
92  def __init__(self, graph_matrix, positive_weight, negative_weight, reduction = None):
93  """!
94  @brief Constructor of the oscillatory network syncgcolor for graph coloring problem.
95 
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.
100 
101  """
102  number_oscillators = len(graph_matrix);
103  super().__init__(number_oscillators, type_conn = conn_type.DYNAMIC, ccore = False);
104 
105  if (reduction == None):
106  self._reduction = self._num_osc;
107  else:
108  self._reduction = reduction;
109 
110  self._positive_weight = positive_weight;
111  self._negative_weight = negative_weight;
112 
113  self._create_connections(graph_matrix);
114 
115 
116  def _create_connections(self, graph_matrix):
117  """!
118  @brief Creates connection in the network in line with graph.
119 
120  @param[in] graph_matrix (list): Matrix representation of the graph.
121 
122  """
123 
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):
127  self.set_connection(row, column);
128 
129 
130  def _phase_kuramoto(self, teta, t, argv):
131  """!
132  @brief Returns result of phase calculation for oscillator in the network.
133 
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.
137 
138  @return (double) New value of phase for oscillator with index argv.
139 
140  """
141 
142  index = argv;
143  phase = 0;
144 
145  for k in range(0, self._num_osc):
146  if (self.has_connection(index, k) == True):
147  phase += self._negative_weight * math.sin(self._phases[k] - teta);
148  else:
149  phase += self._positive_weight * math.sin(self._phases[k] - teta);
150 
151  return ( phase / self._reduction );
152 
153 
154  def process(self, order = 0.998, solution = solve_type.FAST, collect_dynamic = False):
155  """!
156  @brief Performs simulation of the network (performs solving of graph coloring problem).
157 
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.
161 
162  @return (syncnet_analyser) Returns analyser of results of coloring.
163 
164  """
165 
166  analyser = self.simulate_dynamic(order, solution, collect_dynamic);
167  return syncgcolor_analyser(analyser.output, analyser.time, None);
168 
169 
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.
Definition: sync.py:871
def allocate_color_clusters(self, tolerance=0.1)
Allocates clusters, when one cluster defines only one color.
Definition: sync.py:51
Represents output dynamic of Sync.
Definition: sync.py:113
def __init__(self, graph_matrix, positive_weight, negative_weight, reduction=None)
Constructor of the oscillatory network syncgcolor for graph coloring problem.
Definition: sync.py:92
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...
Definition: sync.py:194
def set_connection(self, i, j)
Couples two specified oscillators in the network with dynamic connections.
Definition: __init__.py:387
Analyser of output dynamic of the oscillatory network syncgcolor.
Definition: sync.py:32
def has_connection(self, i, j)
Returns True if there is connection between i and j oscillators and False - if connection doesn&#39;t exi...
Definition: __init__.py:366
Neural Network: Oscillatory Neural Network based on Kuramoto model.
Definition: sync.py:1
def _create_connections(self, graph_matrix)
Creates connection in the network in line with graph.
Definition: sync.py:116
Oscillatory network based on Kuramoto model with negative and positive connections for graph coloring...
Definition: sync.py:86
def process(self, order=0.998, solution=solve_type.FAST, collect_dynamic=False)
Performs simulation of the network (performs solving of graph coloring problem).
Definition: sync.py:154
def __init__(self, phase, time, pointer_sync_analyser)
Constructor of the analyser.
Definition: sync.py:38
def allocate_map_coloring(self, tolerance=0.1)
Allocates coloring map for graph that has been processed.
Definition: sync.py:64
Neural and oscillatory network module.
Definition: __init__.py:1
Model of oscillatory network that is based on the Kuramoto model of synchronization.
Definition: sync.py:722