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