Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/boundary.py @ 1:56ad4e20f292 draft

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