00001 """ Methods for general graphs (XGraph) and digraphs (XDiGraph) allowing self-loops, multiple edges, arbitrary (hashable) objects as nodes and arbitrary objects associated with edges. The XGraph and XDiGraph classes are extensions of the Graph and DiGraph classes in base.py. The key difference is that an XGraph edge is a 3-tuple e=(n1,n2,x), representing an undirected edge between nodes n1 and n2 that is decorated with the object x. Here n1 and n2 are (hashable) node objects and x is a (not necessarily hashable) edge object. Since the edge is undirected, edge (n1,n2,x) is equivalent to edge (n2,n1,x). An XDiGraph edge is a similar 3-tuple e=(n1,n2,x), with the additional property of directedness. I.e. e=(n1,n2,x) is a directed edge from n1 to n2 decorated with the object x, and is not equivalent to the edge (n2,n1,x). Whether a graph or digraph allow self-loops or multiple edges is determined at the time of object instantiation via specifying the parameters selfloops=True/False and multiedges=True/False. For example, an empty XGraph is created with: >>> G=XGraph() which is equivalent to >>> G=XGraph(name="No Name", selfloops=False, multiedges=False) and similarly for XDiGraph. >>> G=XDiGraph(name="empty", multiedges=True) creates an empty digraph G with G.name="empty", that do not allow the addition of selfloops but do allow for multiple edges. XGraph and XDiGraph are implemented using a data structure based on an adjacency list implemented as a dictionary of dictionaries. The outer dictionary is keyed by node to an inner dictionary keyed by neighboring nodes to the edge data/labels/objects (which default to None to correspond the datastructure used in classes Graph and DiGraph). If multiedges=True, a list of edge data/labels/objects is stored as the value of the inner dictionary. This double dict structure mimics a sparse matrix and allows fast addition, deletion and lookup of nodes and neighbors in large graphs. The underlying datastructure should only be visible in this module. In all other modules, graph-like objects are manipulated solely via the methods defined here and not by acting directly on the datastructure. Similarities between XGraph and Graph XGraph and Graph differ fundamentally; XGraph edges are 3-tuples (n1,n2,x) and Graph edges are 2-tuples (n1,n2). XGraph inherits from the Graph class, and XDiGraph from the DiGraph class. They do share important similarities. 1. Edgeless graphs are the same in XGraph and Graph. For an edgeless graph, represented by G (member of the Graph class) and XG (member of XGraph class), there is no difference between the datastructures G.adj and XG.adj, other than in the ordering of the keys in the adj dict. 2. Basic graph construction code for G=Graph() will also work for G=XGraph(). In the Graph class, the simplest graph construction consists of a graph creation command G=Graph() followed by a list of graph construction commands, consisting of successive calls to the methods: G.add_node, G.add_nodes_from, G.add_edge, G.add_edges, G.add_path, G.add_cycle G.delete_node, G.delete_nodes_from, G.delete_edge, G.delete_edges_from with all edges specified as 2-tuples, If one replaces the graph creation command with G=XGraph(), and then apply the identical list of construction commands, the resulting XGraph object will be a simple graph G with identical datastructure G.adj. This property ensures reuse of code developed for graph generation in the Graph class. Notation The following shorthand is used throughout NetworkX documentation and code: (we use mathematical notation n,v,w,... to indicate a node, v=vertex=node). G,G1,G2,H,etc: Graphs n,n1,n2,u,v,v1,v2: nodes (vertices) nlist: a list of nodes (vertices) nbunch: a "bunch" of nodes (vertices). an nbunch is any iterable (non-string) container of nodes that is not itself a node of the graph. e=(n1,n2): an edge (a python "2-tuple"), also written n1-n2 (if undirected) and n1->n2 (if directed). Note that 3-tuple edges of the form (n1,n2,x) are used in the XGraph and XDiGraph classes. If G is an XGraph, then G.add_edge(n1,n2) will add the edge (n1,n2,None), and G.delete_edge(n1,n2) will attempt to delete the edge (n1,n2,None). In the case of multiple edges between nodes n1 and n2, one can use G.delete_multiedge(n1,n2) to delete all edges between n1 and n2. e=(n1,n2,x): an edge triple ("3-tuple") containing the two nodes connected and the edge data/label/object stored associated with the edge. The object x, or a list of objects (if multiedges=True), can be obtained using G.get_edge(n1,n2) elist: a list of edges (as 2- or 3-tuples) ebunch: a bunch of edges (as 2- or 3-tuples) an ebunch is any iterable (non-string) container of edge-tuples (either 2-tuples, 3-tuples or a mixture). (similar to nbunch, also see add_edge). Warning: - The ordering of objects within an arbitrary nbunch/ebunch can be machine-dependent. - Algorithms should treat an arbitrary nbunch/ebunch as once-through-and-exhausted iterable containers. - len(nbunch) and len(ebunch) need not be defined. Methods ======= The XGraph class provides rudimentary graph operations: Mutating Graph methods ---------------------- - G.add_node(n), G.add_nodes_from(nbunch) - G.delete_node(n), G.delete_nodes_from(nbunch) - G.add_edge(n1,n2), G.add_edge(n1,n2,x), G.add_edge(e), - G.add_edges_from(ebunch) - G.delete_edge(n1,n2), G.delete_edge(n1,n2,x), G.delete_edge(e), - G.delete_edges_from(ebunch) - G.delete_multiedge(n1,n2) - G.add_path(nlist) - G.add_cycle(nlist) - G.to_directed() - G.ban_multiedges() - G.allow_multiedges() - G.remove_all_multiedges() - G.ban_selfloops() - G.allow_selfloops() - G.remove_all_selfloops() - G.clear() - G.subgraph(nbunch, inplace=True) Non-mutating Graph methods -------------------------- - G.has_node(n) - G.nodes() - G.nodes_iter() - G.order() - G.neighbors(n), G.neighbors_iter(n) - G.has_edge(n1,n2,x), G.has_neighbor(n1,n2) - G.edges(), G.edges(nbunch) G.edges_iter(), G.edges_iter(nbunch, - G.size() - G.get_edge(n1,n2) - G.degree(), G.degree(n), G.degree(nbunch) - G.degree_iter(), G.degree_iter(n), G.degree_iter(nbunch) - G.number_of_selfloops() - G.nodes_with_selfloops() - G.selfloop_edges() - G.copy() - G.subgraph(nbunch) Examples ======== Create an empty graph structure (a "null graph") with no nodes and no edges >>> from networkx import * >>> G=XGraph() # default no self-loops, no multiple edges You can add nodes in the same way as the simple Graph class >>> G.add_nodes_from(xrange(100,110)) You can add edges as for simple Graph class, but with optional edge data/labels/objects. >>> G.add_edges_from([(1,2,0.776),(1,3,0.535)]) For graph coloring problems, one could use >>> G.add_edges_from([(1,2,"blue"),(1,3,"red")]) """ __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)""" # Copyright (C) 2004-2006 by # Aric Hagberg <hagberg@lanl.gov> # Dan Schult <dschult@colgate.edu> # Pieter Swart <swart@lanl.gov> # Distributed under the terms of the GNU Lesser General Public License # http://www.gnu.org/copyleft/lesser.html # from networkx.base import Graph, DiGraph, NetworkXException, NetworkXError import networkx.convert as convert 00217 class XGraph(Graph): """A class implementing general undirected graphs, allowing (optional) self-loops, multiple edges, arbitrary (hashable) objects as nodes and arbitrary objects associated with edges. An XGraph edge is specified by a 3-tuple e=(n1,n2,x), where n1 and n2 are nodes (hashable objects) and x is an arbitrary (and not necessarily unique) object associated with that edge. >>> G=XGraph() creates an empty simple and undirected graph (no self-loops or multiple edges allowed). It is equivalent to the expression: >>> G=XGraph(name="No Name",selfloops=False,multiedges=False) >>> G=XGraph(name="empty",multiedges=True) creates an empty graph with G.name="empty", that do not allow the addition of self-loops but do allow for multiple edges. See also the XDiGraph class below. """ 00245 def __init__(self,data=None,**kwds): """Initialize XGraph. Optional arguments:: name: graph name (default="No Name") selfloops: if True selfloops are allowed (default=False) multiedges: if True multiple edges are allowed (default=False) """ self.name=kwds.get("name","No Name") self.selfloops=kwds.get("selfloops",False) # no self-loops self.multiedges=kwds.get("multiedges",False) # no multiedges # dna is a dictionary attached to each graph and used to store # information about the graph structure. In this version the # dna is provided as a user-defined variable and should not be # relied on. self.dna={} self.dna["datastructure"]="xgraph_dict_of_dicts" self.adj={} # adjacency list if data is not None: self=convert.from_whatever(data,create_using=self) 00271 def __getitem__(self,n): """Return the neighbors of node n as a list. This provides graph G the natural property that G[n] returns the neighbors of G. """ return self.neighbors(n) 00280 def add_edge(self, n1, n2=None, x=None): """Add a single edge to the graph. Can be called as G.add_edge(n1,n2,x) or as G.add_edge(e), where e=(n1,n2,x). n1,n2 are node objects, and are added to the Graph if not already present. Nodes must be hashable Python objects (except None). x is an arbitrary (not necessarily hashable) object associated with this edge. It can be used to associate one or more: labels, data records, weights or any arbirary objects to edges. The default is the Python None. For example, if the graph G was created with >>> G=XGraph() then G.add_edge(1,2,"blue") will add the edge (1,2,"blue"). If G.multiedges=False, then a subsequent G.add_edge(1,2,"red") will change the above edge (1,2,"blue") into the edge (1,2,"red"). If G.multiedges=True, then two successive calls to G.add_edge(1,2,"red") will result in 2 edges of the form (1,2,"red") that can not be distinguished from one another. G.add_edge(1,2,"green") will add both edges (1,2,X) and (2,1,X). If self.selfloops=False, then calling add_edge(n1,n1,x) will have no effect on the Graph. Objects associated to an edge can be retrieved using edges(), edge_iter(), or get_edge(). """ if n2 is None: # add_edge was called as add_edge(e), with e=(n1,n2,x) if len(n1)==3: # case e=(n1,n2,x) n1,n2,x=n1 else: # assume e=(n1,n2) n1,n2=n1 # x=None # if edge exists, quietly return if multiple edges are not allowed if not self.multiedges and self.has_edge(n1,n2,x): return # add nodes if n1 not in self.adj: self.adj[n1]={} if n2 not in self.adj: self.adj[n2]={} # self loop? quietly return if not allowed if not self.selfloops and n1==n2: return if self.multiedges: # add x to the end of the list of objects # that defines the edges between n1 and n2 self.adj[n1][n2]=self.adj[n1].get(n2,[])+ [x] if n1!=n2: self.adj[n2][n1]=self.adj[n2].get(n1,[])+ [x] else: # x is the new object assigned to single edge between n1 and n2 self.adj[n1][n2]=x if n1!=n2: self.adj[n2][n1]=x # a copy would be required to avoid # modifying both at the same time # when doing a delete_edge 00349 def add_edges_from(self, ebunch): """Add multiple edges to the graph. ebunch: Container of edges. Each edge must be a 3-tuple (n1,n2,x) or a 2-tuple (n1,n2). See add_edge documentation. The container must be iterable or an iterator. It is iterated over once. """ for e in ebunch: self.add_edge(e) 00362 def has_edge(self, n1, n2=None, x=None): """Return True if graph contains edge (n1,n2,x). Can be called as G.has_edge(n1,n2,x) or as G.has_edge(e), where e=(n1,n2,x). If x is unspecified or None, i.e. if called with an edge of the form e=(n1,n2), then return True if there exists ANY edge between n1 and n2 (equivalent to has_neighbor(n1,n2)) """ if n2 is None: # has_edge was called as has_edge(e) if len(n1)==3: #case e=(n1,n2,x) n1,n2,x=n1 else: # assume e=(n1,n2) n1,n2=n1 return self.has_neighbor(n1,n2) else: if x is None: # has_edge was called as has_edge(n1,n2) # return True if there exists ANY # edge between n1 and n2 return self.has_neighbor(n1,n2) # case where x is specified if self.multiedges: return (self.adj.has_key(n1) and self.adj[n1].has_key(n2) and x in self.adj[n1][n2]) else: return (self.adj.has_key(n1) and self.adj[n1].has_key(n2) and x==self.adj[n1][n2]) 00397 def has_neighbor(self, n1, n2): """Return True if node n1 has neighbor n2. Note that this returns True if there exists ANY edge (n1,n2,x) for some x. """ return (self.adj.has_key(n1) and self.adj[n1].has_key(n2)) 00408 def neighbors_iter(self, n): """Return an iterator of nodes connected to node n. Returns the same data as edges(n) but in a different format. """ if n not in self: raise NetworkXError, "node %s not in graph"%n for (u,v,d) in self.edges_iter(n): yield v 00419 def neighbors(self, n): """Return a list of nodes connected to node n. Returns the same data as edges(n) but in a different format. """ return list(self.neighbors_iter(n)) 00427 def get_edge(self, n1, n2): """Return the objects associated with each edge between n1 and n2. If multiedges=False, a single object is returned. If multiedges=True, a list of objects is returned. If no edge exists, raise an exception. """ try: result = self.adj[n1][n2] # raises KeyError if edge not found except KeyError: raise NetworkXError, "no edge (%s,%s) in graph"%(n1,n2) if self.multiedges: return result[:] # return a copy so user can't mess up list return result 00443 def edges_iter(self, nbunch=None): """Return iterator that iterates once over each edge adjacent to nodes in nbunch, or over all nodes in graph if nbunch=None. See add_node for definition of nbunch. Nodes in nbunch that are not in the graph will be (quietly) ignored. """ # prepare nbunch if nbunch is None: # include all nodes via iterator bunch=self.nodes_iter() elif nbunch in self: # if nbunch is a single node bunch=[nbunch] else: # if nbunch is a sequence of nodes try: bunch=[n for n in nbunch if n in self] except TypeError: raise NetworkXError, "nbunch is not a node or a sequence of nodes." # nbunch ready seen={} # helper dict used to avoid duplicate edges if self.multiedges: for n1 in bunch: for n2,elist in self.adj[n1].iteritems(): if n2 not in seen: for data in elist: yield (n1,n2,data) seen[n1]=1 else: for n1 in bunch: for n2,data in self.adj[n1].iteritems(): if n2 not in seen: yield (n1,n2,data) seen[n1]=1 del(seen) # clear copy of temp dictionary # iterators can remain after they finish returning values. 00479 def edges(self, nbunch=None): """Return a list of all edges that originate at a node in nbunch, or a list of all edges if nbunch=None. See add_node for definition of nbunch. Nodes in nbunch that are not in the graph will be (quietly) ignored. For digraphs, edges=out_edges """ return list(self.edges_iter(nbunch)) 00492 def delete_multiedge(self, n1, n2): """ Delete all edges between nodes n1 and n2. When there is only a single edge allowed between nodes (multiedges=False), this just calls delete_edge(n1,n2) otherwise (multiedges=True) all edges between n1 and n2 are deleted. """ if self.multiedges: for x in self.get_edge(n1, n2): self.delete_edge(n1, n2, x) else: self.delete_edge(n1, n2) return 00507 def delete_edge(self, n1, n2=None, x=None): """Delete the edge (n1,n2,x) from the graph. Can be called either as >>> G.delete_edge(n1,n2,x) or >>> G.delete_edge(e) where e=(n1,n2,x). The default edge data is x=None If called with an edge e=(n1,n2), or as G.delete_edge(n1,n2) then the edge (n1,n2,None) will be deleted. If the edge does not exist, do nothing. To delete *all* edges between n1 and n2 use >>> G.delete_multiedges(n1,n2) """ if n2 is None: # was called as delete_edge(e) if len(n1)==3: # case e=(n1,n2,x) n1,n2,x=n1 else: # assume e=(n1,n2), x unspecified, set to None n1,n2=n1 # x=None if self.multiedges: if (self.adj.has_key(n1) and self.adj[n1].has_key(n2) and x in self.adj[n1][n2]): # if (n1,n2,x) is an edge; self.adj[n1][n2].remove(x) # remove the edge item from list if n1!=n2: # and if not self loop self.adj[n2][n1].remove(x) # remove n2->n1 entry if len(self.adj[n1][n2])==0: # if last edge between n1 and n2 del self.adj[n1][n2] # was deleted, remove all trace if n1!=n2: # and if not self loop del self.adj[n2][n1] # remove n2->n1 entry else: # delete single edge if self.has_neighbor(n1,n2): del self.adj[n1][n2] if n1!=n2: del self.adj[n2][n1] return 00553 def delete_edges_from(self, ebunch): """Delete edges in ebunch from the graph. ebunch: Container of edges. Each edge must be a 3-tuple (n1,n2,x) or a 2-tuple (n1,n2). In the latter case all edges between n1 and n2 will be deleted. See delete_edge. The container must be iterable or an iterator, and is iterated over once. Edges that are not in the graph are ignored. """ for e in ebunch: # the function-call-in-a-loop cost can be avoided by pasting # in the code from delete_edge, do we have a good reason ? self.delete_edge(e) 00569 def degree(self, nbunch=None, with_labels=False): """Return degree of single node or of nbunch of nodes. If nbunch is omitted or nbunch=None, then return degrees of *all* nodes. The degree of a node is the number of edges attached to that node. Can be called in three ways: - G.degree(n): return the degree of node n - G.degree(nbunch): return a list of values, one for each n in nbunch (nbunch is any iterable container of nodes.) - G.degree(): same as nbunch = all nodes in graph. Always return a list. If with_labels==True, then return a dict that maps each n in nbunch to degree(n). Any nodes in nbunch that are not in the graph are (quietly) ignored. """ # prepare nbunch if nbunch is None: # include all nodes via iterator bunch=self.nodes_iter() elif nbunch in self: # if nbunch is a single node bunch=[nbunch] else: # if nbunch is a sequence of nodes try: bunch=[n for n in nbunch if n in self] except TypeError: raise NetworkXError, "nbunch is not a node or a sequence of nodes." # nbunch ready d={} if self.multiedges: for n in bunch: deg = sum([len(e) for e in self.adj[n].itervalues()]) if self.adj[n].has_key(n) and self.selfloops: deg+= len(self.adj[n][n]) # double count self-loops d[n]=deg else: for n in bunch: deg=len(self.adj[n]) deg+= self.adj[n].has_key(n) # double count self-loop d[n]=deg if with_labels: return d # return the dict elif nbunch in self: return d.values()[0] # single node, so single value return d.values() # return a list 00618 def degree_iter(self,nbunch=None,with_labels=False): """This is the degree() method returned in iterator form. If with_labels=True, iterator yields 2-tuples of form (n,degree(n)) (like iteritems() on a dict.) """ # prepare nbunch if nbunch is None: # include all nodes via iterator bunch=self.nodes_iter() elif nbunch in self: # if nbunch is a single node bunch=[nbunch] else: # if nbunch is a sequence of nodes try: bunch=[n for n in nbunch if n in self] except TypeError: raise NetworkXError, "nbunch is not a node or a sequence of nodes." # nbunch ready if self.multiedges: for n in bunch: deg = sum([len(e) for e in self.adj[n].itervalues()]) if self.selfloops and self.adj[n].has_key(n): deg+= len(self.adj[n][n]) # double count self-loops if with_labels: yield (n,deg) # tuple (n,degree) else: yield deg else: for n in bunch: deg=len(self.adj[n]) deg+= self.adj[n].has_key(n) # double count self-loop if with_labels: yield (n,deg) # tuple (n,degree) else: yield deg 00652 def number_of_edges(self): """Return number of edges""" return sum(self.degree_iter())/2 # def size(self): # """Return the size of a graph = number of edges. """ # return self.number_of_edges() 00660 def copy(self): """Return a (shallow) copy of the graph. Return a new XGraph with same name and same attributes for selfloop and multiededges. Each node and each edge in original graph are added to the copy. """ H=self.__class__(multiedges=self.multiedges,selfloops=self.selfloops) H.name=self.name H.dna=self.dna.copy() for n in self: H.add_node(n) for e in self.edges_iter(): H.add_edge(e) return H 00677 def to_directed(self): """Return a directed representation of the XGraph G. A new XDigraph is returned with the same name, same nodes and with each edge (u,v,x) replaced by two directed edges (u,v,x) and (v,u,x). """ H=XDiGraph(selfloops=self.selfloops,multiedges=self.multiedges) H.name=self.name H.dna=self.dna.copy() for n in self: H.add_node(n) for e in self.edges_iter(): H.add_edge(e[0],e[1],e[2]) H.add_edge(e[1],e[0],e[2]) return H 00695 def nodes_with_selfloops(self): """Return list of all nodes having self-loops.""" if not self.selfloops: return [] else: return [n for n in self if self.adj[n].has_key(n)] 00702 def selfloop_edges(self): """Return all edges that are self-loops.""" nlist=self.nodes_with_selfloops() loops=[] for n in nlist: if self.multiedges: for x in self.adj[n][n]: loops.append((n,n,x)) else: loops.append((n,n,self.adj[n][n])) return loops 00714 def number_of_selfloops(self): """Return number of self-loops in graph.""" return len(self.selfloop_edges()) 00718 def allow_selfloops(self): """Henceforth allow addition of self-loops (edges from a node to itself). This doesn't change the graph structure, only what you can do to it. """ self.selfloops=True 00726 def remove_all_selfloops(self): """Remove self-loops from the graph (edges from a node to itself).""" if not self.selfloops: # nothing to do return for n in self.adj: if self.adj[n].has_key(n): del self.adj[n][n] 00735 def ban_selfloops(self): """Remove self-loops from the graph and henceforth do not allow their creation. """ self.remove_all_selfloops() self.selfloops=False 00743 def allow_multiedges(self): """Henceforth allow addition of multiedges (more than one edge between two nodes). Warning: This causes all edge data to be converted to lists. """ if self.multiedges: return # already multiedges self.multiedges=True for v in self.adj: for (u,edgedata) in self.adj[v].iteritems(): self.adj[v][u]=[edgedata] 00755 def remove_all_multiedges(self): # FIXME, write tests """Remove multiedges retaining the data from the first edge""" if not self.multiedges: # nothing to do return for v in self.adj: for (u,edgedata) in self.adj[v].iteritems(): if len(edgedata)>1: self.adj[v][u]=[edgedata[0]] 00765 def ban_multiedges(self): """Remove multiedges retaining the data from the first edge. Henceforth do not allow multiedges. """ if not self.multiedges: # nothing to do return self.multiedges=False for v in self.adj: for (u,edgedata) in self.adj[v].iteritems(): self.adj[v][u]=edgedata[0] 00776 def subgraph(self, nbunch, inplace=False, create_using=None): """Return the subgraph induced on nodes in nbunch. nbunch: either a singleton node, a string (which is treated as a singleton node), or any non-string iterable or iterator. (It can be an iterable or an iterator, e.g. a list, set, graph, file, numeric array, etc.) Setting inplace=True will return induced subgraph in original graph by deleting nodes not in nbunch. It overrides any setting of create_using. WARNING: specifying inplace=True makes it easy to destroy the graph. Unless otherwise specified, return a new graph of the same type as self. Use (optional) create_using=R to return the resulting subgraph in R. R can be an existing graph-like object (to be emptied) or R can be a call to a graph object, e.g. create_using=DiGraph(). See documentation for empty_graph() Note: use subgraph(G) rather than G.subgraph() to access the more general subgraph() function from the operators module. """ bunch=self.prepare_nbunch(nbunch) # WARNING: setting inplace=True destroys the graph. if inplace: # demolish all nodes (and attached edges) not in nbunch # override any setting of create_using bunch=dict.fromkeys(bunch) # make a dict self.delete_nodes_from([n for n in self if n not in bunch]) self.name="Subgraph of (%s)"%(self.name) return self # Create new graph if create_using is None: # return a Graph object of the same type as current graph # subgraph inherits multiedges and selfloops settings H=self.__class__(multiedges=self.multiedges, selfloops=self.selfloops) else: # Recreate subgraph with create_using. # Currently create_using must be an XGraph type object # or a multi-edge list will be copied as a single edge H=create_using H.clear() H.name="Subgraph of (%s)"%(self.name) H.add_nodes_from(bunch) # add edges H_adj=H.adj # store in local variables self_adj=self.adj if self.multiedges: for n in H: # create neighbor dict with copy of data list from self H_adj[n]=dict([(u,d[:]) for u,d in self_adj[n].iteritems() if u in H_adj]) else: # no multiedges for n in H: # create neighbor dict with edge data from self H_adj[n]=dict([(u,d) for u,d in self_adj[n].iteritems() if u in H_adj]) return H # End of basic operations (under the hood and close to the datastructure) # The following remaining Graph methods use the above methods and not the # datastructure directly 00844 def add_path(self, nlist): """Add the path through the nodes in nlist to graph""" nfrom = nlist.pop(0) while len(nlist) > 0: nto=nlist.pop(0) self.add_edge(nfrom,nto) nfrom=nto 00852 def add_cycle(self, nlist): """Add the cycle of nodes in nlist to graph""" self.add_path(nlist+[nlist[0]]) # wrap first element 00856 class XDiGraph(DiGraph): """ A class implementing general digraphs, allowing (optional) self-loops, (optional) multiple edges, arbitrary (hashable) objects as nodes, and arbitrary objects associated with edges. As in XGraph, an XDiGraph edge is uniquely specified by a 3-tuple e=(n1,n2,x), where n1 and n2 are (hashable) objects (nodes) and x is an arbitrary (and not necessarily unique) object associated with that edge. See the documentation of XGraph for the use of the optional parameters selfloops (defaults is False) and multiedges (default is False). XDiGraph inherits from DiGraph, with all purely node-specific methods identical to those of DiGraph. XDiGraph edges are identical to XGraph edges, except that they are directed rather than undirected. XDiGraph replaces the following DiGraph methods: - __init__: read multiedges and selfloops kwds. - add_edge - add_edges_from - delete_edge - delete_edges_from - delete_multiedge - has_edge - edges_iter - degree_iter - degree - copy - clear - subgraph - is_directed - to_directed XDiGraph also adds the following methods to those of DiGraph: - allow_selfloops - remove_all_selfloops - ban_selfloops - allow_multiedges - ban_multiedges - remove_all_multiedges XDigraph adds the following methods to those of XGraph: - has_successor - successors - successors_iter - has_predecessor - predecessors - predecessors_iter - out_degree - out_degree_iter - in_degree - in_degree_iter - to_undirected - is_directed """ # XDiGraph, like DiGraph, uses two adjacency lists: # predecessors of node n are stored in the dict # self.pred successors of node n are stored in the # dict self.succ=self.adj # # For each edge (n1,n2,x) in self.succ there exists a corresponding edge # (n2,n1,x) in self.pred 00925 def __init__(self,data=None,**kwds): """Initialize XDiGraph. Optional arguments:: name: digraph name (default="No Name") selfloops: if True then selfloops are allowed (default=False) multiedges: if True then multiple edges are allowed (default=False) """ self.name=kwds.get("name","No Name") self.selfloops=kwds.get("selfloops",False) # no self-loops self.multiedges=kwds.get("multiedges",False) # no multiedges # dna is a dictionary attached to each graph and used to store # information about the graph structure. In this version the # dna is provided as a user-defined variable and should not be # relied on. self.dna={} self.dna["datastructure"]="xgraph_dict_of_dicts" self.adj={} # adjacency list self.pred={} # predecessor self.succ=self.adj # successor is same as adj if data is not None: self=convert.from_whatever(data,create_using=self) 00955 def add_edge(self, n1, n2=None, x=None): """Add a single directed edge to the digraph. Can be called as G.add_edge(n1,n2,x) or as G.add_edge(e), where e=(n1,n2,x). If called as G.add_edge(n1,n2) or G.add_edge(e), with e=(n1,n2), then this is interpreted as adding the edge (n1,n2,None) to be compatible with the Graph and DiGraph classes. n1,n2 are node objects, and are added to the Graph if not already present. Nodes must be hashable Python objects (except None). x is an arbitrary (not necessarily hashable) object associated with this edge. It can be used to associate one or more, labels, data records, weights or any arbirary objects to edges. The default is the Python None. For example, if the graph G was created with >>> G=XDiGraph() then G.add_edge(1,2,"blue") will add the directed edge (1,2,"blue"). If G.multiedges=False, then a subsequent G.add_edge(1,2,"red") will change the above edge (1,2,"blue") into the edge (1,2,"red"). On the other hand, if G.multiedges=True, then two successive calls to G.add_edge(1,2,"red") will result in 2 edges of the form (1,2,"red") that can not be distinguished from one another. If self.selfloops=False, then any attempt to create a self-loop with add_edge(n1,n1,x) will have no effect on the digraph and will not elicit a warning. Objects imbedded in the edges from n1 to n2 (if any), can be retrieved using get_edge(n1,n2), or calling edges(n1) or edge_iter(n1) to return all edges attached to n1. """ if n2 is None: # add_edge was called as add_edge(e), with e a tuple if len(n1)==3: #case e=(n1,n2,x) n1,n2,x=n1 else: # assume e=(n1,n2) n1,n2=n1 # x=None # if edge exists, quietly return if multiple edges are not allowed if not self.multiedges and self.has_edge(n1,n2,x): return # add nodes if n1 not in self.succ: self.succ[n1]={} if n1 not in self.pred: self.pred[n1]={} if n2 not in self.succ: self.succ[n2]={} if n2 not in self.pred: self.pred[n2]={} # self loop? quietly return if not allowed if not self.selfloops and n1==n2: return if self.multiedges: # append x to the end of the list of objects # that defines the edges between n1 and n2 self.succ[n1][n2]=self.succ[n1].get(n2,[])+ [x] self.pred[n2][n1]=self.pred[n2].get(n1,[])+ [x] else: # x is the new object assigned to single edge between n1 and n2 self.succ[n1][n2]=x self.pred[n2][n1]=x # note that the same object is referred to # from both succ and pred 01030 def add_edges_from(self, ebunch): """Add multiple directed edges to the digraph. ebunch: Container of edges. Each edge e in container will be added using add_edge(e). See add_edge documentation. The container must be iterable or an iterator. It is iterated over once. """ for e in ebunch: # the function-call-in-a-loop cost can be avoided by pasting # in the code from add_edge, do we have a good reason ? self.add_edge(e) 01042 def has_edge(self, n1, n2=None, x=None): """Return True if digraph contains directed edge (n1,n2,x). Can be called as G.has_edge(n1,n2,x) or as G.has_edge(e), where e=(n1,n2,x). If x is unspecified, i.e. if called with an edge of the form e=(n1,n2), then return True if there exists ANY edge from n1 to n2 (equivalent to has_successor(n1,n2)). """ # parse args if n2 is None: # has_edge was called as has_edge(e) if len(n1)==3: # case e=(n1,n2,x) n1,n2,x=n1 else: # case=(n1,n2) n1,n2=n1 # return True if there exists ANY edge n1->n2 return self.has_successor(n1,n2) else: if x is None: # has_edge was called as has_edge(n1,n2) # return True if there exists ANY edge n1->n2 return self.has_successor(n1,n2) # case where x is specified if self.multiedges: return (self.succ.has_key(n1) and self.succ[n1].has_key(n2) and x in self.succ[n1][n2]) else: return (self.succ.has_key(n1) and self.succ[n1].has_key(n2) and x==self.succ[n1][n2]) 01076 def has_successor(self, n1, n2): """Return True if node n1 has a successor n2. Return True if there exists ANY edge (n1,n2,x) for some x. """ return (self.succ.has_key(n1) and self.succ[n1].has_key(n2)) 01085 def has_predecessor(self, n1, n2): """Return True if node n1 has a predecessor n2. Return True if there exists ANY edge (n2,n1,x) for some x. """ return (self.pred.has_key(n1) and self.pred[n1].has_key(n2)) 01095 def get_edge(self, n1, n2): """Return the objects associated with each edge between n1 and n2. If multiedges=False, a single object is returned. If multiedges=True, a list of objects is returned. If no edge exists, raise an exception. """ try: result = self.adj[n1][n2] # raises KeyError if edge not found except KeyError: raise NetworkXError, "no edge (%s,%s) in graph"%(n1,n2) if self.multiedges: return result[:] # return a copy so user can't mess up list return result 01112 def delete_multiedge(self, n1, n2): """ Delete all edges between nodes n1 and n2. When there is only a single edge allowed between nodes (multiedges=False), this just calls delete_edge(n1,n2), otherwise (multiedges=True) all edges between n1 and n2 are deleted. """ if self.multiedges: for x in self.get_edge(n1,n2): self.delete_edge(n1,n2,x) else: self.delete_edge(n1,n2) return 01127 def delete_edge(self, n1, n2=None, x=None, all=False): """Delete the directed edge (n1,n2,x) from the graph. Can be called either as >>> G.delete_edge(n1,n2,x) or as >>> G.delete_edge(e) where e=(n1,n2,x). If called with an edge e=(n1,n2), or as G.delete_edge(n1,n2) then the edge (n1,n2,None) will be deleted. If the edge does not exist, do nothing. To delete *all* edges between n1 and n2 use >>> G.delete_multiedges(n1,n2) """ if n2 is None: # was called as delete_edge(e) if len(n1)==3: #case e=(n1,n2,x) n1,n2,x=n1 else: # assume e=(n1,n2) n1,n2=n1 # x=None if self.multiedges: # multiedges are stored as a list if (self.succ.has_key(n1) and self.succ[n1].has_key(n2) and x in self.succ[n1][n2]): self.succ[n1][n2].remove(x) # remove the edge item from list self.pred[n2][n1].remove(x) if len(self.succ[n1][n2])==0: # if last edge between n1 and n2 del self.succ[n1][n2] # was deleted, remove all trace del self.pred[n2][n1] else: # delete single edge if self.has_successor(n1,n2): del self.succ[n1][n2] del self.pred[n2][n1] return 01166 def delete_edges_from(self, ebunch): """Delete edges in ebunch from the graph. ebunch: Container of edges. Each edge must be a 3-tuple (n1,n2,x) or a 2-tuple (n1,n2). The container must be iterable or an iterator, and is iterated over once. Edges that are not in the graph are ignored. """ for e in ebunch: self.delete_edge(e) 01179 def out_edges_iter(self, nbunch=None): """Return iterator that iterates once over each edge pointing out of nodes in nbunch, or over all edges in digraph if no nodes are specified. See add_node for definition of nbunch. Nodes in nbunch that are not in the graph will be (quietly) ignored. """ # prepare nbunch if nbunch is None: # include all nodes via iterator bunch=self.nodes_iter() elif nbunch in self: # if nbunch is a single node bunch=[nbunch] else: # if nbunch is a sequence of nodes try: bunch=[n for n in nbunch if n in self] except TypeError: raise NetworkXError, "nbunch is not a node or a sequence of nodes." # nbunch ready if self.multiedges: for n1 in bunch: for n2,elist in self.succ[n1].iteritems(): for data in elist: yield (n1,n2,data) else: for n1 in bunch: for n2,data in self.succ[n1].iteritems(): yield (n1,n2,data) 01209 def in_edges_iter(self, nbunch=None): """Return iterator that iterates once over each edge pointing in to nodes in nbunch, or over all edges in digraph if no nodes are specified. See add_node for definition of nbunch. Nodes in nbunch that are not in the graph will be (quietly) ignored. """ # prepare nbunch if nbunch is None: # include all nodes via iterator bunch=self.nodes_iter() elif nbunch in self: # if nbunch is a single node bunch=[nbunch] else: # if nbunch is a sequence of nodes try: bunch=[n for n in nbunch if n in self] except TypeError: raise NetworkXError, "nbunch is not a node or a sequence of nodes." # nbunch ready if self.multiedges: for n1 in bunch: for n2,elist in self.pred[n1].iteritems(): for data in elist: yield (n2,n1,data) else: for n1 in bunch: for n2,data in self.pred[n1].iteritems(): yield (n2,n1,data) 01239 def out_edges(self, nbunch=None): """Return a list of all edges that point out of nodes in nbunch, or a list of all edges if nbunch=None. See add_node for definition of nbunch. Nodes in nbunch that are not in the graph will be (quietly) ignored. """ return list(self.out_edges_iter(nbunch)) 01251 def in_edges(self, nbunch=None): """Return a list of all edges that point in to nodes in nbunch, or a list of all edges if nbunch=None. See add_node for definition of nbunch. Nodes in nbunch that are not in the graph will be (quietly) ignored. """ return list(self.in_edges_iter(nbunch)) edges_iter=out_edges_iter edges=out_edges 01267 def successors_iter(self, n): """Return an iterator of nodes pointing out of node n. Returns the same data as out_edges(n) but in a different format. """ if n not in self: raise NetworkXError, "node %s not in graph"%n for (u,v,d) in self.out_edges_iter(n): yield v 01278 def predecessors_iter(self, n): """Return an iterator of nodes pointing in to node n. Returns the same data as out_edges(n) but in a different format. """ if n not in self: raise NetworkXError, "node %s not in graph"%n for (u,v,d) in self.in_edges_iter(n): yield u 01289 def in_degree(self, nbunch=None, with_labels=False): """Return the in-degree of single node or of nbunch of nodes. If nbunch is omitted or nbunch=None, then return in-degrees of *all* nodes. If with_labels=True, then return a dict that maps each n in nbunch to in_degree(n). Any nodes in nbunch that are not in the graph are (quietly) ignored. """ # prepare nbunch if nbunch is None: # include all nodes via iterator bunch=self.nodes_iter() elif nbunch in self: # if nbunch is a single node bunch=[nbunch] else: # if nbunch is a sequence of nodes try: bunch=[n for n in nbunch if n in self] except TypeError: raise NetworkXError, "nbunch is not a node or a sequence of nodes." # nbunch ready d={} if self.multiedges: for n in bunch: d[n] = sum([len(edge) for edge in self.pred[n].itervalues()]) else: for n in bunch: d[n]=len(self.pred[n]) if with_labels: return d # return the dict elif nbunch in self: return d.values()[0] # single node, so single value return d.values() # return a list 01323 def out_degree(self, nbunch=None, with_labels=False): """Return the out-degree of single node or of nbunch of nodes. If nbunch is omitted or nbunch=None, then return out-degrees of *all* nodes. If with_labels=True, then return a dict that maps each n in nbunch to out_degree(n). Any nodes in nbunch that are not in the graph are (quietly) ignored. """ # prepare nbunch if nbunch is None: # include all nodes via iterator bunch=self.nodes_iter() elif nbunch in self: # if nbunch is a single node bunch=[nbunch] else: # if nbunch is a sequence of nodes try: bunch=[n for n in nbunch if n in self] except TypeError: raise NetworkXError, "nbunch is not a node or a sequence of nodes." # nbunch ready d={} if self.multiedges: for n in bunch: d[n] = sum([len(edge) for edge in self.succ[n].itervalues()]) else: for n in bunch: d[n]=len(self.succ[n]) if with_labels: return d # return the dict elif nbunch in self: return d.values()[0] # single node, so single value return d.values() # return a list 01357 def degree(self, nbunch=None, with_labels=False): """Return the out-degree of single node or of nbunch of nodes. If nbunch is omitted or nbunch=None, then return out-degrees of *all* nodes. If with_labels=True, then return a dict that maps each n in nbunch to out_degree(n). Any nodes in nbunch that are not in the graph are (quietly) ignored. """ # prepare nbunch if nbunch is None: # include all nodes via iterator bunch=self.nodes_iter() elif nbunch in self: # if nbunch is a single node bunch=[nbunch] else: # if nbunch is a sequence of nodes try: bunch=[n for n in nbunch if n in self] except TypeError: raise NetworkXError, "nbunch is not a node or a sequence of nodes." # nbunch ready d={} if self.multiedges: for n in bunch: d[n]=sum([len(e) for e in self.succ[n].itervalues()]) + \ sum([len(e) for e in self.pred[n].itervalues()]) else: for n in bunch: d[n]=len(self.succ[n])+len(self.pred[n]) if with_labels: return d # return the dict elif nbunch in self: return d.values()[0] # single node, so single value return d.values() # return a list 01391 def nodes_with_selfloops(self): """Return list of all nodes having self-loops.""" if not self.selfloops: return [] else: # only need to do this for succ return [n for n in self if self.succ[n].has_key(n)] 01399 def selfloop_edges(self): """Return all edges that are self-loops.""" nlist=self.nodes_with_selfloops() loops=[] for n in nlist: if self.multiedges: for x in self.succ[n][n]: loops.append((n,n,x)) else: loops.append((n,n,self.succ[n][n])) return loops 01411 def number_of_selfloops(self): """Return number of self-loops in graph.""" return len(self.selfloop_edges()) 01415 def allow_selfloops(self): """Henceforth allow addition of self-loops (edges from a node to itself). This doesn't change the graph structure, only what you can do to it. """ self.selfloops=True 01423 def remove_all_selfloops(self): """Remove self-loops from the graph (edges from a node to itself).""" for n in self.succ: if self.succ[n].has_key(n): del self.succ[n][n] del self.pred[n][n] 01430 def ban_selfloops(self): """Remove self-loops from the graph and henceforth do not allow their creation. """ self.remove_all_selfloops() self.selfloops=False 01438 def allow_multiedges(self): """Henceforth allow addition of multiedges (more than one edge between two nodes). Warning: This causes all edge data to be converted to lists. """ if self.multiedges: return # already multiedges self.multiedges=True for v in self.succ: for (u,edgedata) in self.succ[v].iteritems(): self.succ[v][u]=[edgedata] self.pred[u][v]=[edgedata] 01451 def remove_all_multiedges(self): # FIXME, write tests """Remove multiedges retaining the data from the first edge""" if not self.multiedges: # nothing to do return for v in self.succ: for (u,edgedata) in self.succ[v].iteritems(): if len(edgedata)>1: self.succ[v][u]=[edgedata[0]] self.pred[u][v]=[edgedata[0]] 01462 def ban_multiedges(self): """Remove multiedges retaining the data from the first edge. Henceforth do not allow multiedges. """ if not self.multiedges: # nothing to do return self.multiedges=False for v in self.succ: for (u,edgedata) in self.succ[v].iteritems(): self.succ[v][u]=edgedata[0] self.pred[u][v]=edgedata[0] 01474 def subgraph(self, nbunch, inplace=False, create_using=None): """Return the subgraph induced on nodes in nbunch. nbunch: can be a singleton node, a string (which is treated as a singleton node), or any iterable container of of nodes. (It can be an iterable or an iterator, e.g. a list, set, graph, file, numeric array, etc.) Setting inplace=True will return induced subgraph in original graph by deleting nodes not in nbunch. It overrides any setting of create_using. WARNING: specifying inplace=True makes it easy to destroy the graph. Unless otherwise specified, return a new graph of the same type as self. Use (optional) create_using=R to return the resulting subgraph in R. R can be an existing graph-like object (to be emptied) or R can be a call to a graph object, e.g. create_using=DiGraph(). See documentation for empty_graph() Note: use subgraph(G) rather than G.subgraph() to access the more general subgraph() function from the operators module. """ bunch=self.prepare_nbunch(nbunch) # WARNING: setting inplace=True destroys the graph. if inplace: # demolish all nodes (and attached edges) not in nbunch # override any setting of create_using bunch=dict.fromkeys(bunch) # make a dict self.delete_nodes_from([n for n in self if n not in bunch]) self.name="Subgraph of (%s)"%(self.name) return self # create new graph if create_using is None: # return a Graph object of the same type as current graph # subgraph inherits multiedges and selfloops settings H=self.__class__(multiedges=self.multiedges, selfloops=self.selfloops) else: # Recreate subgraph with create_using. # Currently create_using must be an XGraph type object # or a multi-edge list will be copied as a single edge H=create_using H.clear() H.name="Subgraph of (%s)"%(self.name) H.add_nodes_from(bunch) # add edges H_succ=H.succ # store in local variables H_pred=H.pred self_succ=self.succ self_pred=self.pred if self.multiedges: for n in H: # create dicts with copies of edge data list from self H_succ[n]=dict([(u,d[:]) for u,d in self_succ[n].iteritems() if u in H_succ]) H_pred[n]=dict([(u,d[:]) for u,d in self_pred[n].iteritems() if u in H_pred]) else: # no multiedges for n in H: # create dicts with edge data from self H_succ[n]=dict([(u,d) for u,d in self_succ[n].iteritems() if u in H_succ]) H_pred[n]=dict([(u,d) for u,d in self_pred[n].iteritems() if u in H_pred]) return H 01539 def copy(self): """Return a (shallow) copy of the digraph. Return a new XDiGraph with same name and same attributes for selfloop and multiededges. Each node and each edge in original graph are added to the copy. """ H=self.__class__(multiedges=self.multiedges,selfloops=self.selfloops) H.name=self.name H.dna=self.dna.copy() for n in self: H.add_node(n) for e in self.edges_iter(): H.add_edge(e) return H 01556 def to_undirected(self): """Return the underlying graph of G. The underlying graph is its undirected representation: each directed edge is replaced with an undirected edge. If multiedges=True, then an XDiGraph with only two directed edges (1,2,"red") and (2,1,"blue") will be converted into an XGraph with two undirected edges (1,2,"red") and (1,2,"blue"). Two directed edges (1,2,"red") and (2,1,"red") will result in in two undirected edges (1,2,"red") and (1,2,"red"). If multiedges=False, then two directed edges (1,2,"red") and (2,1,"blue") can only result in one undirected edge, and there is no guarantee which one it is. """ H=XGraph(multiedges=self.multiedges,selfloops=self.selfloops) H.name=self.name H.dna=self.dna.copy() for n in self: H.add_node(n) # copy nodes for e in self.edges_iter(): H.add_edge(e) # convert each edge return H def _test_suite(): import doctest suite = doctest.DocFileSuite( 'tests/xbase_Graph.txt', 'tests/xbase_PseudoGraph.txt', 'tests/xbase_DiGraph.txt', package='networkx') return suite if __name__ == "__main__": import os import sys import unittest if sys.version_info[:2] < (2, 4): print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] sys.exit(-1) # directory of networkx package (relative to this) nxbase=sys.path[0]+os.sep+os.pardir sys.path.insert(0,nxbase) # prepend to search path unittest.TextTestRunner().run(_test_suite())

Generated by Doxygen 1.6.0 Back to index