<commit_before># -*- coding: utf-8 -*-
"""
Algebraic connectivity and Fiedler vectors of undirected graphs.
"""

__author__ = """ysitu <<EMAIL>>"""
# Copyright (C) 2014 ysitu <<EMAIL>>
# All rights reserved.
# BSD license.

import networkx as nx
from networkx.utils import not_implemented_for
from random import normalvariate

try:
    from numpy import (array, asmatrix, asarray, dot, matrix, ndarray, reshape,
                       zeros)
    from numpy.linalg import norm
    from scipy.linalg import eigh, solve
    from scipy.sparse import csc_matrix
    from scipy.sparse.linalg import eigsh
    __all__ = ['algebraic_connectivity', 'fiedler_vector']
except ImportError:
    __all__ = []


class _PCGSolver(object):
    """Jacobi-preconditioned conjugate gradient method.
    """

    def __init__(self, A, tol):
        self._A = A
        self._M = 1. / A.diagonal()
        self._tol = tol

    def solve(self, b):
        A = self._A
        M = self._M
        tol = self._tol * norm(b, 1)
        # Initialize.
        x = zeros(b.shape)
        r = b.copy()
        z = M * r
        rz = dot(r, z)
        p = z
        # Iterate.
        while True:
            Ap = A * p
            alpha = rz / dot(p, Ap)
            x += alpha * p
            r -= alpha * Ap
            if norm(r, 1) < tol:
                return x
            z = M * r
            beta = dot(r, z)
            beta, rz = beta / rz, beta
            p = z + beta * p


class _CholeskySolver(object):
    """Cholesky factorization.
    """

    def __init__(self, A):
        A = csc_matrix(A, dtype=float, copy=True)
        # Compute an unsymmetric reordering.
        chol = self._analyze(A)
        perm = chol.P()
        # Set the lower-right element after permutation to infinity.
        A[perm[-1], perm[-1]] = float('inf')
        chol.cholesky_inplace(A)
        self._chol = chol

    def solve(self, b):
        return self._chol(b)

    try:
        from scikits.sparse.cholmod import analyze
        _analyze = analyze
        avail = True
    except ImportError:
        avail = False


def _tracemin_fiedler(L, tol, solver=None):
    """Compute the Fiedler vector of L using the TRACEMIN-Fiedler algorithm.
    """
    n = L.shape[0]
    q = 2

    Lnorm = abs(L).sum(axis=0).flatten().max()

    def project(X):
        """Make X orthogonal to the nullspace of L.
        """
        X = asarray(X)
        for j in range(q):
            X[:, j] -= sum(X[:, j]) / n
<commit_msg>Simplify preparation for Cholesky factorization in algebraic_connectivity<commit_after># -*- coding: utf-8 -*-
"""
Algebraic connectivity and Fiedler vectors of undirected graphs.
"""

__author__ = """ysitu <<EMAIL>>"""
# Copyright (C) 2014 ysitu <<EMAIL>>
# All rights reserved.
# BSD license.

import networkx as nx
from networkx.utils import not_implemented_for
from random import normalvariate

try:
    from numpy import (array, asmatrix, asarray, dot, matrix, ndarray, reshape,
                       zeros)
    from numpy.linalg import norm
    from scipy.linalg import eigh, solve
    from scipy.sparse import csc_matrix
    from scipy.sparse.linalg import eigsh
    __all__ = ['algebraic_connectivity', 'fiedler_vector']
except ImportError:
    __all__ = []


class _PCGSolver(object):
    """Jacobi-preconditioned conjugate gradient method.
    """

    def __init__(self, A, tol):
        self._A = A
        self._M = 1. / A.diagonal()
        self._tol = tol

    def solve(self, b):
        A = self._A
        M = self._M
        tol = self._tol * norm(b, 1)
        # Initialize.
        x = zeros(b.shape)
        r = b.copy()
        z = M * r
        rz = dot(r, z)
        p = z
        # Iterate.
        while True:
            Ap = A * p
            alpha = rz / dot(p, Ap)
            x += alpha * p
            r -= alpha * Ap
            if norm(r, 1) < tol:
                return x
            z = M * r
            beta = dot(r, z)
            beta, rz = beta / rz, beta
            p = z + beta * p


class _CholeskySolver(object):
    """Cholesky factorization.
    """

    def __init__(self, A):
        # Convert A to CSC to suppress SparseEfficiencyWarning.
        A = csc_matrix(A, dtype=float, copy=True)
        # Force A to be nonsingular. Since A is the Laplacian matrix of a
        # connected graph, its rank deficiency is one, and thus one diagonal
        # element needs to modified. Changing to infinity forces a zero in the
        # corresponding element in the solution.
        i = A.diagonal().argmin()
        A[i, i] = float('inf')
        self._chol = self._cholesky(A)

    def solve(self, b):
        return self._chol(b)

    try:
        from scikits.sparse.cholmod import cholesky
        _cholesky = cholesky
        avail = True
    except ImportError:
        avail = False


def _tracemin_fiedler(L, tol, solver=None):
    """Compute the Fiedler vector of L using the TRACEMIN-Fiedler algorithm.
    """
    n = L.shape[0]
    q = 2

    Lnorm = abs(L).sum(axis=0).flatten().max()

    def project(X):
        """Make X orthogonal to the nullspace of L.
        """
        X = asarray(X)
        for j in range(q):
            X[:, j] -= sum(X[:, j]) / n

{'fraction_non_alphanumeric': 0.11121782558586246, 'fraction_numerical': 0.004610065309258548, 'mean_word_length': 1.897607122982749, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 11, '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': '4428593', 'n_tokens_mistral': 1759, 'n_tokens_neox': 1667, 'n_words': 521}