Source Code for Module igraph.operators

  1  # vim:ts=4:sw=4:sts=4:et 
  2  # -*- coding: utf-8 -*- 
  3  """Implementation of union, disjoint union and intersection operators.""" 
  4   
  5  from __future__ import with_statement 
  6   
  7  __all__ = ("disjoint_union", "union", "intersection") 
  8  __docformat__ = "restructuredtext en" 
  9  __license__ = u""" 
 10  Copyright (C) 2006-2012  Tamás Nepusz <ntamas@gmail.com> 
 11  Pázmány Péter sétány 1/a, 1117 Budapest, Hungary 
 12   
 13  This program is free software; you can redistribute it and/or modify 
 14  it under the terms of the GNU General Public License as published by 
 15  the Free Software Foundation; either version 2 of the License, or 
 16  (at your option) any later version. 
 17   
 18  This program is distributed in the hope that it will be useful, 
 19  but WITHOUT ANY WARRANTY; without even the implied warranty of 
 20  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 21  GNU General Public License for more details. 
 22   
 23  You should have received a copy of the GNU General Public License 
 24  along with this program; if not, write to the Free Software 
 25  Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
 26  02110-1301 USA 
 27  """ 
 28   
 29  from igraph._igraph import GraphBase, _union, _intersection, _disjoint_union 
 30   
 31  from collections import defaultdict, Counter 
 32  from warnings import warn 
 33   
 34   
 35 -def disjoint_union(graphs): 
 36      """Graph disjoint union. 
 37   
 38      The disjoint union of two or more graphs is created. 
 39   
 40      This function keeps the attributes of all graphs. All graph, vertex and 
 41      edge attributes are copied to the result. If an attribute is present in 
 42      multiple graphs and would result a name clash, then this attribute is 
 43      renamed by adding suffixes: _1, _2, etc. 
 44   
 45      An error is generated if some input graphs are directed and others are 
 46      undirected. 
 47   
 48      @param graph: list of graphs. A lazy sequence is not acceptable. 
 49      @return: the disjoint union graph 
 50      """ 
 51      if any(not isinstance(g, GraphBase) for g in graphs): 
 52          raise TypeError('Not all elements are graphs') 
 53   
 54      ngr = len(graphs) 
 55      # Trivial cases 
 56      if ngr == 0: 
 57          raise ValueError("disjoint_union() needs at least one graph") 
 58      if ngr == 1: 
 59          return graphs[0].copy() 
 60      # Now there are at least two graphs 
 61   
 62      graph_union = _disjoint_union(graphs) 
 63   
 64      # Graph attributes 
 65      # NOTE: a_first_graph tracks which graph has the 1st occurrence of an 
 66      # attribute, while a_conflict track attributes with naming conflicts 
 67      a_first_graph = {} 
 68      a_conflict = set() 
 69      for ig, g in enumerate(graphs, 1): 
 70          # NOTE: a_name is the name of the attribute, a_value its value 
 71          for a_name in g.attributes(): 
 72              a_value = g[a_name] 
 73              # No conflicts 
 74              if a_name not in graph_union.attributes(): 
 75                  a_first_graph[a_name] = ig 
 76                  graph_union[a_name] = a_value 
 77                  continue 
 78              if graph_union[a_name] == a_value: 
 79                  continue 
 80              if a_name not in a_conflict: 
 81                  # New conflict 
 82                  a_conflict.add(a_name) 
 83                  igf = a_first_graph[a_name] 
 84                  graph_union['{:}_{:}'.format(a_name, igf)] = \ 
 85                      graph_union.pop(a_name) 
 86              graph_union['{:}_{:}'.format(a_name, ig)] = a_value 
 87   
 88      # Vertex attributes 
 89      i = 0 
 90      for g in graphs: 
 91          nv = g.vcount() 
 92          for attr in g.vertex_attributes(): 
 93              graph_union.vs[i: i + nv][attr] = g.vs[attr] 
 94          i += nv 
 95   
 96      # Edge attributes 
 97      i = 0 
 98      for g in graphs: 
 99          ne = g.ecount() 
100          for attr in g.edge_attributes(): 
101              graph_union.es[i: i + ne][attr] = g.es[attr] 
102          i += ne 
103   
104      return graph_union 
105   
106   
107 -def union(graphs, byname='auto'): 
108      """Graph union. 
109   
110      The union of two or more graphs is created. The graphs may have identical 
111      or overlapping vertex sets. Edges which are included in at least one graph 
112      will be part of the new graph. 
113   
114      This function keeps the attributes of all graphs. All graph, vertex and 
115      edge attributes are copied to the result. If an attribute is present in 
116      multiple graphs and would result a name clash, then this attribute is 
117      renamed by adding suffixes: _1, _2, etc. 
118   
119      The 'name' vertex attribute is treated specially if the operation is 
120      performed based on symbolic vertex names. In this case 'name' must be 
121      present in all graphs, and it is not renamed in the result graph. 
122   
123      An error is generated if some input graphs are directed and others are 
124      undirected. 
125   
126      @param graph: list of graphs. A lazy sequence is not acceptable. 
127      @param byname: bool or 'auto' specifying the function behaviour with 
128        respect to names vertices (i.e. vertices with the 'name' attribute). If 
129        False, ignore vertex names. If True, merge vertices based on names. If 
130        'auto', use True if all graphs have named vertices and False otherwise 
131        (in the latter case, a warning is generated too). 
132      @return: the union graph 
133      """ 
134   
135      if any(not isinstance(g, GraphBase) for g in graphs): 
136          raise TypeError('Not all elements are graphs') 
137   
138      if byname not in (True, False, 'auto'): 
139          raise ValueError('"byname" should be a bool or "auto"') 
140   
141      ngr = len(graphs) 
142      n_named = sum(g.is_named() for g in graphs) 
143      if byname == 'auto': 
144          byname = n_named == ngr 
145          if n_named not in (0, ngr): 
146              warn("Some, but not all graphs are named, not using vertex names") 
147      elif byname and (n_named != ngr): 
148          raise AttributeError("Some graphs are not named") 
149      # Now we know that byname is only used is all graphs are named 
150   
151      # Trivial cases 
152      if ngr == 0: 
153          raise ValueError("union() needs at least one graph") 
154      if ngr == 1: 
155          return graphs[0].copy() 
156      # Now there are at least two graphs 
157   
158      if byname: 
159          allnames = [g.vs['name'] for g in graphs] 
160          uninames = list(set.union(*(set(vns) for vns in allnames))) 
161          permutation_map = {x: i for i, x in enumerate(uninames)} 
162          nve = len(uninames) 
163          newgraphs = [] 
164          for g, vertex_names in zip(graphs, allnames): 
165              # Make a copy 
166              ng = g.copy() 
167   
168              # Add the missing vertices 
169              v_missing = list(set(uninames) - set(vertex_names)) 
170              ng.add_vertices(v_missing) 
171   
172              # Reorder vertices to match uninames 
173              # vertex k -> p[k] 
174              permutation = [permutation_map[x] for x in ng.vs['name']] 
175              ng = ng.permute_vertices(permutation) 
176   
177              newgraphs.append(ng) 
178      else: 
179          newgraphs = graphs 
180   
181      # If any graph has any edge attributes, we need edgemaps 
182      edgemaps = any(len(g.edge_attributes()) for g in graphs) 
183      res = _union(newgraphs, edgemaps) 
184      if edgemaps: 
185          graph_union = res['graph'] 
186          edgemaps = res['edgemaps'] 
187      else: 
188          graph_union = res 
189   
190      # Graph attributes 
191      a_first_graph = {} 
192      a_conflict = set() 
193      for ig, g in enumerate(newgraphs, 1): 
194          # NOTE: a_name is the name of the attribute, a_value its value 
195          for a_name in g.attributes(): 
196              a_value = g[a_name] 
197              # No conflicts 
198              if a_name not in graph_union.attributes(): 
199                  a_first_graph[a_name] = ig 
200                  graph_union[a_name] = a_value 
201                  continue 
202              if graph_union[a_name] == a_value: 
203                  continue 
204              if a_name not in a_conflict: 
205                  # New conflict 
206                  a_conflict.add(a_name) 
207                  igf = a_first_graph[a_name] 
208                  graph_union['{:}_{:}'.format(a_name, igf)] = \ 
209                      graph_union.pop(a_name) 
210              graph_union['{:}_{:}'.format(a_name, ig)] = a_value 
211   
212      # Vertex attributes 
213      if byname: 
214          graph_union.vs['name'] = uninames 
215      attrs = set.union(*(set(g.vertex_attributes()) for g in newgraphs)) - set(['name']) 
216      nve = graph_union.vcount() 
217      for a_name in attrs: 
218          # Check for conflicts at at least one vertex 
219          conflict = False 
220          vals = [None for i in range(nve)] 
221          for g in newgraphs: 
222              if a_name in g.vertex_attributes(): 
223                  for i, a_value in enumerate(g.vs[a_name]): 
224                      if a_value is None: 
225                          continue 
226                      if vals[i] is None: 
227                          vals[i] = a_value 
228                          continue 
229                      if vals[i] != a_value: 
230                          conflict = True 
231                          break 
232              if conflict: 
233                  break 
234   
235          if not conflict: 
236              graph_union.vs[a_name] = vals 
237              continue 
238   
239          # There is a conflict, name after the graph number 
240          for ig, g in enumerate(newgraphs, 1): 
241              if a_name in g.vertex_attributes(): 
242                  graph_union.vs['{:}_{:}'.format(a_name, ig)] = g.vs[a_name] 
243   
244      # Edge attributes 
245      if edgemaps: 
246          attrs = set.union(*(set(g.edge_attributes()) for g in newgraphs)) 
247          ne = graph_union.ecount() 
248          for a_name in attrs: 
249              # Check for conflicts at at least one edge 
250              conflict = False 
251              vals = [None for i in range(ne)] 
252              for g, emap in zip(newgraphs, edgemaps): 
253                  if a_name not in g.edge_attributes(): 
254                      continue 
255                  for iu, a_value in zip(emap, g.es[a_name]): 
256                      if a_value is None: 
257                          continue 
258                      if vals[iu] is None: 
259                          vals[iu] = a_value 
260                          continue 
261                      if vals[iu] != a_value: 
262                          print(g, g.vs['name'], emap, a_value, iu, vals[iu]) 
263                          conflict = True 
264                          break 
265                  if conflict: 
266                      break 
267   
268              if not conflict: 
269                  graph_union.es[a_name] = vals 
270                  continue 
271   
272              # There is a conflict, name after the graph number 
273              for ig, (g, emap) in enumerate(zip(newgraphs, edgemaps), 1): 
274                  if a_name not in g.edge_attributes(): 
275                      continue 
276                  # Pass through map 
277                  vals = [None for i in range(ne)] 
278                  for iu, a_value in zip(emap, g.es[a_name]): 
279                      vals[iu] = a_value 
280                  graph_union.es['{:}_{:}'.format(a_name, ig)] = vals 
281   
282      return graph_union 
283   
284   
285 -def intersection(graphs, byname='auto', keep_all_vertices=True): 
286      """Graph intersection. 
287   
288      The intersection of two or more graphs is created. The graphs may have 
289      identical or overlapping vertex sets. Edges which are included in all 
290      graphs will be part of the new graph. 
291   
292      This function keeps the attributes of all graphs. All graph, vertex and 
293      edge attributes are copied to the result. If an attribute is present in 
294      multiple graphs and would result a name clash, then this attribute is 
295      renamed by adding suffixes: _1, _2, etc. 
296   
297      The 'name' vertex attribute is treated specially if the operation is 
298      performed based on symbolic vertex names. In this case 'name' must be 
299      present in all graphs, and it is not renamed in the result graph. 
300   
301      An error is generated if some input graphs are directed and others are 
302      undirected. 
303   
304      @param graph: list of graphs. A lazy sequence is not acceptable. 
305      @param byname: bool or 'auto' specifying the function behaviour with 
306        respect to names vertices (i.e. vertices with the 'name' attribute). If 
307        False, ignore vertex names. If True, merge vertices based on names. If 
308        'auto', use True if all graphs have named vertices and False otherwise 
309        (in the latter case, a warning is generated too). 
310      @keep_all_vertices: bool specifying if vertices that are not present in all 
311        graphs should be kept in the intersection. 
312      @return: the intersection graph 
313      """ 
314   
315      if any(not isinstance(g, GraphBase) for g in graphs): 
316          raise TypeError('Not all elements are graphs') 
317   
318      if byname not in (True, False, 'auto'): 
319          raise ValueError('"byname" should be a bool or "auto"') 
320   
321      ngr = len(graphs) 
322      n_named = sum(g.is_named() for g in graphs) 
323      if byname == 'auto': 
324          byname = n_named == ngr 
325          if n_named not in (0, ngr): 
326              warn("Some, but not all graphs are named, not using vertex names") 
327      elif byname and (n_named != ngr): 
328          raise AttributeError("Some graphs are not named") 
329      # Now we know that byname is only used is all graphs are named 
330   
331      # Trivial cases 
332      if ngr == 0: 
333          raise ValueError("intersection() needs at least one graph") 
334      if ngr == 1: 
335          return graphs[0].copy() 
336      # Now there are at least two graphs 
337   
338      if byname: 
339          allnames = [g.vs['name'] for g in graphs] 
340   
341          if keep_all_vertices: 
342              uninames = list(set.union(*(set(vns) for vns in allnames))) 
343          else: 
344              uninames = list(set.intersection(*(set(vns) for vns in allnames))) 
345          permutation_map = {x: i for i, x in enumerate(uninames)} 
346   
347          nv = len(uninames) 
348          newgraphs = [] 
349          for g, vertex_names in zip(graphs, allnames): 
350              # Make a copy 
351              ng = g.copy() 
352   
353              if keep_all_vertices: 
354                  # Add the missing vertices 
355                  v_missing = list(set(uninames) - set(vertex_names)) 
356                  ng.add_vertices(v_missing) 
357              else: 
358                  # Delete the private vertices 
359                  v_private = list(set(vertex_names) - set(uninames)) 
360                  ng.delete_vertices(v_private) 
361   
362              # Reorder vertices to match uninames 
363              # vertex k -> p[k] 
364              permutation = [permutation_map[x] for x in ng.vs['name']] 
365              ng = ng.permute_vertices(permutation) 
366   
367              newgraphs.append(ng) 
368      else: 
369          newgraphs = graphs 
370   
371      # If any graph has any edge attributes, we need edgemaps 
372      edgemaps = any(len(g.edge_attributes()) for g in graphs) 
373      res = _intersection(newgraphs, edgemaps) 
374      if edgemaps: 
375          graph_intsec = res['graph'] 
376          edgemaps = res['edgemaps'] 
377      else: 
378          graph_intsec = res 
379   
380      # Graph attributes 
381      a_first_graph = {} 
382      a_conflict = set() 
383      for ig, g in enumerate(newgraphs, 1): 
384          # NOTE: a_name is the name of the attribute, a_value its value 
385          for a_name in g.attributes(): 
386              a_value = g[a_name] 
387              # No conflicts 
388              if a_name not in graph_intsec.attributes(): 
389                  a_first_graph[a_name] = ig 
390                  graph_intsec[a_name] = a_value 
391                  continue 
392              if graph_intsec[a_name] == a_value: 
393                  continue 
394              if a_name not in a_conflict: 
395                  # New conflict 
396                  a_conflict.add(a_name) 
397                  igf = a_first_graph[a_name] 
398                  graph_intsec['{:}_{:}'.format(a_name, igf)] = \ 
399                      graph_intsec.pop(a_name) 
400              graph_intsec['{:}_{:}'.format(a_name, ig)] = a_value 
401   
402      # Vertex attributes 
403      if byname: 
404          graph_intsec.vs['name'] = uninames 
405      attrs = set.union(*(set(g.vertex_attributes()) for g in newgraphs)) - set(['name']) 
406      nv = graph_intsec.vcount() 
407      for a_name in attrs: 
408          # Check for conflicts at at least one vertex 
409          conflict = False 
410          vals = [None for i in range(nv)] 
411          for g in newgraphs: 
412              if a_name not in g.vertex_attributes(): 
413                  continue 
414              for i, a_value in enumerate(g.vs[a_name]): 
415                  if a_value is None: 
416                      continue 
417                  if vals[i] is None: 
418                      vals[i] = a_value 
419                      continue 
420                  if vals[i] != a_value: 
421                      conflict = True 
422                      break 
423              if conflict: 
424                  break 
425   
426          if not conflict: 
427              graph_intsec.vs[a_name] = vals 
428              continue 
429   
430          # There is a conflict, name after the graph number 
431          for ig, g in enumerate(newgraphs, 1): 
432              if a_name in g.vertex_attributes(): 
433                  graph_intsec.vs['{:}_{:}'.format(a_name, ig)] = g.vs[a_name] 
434   
435      # Edge attributes 
436      if edgemaps: 
437          attrs = set.union(*(set(g.edge_attributes()) for g in newgraphs)) 
438          ne = graph_intsec.ecount() 
439          for a_name in attrs: 
440              # Check for conflicts at at least one edge 
441              conflict = False 
442              vals = [None for i in range(ne)] 
443              for g, emap in zip(newgraphs, edgemaps): 
444                  if a_name not in g.edge_attributes(): 
445                      continue 
446                  for iu, a_value in zip(emap, g.es[a_name]): 
447                      if iu == -1: 
448                          continue 
449                      if a_value is None: 
450                          continue 
451                      if vals[iu] is None: 
452                          vals[iu] = a_value 
453                          continue 
454                      if vals[iu] != a_value: 
455                          conflict = True 
456                          break 
457                  if conflict: 
458                      break 
459   
460              if not conflict: 
461                  graph_intsec.es[a_name] = vals 
462                  continue 
463   
464              # There is a conflict, name after the graph number 
465              for ig, (g, emap) in enumerate(zip(newgraphs, edgemaps), 1): 
466                  if a_name not in g.edge_attributes(): 
467                      continue 
468                  # Pass through map 
469                  vals = [None for i in range(ne)] 
470                  for iu, a_value in zip(emap, g.es[a_name]): 
471                      if iu == -1: 
472                          continue 
473                      vals[iu] = a_value 
474                  graph_intsec.es['{:}_{:}'.format(a_name, ig)] = vals 
475   
476      return graph_intsec 
477