# local imports
from . import graph
#import .
from .algebraic import adjacencyEigenvectors
class SpectralColoring(object):
def __init__(self, G):
super(SpectralColoring, self).__init__()
self.graph = G
def prepareSpectrum(self):
spectrum = adjacencyEigenvectors(self.graph)
self.eigenvalues = spectrum[0]
self.eigenvectors = spectrum[1]
def valid(self, color):
for v in self.colors[color]:
for u in self.graph.neighbors(v):
if u in self.colors[color]:
return False
return True
def split(self, color, depth=0):
otherColor = self.nextColor
self.nextColor += 1
vs = self.colors[color]
self.colors[color] = [v for v in vs if self.eigenvectors[depth][v] >= 0]
self.colors[otherColor] = [v for v in vs if self.eigenvectors[depth][v] < 0]
if not self.valid(color):
self.split(color, depth=depth+1)
if not self.valid(otherColor):
self.split(otherColor, depth=depth+1)
def buildReverseDict(self):
self.coloring = {}
for color in self.colors:
for v in self.colors[color]:
self.coloring[v] = color
def run(self):
self.prepareSpectrum()
self.colors = {0 : set(self.graph.iterNodes())}
self.nextColor = 1
self.split(0)
self.buildReverseDict()
def getColoring(self):
return self.coloring