graphs

graphs.py

from __future__ import division
import numpy as np
na = np.newaxis
from matplotlib import pyplot as plt

def adj_path(n):
    a = np.zeros((n,n))
    a.flat[1::a.shape[0]+1] = a.flat[a.shape[0]::a.shape[0]+1] = 1
    return a

def adj_grid((m,n)):
    return np.kron(np.eye(n),adj_path(m)) + np.kron(adj_path(n),np.eye(m))

def plot_spectral(A):
    L = np.diag(A.sum(1)) - A
    x,y = np.linalg.eigh(L)[1].T[1:3]
    for i,j in zip(*np.nonzero(np.triu(A,1))):
        plt.plot([x[i],x[j]],[y[i],y[j]],'b-')


def path_redblack_perm(n):
    perm = np.empty(n,dtype=int)
    perm[:(n+1)//2] = np.arange(0,n,2)
    perm[(n+1)//2:] = np.arange(1,n,2)
    return perm

def grid_redblack_perm((m,n)):
    A = np.tile((1,-1),(m+1)//2)[:m,na] * np.tile((1,-1),(n+1)//2)[:n]
    a = np.arange(m*n,dtype=int)
    return np.concatenate((a[A.flat == 1],a[A.flat == -1]))

from graphs import *
plot_spectral(adj_grid((10,10)))