## File: boundary.py

package info (click to toggle)
python-networkx 1.7~rc1-3
 `123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102` ``````""" 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 # Dan Schult # Pieter Swart # 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) ``````