content: from itertools import product
  from nose.tools import assert_true
  
  import numpy as np
  from numpy.testing import assert_almost_equal, assert_array_almost_equal
  from scipy import linalg
  
  from sklearn import neighbors, manifold
  from sklearn.manifold.locally_linear import barycenter_kneighbors_graph
  from sklearn.utils.testing import assert_less
  from sklearn.utils.testing import ignore_warnings
  
  eigen_solvers = ['dense', 'arpack']
  
  
  #----------------------------------------------------------------------
  # Test utility routines
  def test_barycenter_kneighbors_graph():
      X = np.array([[0, 1], [1.01, 1.], [2, 0]])
  
      A = barycenter_kneighbors_graph(X, 1)
      assert_array_almost_equal(
          A.toarray(),
          [[0.,  1.,  0.],
           [1.,  0.,  0.],
           [0.,  1.,  0.]])
  
      A = barycenter_kneighbors_graph(X, 2)
      # check that columns sum to one
      assert_array_almost_equal(np.sum(A.toarray(), 1), np.ones(3))
      pred = np.dot(A.toarray(), X)
      assert_less(linalg.norm(pred - X) / X.shape[0], 1)
  
  
  #----------------------------------------------------------------------
  # Test LLE by computing the reconstruction error on some manifolds.
  
  def test_lle_simple_grid():
      # note: ARPACK is numerically unstable, so this test will fail for
      #       some random seeds.  We choose 2 because the tests pass.
      rng = np.random.RandomState(2)
      tol = 0.1
  
      # grid of equidistant points in 2D, n_components = n_dim
      X = np.array(list(product(range(5), repeat=2)))
      X = X + 1e-10 * rng.uniform(size=X.shape)
      n_components = 2
      clf = manifold.LocallyLinearEmbedding(n_neighbors=5,
                                            n_components=n_components,
                                            random_state=rng)
      tol = 0.1
  
      N = barycenter_kneighbors_graph(X, clf.n_neighbors).toarray()
      reconstruction_error = linalg.norm(np.dot(N, X) - X, 'fro')
      assert_less(reconstruction_error, tol)
  
      for solver in eigen_solvers:
          clf.set_params(eigen_solver=solver)
          clf.fit(X)
          assert_true(clf.embedding_.shape[1] == n_components)
          reconstruction_error = linalg.norm(
              np.dot(N, clf.embedding_) - clf.embedding_, 'fro') ** 2
  
          assert_less(reconstruction_error, tol)
          assert_almost_equal(clf.reconstruction_error_,
                              reconstruction_error, decimal=1)
  
      # re-embed a noisy version of X using the transform method
      noise = rng.randn(*X.shape) / 100
      X_reembedded = clf.transform(X + noise)
      assert_less(linalg.norm(X_reembedded - clf.embedding_), tol)
  
  
  def test_lle_manifold():
      rng = np.random.RandomState(0)
      # similar test on a slightly more complex manifold
      X = np.array(list(product(np.arange(18), repeat=2)))
      X = np.c_[X, X[:, 0] ** 2 / 18]
      X = X + 1e-10 * rng.uniform(size=X.shape)
      n_components = 2
      for method in ["standard", "hessian", "modified", "ltsa"]:
          clf = manifold.LocallyLinearEmbedding(n_neighbors=6,
                                                n_components=n_components,
                                                method=method, random_state=0)
          tol = 1.5 if method == "standard" else 3
  
          N = barycenter_kneighbors_graph(X, clf.n_neighbors).toarray()
          reconstruction_error = linalg.norm(np.dot(N, X) - X)
          assert_less(reconstruction_error, tol)
  
          for solver in eigen_solvers:
              clf.set_params(eigen_solver=solver)
              clf.fit(X)
              assert_true(clf.embedding_.shape[1] == n_components)
              reconstruction_error = linalg.norm(
                  np.dot(N, clf.embedding_) - clf.embedding_, 'fro') ** 2
              details = ("solver: %s, method: %s" % (solver, method))
              assert_less(reconstruction_error, tol, msg=details)
              assert_less(np.abs(clf.reconstruction_error_ -
                                 reconstruction_error),
                          tol * reconstruction_error, msg=details)
  
  
  def test_pipeline():
      # check that LocallyLinearEmbedding works fine as a Pipeline
      # only checks that no error is raised.
      # TODO check that it actually does something useful
      from sklearn import pipeline, datasets
      X, y = datasets.make_blobs(random_state=0)
      clf = pipeline.Pipeline(
          [('filter', manifold.LocallyLinearEmbedding(random_state=0)),
           ('clf', neighbors.KNeighborsClassifier())])
      clf.fit(X, y)
      assert_less(.9, clf.score(X, y))
  
  
  # Test the error raised when the weight matrix is singular
  def test_singular_matrix():
      from nose.tools import assert_raises
      M = np.ones((10, 3))
      f = ignore_warnings
      assert_raises(ValueError, f(manifold.locally_linear_embedding),
                    M, 2, 1, method='standard', eigen_solver='arpack')
  