ioftools / networkxMiCe / networkxmaster / networkx / algorithms / operators / all.py @ 5cef0f13
History  View  Annotate  Download (4.54 KB)
1 
"""Operations on many graphs.


2 
"""

3 
# Copyright (C) 2013 by

4 
# Aric Hagberg <hagberg@lanl.gov>

5 
# Dan Schult <dschult@colgate.edu>

6 
# Pieter Swart <swart@lanl.gov>

7 
# All rights reserved.

8 
# BSD license.

9 
try:

10 
from itertools import izip_longest as zip_longest 
11 
except ImportError: # Python3 has zip_longest 
12 
from itertools import zip_longest 
13 
import networkx as nx 
14  
15 
__author__ = """\n""".join(['Robert King <kingrobertking@gmail.com>', 
16 
'Aric Hagberg <aric.hagberg@gmail.com>'])

17  
18 
__all__ = ['union_all', 'compose_all', 'disjoint_union_all', 
19 
'intersection_all']

20  
21  
22 
def union_all(graphs, rename=(None,)): 
23 
"""Returns the union of all graphs.

24 

25 
The graphs must be disjoint, otherwise an exception is raised.

26 

27 
Parameters

28 


29 
graphs : list of graphs

30 
List of NetworkX graphs

31 

32 
rename : bool , default=(None, None)

33 
Node names of G and H can be changed by specifying the tuple

34 
rename=('G','H') (for example). Node "u" in G is then renamed

35 
"Gu" and "v" in H is renamed "Hv".

36 

37 
Returns

38 


39 
U : a graph with the same type as the first graph in list

40 

41 
Raises

42 


43 
ValueError

44 
If `graphs` is an empty list.

45 

46 
Notes

47 


48 
To force a disjoint union with node relabeling, use

49 
disjoint_union_all(G,H) or convert_node_labels_to integers().

50 

51 
Graph, edge, and node attributes are propagated to the union graph.

52 
If a graph attribute is present in multiple graphs, then the value

53 
from the last graph in the list with that attribute is used.

54 

55 
See Also

56 


57 
union

58 
disjoint_union_all

59 
"""

60 
if not graphs: 
61 
raise ValueError('cannot apply union_all to an empty list') 
62 
graphs_names = zip_longest(graphs, rename) 
63 
U, gname = next(graphs_names)

64 
for H, hname in graphs_names: 
65 
U = nx.union(U, H, (gname, hname)) 
66 
gname = None

67 
return U

68  
69  
70 
def disjoint_union_all(graphs): 
71 
"""Returns the disjoint union of all graphs.

72 

73 
This operation forces distinct integer node labels starting with 0

74 
for the first graph in the list and numbering consecutively.

75 

76 
Parameters

77 


78 
graphs : list

79 
List of NetworkX graphs

80 

81 
Returns

82 


83 
U : A graph with the same type as the first graph in list

84 

85 
Raises

86 


87 
ValueError

88 
If `graphs` is an empty list.

89 

90 
Notes

91 


92 
It is recommended that the graphs be either all directed or all undirected.

93 

94 
Graph, edge, and node attributes are propagated to the union graph.

95 
If a graph attribute is present in multiple graphs, then the value

96 
from the last graph in the list with that attribute is used.

97 
"""

98 
if not graphs: 
99 
raise ValueError('cannot apply disjoint_union_all to an empty list') 
100 
graphs = iter(graphs)

101 
U = next(graphs)

102 
for H in graphs: 
103 
U = nx.disjoint_union(U, H) 
104 
return U

105  
106  
107 
def compose_all(graphs): 
108 
"""Returns the composition of all graphs.

109 

110 
Composition is the simple union of the node sets and edge sets.

111 
The node sets of the supplied graphs need not be disjoint.

112 

113 
Parameters

114 


115 
graphs : list

116 
List of NetworkX graphs

117 

118 
Returns

119 


120 
C : A graph with the same type as the first graph in list

121 

122 
Raises

123 


124 
ValueError

125 
If `graphs` is an empty list.

126 

127 
Notes

128 


129 
It is recommended that the supplied graphs be either all directed or all

130 
undirected.

131 

132 
Graph, edge, and node attributes are propagated to the union graph.

133 
If a graph attribute is present in multiple graphs, then the value

134 
from the last graph in the list with that attribute is used.

135 
"""

136 
if not graphs: 
137 
raise ValueError('cannot apply compose_all to an empty list') 
138 
graphs = iter(graphs)

139 
C = next(graphs)

140 
for H in graphs: 
141 
C = nx.compose(C, H) 
142 
return C

143  
144  
145 
def intersection_all(graphs): 
146 
"""Returns a new graph that contains only the edges that exist in

147 
all graphs.

148 

149 
All supplied graphs must have the same node set.

150 

151 
Parameters

152 


153 
graphs : list

154 
List of NetworkX graphs

155 

156 
Returns

157 


158 
R : A new graph with the same type as the first graph in list

159 

160 
Raises

161 


162 
ValueError

163 
If `graphs` is an empty list.

164 

165 
Notes

166 


167 
Attributes from the graph, nodes, and edges are not copied to the new

168 
graph.

169 
"""

170 
if not graphs: 
171 
raise ValueError('cannot apply intersection_all to an empty list') 
172 
graphs = iter(graphs)

173 
R = next(graphs)

174 
for H in graphs: 
175 
R = nx.intersection(R, H) 
176 
return R
