<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,nodelist=None):
    """Return adjacency matrix of graph

    If nodelist is defined return adjacency matrix with nodes in nodelist
    in the order specified.

    The value of the entry in the adjacency matrix is zero or one.
    E.g. self-loops, multi-edges, or weighted graphs are not handled.

    """
    if nodelist is None:
        nodelist=G.nodes()
    nlen=len(nodelist)    
    index=dict(zip(nodelist,range(nlen)))# dict mapping vertex name to position
    a = Numeric.zeros((nlen,nlen))
    for n1 in nodelist:
        nbrs=[n for n in G.neighbors(n1) if n in nodelist]
        for n2 in nbrs:
            a[index[n1],index[n2]]=1
            a[index[n2],index[n1]]=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.where(d,Numeric.sqrt(1./d),0))
    L=Numeric.dot(T,Numeric.dot(L,T))
    return L

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


if __name__ == "__main__":
    import os
    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)
    # directory of networkx package (relative to this)
    nxbase=sys.path[0]+os.sep+os.pardir
    sys.path.insert(0,nxbase) # prepend to search path
    unittest.TextTestRunner().run(_test_suite())
    <commit_msg>clear up some naming issues in laplacian:<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,nodelist=None):
    """Return adjacency matrix of graph

    If nodelist is defined return adjacency matrix with nodes in nodelist
    in the order specified.

    The value of the entry in the adjacency matrix is zero or one.
    E.g. self-loops, multi-edges, or weighted graphs are not handled.

    """
    if nodelist is None:
        nodelist=G.nodes()
    nlen=len(nodelist)    
    index=dict(zip(nodelist,range(nlen)))# dict mapping vertex name to position
    a = Numeric.zeros((nlen,nlen))
    for n1 in nodelist:
        nbrs=[n for n in G.neighbors(n1) if n in nodelist]
        for n2 in nbrs:
            a[index[n1],index[n2]]=1
            a[index[n2],index[n1]]=1
    return a            

def laplacian(G):
    """Return standard cobinatorial Laplacian of G"""
    # 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 normalized_laplacian(G):
    """Return normalized Laplacian of G

    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.where(d,Numeric.sqrt(1./d),0))
    L=Numeric.dot(T,Numeric.dot(L,T))
    return L

combinatorial_laplacian=laplacian
generalized_laplacian=normalized_laplacian


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


if __name__ == "__main__":
    import os
    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)
    # directory of networkx package (relative to this)
    nxbase=sys.path[0]+os.sep+os.pardir
    sys.path.insert(0,nxbase) # prepend to search path
    unittest.TextTestRunner().run(_test_suite())
    
{'fraction_non_alphanumeric': 0.13130151428023767, 'fraction_numerical': 0.021468276787425723, 'mean_word_length': 3.0169361046959198, 'pattern_counts': {'":': 2, '<': 37, '<?xml version=': 0, '>': 35, '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': '7279510', 'n_tokens_mistral': 1973, 'n_tokens_neox': 1801, 'n_words': 505}