""" Functional interface to graph methods and assorted utilities. """ __author__ = """\n""".join(['Aric Hagberg (hagberg@lanl.gov)', 'Pieter Swart (swart@lanl.gov)', 'Dan Schult(dschult@colgate.edu)']) # Copyright (C) 2004-2010 by # Aric Hagberg # Dan Schult # Pieter Swart # All rights reserved. # BSD license. # import networkx as nx # functional style helpers __all__ = ['nodes', 'edges', 'degree', 'degree_histogram', 'neighbors', 'number_of_nodes', 'number_of_edges', 'density', 'nodes_iter', 'edges_iter', 'is_directed','info', 'freeze','is_frozen','subgraph','create_empty_copy'] def nodes(G): """Return a copy of the graph nodes in a list.""" return G.nodes() def nodes_iter(G): """Return an iterator over the graph nodes.""" return G.nodes_iter() def edges(G,nbunch=None): """Return list of edges adjacent to nodes in nbunch. Return all edges if nbunch is unspecified or nbunch=None. For digraphs, edges=out_edges """ return G.edges(nbunch) def edges_iter(G,nbunch=None): """Return iterator over edges adjacent to nodes in nbunch. Return all edges if nbunch is unspecified or nbunch=None. For digraphs, edges=out_edges """ return G.edges_iter(nbunch) def degree(G,nbunch=None,weighted=False): """Return degree of single node or of nbunch of nodes. If nbunch is ommitted, then return degrees of *all* nodes. """ return G.degree(nbunch,weighted=weighted) def neighbors(G,n): """Return a list of nodes connected to node n. """ return G.neighbors(n) def number_of_nodes(G): """Return the number of nodes in the graph.""" return G.number_of_nodes() def number_of_edges(G): """Return the number of edges in the graph. """ return G.number_of_edges() def density(G): """Return the density of a graph. The density for undirected graphs is .. math:: d = \\frac{2m}{n(n-1)}, and for directed graphs is .. math:: d = \\frac{m}{n(n-1)}, where :math:`n` is the number of nodes and :math:`m` is the number of edges in :math:`G`. Notes ----- The density is 0 for an graph without edges and 1.0 for a complete graph. The density of multigraphs can be higher than 1. """ n=number_of_nodes(G) m=number_of_edges(G) if m==0: # includes cases n==0 and n==1 d=0.0 else: if G.is_directed(): d=m/float(n*(n-1)) else: d= m*2.0/float(n*(n-1)) return d def degree_histogram(G): """Return a list of the frequency of each degree value. Parameters ---------- G : Networkx graph A graph Returns ------- hist : list A list of frequencies of degrees. The degree values are the index in the list. Notes ----- Note: the bins are width one, hence len(list) can be large (Order(number_of_edges)) """ degseq=G.degree().values() dmax=max(degseq)+1 freq= [ 0 for d in xrange(dmax) ] for d in degseq: freq[d] += 1 return freq def is_directed(G): """ Return True if graph is directed.""" return G.is_directed() def info(G, n=None): """Print short summary of information for graph G or node n.""" import textwrap width_left = 22 if n is None: print ("Name:").ljust(width_left), G.name type_name = [type(G).__name__] print ("Type:").ljust(width_left), ",".join(type_name) print ("Number of nodes:").ljust(width_left), G.number_of_nodes() print ("Number of edges:").ljust(width_left), G.number_of_edges() if len(G) > 0: if G.is_directed(): print ("Average in degree:").ljust(width_left), \ round( sum(G.in_degree())/float(len(G)), 4) print ("Average out degree:").ljust(width_left), \ round( sum(G.out_degree())/float(len(G)), 4) else: print ("Average degree:").ljust(width_left), \ round( sum(G.degree())/float(len(G)), 4) else: try: list_neighbors = G.neighbors(n) except (KeyError, TypeError): raise NetworkXError, "node %s not in graph"%(n,) print "\nNode", n, "has the following properties:" print ("Degree:").ljust(width_left), len(list_neighbors) str_neighbors = str(list_neighbors) str_neighbors = str_neighbors[1:len(str_neighbors)-1] wrapped_neighbors = textwrap.wrap(str_neighbors, 50) print ("Neighbors:").ljust(width_left), wrapped_neighbors[0] for i in wrapped_neighbors[1:]: print "".ljust(width_left), i def freeze(G): """Modify graph to prevent addition of nodes or edges. Parameters ----------- G : graph A NetworkX graph Examples -------- >>> G=nx.path_graph(4) >>> G=nx.freeze(G) >>> G.add_edge(4,5) Traceback (most recent call last): ... NetworkXError: Frozen graph can't be modified Notes ----- This does not prevent modification of edge data. To "unfreeze" a graph you must make a copy. See Also -------- is_frozen """ def frozen(*args): raise nx.NetworkXError("Frozen graph can't be modified") G.add_node=frozen G.add_nodes_from=frozen G.remove_node=frozen G.remove_nodes_from=frozen G.add_edge=frozen G.add_edges_from=frozen G.remove_edge=frozen G.remove_edges_from=frozen G.clear=frozen G.frozen=True return G def is_frozen(G): """Return True if graph is frozen. Parameters ----------- G : graph A NetworkX graph See Also -------- freeze """ try: return G.frozen except AttributeError: return False def subgraph(G, nbunch): """Return the subgraph induced on nodes in nbunch. Parameters ---------- G : graph A NetworkX graph nbunch : list, iterable A container of nodes that will be iterated through once (thus it should be an iterator or be iterable). Each element of the container should be a valid node type: any hashable type except None. If nbunch is None, return all edges data in the graph. Nodes in nbunch that are not in the graph will be (quietly) ignored. Notes ----- subgraph(G) calls G.subgraph() """ return G.subgraph(nbunch) def create_empty_copy(G,with_nodes=True): """Return a copy of the graph G with all of the edges removed. Parameters ---------- G : graph A NetworkX graph with_nodes : bool (default=True) Include nodes. Notes ----- Graph, node, and edge data is not propagated to the new graph. """ H=G.__class__() H.name='empty '+G.name if with_nodes: H.add_nodes_from(G) return H