Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/boundary.py: 35%

1"""Routines to find the boundary of a set of nodes. 

2 

3An edge boundary is a set of edges, each of which has exactly one 

4endpoint in a given set of nodes (or, in the case of directed graphs, 

5the set of edges whose source node is in the set). 

6 

7A node boundary of a set *S* of nodes is the set of (out-)neighbors of 

8nodes in *S* that are outside *S*. 

9 

10""" 

11from itertools import chain 

12 

13import networkx as nx 

14 

15__all__ = ["edge_boundary", "node_boundary"] 

16 

17 

18@nx._dispatch(edge_attrs={"data": "default"}, preserve_edge_attrs="data") 

19def edge_boundary(G, nbunch1, nbunch2=None, data=False, keys=False, default=None): 

20 """Returns the edge boundary of `nbunch1`. 

21 

22 The *edge boundary* of a set *S* with respect to a set *T* is the 

23 set of edges (*u*, *v*) such that *u* is in *S* and *v* is in *T*. 

24 If *T* is not specified, it is assumed to be the set of all nodes 

25 not in *S*. 

26 

27 Parameters 

28 ---------- 

29 G : NetworkX graph 

30 

31 nbunch1 : iterable 

32 Iterable of nodes in the graph representing the set of nodes 

33 whose edge boundary will be returned. (This is the set *S* from 

34 the definition above.) 

35 

36 nbunch2 : iterable 

37 Iterable of nodes representing the target (or "exterior") set of 

38 nodes. (This is the set *T* from the definition above.) If not 

39 specified, this is assumed to be the set of all nodes in `G` 

40 not in `nbunch1`. 

41 

42 keys : bool 

43 This parameter has the same meaning as in 

44 :meth:`MultiGraph.edges`. 

45 

46 data : bool or object 

47 This parameter has the same meaning as in 

48 :meth:`MultiGraph.edges`. 

49 

50 default : object 

51 This parameter has the same meaning as in 

52 :meth:`MultiGraph.edges`. 

53 

54 Returns 

55 ------- 

56 iterator 

57 An iterator over the edges in the boundary of `nbunch1` with 

58 respect to `nbunch2`. If `keys`, `data`, or `default` 

59 are specified and `G` is a multigraph, then edges are returned 

60 with keys and/or data, as in :meth:`MultiGraph.edges`. 

61 

62 Examples 

63 -------- 

64 >>> G = nx.wheel_graph(6) 

65 

66 When nbunch2=None: 

67 

68 >>> list(nx.edge_boundary(G, (1, 3))) 

69 [(1, 0), (1, 2), (1, 5), (3, 0), (3, 2), (3, 4)] 

70 

71 When nbunch2 is given: 

72 

73 >>> list(nx.edge_boundary(G, (1, 3), (2, 0))) 

74 [(1, 0), (1, 2), (3, 0), (3, 2)] 

75 

76 Notes 

77 ----- 

78 Any element of `nbunch` that is not in the graph `G` will be 

79 ignored. 

80 

81 `nbunch1` and `nbunch2` are usually meant to be disjoint, but in 

82 the interest of speed and generality, that is not required here. 

83 

84 """ 

85 nset1 = {n for n in nbunch1 if n in G} 

86 # Here we create an iterator over edges incident to nodes in the set 

87 # `nset1`. The `Graph.edges()` method does not provide a guarantee 

88 # on the orientation of the edges, so our algorithm below must 

89 # handle the case in which exactly one orientation, either (u, v) or 

90 # (v, u), appears in this iterable. 

91 if G.is_multigraph(): 

92 edges = G.edges(nset1, data=data, keys=keys, default=default) 

93 else: 

94 edges = G.edges(nset1, data=data, default=default) 

95 # If `nbunch2` is not provided, then it is assumed to be the set 

96 # complement of `nbunch1`. For the sake of efficiency, this is 

97 # implemented by using the `not in` operator, instead of by creating 

98 # an additional set and using the `in` operator. 

99 if nbunch2 is None: 

100 return (e for e in edges if (e[0] in nset1) ^ (e[1] in nset1)) 

101 nset2 = set(nbunch2) 

102 return ( 

103 e 

104 for e in edges 

105 if (e[0] in nset1 and e[1] in nset2) or (e[1] in nset1 and e[0] in nset2) 

106 ) 

107 

108 

109@nx._dispatch 

110def node_boundary(G, nbunch1, nbunch2=None): 

111 """Returns the node boundary of `nbunch1`. 

112 

113 The *node boundary* of a set *S* with respect to a set *T* is the 

114 set of nodes *v* in *T* such that for some *u* in *S*, there is an 

115 edge joining *u* to *v*. If *T* is not specified, it is assumed to 

116 be the set of all nodes not in *S*. 

117 

118 Parameters 

119 ---------- 

120 G : NetworkX graph 

121 

122 nbunch1 : iterable 

123 Iterable of nodes in the graph representing the set of nodes 

124 whose node boundary will be returned. (This is the set *S* from 

125 the definition above.) 

126 

127 nbunch2 : iterable 

128 Iterable of nodes representing the target (or "exterior") set of 

129 nodes. (This is the set *T* from the definition above.) If not 

130 specified, this is assumed to be the set of all nodes in `G` 

131 not in `nbunch1`. 

132 

133 Returns 

134 ------- 

135 set 

136 The node boundary of `nbunch1` with respect to `nbunch2`. 

137 

138 Examples 

139 -------- 

140 >>> G = nx.wheel_graph(6) 

141 

142 When nbunch2=None: 

143 

144 >>> list(nx.node_boundary(G, (3, 4))) 

145 [0, 2, 5] 

146 

147 When nbunch2 is given: 

148 

149 >>> list(nx.node_boundary(G, (3, 4), (0, 1, 5))) 

150 [0, 5] 

151 

152 Notes 

153 ----- 

154 Any element of `nbunch` that is not in the graph `G` will be 

155 ignored. 

156 

157 `nbunch1` and `nbunch2` are usually meant to be disjoint, but in 

158 the interest of speed and generality, that is not required here. 

159 

160 """ 

161 nset1 = {n for n in nbunch1 if n in G} 

162 bdy = set(chain.from_iterable(G[v] for v in nset1)) - nset1 

163 # If `nbunch2` is not specified, it is assumed to be the set 

164 # complement of `nbunch1`. 

165 if nbunch2 is not None: 

166 bdy &= set(nbunch2) 

167 return bdy