<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

__all__ = ['algebraic_connectivity', 'fiedler_vector']


def _pcg(A, b, tol):
    """Jacobi-preconditioned conjugate gradient method.
    """
    from numpy import dot, zeros
    from numpy.linalg import norm

    # Jacobi preconditioner.
    M = 1 / A.diagonal()
    x = zeros(b.shape)
    r = b.copy()
    z = M * r
    rz = dot(r, z)
    p = z

    tol *= norm(r, 1)
    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


def _tracemin_fiedler(L, tol):
    """Compute the Fiedler vector of L using the TRACEMIN-Fiedler algorithm.
    """
    from numpy import array, asmatrix, asarray, dot, matrix, ndarray, reshape
    from numpy.linalg import norm
    from scipy.linalg import eigh, solve

    n = L.shape[0]
    q = 2

    # Convert to CSC format to silence a SparseEfficiencyWarning generated by
    # splu.
    Lnorm = max(asarray(abs(L).sum(axis=0))[0, :])

    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

    def gram_schmidt(X):
        """Return an orthonormalized copy of X.
        """
        X = array(X)
        for j in range(q):
            for k in range(j):
                X[:, j] -= dot(X[:, k], X[:, j]) * X[:, k]
            X[:, j] /= norm(X[:, j])
        return asmatrix(X)

    # Randomly initialize eigenvectors.
    X = asmatrix(reshape([normalvariate(0, 1) for i in range(n * q)], (n, q)))
    project(X)
    W = asmatrix(ndarray((n, q)))

    first = True
    while True:
        V = gram_schmidt(X)
        # Compute interation matrix H.
        H = V.transpose() * L * V
        sigma, Y = eigh(H, overwrite_a=True)
        # Test for convergence.
        if not first:
            r = L * X[:, 0] - sigma[0] * X[:, 0]
            if norm(r, 1) < tol * Lnorm:
                break
        else:
            first = False
        # Compute Ritz vectors.
        X = V * Y
        # Solve saddle point problem using the Schur complement.
        for j in range(q):
            asarray(W)[:, j] = _pcg(L, asarray(X)[:, j], tol / 10)
        project(W)
        S = X.transpose() * W  # Schur complement
        N = solve(S, X.transpose() * X, overwrite_a=True, overwrite_b=True,
                  check_finite=False)
        X = W * N

    return sigma, asarray(X)


@not_implemented_for('directed')
def algebraic_connectivity(G, weight='weight', tol=1e-8, method='tracemin'):
    """Return the algebraic connectivity of a connected undirected graph.

    The algebraic connectivity of a connected undirected graph is the second
    smallest eigenvalue of its Laplacian matrix.

    Parameters
    ----------
    G : NetworkX graph
        An undirected graph.

    weight : string or None
        The data key used to determine the weight of each edge. If None, then
        each edge has unit weight. Default value: None.

    tol : float
        Tolerance of eigenvalue computation. Default value: 1e-8.<commit_msg>Hide pcg inside tracemin_fiedler<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

__all__ = ['algebraic_connectivity', 'fiedler_vector']


def _tracemin_fiedler(L, tol):
    """Compute the Fiedler vector of L using the TRACEMIN-Fiedler algorithm.
    """
    from numpy import (array, asmatrix, asarray, dot, matrix, ndarray, reshape,
                       zeros)
    from numpy.linalg import norm
    from scipy.linalg import eigh, solve

    n = L.shape[0]
    q = 2
    # Jacobi preconditioner.
    M = 1 / L.diagonal()

    Lnorm = max(asarray(abs(L).sum(axis=0))[0, :])

    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

    def gram_schmidt(X):
        """Return an orthonormalized copy of X.
        """
        V = asarray(X.copy())
        for j in range(q):
            for k in range(j):
                V[:, j] -= dot(V[:, k], V[:, j]) * V[:, k]
            V[:, j] /= norm(V[:, j])
        return asmatrix(V)

    def pcg(b, tol):
        """Jacobi-preconditioned conjugate gradient method.
        """
        x = zeros(b.shape)
        r = b.copy()
        z = M * r
        rz = dot(r, z)
        p = z

        tol *= norm(r, 1)
        while True:
            Lp = L * p
            alpha = rz / dot(p, Lp)
            x += alpha * p
            r -= alpha * Lp
            if norm(r, 1) < tol:
                return x
            z = M * r
            beta = dot(r, z)
            beta, rz = beta / rz, beta
            p = z + beta * p

    # Randomly initialize eigenvectors.
    X = asmatrix(reshape([normalvariate(0, 1) for i in range(n * q)], (n, q),
                         order='F'))
    project(X)
    W = asmatrix(ndarray((n, q), order='F'))

    first = True
    while True:
        V = gram_schmidt(X)
        # Compute interation matrix H.
        H = V.transpose() * L * V
        sigma, Y = eigh(H, overwrite_a=True)
        # Test for convergence.
        if not first:
            r = L * X[:, 0] - sigma[0] * X[:, 0]
            if norm(r, 1) < tol * Lnorm:
                break
        else:
            first = False
        # Compute Ritz vectors.
        X = V * Y
        # Solve saddle point problem using the Schur complement.
        for j in range(q):
            asarray(W)[:, j] = pcg(asarray(X)[:, j], tol / 10)
        project(W)
        S = X.transpose() * W  # Schur complement
        N = solve(S, X.transpose() * X, overwrite_a=True, overwrite_b=True,
                  check_finite=False)
        X = W * N

    return sigma, asarray(X)


@not_implemented_for('directed')
def algebraic_connectivity(G, weight='weight', tol=1e-8, method='tracemin'):
    """Return the algebraic connectivity of a connected undirected graph.

    The algebraic connectivity of a connected undirected graph is the second
    smallest eigenvalue of its Laplacian matrix.

    Parameters
    ----------
    G : NetworkX graph
        An undirected graph.

    weight : string or None
        The data key used to determine the weight of each edge. If None, then
        each edge has unit weight. Default value: None.

    tol : float
        Tolerance of eigenvalue computation. Default value: 1e-8.
{'fraction_non_alphanumeric': 0.12174036281179139, 'fraction_numerical': 0.006802721088435374, 'mean_word_length': 1.9137076796036334, 'pattern_counts': {'":': 0, '<': 15, '<?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': '514881', 'n_tokens_mistral': 2378, 'n_tokens_neox': 2247, 'n_words': 761}