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