#! /usr/bin/python

###############################
# Author : Alexandre Mouradian
# year : 2013
###############################


#input : - infile.xml -> node TA
#		 - graph -> description of the topology

#output : outfile.xml -> NTA + query.q

#graph example :
#
#0 1 2 3 4 
#1 0 4 
#2 0 4 
#3 0 4 
#4 0 1 2 3

import sys
import copy

try:
	from lxml import etree as ElementTree
except ImportError, e:
	try:
		from elementtree import ElementTree
	except ImportError, e:
		print '***'
		print '*** Error: Must install either ElementTree or lxml.'
		print '***'
		raise ImportError, 'must install either ElementTree or lxml'

class Node:
	def __init__(self):
		self.neighbors=[]
		self.myCliques=[]
	ID=0
	rank=100
	mts=0

#global variables
V=0
graph=[]
boolGraph=[]

def parseGraph(graphFile):#retreiving the graph from the file (parse 2 times)
	ifi=open(graphFile,'r')
	l=ifi.readline()
	i=0
	while l!="":#creates nodes
		ls=l.split()
		graph.append(Node())
		graph[i].ID=int(ls[0])
		i+=1
		l=ifi.readline()
	ifi=open(graphFile,'r')
	l=ifi.readline()
	
	i=0
	while l!="":#assigns neighbors to nodes
		ls=l.split()
		for j in range(1,len(ls)):
			for k in range(len(graph)):
				if graph[k].ID==int(ls[j]):
					graph[i].neighbors.append(graph[k])
		i+=1
		l=ifi.readline()

def setRank(node):#recursive algorithm to set ranks, call with the sink as parameter
	for i in range(len(node.neighbors)):
		if node.neighbors[i].rank>node.rank+1:
			node.neighbors[i].rank=node.rank+1
			setRank(node.neighbors[i])
		
def setAutomata(inFileName, outFileName):
	V=len(graph)
	sysString1=""
	sysString2="system"
	docO = ElementTree.parse(inFileName)#the new templates will be added to this tree (O is for ouput)
	ntaO = docO.getroot()
	for i in range(V):
		if graph[i].mts==1:
			sysString1=sysString1+" n"+str(i)+" = "+"Template(1,"+str(graph[i].rank)+","+str(i)+")"+";"#strings which create the system objects, case sender
		else:
			sysString1=sysString1+" n"+str(i)+" = "+"Template(0,"+str(graph[i].rank)+","+str(i)+")"+";"#strings which create the system objects, case not sender
		if i==0:
			sysString2=sysString2+" n"+str(i) #define the object which are part of the system
		else:
			sysString2=sysString2+", n"+str(i) 
	sysString2=sysString2+";"
	system=ntaO.find("system")
	system.text=sysString1+sysString2#put the text in the xml file
	
	declaration=ntaO.find("declaration")# this part sets the general declarations
	decString="const int N="+str(V)+"; const bool graph[N][N]={"	
	for i in range(len(boolGraph)):
		decString=decString+"{"
		for j in range(len(boolGraph)):
			decString=decString+str(boolGraph[i][j])
			if j<len(boolGraph)-1:
				decString=decString+","
		if i<len(boolGraph)-1:
			decString=decString+"},"
		else:
			decString=decString+"}"
	decString=decString+"};"
	declaration.text=decString+declaration.text #put the declaration string in the xml

	docO.write(outFileName)#write the tree in the output file
	

def main():
	args = sys.argv[1:]
	if len(args) != 3:
		print 'usage: checkConnectivity.py infile.xml outfile.xml graphFile'
		sys.exit(-1)
	parseGraph(sys.argv[3])
	ofiQueries=open("query.q",'w')

	for i in range(len(graph)):#allocate list
		boolGraph.append(len(graph)*[0])

	for i in range(len(graph)):#produce a matrix of booleans which represent the graph
		for j in range(len(graph[i].neighbors)):
			boolGraph[graph[i].ID][graph[i].neighbors[j].ID]=1

	V=len(graph)
	graph[0].rank=0
	setRank(graph[0])

	#these two loops aim at selecting the sender of the packet
	maxRank=0
	maxRankID=0
	for i in range(len(graph)):#search a node with a maximum rank value
		if maxRank<graph[i].rank:
			maxRank=graph[i].rank
			maxRankID=graph[i].ID

	for i in range(len(graph)):#then find the node and put mts value at one
		if maxRankID==graph[i].ID:
			graph[i].mts=1

	ofiQueries.write("A[] n0.m imply (z>"+str(maxRank*3)+" and z<="+str((maxRank+1)*5)+")\n")#write the query in a .q file
	print "NB", V
	setAutomata(args[0],args[1])

if __name__ == '__main__':
    main()