# experiment met een genetisch algoritme voor de kanalenplanning
# het genetische zit er nu nauwelijks in, en wat er in zit is ongetwijfeld
# fout. wat er wel goed in zit is het parseren van de bestaande situatie en
# het scoren van (nu random) configuraties.

# de score functie is nu redelijk simplistisch:
#   - de score van een combinatie van twee interfaces op een node is 1 als er
#     twee of meer kanalen tussen zitten, en -1 als dat niet zo is
#   - de score van een node is de som van de scores van alle combinaties van
#     interfaces van die node, maal het aantal interfaces. dat laatste omdat
#     een positieve score hebben knapper is met meer interfaces dan met minder,
#     dus dat moet beloond. een negatieve score is erger met meer interfaces
#     (belangrijker node, waarschijnlijk) dan met minder, dus dat moet
#     bestraft.
#   - de totale score is de som van de scores van de nodes
#
# het stukje "genetisch" aan het einde is afgeraffeld. mutation en
# recombination gebeuren op de oplossing zelf ipv op een bitstring
# representatie. selection is dom en neemt gewoon de helft beste oplossingen.
import re
import random
import os

# deze twee zijn nodig voor de evaluatie van een configuratie
nodes = {}		# lijst van Node instanties
groups = []		# lijst van Group instanties

population = []

# gegeven een lijst, geef de lijst zonder dubbele elementen
def uniq(l):
	d = {}
	for e in l:
		d[e] = 1
	return d.keys()

class Node:
	def __init__(self, name, wis):
		self.name = name
		self.wis = wis
		for wi in wis:
			wi.setNode(self)
	def wi_byname(self, name):
		wi = filter(lambda wi: wi.name == name, self.wis)
		assert len(wi) == 1
		return wi[0]
	def score(self):
		score = 0
		for i in range(len(self.wis)):
			wi_i = self.wis[i]
			if wi_i.group == None:
				# orphaned interface
				continue
			if wi_i.group.channel == None:
				print "huh?"
			for j in range(len(self.wis)):
				if i != j:
					wi_j = self.wis[j]
					if wi_j.group == None:
						continue
					diff = abs(wi_i.group.channel - wi_j.group.channel)
					if diff > 2:
						score = score + 1
					else:
						score = score - 1
		score = score * len(self.wis)
		return score

class WI:
	def __init__(self, name):
		self.name = name
		self.node = None
		self.group = None
		self.omni = 0
	def setNode(self, node):
		self.node = node
	def setGroup(self, group):
		self.group = group

class WIGroup:
	def __init__(self, name):
		self.name = name
		self.wis = []
		self.channel = None
	def add_wi(self, wi):
		self.wis.append(wi)
		wi.setGroup(self)

class Configuration:
	def __init__(self):
		self.conf = None
		self.calculated_score = None
	def copy(self):
		c = Configuration()
		c.conf = self.conf[:]
		c.calculated_score = None
		return c
	def randomize(self):
		self.conf = [random.randint(1, 13) for i in range(len(groups))]
		self.calculated_score = None
	def score(self):
		assert len(self.conf) == len(groups)
		if self.calculated_score != None:
			return self.calculated_score
		for i in range(len(self.conf)):
			groups[i].channel = self.conf[i]
		score = 0
		for node in nodes.values():
			score = score + node.score()
		self.calculated_score = score
		return score
	def mutate(self, rate):
		for i in range(len(groups)):
			if random.random() <= rate:
				self.conf[i] = random.randint(1, 13)
	def crossover(self, partner, numpoints):
		# pick the crossover points
		points = [random.randint(0, len(groups) - 1) for i in range(numpoints)]
		points.sort()
		conf = []
		who = 0
		lastpoint = 0
		while len(points):
			point = points.pop(0)
			if who == 0:
				l = self.conf[lastpoint:point]
				who = 1
			else:
				l = partner.conf[lastpoint:point]
				who = 0
			conf.extend(l)
			lastpoint = point
		if who == 0:
			l = self.conf[lastpoint:]
		else:
			l = partner.conf[lastpoint:]
		conf.extend(l)
		assert len(conf) == len(groups)
		self.conf = conf


# BEGIN UGLY PARSING CODE

ipdict = {}
ipnr_node = {}
node_ipnr = {}
node_links = {}

def parse_wleiden_conf(lines):
	ipnr = None
	wi = None
	peer = None
	omni = 0
	for l in lines:
		if wi != None:
			match = re.match("^\EW.*", l)
			if match != None:
				wi = None
				ipnr = None
				peer = None
				continue
			match = re.match("^SDESC=omni.*", l)
			if match != None:
				omni = 1
			match = re.match("^IP=([0-9]*\.[0-9]*\.[0-9]*\.[0-9]*).*", l)
			if match != None:
				ipnr = match.group(1)
				if not node_ipnr.has_key(nodename):
					node_ipnr[nodename] = []
				node_ipnr[nodename].append(ipnr)
				ipnr_node[ipnr] = nodename
			match = re.match("^POINT_TO_POINT=([0-9]*\.[0-9]*\.[0-9]*\.[0-9]*).*", l)
			if match != None:
				peer = match.group(1)
				if not node_links.has_key(nodename):
					node_links[nodename] = []
				node_links[nodename].append( (peer, wi) )
		else:
			match = re.match("^\$nodename='([^']*)';.*", l)
			if match != None:
				nodename = match.group(1).lower()
			match = re.match("^\$config{'(wi[0-9]*).*", l)
			if match != None:
				wi = match.group(1)
				omni = 0

# gegeven een file met filenames van wleiden.conf's, parseer ze allemaal en
# vul de datastructuren
def parse_metafile(filename):
	for fname in open(filename).readlines():
		parse_wleiden_conf(open(fname[:-1]).readlines())
	for nodename in node_ipnr.keys():
		wis = []
		if node_links.has_key(nodename):
			d = {}
			for peer, wi in node_links[nodename]:
				if not d.has_key(wi):
					wis.append(WI(wi))
					d[wi] = 1
		node = Node(nodename, wis)
		nodes[nodename] = node

	for nodename in node_links.keys():
		node = nodes[nodename]

		for peerip, winame in node_links[nodename]:
			wi = node.wi_byname(winame)
			if not ipnr_node.has_key(peerip):
				print "Warning: node %s links to phantom IP %s" % (nodename, peerip)
				continue
			peername = ipnr_node[peerip]
			bail = 0
			for peerspeerip, peerswiname in node_links[peername]:
				if not ipnr_node.has_key(peerspeerip):
					print "Warning: node %s links to phantom IP %s" % (nodename, peerspeerip)
					bail = 1
					break
				if ipnr_node[peerspeerip] == nodename:
					break
			if bail:
				continue
			peer = nodes[peername]
			peerwi = peer.wi_byname(peerswiname)
			# komt wi voor deze node al voor in de bestaande
			# groepen?
			group = None
			for i in range(len(groups)):
				if filter(lambda wi: wi.node.name == nodename and wi.name == winame, groups[i].wis) != []:
					group = groups[i]
					break
			if group == None:
				for i in range(len(groups)):
					if filter(lambda wi: wi.node.name == peername and wi.name == peerswiname, groups[i].wis) != []:
						group = groups[i]
						break
				if group == None:
					# nee. maak een groep en voeg beide
					# endpoints toe
					group = WIGroup("group%d" % len(groups))
					group.add_wi(wi)
					groups.append(group)
			group.add_wi(peerwi)
	for group in groups:
		group.wis = uniq(group.wis)

# END UGLY PARSING CODE

def plot_configuration(conf, out):
	out.write("digraph plot {\n")
	for i in range(len(groups)):
		out.write("group%s [label=\"%d\"]\n" % (i, conf[i]))
	for nodename in nodes.keys():
		for wi in nodes[nodename].wis:
			if wi.group == None:
				continue
			out.write("%s -> %s\n" % (nodename, wi.group.name))
	out.write("}")

parse_metafile('l')

for i in range(20):
	conf = Configuration()
	conf.randomize()
	population.append(conf)

for iteration in range(1000):
	for i in range(0, 9):
		p = population[i].copy()
		population[i].crossover(population[i + 10], random.randint(1, 4) * 2)
		population[i + 10] = p
		population[i + 10].mutate(0.05)
	population.sort(lambda a, b: cmp(b.score(), a.score()))
print population[0].score()
plot_configuration(population[0].conf, open("foo.dot", 'w'))
os.system('neato -Gstart=foo -Goverlap=false/scale -Gsplines=true -Gsep=2 -Gratio=fill -Gnslimit=50.0 -Grotate=90 -Gsize="11,7.5" -Tps -o channelga.ps foo.dot')