diff env/lib/python3.9/site-packages/networkx/linalg/laplacianmatrix.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/linalg/laplacianmatrix.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,366 @@
+"""Laplacian matrix of graphs.
+"""
+import networkx as nx
+from networkx.utils import not_implemented_for
+
+__all__ = [
+    "laplacian_matrix",
+    "normalized_laplacian_matrix",
+    "directed_laplacian_matrix",
+    "directed_combinatorial_laplacian_matrix",
+]
+
+
+@not_implemented_for("directed")
+def laplacian_matrix(G, nodelist=None, weight="weight"):
+    """Returns the Laplacian matrix of G.
+
+    The graph Laplacian is the matrix L = D - A, where
+    A is the adjacency matrix and D is the diagonal matrix of node degrees.
+
+    Parameters
+    ----------
+    G : graph
+       A NetworkX graph
+
+    nodelist : list, optional
+       The rows and columns are ordered according to the nodes in nodelist.
+       If nodelist is None, then the ordering is produced by G.nodes().
+
+    weight : string or None, optional (default='weight')
+       The edge data key used to compute each value in the matrix.
+       If None, then each edge has weight 1.
+
+    Returns
+    -------
+    L : SciPy sparse matrix
+      The Laplacian matrix of G.
+
+    Notes
+    -----
+    For MultiGraph/MultiDiGraph, the edges weights are summed.
+
+    See Also
+    --------
+    to_numpy_array
+    normalized_laplacian_matrix
+    laplacian_spectrum
+    """
+    import scipy.sparse
+
+    if nodelist is None:
+        nodelist = list(G)
+    A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
+    n, m = A.shape
+    diags = A.sum(axis=1)
+    D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format="csr")
+    return D - A
+
+
+@not_implemented_for("directed")
+def normalized_laplacian_matrix(G, nodelist=None, weight="weight"):
+    r"""Returns the normalized Laplacian matrix of G.
+
+    The normalized graph Laplacian is the matrix
+
+    .. math::
+
+        N = D^{-1/2} L D^{-1/2}
+
+    where `L` is the graph Laplacian and `D` is the diagonal matrix of
+    node degrees.
+
+    Parameters
+    ----------
+    G : graph
+       A NetworkX graph
+
+    nodelist : list, optional
+       The rows and columns are ordered according to the nodes in nodelist.
+       If nodelist is None, then the ordering is produced by G.nodes().
+
+    weight : string or None, optional (default='weight')
+       The edge data key used to compute each value in the matrix.
+       If None, then each edge has weight 1.
+
+    Returns
+    -------
+    N : Scipy sparse matrix
+      The normalized Laplacian matrix of G.
+
+    Notes
+    -----
+    For MultiGraph/MultiDiGraph, the edges weights are summed.
+    See to_numpy_array for other options.
+
+    If the Graph contains selfloops, D is defined as diag(sum(A,1)), where A is
+    the adjacency matrix [2]_.
+
+    See Also
+    --------
+    laplacian_matrix
+    normalized_laplacian_spectrum
+
+    References
+    ----------
+    .. [1] Fan Chung-Graham, Spectral Graph Theory,
+       CBMS Regional Conference Series in Mathematics, Number 92, 1997.
+    .. [2] Steve Butler, Interlacing For Weighted Graphs Using The Normalized
+       Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98,
+       March 2007.
+    """
+    import numpy as np
+    import scipy
+    import scipy.sparse
+
+    if nodelist is None:
+        nodelist = list(G)
+    A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
+    n, m = A.shape
+    diags = A.sum(axis=1).flatten()
+    D = scipy.sparse.spdiags(diags, [0], m, n, format="csr")
+    L = D - A
+    with scipy.errstate(divide="ignore"):
+        diags_sqrt = 1.0 / np.sqrt(diags)
+    diags_sqrt[np.isinf(diags_sqrt)] = 0
+    DH = scipy.sparse.spdiags(diags_sqrt, [0], m, n, format="csr")
+    return DH.dot(L.dot(DH))
+
+
+###############################################################################
+# Code based on
+# https://bitbucket.org/bedwards/networkx-community/src/370bd69fc02f/networkx/algorithms/community/
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def directed_laplacian_matrix(
+    G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
+):
+    r"""Returns the directed Laplacian matrix of G.
+
+    The graph directed Laplacian is the matrix
+
+    .. math::
+
+        L = I - (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} ) / 2
+
+    where `I` is the identity matrix, `P` is the transition matrix of the
+    graph, and `\Phi` a matrix with the Perron vector of `P` in the diagonal and
+    zeros elsewhere.
+
+    Depending on the value of walk_type, `P` can be the transition matrix
+    induced by a random walk, a lazy random walk, or a random walk with
+    teleportation (PageRank).
+
+    Parameters
+    ----------
+    G : DiGraph
+       A NetworkX graph
+
+    nodelist : list, optional
+       The rows and columns are ordered according to the nodes in nodelist.
+       If nodelist is None, then the ordering is produced by G.nodes().
+
+    weight : string or None, optional (default='weight')
+       The edge data key used to compute each value in the matrix.
+       If None, then each edge has weight 1.
+
+    walk_type : string or None, optional (default=None)
+       If None, `P` is selected depending on the properties of the
+       graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
+
+    alpha : real
+       (1 - alpha) is the teleportation probability used with pagerank
+
+    Returns
+    -------
+    L : NumPy matrix
+      Normalized Laplacian of G.
+
+    Notes
+    -----
+    Only implemented for DiGraphs
+
+    See Also
+    --------
+    laplacian_matrix
+
+    References
+    ----------
+    .. [1] Fan Chung (2005).
+       Laplacians and the Cheeger inequality for directed graphs.
+       Annals of Combinatorics, 9(1), 2005
+    """
+    import numpy as np
+    from scipy.sparse import spdiags, linalg
+
+    P = _transition_matrix(
+        G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
+    )
+
+    n, m = P.shape
+
+    evals, evecs = linalg.eigs(P.T, k=1)
+    v = evecs.flatten().real
+    p = v / v.sum()
+    sqrtp = np.sqrt(p)
+    Q = spdiags(sqrtp, [0], n, n) * P * spdiags(1.0 / sqrtp, [0], n, n)
+    I = np.identity(len(G))
+
+    return I - (Q + Q.T) / 2.0
+
+
+@not_implemented_for("undirected")
+@not_implemented_for("multigraph")
+def directed_combinatorial_laplacian_matrix(
+    G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
+):
+    r"""Return the directed combinatorial Laplacian matrix of G.
+
+    The graph directed combinatorial Laplacian is the matrix
+
+    .. math::
+
+        L = \Phi - (\Phi P + P^T \Phi) / 2
+
+    where `P` is the transition matrix of the graph and and `\Phi` a matrix
+    with the Perron vector of `P` in the diagonal and zeros elsewhere.
+
+    Depending on the value of walk_type, `P` can be the transition matrix
+    induced by a random walk, a lazy random walk, or a random walk with
+    teleportation (PageRank).
+
+    Parameters
+    ----------
+    G : DiGraph
+       A NetworkX graph
+
+    nodelist : list, optional
+       The rows and columns are ordered according to the nodes in nodelist.
+       If nodelist is None, then the ordering is produced by G.nodes().
+
+    weight : string or None, optional (default='weight')
+       The edge data key used to compute each value in the matrix.
+       If None, then each edge has weight 1.
+
+    walk_type : string or None, optional (default=None)
+       If None, `P` is selected depending on the properties of the
+       graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
+
+    alpha : real
+       (1 - alpha) is the teleportation probability used with pagerank
+
+    Returns
+    -------
+    L : NumPy matrix
+      Combinatorial Laplacian of G.
+
+    Notes
+    -----
+    Only implemented for DiGraphs
+
+    See Also
+    --------
+    laplacian_matrix
+
+    References
+    ----------
+    .. [1] Fan Chung (2005).
+       Laplacians and the Cheeger inequality for directed graphs.
+       Annals of Combinatorics, 9(1), 2005
+    """
+    from scipy.sparse import spdiags, linalg
+
+    P = _transition_matrix(
+        G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
+    )
+
+    n, m = P.shape
+
+    evals, evecs = linalg.eigs(P.T, k=1)
+    v = evecs.flatten().real
+    p = v / v.sum()
+    Phi = spdiags(p, [0], n, n)
+
+    Phi = Phi.todense()
+
+    return Phi - (Phi * P + P.T * Phi) / 2.0
+
+
+def _transition_matrix(G, nodelist=None, weight="weight", walk_type=None, alpha=0.95):
+    """Returns the transition matrix of G.
+
+    This is a row stochastic giving the transition probabilities while
+    performing a random walk on the graph. Depending on the value of walk_type,
+    P can be the transition matrix induced by a random walk, a lazy random walk,
+    or a random walk with teleportation (PageRank).
+
+    Parameters
+    ----------
+    G : DiGraph
+       A NetworkX graph
+
+    nodelist : list, optional
+       The rows and columns are ordered according to the nodes in nodelist.
+       If nodelist is None, then the ordering is produced by G.nodes().
+
+    weight : string or None, optional (default='weight')
+       The edge data key used to compute each value in the matrix.
+       If None, then each edge has weight 1.
+
+    walk_type : string or None, optional (default=None)
+       If None, `P` is selected depending on the properties of the
+       graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
+
+    alpha : real
+       (1 - alpha) is the teleportation probability used with pagerank
+
+    Returns
+    -------
+    P : NumPy matrix
+      transition matrix of G.
+
+    Raises
+    ------
+    NetworkXError
+        If walk_type not specified or alpha not in valid range
+    """
+    import numpy as np
+    from scipy.sparse import identity, spdiags
+
+    if walk_type is None:
+        if nx.is_strongly_connected(G):
+            if nx.is_aperiodic(G):
+                walk_type = "random"
+            else:
+                walk_type = "lazy"
+        else:
+            walk_type = "pagerank"
+
+    M = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, dtype=float)
+    n, m = M.shape
+    if walk_type in ["random", "lazy"]:
+        DI = spdiags(1.0 / np.array(M.sum(axis=1).flat), [0], n, n)
+        if walk_type == "random":
+            P = DI * M
+        else:
+            I = identity(n)
+            P = (I + DI * M) / 2.0
+
+    elif walk_type == "pagerank":
+        if not (0 < alpha < 1):
+            raise nx.NetworkXError("alpha must be between 0 and 1")
+        # this is using a dense representation
+        M = M.todense()
+        # add constant to dangling nodes' row
+        dangling = np.where(M.sum(axis=1) == 0)
+        for d in dangling[0]:
+            M[d] = 1.0 / n
+        # normalize
+        M = M / M.sum(axis=1)
+        P = alpha * M + (1 - alpha) / n
+    else:
+        raise nx.NetworkXError("walk_type must be random, lazy, or pagerank")
+
+    return P