<commit_before>"""
Laplacian, adjacency matrix, and spectrum of graphs.

Uses Numeric.

"""
__author__ = """<NAME> (<EMAIL>)\<NAME> (<EMAIL>)\n<NAME>(<EMAIL>)"""
__date__ = "$Date: 2005-06-15 14:18:07 -0600 (Wed, 15 Jun 2005) $"
__credits__ = """"""
__revision__ = "$Revision: 1044 $"
#    Copyright (C) 2004,2005 by 
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html


try:
    import Numeric
except ImportError:
#    print "Import Error: Not able to import Python module Numeric"
    raise


def adj_matrix(G,u=None):
    """Return adjacency matrix of graph
    If u is defined return row of adjacency matrix at row u.
    """
    n=G.order()
    # make an dictionary that maps vertex name to position
    index={}
    count=0
    for a in G.nodes():
        index[a]=count
        count = count+1
    # the entire adjacency matrix
    if u == None:
        a = Numeric.zeros((n,n))
        for x in G.nodes():
            for y in G.neighbors(x):
                a[index[x],index[y]]=1
                a[index[y],index[x]]=1
    # one row of the adjacency matrix
    else:
        a = Numeric.zeros((n))
        for y in G.neighbors(u): 
            a[index[y]]=1
    return a            

def laplacian(G):
    """Return standard Laplacian of graph"""
    n=G.order()
    I=Numeric.identity(n)
    d=Numeric.array(G.degree())
    l=I*d-adj_matrix(G)
    return l            

def generalized_laplacian(G):
    """Return generalized Laplacian of graph

    See Spectral Graph Theory by <NAME>.

    """
    l=laplacian(G) # standard laplacian
    # build S=1/sqrt(T) matrix
    n=G.order()
    I=Numeric.identity(n)
    d=Numeric.array(G.degree())
    tmhalf=Numeric.where(d, 1/Numeric.sqrt(d),0)
    S=I*tmhalf
    # multiply L = S l S
    L=Numeric.matrixmultiply(Numeric.matrixmultiply(S,l),S)
    return L 


def _test_suite():
    import doctest
    suite = doctest.DocFileSuite('../tests/spectrum.txt',package='networkx')
    return suite


if __name__ == "__main__":
    import sys
    import unittest
    if sys.version_info[:2] < (2, 4):
        print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2]
        sys.exit(-1)
    unittest.TextTestRunner().run(_test_suite())
    <commit_msg>Error in the calculation of the graph laplacian due to the random ordering of G.degree() compared to an iteration over the nodes of the adjacency matrix now fixed. Thanks to <NAME> for pointing this out and suggesting a fix.<commit_after>"""
Laplacian, adjacency matrix, and spectrum of graphs.

Uses Numeric.

"""
__author__ = """<NAME> (<EMAIL>)\<NAME> (<EMAIL>)\n<NAME>(<EMAIL>)"""
__date__ = "$Date: 2005-06-15 14:18:07 -0600 (Wed, 15 Jun 2005) $"
__credits__ = """"""
__revision__ = "$Revision: 1044 $"
#    Copyright (C) 2004,2005 by 
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html


try:
    import Numeric
except ImportError:
#    print "Import Error: Not able to import Python module Numeric"
    raise


def adj_matrix(G,u=None):
    """Return adjacency matrix of graph
    If u is defined return row of adjacency matrix at row u.
    """
    n=G.order()
    # make an dictionary that maps vertex name to position
    index={}
    count=0
    for a in G.nodes():
        index[a]=count
        count = count+1
    # the entire adjacency matrix
    if u == None:
        a = Numeric.zeros((n,n))
        for x in G.nodes():
            for y in G.neighbors(x):
                a[index[x],index[y]]=1
                a[index[y],index[x]]=1
    # one row of the adjacency matrix
    else:
        a = Numeric.zeros((n))
        for y in G.neighbors(u): 
            a[index[y]]=1
    return a            

def laplacian(G):
    """Return standard Laplacian of graph"""
    # this isn't the most efficient way to do this...
    n=G.order()
    I=Numeric.identity(n)
    A=adj_matrix(G)
    D=I*Numeric.sum(A)
    L=D-A
    return L

def generalized_laplacian(G):
    """Return generalized Laplacian of graph

    See Spectral Graph Theory by <NAME>.

    """
    # this isn't the most efficient way to do this...
    n=G.order()
    I=Numeric.identity(n)
    A=adj_matrix(G)
    D=I*Numeric.sum(A)
    L=D-A
    d=sum(A)
    T=I*(Numeric.sqrt(1./d))
    L=I-Numeric.dot(T,Numeric.dot(A,T))
    return L

def _test_suite():
    import doctest
    suite = doctest.DocFileSuite('../tests/spectrum.txt',package='networkx')
    return suite


if __name__ == "__main__":
    import sys
    import unittest
    if sys.version_info[:2] < (2, 4):
        print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2]
        sys.exit(-1)
    unittest.TextTestRunner().run(_test_suite())
    
{'fraction_non_alphanumeric': 0.1377354668827223, 'fraction_numerical': 0.020255215718047396, 'mean_word_length': 2.6469719350073855, 'pattern_counts': {'":': 2, '<': 38, '<?xml version=': 0, '>': 36, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, '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': '4852172', 'n_tokens_mistral': 1820, 'n_tokens_neox': 1672, 'n_words': 481}