"""
Routines to find the boundary of a set of nodes.
Edge boundaries are edges that have only one end
in the set of nodes.
Node boundaries are nodes outside the set of nodes
that have an edge to a node in the set.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)"""
# Copyright (C) 2004-2008 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__all__=['edge_boundary','node_boundary']
def edge_boundary(G, nbunch1, nbunch2=None):
"""Return the edge boundary.
Edge boundaries are edges that have only one end
in the given set of nodes.
Parameters
-----------
G : graph
A networkx graph
nbunch1 : list, container
Interior node set
nbunch2 : list, container
Exterior node set. If None then it is set to all of the
nodes in G not in nbunch1.
Returns
-------
elist : list
List of edges
Notes
------
Nodes in nbunch1 and nbunch2 that are not in G are ignored.
nbunch1 and nbunch2 are usually meant to be disjoint,
but in the interest of speed and generality, that is
not required here.
"""
if nbunch2 is None: # Then nbunch2 is complement of nbunch1
nset1=set((n for n in nbunch1 if n in G))
return [(n1,n2) for n1 in nset1 for n2 in G[n1] \
if n2 not in nset1]
nset2=set(nbunch2)
return [(n1,n2) for n1 in nbunch1 if n1 in G for n2 in G[n1] \
if n2 in nset2]
def node_boundary(G, nbunch1, nbunch2=None):
"""Return the node boundary.
The node boundary is all nodes in the edge boundary of a given
set of nodes that are in the set.
Parameters
-----------
G : graph
A networkx graph
nbunch1 : list, container
Interior node set
nbunch2 : list, container
Exterior node set. If None then it is set to all of the
nodes in G not in nbunch1.
Returns
-------
nlist : list
List of nodes.
Notes
------
Nodes in nbunch1 and nbunch2 that are not in G are ignored.
nbunch1 and nbunch2 are usually meant to be disjoint,
but in the interest of speed and generality, that is
not required here.
"""
nset1=set(n for n in nbunch1 if n in G)
bdy=set()
for n1 in nset1:
bdy.update(G[n1])
bdy -= nset1
if nbunch2 is not None: # else nbunch2 is complement of nbunch1
bdy &= set(nbunch2)
return list(bdy)
|