hysteresis.py
1 """!
2 
3 @brief Graph coloring algorithm: Algorithm based on Hysteresis Oscillatory Network
4 @details Implementation based on paper @cite article::gcolor::hysteresis::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 
28 from pyclustering.nnet.hysteresis import hysteresis_network, hysteresis_dynamic
29 
30 
32  """!
33  @brief Performs analysis of output dynamic of the hysteresis oscillatory network to extract information about clusters or color allocation.
34 
35  """
36 
37  def __init__(self, amplitudes, time):
38  """!
39  @brief Constructor of the analyser.
40 
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.
43 
44  """
45  super().__init__(amplitudes, time)
46 
47 
48  def allocate_clusters(self, tolerance=0.1, threshold_steps=10):
49  """!
50  @brief Returns list of clusters in line with state of ocillators (phases).
51 
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
55  of simulation steps.
56 
57  @remark Results can be obtained only after network simulation (graph processing by the network).
58 
59  @return (list) List of clusters, for example [ [cluster1], [cluster2], ... ].
60 
61  @see allocate_map_coloring()
62 
63  """
64  return self.allocate_sync_ensembles(tolerance, threshold_steps=threshold_steps)
65 
66 
67  def allocate_map_coloring(self, tolerance, threshold_steps = 10):
68  """!
69  @brief Returns list of color indexes that are assigned to each object from input data space accordingly.
70 
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
74  of simulation steps.
75 
76  @remark Results can be obtained only after network simulation (graph processing by the network).
77 
78  @return (list) Color indexes that are assigned to each object from input data space accordingly.
79 
80  @see allocate_clusters()
81 
82  """
83  clusters = self.allocate_clusters(tolerance, threshold_steps)
84 
85  coloring_map = [0] * len(self._dynamic[0])
86 
87  for color_index in range(len(clusters)):
88  for node_index in clusters[color_index]:
89  coloring_map[node_index] = color_index
90 
91  return coloring_map
92 
93 
95  """!
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
99  only one color.
100 
101  Example
102  @code
103  # import required modules
104  from pyclustering.nnet.hysteresis import hysteresis_visualizer;
105 
106  from pyclustering.gcolor.hysteresis import hysteresisgcolor;
107 
108  from pyclustering.utils.graph import read_graph, draw_graph;
109 
110  # load graph from a file
111  graph = read_graph(filename);
112 
113  # create oscillatory network for solving graph coloring problem
114  network = hysteresisgcolor(graph.data, alpha, eps);
115 
116  # perform simulation of the network
117  output_dynamic = network.simulate(2000, 20);
118 
119  # show dynamic of the network
120  hysteresis_visualizer.show_output_dynamic(output_dynamic);
121 
122  # obtain results of graph coloring and display results
123  coloring_map = hysteresis_visualizer.allocate_map_coloring();
124  draw_graph(graph, coloring_map);
125  @endcode
126 
127  """
128 
129  def __init__(self, graph_matrix, alpha, eps):
130  """!
131  @brief Constructor of hysteresis oscillatory network for graph coloring.
132 
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).
136 
137  """
138  number_oscillators = len(graph_matrix)
139 
140  super().__init__(number_oscillators)
141 
142  self._states = [0] * self._num_osc
143  for i in range(0, self._num_osc):
144  self._states[i] = 1 - (2 / self._num_osc) * i
145 
146  self._outputs = [-1] * self._num_osc
147  self._outputs_buffer = [-1] * self._num_osc
148  self._time_contant = 1
149 
150  # Create connections
151  self._weight = []
152  for row in range(0, self._num_osc):
153  self._weight.append([0] * self._num_osc)
154  for col in range(0, self._num_osc):
155  if (row != col):
156  self._weight[row][col] = -alpha * (graph_matrix[row][col]) / sum(graph_matrix[row])
157  else:
158  self._weight[row][col] = -alpha - eps
159 
160 
161  def process(self, steps, time, collect_dynamic=True):
162  """!
163  @brief Peforms graph coloring analysis using simulation of the oscillatory network.
164 
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.
168 
169  @return (hysteresis_analyser) Returns analyser of results of clustering.
170 
171  """
172 
173  output_dynamic = super().simulate(steps, time, collect_dynamic=collect_dynamic)
174  return hysteresis_analyser(output_dynamic.output, output_dynamic.time)
Neural Network: Hysteresis Oscillatory Network.
Definition: hysteresis.py:1
Hysteresis oscillatory network that uses relaxation oscillators that are represented by objective hys...
Definition: hysteresis.py:152
Represents output dynamic of hysteresis oscillatory network.
Definition: hysteresis.py:36
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...
Definition: hysteresis.py:87
def allocate_clusters(self, tolerance=0.1, threshold_steps=10)
Returns list of clusters in line with state of ocillators (phases).
Definition: hysteresis.py:48
def __init__(self, graph_matrix, alpha, eps)
Constructor of hysteresis oscillatory network for graph coloring.
Definition: hysteresis.py:129
def simulate(self, steps, time, solution=solve_type.RK4, collect_dynamic=True)
Performs static simulation of hysteresis oscillatory network.
Definition: hysteresis.py:282
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...
Definition: hysteresis.py:67
Class represents graph coloring algorithm based on hysteresis oscillatory network.
Definition: hysteresis.py:94
def process(self, steps, time, collect_dynamic=True)
Peforms graph coloring analysis using simulation of the oscillatory network.
Definition: hysteresis.py:161
Performs analysis of output dynamic of the hysteresis oscillatory network to extract information abou...
Definition: hysteresis.py:31
def __init__(self, amplitudes, time)
Constructor of the analyser.
Definition: hysteresis.py:37