#routing[vrchol][prichozi smer][odchozi smery]

#routing 0 po smeru rucicek
routing_text_0 = """1 	5: 0,2,6,5 	6: 5,0,2,6 	2: 6,5,5,2 	0: 5,0,2,6
2 	1: 0,3,6,1 	0: 3,6,1,0 	3: 6,1,0,3 	6: 1,0,3,6
3 	2: 0,7,6,2 	0: 7,6,2,0 	7: 6,2,0,7 	6: 2,0,7,6
4 	8: 7,0,5,8 	7: 0,5,8,7 	0: 5,8,7,0 	5: 8,7,0,5 
5 	4: 1,9,8,4 	1: 9,8,4,1 	9: 8,4,1,9 	8: 4,1,9,8
6 	1: 2,3,9,1 	2: 3,9,1,2 	3: 9,1,2,3 	9: 1,2,3,9
7 	3: 4,8,9,3 	4: 8,9,3,4 	8: 9,3,4,8 	9: 3,4,8,9
8  	7: 4,5,9,7 	4: 5,9,7,4 	5: 9,7,4,5 	9: 7,4,5,9
9 	5: 6,7,8,5 	6: 7,8,5,6 	7: 8,5,6,7 	8: 5,6,7,8"""

#routing 1 vracim se az posledni, jdu do nizssiho bfs cisla, po smeru
routing_text_1 = """1 	5: 0,2,6,5 	6: 0,2,5,6 	2: 0,5,6,2 	0: 2,6,5,0
2 	1: 0,3,6,1 	0: 3,6,1,0 	3: 6,1,0,3 	6: 1,0,3,6
3 	2: 0,7,6,2 	0: 7,6,2,0 	7: 6,2,0,7 	6: 2,0,7,6
4 	8: 7,0,5,8 	7: 0,5,8,7 	0: 5,8,7,0 	5: 8,7,0,5 
5 	4: 1,9,8,4 	1: 9,8,4,1 	9: 8,4,1,9 	8: 4,1,9,8
6 	1: 2,3,9,1 	2: 3,9,1,2 	3: 9,1,2,3 	9: 1,2,3,9
7 	3: 4,8,9,3 	4: 8,9,3,4 	8: 9,3,4,8 	9: 3,4,8,9
8  	7: 4,5,9,7 	4: 5,9,7,4 	5: 9,7,4,5 	9: 7,4,5,9
9 	5: 6,7,8,5 	6: 7,8,5,6 	7: 8,5,6,7 	8: 5,6,7,8"""

#routing vychazejici z ctyr koster 
routing_text_3 = """1 	5: 6,5,2,0 	6: 0,6,5,2 	2: 5,2,0,6 	0: 2,6,5,0
2 	1: 3,6,0,1 	0: 3,6,1,0 	3: 0,1,3,6 	6: 1,3,6,0
3 	2: 0,6,2,7 	0: 7,6,2,0 	7: 0,6,2,7 	6: 2,7,0,6
4 	8: 7,5,8,0 	7: 0,7,5,8 	0: 5,8,7,0 	5: 0,7,5,8 
5 	4: 9,1,4,8 	1: 4,8,9,1 	9: 1,4,8,9 	8: 4,8,9,1
6 	1: 3,2,9,1 	2: 1,3,2,9 	3: 1,3,2,9 	9: 1,3,2,9
7 	3: 4,3,8,9 	4: 3,8,9,4 	8: 9,4,3,8 	9: 4,3,8,9
8  	7: 9,7,5,4 	4: 7,5,4,9 	5: 4,9,7,5 	9: 4,9,7,5
9 	5: 6,5,7,8 	6: 8,6,5,7 	7: 5,7,8,6 	8: 6,5,7,8"""

#routing resicici zvlast krouzek (viz papir) a zbytek z dalky,boku: 1.bliz 2.po smeru 3.proti 4.dal, z blizka se vracim posledni
routing_text_4 = """1 	5: 0,2,6,5   	6: 0,2,6,5 	2: 0,5,6,2 	0: 5,0,2,6
2 	1: 0,3,1,6 	0: 6,0,3,1	3: 0,1,3,6 	6: 0,1,3,6
3 	2: 0,7,6,2 	0: 7,0,2,6 	7: 0,2,6,7 	6: 0,2,6,7
4 	8: 0,7,5,8 	7: 0,5,7,8 	0: 7,5,8,0 	5: 0,7,5,8 
5 	4: 1,9,4,8 	1: 4,9,8,1 	9: 1,4,9,8 	8: 1,4,9,8
6 	1: 3,2,1,9 	2: 3,1,2,9 	3: 1,2,3,9 	9: 3,1,2,9
7 	3: 9,4,8,3 	4: 3,9,4,8 	8: 3,9,4,8 	9: 3,4,9,8
8  	7: 4,5,9,7 	4: 5,9,7,4 	5: 9,7,4,5 	9: 7,4,5,9
9 	5: 6,7,5,8 	6: 5,7,8,6 	7: 6,5,7,8 	8: 6,5,7,8"""

#routing resicici zvlast krouzek (viz 2.papir) a zbytek z dalky,boku: 1.bliz 2.po smeru 3.proti 4.dal, z blizka se vracim posledni
routing_text_5 = """1 	5: 0,2,6,5   	6: 0,5,2,6 	2: 0,5,2,6 	0: 5,2,6,0
2 	1: 0,3,6,1 	0: 6,3,1,0	3: 0,1,6,3 	6: 0,3,1,6
3 	2: 0,6,2,7 	0: 7,2,6,0 	7: 0,2,6,7 	6: 0,2,6,7
4 	8: 0,7,5,8 	7: 0,5,7,8 	0: 7,5,8,0 	5: 0,7,5,8 
5 	4: 1,9,4,8 	1: 4,9,8,1 	9: 1,4,9,8 	8: 1,4,9,8
6 	1: 2,3,1,9 	2: 1,3,2,9 	3: 1,9,2,3 	9: 2,3,1,9
7 	3: 9,4,8,3 	4: 3,9,4,8 	8: 3,9,4,8 	9: 3,4,9,8
8  	7: 4,5,9,7 	4: 5,9,7,4 	5: 9,7,4,5 	9: 7,4,5,9
9 	5: 6,7,5,8 	6: 5,7,8,6 	7: 6,5,7,8 	8: 6,5,7,8"""

trees1=[[0,5,1,7,0,4,2,4,5,7],[0,2,3,0,7,8,9,3,4,8],[0,0,6,6,5,9,1,8,9,6],[0,6,0,2,8,1,3,9,7,5]]

#hrany meho grafu
edges0 = [(0,1),(0,2),(0,3),(0,4),(1,2),(1,5),(1,6),(2,3),(2,6),(3,6),(3,7),(4,5),(4,7),(4,8),(5,8),(5,9),(6,9),(7,8),(7,9),(8,9)]

def print_routing(table):
	for i in range(1,10):
		text = "Tabulka pro vrchol %s: " % i
		for j in range(0,10):
			if table[i][j] <> []:
				text2 = "%s:[" %j
				for k in table[i][j]:
					text2 += "%s," %k
				text += text2 + "], "
		print text

def parse_routnig_text(text):
	routing = [ [[]]*10 for i in range(10) ]
	routing[0] = [[0]]*10
	lines = text.split("\n")
	for line in lines:
		vertex = int(line.split("\t")[0])
		directions = line.split("\t")[1:]
		for d in directions:
			previous = int(d.split(":")[0])
			t = [int(x) for x in d.split(":")[1].split(",")]
			routing[vertex][previous] = t
	return routing

def routing_from_tree(trees):
	routing = [ [[]]*10 for i in range(10) ]
	for c in range(4):
		for u in range(0,10):
			for v in range(0,10):
                                #presla jsem z vrchlou u do vrcholu v
				if trees[c][u] == v:
					routing[v][u] = [ (trees[(c+i)%4][v]) for i in range(4) ]
	return routing

##############################################################################################

#fib = [0,1, lambda a: fib[a-1]+fib[a-2] for i in range (20) ] 

#simuluje jeden krok routingu
def next(current,previous,table,disconnect):
	for n in table[current][previous]:
		if (not (current,n) in disconnect) and (not (n,current) in disconnect): 
			return n
	print "auuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu"
	print current, previous, disconnect, table[current][previous]
	print_routing(table)
	
#simuluje routingy pro zacatky s konkretnima vyhozenyma hranama
def route(start1,start2,table,disconnect):
	r = range(0,25) #po 23 krocich je bud v cili nebo nektera hrana byla navstivena 2x => cyklus
	r[0] = start1
	r[1] = start2
	for i in range(2,25):
		r[i]=next(r[i-1],r[i-2],table,disconnect)
	return r


def disconnect(edges):
	ch = []
	for i in range (0,20):
		for j in range (i+1,20):
			for k in range (j+1,20):
				ch += [[edges[i],edges[j],edges[k]]]
	return ch	


def reverse(a):
	return (a[1],a[0])

#overi zda routing je validni 
def try_table(table,edges):
	kolik = 0
	kolik2 = 0
	routes = []
	for s1 in range(0,10):
		for s2 in range(0,10):
			if ((s1,s2) in edges) or ((s2,s1) in edges):
				for dis in disconnect(edges):
					kolik += 1
					r = route(s1,s2,table,dis)
					if r[len(edges)+1]<>0:
						print s1,s2,dis
						print r
						routes += r
						kolik2 +=1
	print "pokusu %s cyklu %s" % (kolik,kolik2)
#	print disconnect
#	print_routing(table)
	return routes 
#########################################################################

p = try_table( parse_routnig_text(routing_text_5) , edges0 )
#po = try_table( routing_from_tree(trees1) , edges0)