<commit_before>import numpy as np
import warnings
from scipy.sparse import issparse
from scipy.sparse.linalg import eigsh
from scipy.linalg import eigh
from sklearn.decomposition import KernelPCA

from analysis import shortest_path, laplacian

__all__ = [
    'isomap', 'laplacian_eigenmaps', 'locality_preserving_projections',
    'laplacian_pca'
]


def isomap(G, num_vecs=None, directed=True):
  directed = directed and G.is_directed()
  W = -0.5 * shortest_path(G, directed=directed) ** 2
  return KernelPCA(n_components=num_vecs, kernel='precomputed').fit_transform(W)


def laplacian_eigenmaps(G, num_vecs=None, return_vals=False, val_thresh=1e-8):
  L = laplacian(G, normed=True)
  return _lapeig(L, num_vecs, return_vals, val_thresh)


def locality_preserving_projections(G, coordinates, num_vecs=None):
  X = np.atleast_2d(coordinates)
  L = laplacian(G, normed=True)
  u,s,_ = np.linalg.svd(X.T.dot(X))
  Fplus = np.linalg.pinv(u * np.sqrt(s))
  T = reduce(np.dot,(Fplus,X.T,L,X,Fplus.T))
  L = 0.5*(T+T.T)
  return _lapeig(L, num_vecs, False, 1e-8)


def laplacian_pca(G, coordinates, num_vecs=None, beta=0.5):
  '''Graph-Laplacian PCA (CVPR 2013).
  Assumes coordinates are mean-centered.
  Parameter beta in [0,1], scales how much PCA/LapEig contributes.
  Returns an approximation of input coordinates, ala PCA.'''
  X = np.atleast_2d(coordinates)
  L = laplacian(G, normed=True)
  kernel = X.dot(X.T)
  kernel /= eigsh(kernel, k=1, which='LM', return_eigenvectors=False)
  L /= eigsh(L, k=1, which='LM', return_eigenvectors=False)
  W = (1-beta)*(np.identity(kernel.shape[0]) - kernel) + beta*L
  vals, vecs = eigh(W, eigvals=(0, num_vecs-1), overwrite_a=True)
  return X.T.dot(vecs).dot(vecs.T).T


def _lapeig(L, num_vecs, return_vals, val_thresh):
  if issparse(L):
    # This is a bit of a hack. Make sure we end up with enough eigenvectors.
    k = L.shape[0] - 1 if num_vecs is None else num_vecs + 1
    try:
      # TODO: try using shift-invert mode (sigma=0?) for speed here.
      vals,vecs = eigsh(L, k, which='SM')
    except:
      warnings.warn('Sparse eigsh failed, falling back to dense version')
      vals,vecs = eigh(L.A, overwrite_a=True)
  else:
    vals,vecs = eigh(L, overwrite_a=True)
  # vals not guaranteed to be in sorted order
  idx = np.argsort(vals)
  vecs = vecs.real[:,idx]
  vals = vals.real[idx]
  # discard any with really small eigenvalues
  i = np.searchsorted(vals, val_thresh)
  if num_vecs is None:
    # take all of them
    num_vecs = vals.shape[0] - i
  embedding = vecs[:,i:i+num_vecs]
  if return_vals:
    return embedding, vals[i:i+num_vecs]
  return embedding
<commit_msg>adding some layouts, borrowed from networkx<commit_after>import numpy as np
import warnings
from scipy.sparse import issparse
from scipy.sparse.linalg import eigsh
from scipy.linalg import eigh
from sklearn.decomposition import KernelPCA

from analysis import shortest_path, laplacian

__all__ = [
    'isomap', 'laplacian_eigenmaps', 'locality_preserving_projections',
    'laplacian_pca'
]


def isomap(G, num_vecs=None, directed=True):
  directed = directed and G.is_directed()
  W = -0.5 * shortest_path(G, directed=directed) ** 2
  return KernelPCA(n_components=num_vecs, kernel='precomputed').fit_transform(W)


def laplacian_eigenmaps(G, num_vecs=None, return_vals=False, val_thresh=1e-8):
  L = laplacian(G, normed=True)
  return _lapeig(L, num_vecs, return_vals, val_thresh)


def locality_preserving_projections(G, coordinates, num_vecs=None):
  X = np.atleast_2d(coordinates)
  L = laplacian(G, normed=True)
  u,s,_ = np.linalg.svd(X.T.dot(X))
  Fplus = np.linalg.pinv(u * np.sqrt(s))
  T = reduce(np.dot,(Fplus,X.T,L,X,Fplus.T))
  L = 0.5*(T+T.T)
  return _lapeig(L, num_vecs, False, 1e-8)


def laplacian_pca(G, coordinates, num_vecs=None, beta=0.5):
  '''Graph-Laplacian PCA (CVPR 2013).
  Assumes coordinates are mean-centered.
  Parameter beta in [0,1], scales how much PCA/LapEig contributes.
  Returns an approximation of input coordinates, ala PCA.'''
  X = np.atleast_2d(coordinates)
  L = laplacian(G, normed=True)
  kernel = X.dot(X.T)
  kernel /= eigsh(kernel, k=1, which='LM', return_eigenvectors=False)
  L /= eigsh(L, k=1, which='LM', return_eigenvectors=False)
  W = (1-beta)*(np.identity(kernel.shape[0]) - kernel) + beta*L
  vals, vecs = eigh(W, eigvals=(0, num_vecs-1), overwrite_a=True)
  return X.T.dot(vecs).dot(vecs.T).T


def _lapeig(L, num_vecs, return_vals, val_thresh):
  if issparse(L):
    # This is a bit of a hack. Make sure we end up with enough eigenvectors.
    k = L.shape[0] - 1 if num_vecs is None else num_vecs + 1
    try:
      # TODO: try using shift-invert mode (sigma=0?) for speed here.
      vals,vecs = eigsh(L, k, which='SM')
    except:
      warnings.warn('Sparse eigsh failed, falling back to dense version')
      vals,vecs = eigh(L.A, overwrite_a=True)
  else:
    vals,vecs = eigh(L, overwrite_a=True)
  # vals not guaranteed to be in sorted order
  idx = np.argsort(vals)
  vecs = vecs.real[:,idx]
  vals = vals.real[idx]
  # discard any with really small eigenvalues
  i = np.searchsorted(vals, val_thresh)
  if num_vecs is None:
    # take all of them
    num_vecs = vals.shape[0] - i
  embedding = vecs[:,i:i+num_vecs]
  if return_vals:
    return embedding, vals[i:i+num_vecs]
  return embedding


def random_layout(G, num_dims=2):
  return np.random.random((G.num_vertices(), num_dims))


def circular_layout(G):
  n = G.num_vertices()
  t = np.linspace(0, 2*np.pi, n)
  return np.column_stack((np.cos(t), np.sin(t)))


def spring_layout(G, num_dims=2, spring_constant=None, iterations=50):
  """Position nodes using Fruchterman-Reingold force-directed algorithm.

  spring_constant : float (default=None)
     Optimal distance between nodes.  If None the distance is set to
     1/sqrt(n) where n is the number of nodes.  Increase this value
     to move nodes farther apart.

  iterations : int  optional (default=50)
     Number of iterations of spring-force relaxation
  """
  X = random_layout(G, num_dims=num_dims)
  if spring_constant is None:
    spring_constant = X.shape[0] ** -0.5
  adj = G.matrix()
  # the initial "temperature"  is about .1 of domain area (=1x1)
  # this is the largest step allowed in the dynamics.
  initial_temp = 0.1
  # simple cooling scheme, linearly steps down
  cooling_scheme = np.linspace(initial_temp, 0, iterations+2)[:-2]
  # this is still O(V^2)
  # could use multilevel methods to speed this up significantly
  for t in cooling_scheme:
    delta = X[:,None] - X[None]
    distance = np.linalg.norm(delta, ord=2, axis=2)
    # enforce minimum distance of 0.01
    np.maximum(distance, 0.01, out=distance)
    # displacement "force"
    # TODO: this seems like a bug, where small weights are made big
    #   maybe do 1/adj or something (without div by zero)
    accel = (spring_constant/distance)**2 - adj*distance/spring_constant
    displacement = (delta * accel[:,:,None]).sum(axis=1)
    # update positions
    length = np.linalg.norm(displacement, axis=1)
    np.maximum(length, 0.01, out=length)
    X += displacement * t / length[:,None]
  return X

{'fraction_non_alphanumeric': 0.12385643912737508, 'fraction_numerical': 0.013511611541168192, 'mean_word_length': 4.097560975609756, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5782611', 'n_tokens_mistral': 2809, 'n_tokens_neox': 2668, 'n_words': 687}