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.
"""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 in nset1) ^ (e in nset1))
nset2 = set(nbunch2)
return (e for e in edges
if (e in nset1 and e in nset2)
or (e in nset1 and e 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