"""
******
Layout
******

Node positioning algorithms for graph drawing.

"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
#    Copyright (C) 2004-2009 by 
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.

__all__ = ['circular_layout',
           'random_layout',
           'shell_layout',
           'spring_layout',
           'spectral_layout',
           'fruchterman_reingold_layout']

import networkx as nx


def random_layout(G,dim=2):
    """Position nodes uniformly at random in the unit square.

    For every node, a position is generated by choosing each of dim
    coordinates uniformly at random on the interval [0.0, 1.0).

    NumPy (http://scipy.org) is required for this function.

    Parameters
    ----------
    G : NetworkX graph
       A position will be assigned to every node in G.

    dim : int 
       Dimension of layout.

    Returns
    -------
    dict : 
       A dictionary of positions keyed by node

    Examples
    --------
    >>> G = nx.lollipop_graph(4, 3)
    >>> pos = nx.random_layout(G)

    """
    try:
        import numpy as np
    except ImportError:
        raise ImportError("random_layout() requires numpy: http://scipy.org/ ")
    n=len(G)
    pos=np.asarray(np.random.random((n,dim)),dtype=np.float32)
    return dict(list(zip(G,pos)))


def circular_layout(G, dim=2, scale=1):
    # dim=2 only
    """Position nodes on a circle.

    Parameters
    ----------
    G : NetworkX graph 

    dim : int 
       Dimension of layout, currently only dim=2 is supported

    scale : float
        Scale factor for positions 

    Returns
    -------
    dict : 
       A dictionary of positions keyed by node

    Examples
    --------
    >>> G=nx.path_graph(4)
    >>> pos=nx.circular_layout(G)
    
    Notes
    ------
    This algorithm currently only works in two dimensions and does not
    try to minimize edge crossings.

    """
    try:
        import numpy as np
    except ImportError:
        raise ImportError("circular_layout() requires numpy: http://scipy.org/ ")
    if len(G)==0:
        return {}
    if len(G)==1:
        return {G.nodes()[0]:(1,)*dim}
    t=np.arange(0,2.0*np.pi,2.0*np.pi/len(G),dtype=np.float32)
    pos=np.transpose(np.array([np.cos(t),np.sin(t)]))
    pos=_rescale_layout(pos,scale=scale)
    return dict(list(zip(G,pos)))

def shell_layout(G,nlist=None,dim=2,scale=1):
    """Position nodes in concentric circles.

    Parameters
    ----------
    G : NetworkX graph 

    nlist : list of lists
       List of node lists for each shell.

    dim : int 
       Dimension of layout, currently only dim=2 is supported

    scale : float
        Scale factor for positions 

    Returns
    -------
    dict : 
       A dictionary of positions keyed by node

    Examples
    --------
    >>> G=nx.path_graph(4)
    >>> shells=[[0],[1,2,3]]
    >>> pos=nx.shell_layout(G,shells)
    
    Notes
    ------
    This algorithm currently only works in two dimensions and does not
    try to minimize edge crossings.

    """
    try:
        import numpy as np
    except ImportError:
        raise ImportError("shell_layout() requires numpy: http://scipy.org/ ")
    if len(G)==0:
        return {}
    if len(G)==1:
        return {G.nodes()[0]:(1,)*dim}
    if nlist==None:
        nlist=[G.nodes()] # draw the whole graph in one shell

    nshells=len(nlist)
    if len(nlist[0])==1:
        radius=0.0 # single node at center
    else:
        radius=1.0 # else start at r=1

    npos={}        
    for nodes in nlist:
        t=np.arange(0,2.0*np.pi,2.0*np.pi/len(nodes),dtype=np.float32)
        pos=np.transpose(np.array([radius*np.cos(t),radius*np.sin(t)]))
        npos.update(dict(list(zip(nodes,pos))))
        radius+=1.0

    # FIXME: rescale        
    return npos        


def fruchterman_reingold_layout(G,dim=2,
                                pos=None,
                                fixed=None,
                                iterations=50,
                                weighted=True,scale=1):
    """Position nodes using Fruchterman-Reingold force-directed algorithm. 

    Parameters
    ----------
    G : NetworkX graph 

    dim : int 
       Dimension of layout

    pos : dict
       Initial positions for nodes as a dictionary with node as keys
       and values as a list or tuple.  

    fixed : list
      Nodes to keep fixed at initial position.


    iterations : int
       Number of iterations of spring-force relaxation 

    weighted : boolean
        If True, use edge weights in layout 

    scale : float
        Scale factor for positions 

    Returns
    -------
    dict : 
       A dictionary of positions keyed by node

    Examples
    --------
    >>> G=nx.path_graph(4)
    >>> pos=nx.spring_layout(G)

    # The same using longer function name
    >>> pos=nx.fruchterman_reingold_layout(G)
    
    """
    try:
        import numpy as np
    except ImportError:
        raise ImportError("fruchterman_reingold_layout() requires numpy: http://scipy.org/ ")
    if fixed is not None:
        nfixed=dict(list(zip(G,list(range(len(G))))))
        fixed=np.asarray([nfixed[v] for v in fixed])

    if pos is not None:
        pos_arr=np.asarray(np.random.random((len(G),dim)))
        for n,i in zip(G,list(range(len(G)))):
            if n in pos:
                pos_arr[i]=np.asarray(pos[n])
    else:
        pos_arr=None

    if len(G)==0:
        return {}
    if len(G)==1:
        return {G.nodes()[0]:(1,)*dim}

    try:
        # Sparse matrix 
        if len(G) < 500:  # sparse solver for large graphs
            raise ValueError
        A=nx.to_scipy_sparse_matrix(G)
        pos=_sparse_fruchterman_reingold(A,
                                         pos=pos_arr,
                                         fixed=fixed,
                                         dim=dim,
                                         iterations=iterations,
                                         weighted=weighted)
    except:
        A=nx.to_numpy_matrix(G)
        pos=_fruchterman_reingold(A,
                                  pos=pos_arr,
                                  fixed=fixed,
                                  dim=dim,
                                  iterations=iterations,
                                  weighted=weighted)
    if fixed is None:
        pos=_rescale_layout(pos,scale=scale)
    return dict(list(zip(G,pos)))





spring_layout=fruchterman_reingold_layout


def _fruchterman_reingold(A,dim=2,
                          pos=None,
                          fixed=None,
                          iterations=50,
                          weighted=True):
    # Position nodes in adjacency matrix A using Fruchterman-Reingold  
    # Entry point for NetworkX graph is fruchterman_reingold_layout()
    try:
        import numpy as np
    except ImportError:
        raise ImportError("_fruchterman_reingold() requires numpy: http://scipy.org/ ")

    try:
        nnodes,_=A.shape
    except AttributeError:
        raise nx.NetworkXError(
            "fruchterman_reingold() takes an adjacency matrix as input")
    
    A=np.asarray(A) # make sure we have an array instead of a matrix
    if not weighted: # use 0/1 adjacency instead of weights
        A=np.where(A==0,A,A/A)

    if pos==None:
        # random initial positions
        pos=np.asarray(np.random.random((nnodes,dim)),dtype=A.dtype)
    else:
        # make sure positions are of same type as matrix
        pos=pos.astype(A.dtype)

    # optimal distance between nodes
    k=np.sqrt(1.0/nnodes) 
    # the initial "temperature"  is about .1 of domain area (=1x1)
    # this is the largest step allowed in the dynamics.
    t=0.1
    # simple cooling scheme.
    # linearly step down by dt on each iteration so last iteration is size dt.
    dt=t/float(iterations+1) 
    delta = np.zeros((pos.shape[0],pos.shape[0],pos.shape[1]),dtype=A.dtype)
    # the inscrutable (but fast) version
    # this is still O(V^2)
    # could use multilevel methods to speed this up significantly
    for iteration in range(iterations):
        # matrix of difference between points
        for i in range(pos.shape[1]):
            delta[:,:,i]= pos[:,i,None]-pos[:,i]
        # distance between points
        distance=np.sqrt((delta**2).sum(axis=-1))
        # enforce minimum distance of 0.01
        distance=np.where(distance<0.01,0.01,distance)
        # displacement "force"
        displacement=np.transpose(np.transpose(delta)*\
                                  (k*k/distance**2-A*distance/k))\
                                  .sum(axis=1)
        # update positions            
        length=np.sqrt((displacement**2).sum(axis=1))
        length=np.where(length<0.01,0.1,length)
        delta_pos=np.transpose(np.transpose(displacement)*t/length)
        if fixed is not None:
            # don't change positions of fixed nodes
            delta_pos[fixed]=0.0
        pos+=delta_pos
        # cool temperature
        t-=dt

    return pos


def _sparse_fruchterman_reingold(A,dim=2,
                                 pos=None,
                                 fixed=None,
                                 iterations=50,
                                 weighted=True):
    # Position nodes in adjacency matrix A using Fruchterman-Reingold  
    # Entry point for NetworkX graph is fruchterman_reingold_layout()
    # Sparse version
    try:
        import numpy as np
    except ImportError:
        raise ImportError("_sparse_fruchterman_reingold() requires numpy: http://scipy.org/ ")
    try:
        nnodes,_=A.shape
    except AttributeError:
        raise nx.NetworkXError(
            "fruchterman_reingold() takes an adjacency matrix as input")
    
    try:
        from scipy.sparse import spdiags,coo_matrix
    except ImportError:
        raise ImportError("_sparse_fruchterman_reingold() scipy numpy: http://scipy.org/ ")
    
    # make sure we have a LIst of Lists representation
    try:
        A=A.tolil() 
    except:
        A=(coo_matrix(A)).tolil()

    if not weighted: # use 0/1 adjacency instead of weights
        A=np.where(A==0,A,A/A)

    if pos==None:
        # random initial positions
        pos=np.asarray(np.random.random((nnodes,dim)),dtype=A.dtype)
    else:
        # make sure positions are of same type as matrix
        pos=pos.astype(A.dtype)

    # no fixed nodes
    if fixed==None:
        fixed=[]

    # optimal distance between nodes
    k=np.sqrt(1.0/nnodes) 
    # the initial "temperature"  is about .1 of domain area (=1x1)
    # this is the largest step allowed in the dynamics.
    t=0.1
    # simple cooling scheme.
    # linearly step down by dt on each iteration so last iteration is size dt.
    dt=t/float(iterations+1) 

    displacement=np.zeros((dim,nnodes))
    for iteration in range(iterations):
        displacement*=0
        # loop over rows
        for i in range(A.shape[0]):
            if i in fixed:
                continue
            # difference between this row's node position and all others
            delta=(pos[i]-pos).T
            # distance between points
            distance=np.sqrt((delta**2).sum(axis=0))
            # enforce minimum distance of 0.01
            distance=np.where(distance<0.01,0.01,distance)
            # the adjacency matrix row
            Ai=np.asarray(A.getrowview(i).toarray())
            # displacement "force"
            displacement[:,i]+=\
                (delta*(k*k/distance**2-Ai*distance/k)).sum(axis=1)
        # update positions            
        length=np.sqrt((displacement**2).sum(axis=0))
        length=np.where(length<0.01,0.1,length) 
        pos+=(displacement*t/length).T
        # cool temperature
        t-=dt

    return pos


def spectral_layout(G,dim=2,weighted=True,scale=1):
    """Position nodes using the eigenvectors of the graph Laplacian. 

    Parameters
    ----------
    G : NetworkX graph 

    dim : int 
       Dimension of layout

    weighted : boolean
        If True, use edge weights in layout 

    scale : float
        Scale factor for positions 

    Returns
    -------
    dict : 
       A dictionary of positions keyed by node

    Examples
    --------
    >>> G=nx.path_graph(4)
    >>> pos=nx.spectral_layout(G)

    Notes
    -----
    Directed graphs will be considered as unidrected graphs when
    positioning the nodes.

    For larger graphs (>500 nodes) this will use the SciPy sparse
    eigenvalue solver (ARPACK).
    """
    # handle some special cases that break the eigensolvers
    try:
        import numpy as np
    except ImportError:
        raise ImportError("spectral_layout() requires numpy: http://scipy.org/ ")
    if len(G)<=2:
        if len(G)==0:
            pos=np.array([])
        elif len(G)==1:
            pos=np.array([[1,1]])
        else:
            pos=np.array([[0,0.5],[1,0.5]])
        return dict(list(zip(G,pos)))
    try:
        # Sparse matrix 
        if len(G)< 500:  # dense solver is faster for small graphs
            raise ValueError
        A=nx.to_scipy_sparse_matrix(G)
        # Symmetrize directed graphs
        if G.is_directed():
            A=A+np.transpose(A)
        pos=_sparse_spectral(A,dim=dim,weighted=weighted)
    except (ImportError,ValueError):
        # Dense matrix
        A=nx.to_numpy_matrix(G)
        # Symmetrize directed graphs
        if G.is_directed():
            A=A+np.transpose(A)
        pos=_spectral(A,dim=dim,weighted=weighted)

    pos=_rescale_layout(pos,scale=scale)
    return dict(list(zip(G,pos)))


def _spectral(A,dim=2,weighted=True):
    # Input adjacency matrix A
    # Uses dense eigenvalue solver from numpy
    try:
        import numpy as np
    except ImportError:
        raise ImportError("spectral_layout() requires numpy: http://scipy.org/ ")
    try:
        nnodes,_=A.shape
    except AttributeError:
        raise nx.NetworkXError(\
            "spectral() takes an adjacency matrix as input")
    
    # form Laplacian matrix
    # make sure we have an array instead of a matrix
    A=np.asarray(A) 
    I=np.identity(nnodes,dtype=A.dtype)
    D=I*np.sum(A,axis=1) # diagonal of degrees
    L=D-A 

    eigenvalues,eigenvectors=np.linalg.eig(L)
    # sort and keep smallest nonzero 
    index=np.argsort(eigenvalues)[1:dim+1] # 0 index is zero eigenvalue
    return np.real(eigenvectors[:,index])

def _sparse_spectral(A,dim=2,weighted=True):
    # Input adjacency matrix A
    # Uses sparse eigenvalue solver from scipy
    # Could use multilevel methods here, see Koren "On spectral graph drawing" 
    
    try:
        from scipy.sparse import spdiags
        from scipy.sparse.linalg import eigen_symmetric
    except ImportError:
        raise ImportError("_sparse_spectral() scipy numpy: http://scipy.org/ ")
    try:
        nnodes,_=A.shape
    except AttributeError:
        raise nx.NetworkXError(\
            "sparse_spectral() takes an adjacency matrix as input")
    
    # form Laplacian matrix
    data=np.asarray(A.sum(axis=1).T)
    D=spdiags(data,0,nnodes,nnodes)
    L=D-A
    # number of Lanczos vectors for ARPACK solver, what is the right scaling?
    ncv=int(np.sqrt(nnodes)) 
    # return smalest dim+1 eigenvalues and eigenvectors
    eigenvalues,eigenvectors=eigen_symmetric(L,dim+1,which='SM',ncv=ncv)
    index=np.argsort(eigenvalues)[1:dim+1] # 0 index is zero eigenvalue
    return np.real(eigenvectors[:,index])


def _rescale_layout(pos,scale=1):
    # rescale to (0,pscale) in all axes

    # shift origin to (0,0)
    lim=0 # max coordinate for all axes
    for i in range(pos.shape[1]):
        pos[:,i]-=pos[:,i].min()
        lim=max(pos[:,i].max(),lim)
    # rescale to (0,scale) in all directions, preserves aspect
    for i in range(pos.shape[1]):
        pos[:,i]*=scale/lim
    return pos


# fixture for nose tests
def setup_module(module):
    from nose import SkipTest
    try:
        import numpy
    except:
        raise SkipTest("NumPy not available")
    try:
        import scipy
    except:
        raise SkipTest("SciPy not available")
