graph.py
1 """!
2 
3 @brief Graph representation (uses format GRPR).
4 
5 @authors Andrei Novikov (pyclustering@yandex.ru)
6 @date 2014-2019
7 @copyright GNU Public License
8 
9 @cond GNU_PUBLIC_LICENSE
10  PyClustering is free software: you can redistribute it and/or modify
11  it under the terms of the GNU General Public License as published by
12  the Free Software Foundation, either version 3 of the License, or
13  (at your option) any later version.
14 
15  PyClustering is distributed in the hope that it will be useful,
16  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  GNU General Public License for more details.
19 
20  You should have received a copy of the GNU General Public License
21  along with this program. If not, see <http://www.gnu.org/licenses/>.
22 @endcond
23 
24 """
25 
26 import warnings
27 
28 try:
29  import matplotlib.pyplot as plt
30  from matplotlib import colors
31 except Exception as error_instance:
32  warnings.warn("Impossible to import matplotlib (please, install 'matplotlib'), pyclustering's visualization "
33  "functionality is not available (details: '%s')." % str(error_instance))
34 
35 from enum import IntEnum
36 
37 class type_graph_descr(IntEnum):
38  """!
39  @brief Enumeration of graph description.
40  @details Matrix representation is list of lists where number of rows equals number of columns and each element
41  of square matrix determines whether there is connection between two vertices. For example:
42  [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ].
43 
44  Vector representation is list of lists where index of row corresponds to index of vertex and elements
45  of row consists of indexes of connected vertices. For example:
46  [ [1, 2], [0, 2], [0, 1] ].
47 
48  """
49 
50 
51  GRAPH_UNKNOWN = 0;
52 
53 
54  GRAPH_MATRIX_DESCR = 1;
55 
56 
57  GRAPH_VECTOR_DESCR = 2;
58 
59 
60 class graph:
61  """!
62  @brief Graph representation.
63 
64  """
65 
66  def __init__(self, data, type_graph = None, space_descr = None, comments = None):
67  """!
68  @brief Constructor of graph.
69 
70  @param[in] data (list): Representation of graph. Considered as matrix if 'type_graph' is not specified.
71  @param[in] type_graph (type_graph_descr): Type of graph representation in 'data'.
72  @param[in] space_descr (list): Coordinates of each vertex that are used for graph drawing (can be omitted).
73  @param[in] comments (string): Comments related to graph.
74 
75  """
76  self.__data = data;
77  self.__space_descr = space_descr;
78  self.__comments = comments;
79 
80  if (type_graph is not None):
81  self.__type_graph = type_graph;
82  else:
83  self.__type_graph = type_graph_descr.GRAPH_MATRIX_DESCR;
84  for row in self.__data:
85  if (len(row) != len(self.__data)):
86  self.__type_graph = type_graph_descr.GRAPH_VECTOR_DESCR;
87  break;
88 
89  for element in row:
90  if ( (element != 0) or (element != 1) ):
91  self.__type_graph = type_graph_descr.GRAPH_VECTOR_DESCR;
92 
93 
94  def __len__(self):
95  """!
96  @return (uint) Size of graph defined by number of vertices.
97 
98  """
99  return len(self.__data);
100 
101 
102  @property
103  def data(self):
104  """!
105  @return (list) Graph representation.
106 
107  """
108  return self.__data;
109 
110  @property
111  def space_description(self):
112  """!
113  @return (list) Space description.
114 
115  """
116  if (self.__space_descr == [] or self.__space_descr is None):
117  return None;
118 
119  return self.__space_descr;
120 
121  @property
122  def comments(self):
123  """!
124  @return (string) Comments.
125 
126  """
127  return self.__comments;
128 
129  @property
130  def type_graph_descr(self):
131  """!
132  @return (type_graph_descr) Type of graph representation.
133 
134  """
135  return self.__type_graph;
136 
137 
138 def read_graph(filename):
139  """!
140  @brief Read graph from file in GRPR format.
141 
142  @param[in] filename (string): Path to file with graph in GRPR format.
143 
144  @return (graph) Graph that is read from file.
145 
146  """
147 
148  file = open(filename, 'r');
149 
150  comments = "";
151  space_descr = [];
152  data = [];
153  data_type = None;
154 
155  map_data_repr = dict(); # Used as a temporary buffer only when input graph is represented by edges.
156 
157  for line in file:
158  if (line[0] == 'c' or line[0] == 'p'):
159  comments += line[1:];
160 
161  elif (line[0] == 'r'):
162  node_coordinates = [float(val) for val in line[1:].split()];
163  if (len(node_coordinates) != 2):
164  raise NameError('Invalid format of space description for node (only 2-dimension space is supported)');
165 
166  space_descr.append( [float(val) for val in line[1:].split()] );
167 
168  elif (line[0] == 'm'):
169  if ( (data_type is not None) and (data_type != 'm') ):
170  raise NameError('Invalid format of graph representation (only one type should be used)');
171 
172  data_type = 'm';
173  data.append( [float(val) for val in line[1:].split()] );
174 
175  elif (line[0] == 'v'):
176  if ( (data_type is not None) and (data_type != 'v') ):
177  raise NameError('Invalid format of graph representation (only one type should be used)');
178 
179  data_type = 'v';
180  data.append( [float(val) for val in line[1:].split()] );
181 
182  elif (line[0] == 'e'):
183  if ( (data_type is not None) and (data_type != 'e') ):
184  raise NameError('Invalid format of graph representation (only one type should be used)');
185 
186  data_type = 'e';
187  vertices = [int(val) for val in line[1:].split()];
188 
189  if (vertices[0] not in map_data_repr):
190  map_data_repr[ vertices[0] ] = [ vertices[1] ];
191  else:
192  map_data_repr[ vertices[0] ].append(vertices[1])
193 
194  if (vertices[1] not in map_data_repr):
195  map_data_repr[ vertices[1] ] = [ vertices[0] ];
196  else:
197  map_data_repr[ vertices[1] ].append(vertices[0]);
198 
199 
200  elif (len(line.strip()) == 0): continue;
201 
202  else:
203  print(line);
204  raise NameError('Invalid format of file with graph description');
205 
206  # In case of edge representation result should be copied.
207  if (data_type == 'e'):
208  for index in range(len(map_data_repr)):
209  data.append([0] * len(map_data_repr));
210 
211  for index_neighbour in map_data_repr[index + 1]:
212  data[index][index_neighbour - 1] = 1;
213 
214  file.close();
215 
216  # Set graph description
217  graph_descr = None;
218  if (data_type == 'm'): graph_descr = type_graph_descr.GRAPH_MATRIX_DESCR;
219  elif (data_type == 'v'): graph_descr = type_graph_descr.GRAPH_VECTOR_DESCR;
220  elif (data_type == 'e'): graph_descr = type_graph_descr.GRAPH_MATRIX_DESCR;
221  else:
222  raise NameError('Invalid format of file with graph description');
223 
224  if (space_descr != []):
225  if (len(data) != len(space_descr)):
226  raise NameError("Invalid format of file with graph - number of nodes is different in space representation and graph description");
227 
228  return graph(data, graph_descr, space_descr, comments);
229 
230 
231 
232 def draw_graph(graph_instance, map_coloring = None):
233  """!
234  @brief Draw graph.
235 
236  @param[in] graph_instance (graph): Graph that should be drawn.
237  @param[in] map_coloring (list): List of color indexes for each vertex. Size of this list should be equal to size of graph (number of vertices).
238  If it's not specified (None) than graph without coloring will be dwarn.
239 
240  @warning Graph can be represented if there is space representation for it.
241 
242  """
243 
244  if (graph_instance.space_description is None):
245  raise NameError("The graph haven't got representation in space");
246 
247  if (map_coloring is not None):
248  if (len(graph_instance) != len(map_coloring)):
249  raise NameError("Size of graph should be equal to size coloring map");
250 
251 
252  fig = plt.figure();
253  axes = fig.add_subplot(111);
254 
255  available_colors = ['#00a2e8', '#22b14c', '#ed1c24',
256  '#fff200', '#000000', '#a349a4',
257  '#ffaec9', '#7f7f7f', '#b97a57',
258  '#c8bfe7', '#880015', '#ff7f27',
259  '#3f48cc', '#c3c3c3', '#ffc90e',
260  '#efe4b0', '#b5e61d', '#99d9ea',
261  '#7092b4', '#ffffff'];
262 
263  if (map_coloring is not None):
264  if (len(map_coloring) > len(available_colors)):
265  raise NameError('Impossible to represent colored graph due to number of specified colors.');
266 
267  x_maximum = -float('inf');
268  x_minimum = float('inf');
269  y_maximum = -float('inf');
270  y_minimum = float('inf');
271 
272  for i in range(0, len(graph_instance.space_description), 1):
273  if (graph_instance.type_graph_descr == type_graph_descr.GRAPH_MATRIX_DESCR):
274  for j in range(i, len(graph_instance.space_description), 1): # draw connection between two points only one time
275  if (graph_instance.data[i][j] == 1):
276  axes.plot([graph_instance.space_description[i][0], graph_instance.space_description[j][0]], [graph_instance.space_description[i][1], graph_instance.space_description[j][1]], 'k-', linewidth = 1.5);
277 
278  elif (graph_instance.type_graph_descr == type_graph_descr.GRAPH_VECTOR_DESCR):
279  for j in graph_instance.data[i]:
280  if (i > j): # draw connection between two points only one time
281  axes.plot([graph_instance.space_description[i][0], graph_instance.space_description[j][0]], [graph_instance.space_description[i][1], graph_instance.space_description[j][1]], 'k-', linewidth = 1.5);
282 
283  color_node = 'b';
284  if (map_coloring is not None):
285  color_node = colors.hex2color(available_colors[map_coloring[i]]);
286 
287  axes.plot(graph_instance.space_description[i][0], graph_instance.space_description[i][1], color = color_node, marker = 'o', markersize = 20);
288 
289  if (x_maximum < graph_instance.space_description[i][0]): x_maximum = graph_instance.space_description[i][0];
290  if (x_minimum > graph_instance.space_description[i][0]): x_minimum = graph_instance.space_description[i][0];
291  if (y_maximum < graph_instance.space_description[i][1]): y_maximum = graph_instance.space_description[i][1];
292  if (y_minimum > graph_instance.space_description[i][1]): y_minimum = graph_instance.space_description[i][1];
293 
294  plt.xlim(x_minimum - 0.5, x_maximum + 0.5);
295  plt.ylim(y_minimum - 0.5, y_maximum + 0.5);
296 
297  plt.show();
def __init__(self, data, type_graph=None, space_descr=None, comments=None)
Constructor of graph.
Definition: graph.py:66
Graph representation.
Definition: graph.py:60
def draw_graph(graph_instance, map_coloring=None)
Draw graph.
Definition: graph.py:232
Enumeration of graph description.
Definition: graph.py:37
def read_graph(filename)
Read graph from file in GRPR format.
Definition: graph.py:138