Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.algorithms.boundary

#    Copyright (C) 2004-2019 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    Copyright 2015 NetworkX developers.
#    All rights reserved.
#    BSD license.
"""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*.

"""
from itertools import chain

__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)"""

__all__ = ['edge_boundary', 'node_boundary']


[docs]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 = {v for v in G if v in nbunch1} # 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))
[docs]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