Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/boundary.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Routines to find the boundary of a set of nodes. | |
2 | |
3 An edge boundary is a set of edges, each of which has exactly one | |
4 endpoint in a given set of nodes (or, in the case of directed graphs, | |
5 the set of edges whose source node is in the set). | |
6 | |
7 A node boundary of a set *S* of nodes is the set of (out-)neighbors of | |
8 nodes in *S* that are outside *S*. | |
9 | |
10 """ | |
11 from itertools import chain | |
12 | |
13 __all__ = ["edge_boundary", "node_boundary"] | |
14 | |
15 | |
16 def edge_boundary(G, nbunch1, nbunch2=None, data=False, keys=False, default=None): | |
17 """Returns the edge boundary of `nbunch1`. | |
18 | |
19 The *edge boundary* of a set *S* with respect to a set *T* is the | |
20 set of edges (*u*, *v*) such that *u* is in *S* and *v* is in *T*. | |
21 If *T* is not specified, it is assumed to be the set of all nodes | |
22 not in *S*. | |
23 | |
24 Parameters | |
25 ---------- | |
26 G : NetworkX graph | |
27 | |
28 nbunch1 : iterable | |
29 Iterable of nodes in the graph representing the set of nodes | |
30 whose edge boundary will be returned. (This is the set *S* from | |
31 the definition above.) | |
32 | |
33 nbunch2 : iterable | |
34 Iterable of nodes representing the target (or "exterior") set of | |
35 nodes. (This is the set *T* from the definition above.) If not | |
36 specified, this is assumed to be the set of all nodes in `G` | |
37 not in `nbunch1`. | |
38 | |
39 keys : bool | |
40 This parameter has the same meaning as in | |
41 :meth:`MultiGraph.edges`. | |
42 | |
43 data : bool or object | |
44 This parameter has the same meaning as in | |
45 :meth:`MultiGraph.edges`. | |
46 | |
47 default : object | |
48 This parameter has the same meaning as in | |
49 :meth:`MultiGraph.edges`. | |
50 | |
51 Returns | |
52 ------- | |
53 iterator | |
54 An iterator over the edges in the boundary of `nbunch1` with | |
55 respect to `nbunch2`. If `keys`, `data`, or `default` | |
56 are specified and `G` is a multigraph, then edges are returned | |
57 with keys and/or data, as in :meth:`MultiGraph.edges`. | |
58 | |
59 Notes | |
60 ----- | |
61 Any element of `nbunch` that is not in the graph `G` will be | |
62 ignored. | |
63 | |
64 `nbunch1` and `nbunch2` are usually meant to be disjoint, but in | |
65 the interest of speed and generality, that is not required here. | |
66 | |
67 """ | |
68 nset1 = {v for v in G if v in nbunch1} | |
69 # Here we create an iterator over edges incident to nodes in the set | |
70 # `nset1`. The `Graph.edges()` method does not provide a guarantee | |
71 # on the orientation of the edges, so our algorithm below must | |
72 # handle the case in which exactly one orientation, either (u, v) or | |
73 # (v, u), appears in this iterable. | |
74 if G.is_multigraph(): | |
75 edges = G.edges(nset1, data=data, keys=keys, default=default) | |
76 else: | |
77 edges = G.edges(nset1, data=data, default=default) | |
78 # If `nbunch2` is not provided, then it is assumed to be the set | |
79 # complement of `nbunch1`. For the sake of efficiency, this is | |
80 # implemented by using the `not in` operator, instead of by creating | |
81 # an additional set and using the `in` operator. | |
82 if nbunch2 is None: | |
83 return (e for e in edges if (e[0] in nset1) ^ (e[1] in nset1)) | |
84 nset2 = set(nbunch2) | |
85 return ( | |
86 e | |
87 for e in edges | |
88 if (e[0] in nset1 and e[1] in nset2) or (e[1] in nset1 and e[0] in nset2) | |
89 ) | |
90 | |
91 | |
92 def node_boundary(G, nbunch1, nbunch2=None): | |
93 """Returns the node boundary of `nbunch1`. | |
94 | |
95 The *node boundary* of a set *S* with respect to a set *T* is the | |
96 set of nodes *v* in *T* such that for some *u* in *S*, there is an | |
97 edge joining *u* to *v*. If *T* is not specified, it is assumed to | |
98 be the set of all nodes not in *S*. | |
99 | |
100 Parameters | |
101 ---------- | |
102 G : NetworkX graph | |
103 | |
104 nbunch1 : iterable | |
105 Iterable of nodes in the graph representing the set of nodes | |
106 whose node boundary will be returned. (This is the set *S* from | |
107 the definition above.) | |
108 | |
109 nbunch2 : iterable | |
110 Iterable of nodes representing the target (or "exterior") set of | |
111 nodes. (This is the set *T* from the definition above.) If not | |
112 specified, this is assumed to be the set of all nodes in `G` | |
113 not in `nbunch1`. | |
114 | |
115 Returns | |
116 ------- | |
117 set | |
118 The node boundary of `nbunch1` with respect to `nbunch2`. | |
119 | |
120 Notes | |
121 ----- | |
122 Any element of `nbunch` that is not in the graph `G` will be | |
123 ignored. | |
124 | |
125 `nbunch1` and `nbunch2` are usually meant to be disjoint, but in | |
126 the interest of speed and generality, that is not required here. | |
127 | |
128 """ | |
129 nset1 = {n for n in nbunch1 if n in G} | |
130 bdy = set(chain.from_iterable(G[v] for v in nset1)) - nset1 | |
131 # If `nbunch2` is not specified, it is assumed to be the set | |
132 # complement of `nbunch1`. | |
133 if nbunch2 is not None: | |
134 bdy &= set(nbunch2) | |
135 return bdy |