python-igraph manual

For using igraph from Python

   Home       Trees       Indices       Help   
Package igraph :: Module operators
[hide private]

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

   Home       Trees       Indices       Help