Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Routines to find the boundary of a set of nodes.
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).
7A node boundary of a set *S* of nodes is the set of (out-)neighbors of
8nodes in *S* that are outside *S*.
10"""
12from itertools import chain
14import networkx as nx
16__all__ = ["edge_boundary", "node_boundary"]
19@nx._dispatchable(edge_attrs={"data": "default"}, preserve_edge_attrs="data")
20def edge_boundary(G, nbunch1, nbunch2=None, data=False, keys=False, default=None):
21 """Returns the edge boundary of `nbunch1`.
23 The *edge boundary* of a set *S* with respect to a set *T* is the
24 set of edges (*u*, *v*) such that *u* is in *S* and *v* is in *T*.
25 If *T* is not specified, it is assumed to be the set of all nodes
26 not in *S*.
28 Parameters
29 ----------
30 G : NetworkX graph
32 nbunch1 : iterable
33 Iterable of nodes in the graph representing the set of nodes
34 whose edge boundary will be returned. (This is the set *S* from
35 the definition above.)
37 nbunch2 : iterable
38 Iterable of nodes representing the target (or "exterior") set of
39 nodes. (This is the set *T* from the definition above.) If not
40 specified, this is assumed to be the set of all nodes in `G`
41 not in `nbunch1`.
43 keys : bool
44 This parameter has the same meaning as in
45 :meth:`MultiGraph.edges`.
47 data : bool or object
48 This parameter has the same meaning as in
49 :meth:`MultiGraph.edges`.
51 default : object
52 This parameter has the same meaning as in
53 :meth:`MultiGraph.edges`.
55 Returns
56 -------
57 iterator
58 An iterator over the edges in the boundary of `nbunch1` with
59 respect to `nbunch2`. If `keys`, `data`, or `default`
60 are specified and `G` is a multigraph, then edges are returned
61 with keys and/or data, as in :meth:`MultiGraph.edges`.
63 Examples
64 --------
65 >>> G = nx.wheel_graph(6)
67 When nbunch2=None:
69 >>> list(nx.edge_boundary(G, (1, 3)))
70 [(1, 0), (1, 2), (1, 5), (3, 0), (3, 2), (3, 4)]
72 When nbunch2 is given:
74 >>> list(nx.edge_boundary(G, (1, 3), (2, 0)))
75 [(1, 0), (1, 2), (3, 0), (3, 2)]
77 Notes
78 -----
79 Any element of `nbunch` that is not in the graph `G` will be
80 ignored.
82 `nbunch1` and `nbunch2` are usually meant to be disjoint, but in
83 the interest of speed and generality, that is not required here.
85 """
86 nset1 = {n for n in nbunch1 if n in G}
87 # Here we create an iterator over edges incident to nodes in the set
88 # `nset1`. The `Graph.edges()` method does not provide a guarantee
89 # on the orientation of the edges, so our algorithm below must
90 # handle the case in which exactly one orientation, either (u, v) or
91 # (v, u), appears in this iterable.
92 if G.is_multigraph():
93 edges = G.edges(nset1, data=data, keys=keys, default=default)
94 else:
95 edges = G.edges(nset1, data=data, default=default)
96 # If `nbunch2` is not provided, then it is assumed to be the set
97 # complement of `nbunch1`. For the sake of efficiency, this is
98 # implemented by using the `not in` operator, instead of by creating
99 # an additional set and using the `in` operator.
100 if nbunch2 is None:
101 return (e for e in edges if (e[0] in nset1) ^ (e[1] in nset1))
102 nset2 = set(nbunch2)
103 return (
104 e
105 for e in edges
106 if (e[0] in nset1 and e[1] in nset2) or (e[1] in nset1 and e[0] in nset2)
107 )
110@nx._dispatchable
111def node_boundary(G, nbunch1, nbunch2=None):
112 """Returns the node boundary of `nbunch1`.
114 The *node boundary* of a set *S* with respect to a set *T* is the
115 set of nodes *v* in *T* such that for some *u* in *S*, there is an
116 edge joining *u* to *v*. If *T* is not specified, it is assumed to
117 be the set of all nodes not in *S*.
119 Parameters
120 ----------
121 G : NetworkX graph
123 nbunch1 : iterable
124 Iterable of nodes in the graph representing the set of nodes
125 whose node boundary will be returned. (This is the set *S* from
126 the definition above.)
128 nbunch2 : iterable
129 Iterable of nodes representing the target (or "exterior") set of
130 nodes. (This is the set *T* from the definition above.) If not
131 specified, this is assumed to be the set of all nodes in `G`
132 not in `nbunch1`.
134 Returns
135 -------
136 set
137 The node boundary of `nbunch1` with respect to `nbunch2`.
139 Examples
140 --------
141 >>> G = nx.wheel_graph(6)
143 When nbunch2=None:
145 >>> list(nx.node_boundary(G, (3, 4)))
146 [0, 2, 5]
148 When nbunch2 is given:
150 >>> list(nx.node_boundary(G, (3, 4), (0, 1, 5)))
151 [0, 5]
153 Notes
154 -----
155 Any element of `nbunch` that is not in the graph `G` will be
156 ignored.
158 `nbunch1` and `nbunch2` are usually meant to be disjoint, but in
159 the interest of speed and generality, that is not required here.
161 """
162 nset1 = {n for n in nbunch1 if n in G}
163 bdy = set(chain.from_iterable(G[v] for v in nset1)) - nset1
164 # If `nbunch2` is not specified, it is assumed to be the set
165 # complement of `nbunch1`.
166 if nbunch2 is not None:
167 bdy &= set(nbunch2)
168 return bdy