"""
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 <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    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