1
2
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
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
56 if ngr == 0:
57 raise ValueError("disjoint_union() needs at least one graph")
58 if ngr == 1:
59 return graphs[0].copy()
60
61
62 graph_union = _disjoint_union(graphs)
63
64
65
66
67 a_first_graph = {}
68 a_conflict = set()
69 for ig, g in enumerate(graphs, 1):
70
71 for a_name in g.attributes():
72 a_value = g[a_name]
73
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
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
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
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
150
151
152 if ngr == 0:
153 raise ValueError("union() needs at least one graph")
154 if ngr == 1:
155 return graphs[0].copy()
156
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
166 ng = g.copy()
167
168
169 v_missing = list(set(uninames) - set(vertex_names))
170 ng.add_vertices(v_missing)
171
172
173
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
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
191 a_first_graph = {}
192 a_conflict = set()
193 for ig, g in enumerate(newgraphs, 1):
194
195 for a_name in g.attributes():
196 a_value = g[a_name]
197
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
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
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
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
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
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
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
273 for ig, (g, emap) in enumerate(zip(newgraphs, edgemaps), 1):
274 if a_name not in g.edge_attributes():
275 continue
276
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 @param keep_all_vertices: bool specifying if vertices that are not present
311 in all 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
330
331
332 if ngr == 0:
333 raise ValueError("intersection() needs at least one graph")
334 if ngr == 1:
335 return graphs[0].copy()
336
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
351 ng = g.copy()
352
353 if keep_all_vertices:
354
355 v_missing = list(set(uninames) - set(vertex_names))
356 ng.add_vertices(v_missing)
357 else:
358
359 v_private = list(set(vertex_names) - set(uninames))
360 ng.delete_vertices(v_private)
361
362
363
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
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
381 a_first_graph = {}
382 a_conflict = set()
383 for ig, g in enumerate(newgraphs, 1):
384
385 for a_name in g.attributes():
386 a_value = g[a_name]
387
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
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
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
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
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
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
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
465 for ig, (g, emap) in enumerate(zip(newgraphs, edgemaps), 1):
466 if a_name not in g.edge_attributes():
467 continue
468
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