"""
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)