network - shortest path algorithm python
Encontrar un tour euleriano (9)
Estoy tratando de resolver un problema en Udacity descrito de la siguiente manera:
# Find Eulerian Tour
#
# Write a function that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]
Se me ocurrió la siguiente solución, que aunque no es tan elegante como algunos de los algoritmos recursivos, parece funcionar dentro de mi caso de prueba.
def find_eulerian_tour(graph):
tour = []
start_vertex = graph[0][0]
tour.append(start_vertex)
while len(graph) > 0:
current_vertex = tour[len(tour) - 1]
for edge in graph:
if current_vertex in edge:
if edge[0] == current_vertex:
current_vertex = edge[1]
elif edge[1] == current_vertex:
current_vertex = edge[0]
else:
# Edit to account for case no tour is possible
return False
graph.remove(edge)
tour.append(current_vertex)
break
return tour
graph = [(1, 2), (2, 3), (3, 1)]
print find_eulerian_tour(graph)
>> [1, 2, 3, 1]
Sin embargo, al enviar esto, el alumno me rechaza. Estoy haciendo algo mal? No puedo ver ningún error
Aquí hay un caso que su algoritmo no puede manejar: el gráfico completo en 4 vértices. Al realizar un print tour , obtienes:
>>> cg4 = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
>>> find_eulerian_tour(cg4)
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 0]
[0, 1, 2, 0, 3]
[0, 1, 2, 0, 3, 1]
[0, 1, 2, 0, 3, 1]
[0, 1, 2, 0, 3, 1]
[etc.]
Lo dejaré para que encuentre el problema con su enfoque; podría buscar fácilmente en Google una implementación completa, ya que como no lo hizo, supongo que desea divertirse averiguándolo por usted mismo. : ^)
Editar:
Hmmph. Admito que pensé que era simplemente un error fallido al principio. De todos modos, @WolframH me gano un ejemplo actualizado, pero también puedes ver el gráfico completo en 5 vértices, donde tu código da
[0, 1, 2, 0, 3, 1, 4, 0]
y pierde los bordes (2,3), (2,4) y (3,4).
La pregunta se puede resolver fácilmente que las soluciones anteriores que usan recursión simple.
def find_eulerian_tour(graph):
tour=[]
find_tour(graph[0][0],graph,tour)
return tour
def find_tour(u,E,tour):
for (a,b) in E:
if a==u:
E.remove((a,b))
find_tour(b,E,tour)
elif b==u:
E.remove((a,b))
find_tour(a,E,tour)
tour.insert(0,u)
Este código funciona para cualquier lista de entrada de tuplas y devuelve una lista de la gira. Pls envía sugerencias y cambios si los hay. Gracias @WolframH: Tu código no funciona si existe un bucle en el gráfico y las tuplas se ingresan solo para que falle tu código.
Estaba pasando por el mismo curso en Udacity. E implementé el algoritmo de Hierholzer después de leerlo de Wikipedia. Aquí está el enlace al algoritmo https://en.wikipedia.org/wiki/Eulerian_path
Y abajo está mi código. Sin duda, fue aceptado por el clasificador (después de hacer algunos cambios de Python3 a Python2). :)
#!/usr/bin/env python3
# Find Eulerian Tour
#
# Write a program that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]
def get_a_tour():
''''''This function returns a possible tour in the current graph and removes the edges included in that tour, from the graph.''''''
global graph
nodes_degree = {} # Creating a {node: degree} dictionary for current graph.
for edge in graph:
a, b = edge[0], edge[1]
nodes_degree[a] = nodes_degree.get(a, 0) + 1
nodes_degree[b] = nodes_degree.get(b, 0) + 1
tour =[] # Finding a tour in the current graph.
loop = enumerate(nodes_degree)
while True:
try:
l = loop.__next__()
index = l[0]
node = l[1]
degree = nodes_degree[node]
try:
if (tour[-1], node) in graph or (node, tour[-1]) in graph:
tour.append(node)
try:
graph.remove((tour[-2], tour[-1]))
nodes_degree[tour[-1]] -= 1 # Updating degree of nodes in the graph, not required but for the sake of completeness.
nodes_degree[tour[-2]] -= 1 # Can also be used to check the correctness of program. In the end all degrees must zero.
except ValueError:
graph.remove((tour[-1], tour[-2]))
nodes_degree[tour[-1]] -= 1
nodes_degree[tour[-2]] -= 1
except IndexError:
tour.append(node)
except StopIteration:
loop = enumerate(nodes_degree)
if len(tour) > 2:
if tour[0] == tour[-1]:
return tour
def get_eulerian_tour():
''''''This function returns a Eulerian Tour for the input graph.''''''
global graph
tour = get_a_tour()
if graph: # If stuck at the beginning, finding additional tour in the graph.
loop = enumerate(tour[: -1])
l = loop.__next__()
i = l[0]
node = l[1]
try:
while True:
if node in list(zip(*graph))[0] or node in list(zip(*graph))[1]:
t = get_a_tour() # Retreivng the additional tour
j = t.index(node)
tour = tour[ : i] + t[j:-1] + t[ :j+1] + tour[i+1: ] # Joining the two tours.
if not graph: # Found Eulerian Tour
return tour # Returning the Eulerian Tour
loop = enumerate(tour[: -1]) # Still stuck? Looping back to search for another tour.
l = loop.__next__()
i = l[0]
node = l[1]
except StopIteration: # Oops! seems like the vertices in the current tour cannot connect to rest of the edges in the graph.
print("Your graph doesn''t seem to be connected")
exit()
else: # Found the Eulerian Tour in the very first call. Lucky Enough!
return tour
# Sample inputs
# graph = [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (4, 6)]
# graph = [(1, 2), (1, 3), (2, 3)]
# graph = [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (4, 6), (9, 10), (10, 11), (11, 9)]
# graph = [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (4, 6), (2, 7), (7, 8), (8, 2)]
# graph = [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (4, 6), (1, 5), (5, 6), (1, 6)]
# graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
# graph = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
# graph = [(2, 6), (4, 2), (5, 4), (6, 5), (6, 8), (7, 9), (8, 7), (9, 6)]
# creating a {node: degree} dictionary
nodes_degree = {}
for edge in graph:
a, b = edge[0], edge[1]
nodes_degree[a] = nodes_degree.get(a, 0) + 1
nodes_degree[b] = nodes_degree.get(b, 0) + 1
#checking degree
degrees = nodes_degree.values() # remember it return a view
for degree in degrees:
if degree % 2:
print("Your graph have one or more nodes with odd degrees. Hence an Eulerian Tour is impossible.")
exit()
#finding Eulerian Tour
tour = get_eulerian_tour()
print(tour)
Espero que esto ayude.
Aunque el código falla para gráficos sin dirección pero funciona perfectamente con los dirigidos. Sin embargo, aún así, no resuelve el problema en cuestión desde el lado de Udacity, pero puede tratarse como una versión más baja de la misma. Por favor, no te moleste el Python mal usado ya que todavía soy nuevo en el lenguaje.
Se agregaron dos escenarios de prueba con un nivel bastante bueno de complejidad en la parte inferior.
initialNode = ''''
nglength = 0
in_graphLength = 0
normalizedGraph = list()
path = []
node_dict = {}
mod_flag = ''''
def find_eulerian_tour(graph):
global in_graphLength
in_graphLength = len(graph)
graph = normalize_graph(graph,[],-1,len(graph))
print (path)
return path
def normalize_graph(graph,nG,remNode,length):
counter = 0
global path
global initialNode
global in_graphLength
global nglength
global normalizedGraph
localGraph = list()
path = []
pathList = []
if(remNode != -1):
normalizedGraph = nG
baseNode = 0
if(len(normalizedGraph) != 0):
ini1, ini2 = normalizedGraph[0]
initialNode = ini1
a1,b1 = normalizedGraph[len(normalizedGraph) - 1]
baseNode = b1
if(remNode != -2):
graph.pop(remNode)
if(remNode == -1):
a,b = graph[0]
baseNode = b
normalizedGraph.append(graph[0])
initialNode = a
nglength = 1
graph.pop(0)
i = 0
if(len(graph) != 0):
for n1, n2 in graph:
i = i + 1
if(n1 == baseNode):
localGraph = graph[:]
if(isJunction((n1,n2),localGraph, nglength)):
graph.pop(i-1)
graph.append((n1,n2))
normalize_graph(graph, normalizedGraph, -2,in_graphLength)
break
else:
normalizedGraph.append((n1, n2))
nglength = nglength + 1
normalize_graph(graph, normalizedGraph, i - 1,in_graphLength)
break
else:
if( counter == 0):
counter = counter + 1
a0, b0 = normalizedGraph[0]
for n1, n2 in normalizedGraph:
path.append(n1)
path.append(a0)
path = path
return path
def isJunction((n1,n2), graph, nglength):
global node_dict
count = 0
if(len(graph) > 1):
for a1, a2 in graph:
if (n1 == a1):
count = count + 1
if (count > 1):
if(str(n1) not in node_dict):
key = str(n1)
node_dict[key] = count
else:
return handle_degree(n1)
return modification_needed((n1, n2), graph, nglength)
else:
return False
else:
return False
def handle_degree(n1):
global node_dict
key = str(n1)
if(node_dict.get(key) == 2):
return False
def modification_needed((n1,n2),graph, tmplength):
i = 0
global mod_flag
if( n2 == initialNode):
return True
if(len(graph) > 1):
for b1, b2 in graph:
if(n2 == b1):
i = i + 1
tmplength = tmplength + 1
if (b1,b2) in normalizedGraph:
mod_flag = True
continue
if(tmplength < in_graphLength and b2 == initialNode):
mod_flag = True
continue
else:
graph.pop(i-1)
modification_needed((b1,b2),graph,tmplength)
return mod_flag
#find_eulerian_tour([(1,2),(2,6),(7,2),(6,1),(2,3),(3,5),(3,4),(4,5),(5,7),(7,3),(5,6),(6,7)])
#find_eulerian_tour([(0,4),(1,0),(4,2),(4,8),(2,5),(9,5),(8,9),(5,4),(5,1),(7,1),(3,7),(1,6),(6,3)])
Aquí está el código original en la página web de Gregor Ulm y funciona.
def find_eulerian_tour(graph):
def freqencies():
# save all nodes of edges to my_list
# e.g. [3,4,5,1,2,2,3,5]
my_list = [x for (x, y) in graph]
# get the max num of nodes-->create a list
# set all to 0
# for i in range(5) = 0 1 2 3 4
# so range("5" +1) means
# len=6, result=[0,0,0,0,0,0]
# so that the index = the number itself
result = [0 for i in range(max(my_list) + 1)]
# nodes in my_list, increment
# e.g. [0,1,2,2,1,2]
# 3appears 2times.
for i in my_list:
result[i] += 1
return result
# this is Frequencies of each nodes.
def find_node(tour):
for i in tour:
if freq[i] != 0:
return i
return -1
def helper(tour, next):
find_path(tour, next)
u = find_node(tour)
while sum(freq) != 0:
sub = find_path([], u)
# get the sub_path
# add them together
# when draw to u, turn to sub, and then come back to go on the original tour path
# [:a], start to a; [a+1:] a+1 to end
tour = tour[:tour.index(u)] + sub + tour[tour.index(u) + 1:]
u = find_node(tour)
return tour
def find_path(tour, next):
for (x, y) in graph:
if x == next:
# from "double-graph"
# pop out the current one and its respondent one
# actually it means we delete this edge
current = graph.pop(graph.index((x,y)))
graph.pop(graph.index((current[1], current[0])))
# now add this "next" node into the tour
tour.append(current[0])
# decrement in frequency
freq[current[0]] -= 1
freq[current[1]] -= 1
return find_path(tour, current[1])
# if this "next" node is not connected to any other nodes
# single one
tour.append(next)
return tour
# in graph, all edges get reversed one and be added to graph
# can call it "double-graph"
# it helps to calculate the frequency in find_path
# actually we can regard frequency as degrees for each node
graph += [(y, x) for (x, y) in graph]
freq = freqencies()
# set graph[0][0] as starting point
return helper([], graph[0][0])
graph = [(1, 2), (2, 3), (3, 1)]
print find_eulerian_tour(graph)
Esta solución está optimizada para la complejidad O (V + E) es decir, es lineal en el número de bordes y vértices en el gráfico
Para aquellos que desean ver el código directamente: https://github.com/cubohan/py-algos/blob/master/eulerian_tour.py
Tenga en cuenta que el código infringe la legibilidad y el diseño DRY principalmente, pero después de leer la explicación, puede generar fácilmente su propia versión.
# eulerian_tour.py by cubohan
# circa 2017
#
# Problem statement: Given a list of edges, output a list of vertices followed in an eulerian tour
#
# complexity analysis: O(E + V) LINEAR
def find_eulerian_tour(graph):
edges = graph
graph = {}
degree = {}
start = edges[0][0]
count_e = 0
for e in edges:
if not e[0] in graph:
graph[e[0]] = {}
if not e[0] in degree:
degree[e[0]] = 0
if not e[1] in graph:
graph[e[1]] = {}
if not e[1] in degree:
degree[e[1]] = 0
graph[e[0]][e[1]] = 1
graph[e[1]][e[0]] = 1
degree[e[0]] += 1
degree[e[1]] += 1
count_e += 1
max_d = 0
this_ = 0
for v, d in degree.items():
if not d%2 == 0:
# Eulerian tour not possible as odd degree found!
return False
if d>max_d:
this_ = v
max_d = d
visited_e = {}
def is_visited(i, j):
key = str(sorted([i,j]))
if key in visited_e:
return True
else:
visited_e[key] = True
return False
start = this_
route = [start]
indexof = {}
indexof[start] = 0
while count_e>0:
flag = False
for to_v in graph[this_]:
if not is_visited(to_v, this_):
route.append([to_v])
indexof[to_v] = len(route)-1
degree[to_v] -= 1
if degree[to_v] == 0:
del degree[to_v]
degree[this_] -= 1
if degree[this_] == 0:
del degree[this_]
this_ = to_v
flag = True
count_e -= 1
break
if not flag:
break
for key, v in degree.items():
if v <=0:
continue
try:
ind = indexof[key]
except Exception as e:
continue
this_ = key
while count_e>0:
flag = False
for to_v in graph[this_]:
if not is_visited(to_v, this_):
route[ind].append(to_v)
degree[to_v] -= 1
degree[this_] -= 1
this_ = to_v
flag = True
count_e -= 1
break
if not flag:
break
route_ref = []
for r in route:
if type(r) == list:
for _r in r:
route_ref.append(_r)
else:
route_ref.append(r)
return route_ref
if __name__ == "__main__":
print find_eulerian_tour([(0, 1), (1, 5), (1, 7), (4, 5),(4, 8), (1, 6), (3, 7), (5, 9),(2, 4), (0, 4), (2, 5), (3, 6), (8, 9)])
** Primero, el problema se puede dividir en estas subtareas: **
Construya el gráfico en una estructura más amigable que una lista de bordes para facilitar el procesamiento, es decir, (Listas de adyacencia)
Encuentre los grados de cada vértice para verificar primero si es posible realizar un recorrido euleriano (¿Hay solo grados uniformes? Además, ALMACENE estos valores en un dict con vértice como clave => para usar más adelante)
Construye la gira euleriana
El concepto detrás de mi solución es simple.
Eliges el vértice con el grado más alto como punto de partida y lo configuras como el vértice actual. (Nota: Usted logra esto al mismo tiempo mientras calcula los grados de cada vértice. Almacena todos estos grados en un diccionario).
Inserta el vértice actual en la lista de rutas que es su respuesta (Nota: también haga un diccionario de vértices y sus índices en la lista de rutas. Esto se usará más adelante).
Visita el primer borde del vértice actual si aún no lo ha visitado. (Nota: se mantiene un diccionario de bordes visitados, la clave para este dict es una tupla ordenada del par de vértices que constituyen el borde. Después de visitar un borde, márquelo visitado insertándolo en el dict).
Mantiene un recuento de los grados restantes del vértice actual y el vértice visitado (Esto resultará útil más adelante) (Nota: solo necesita restar 1 del dictado de los grados que genera cada vez que elige un borde)
Cambia el vértice actual al vértice en el otro extremo del borde que decidió visitar.
Repita los pasos 2 a 5 hasta que no pueda encontrar un borde no visitado en el vértice actual. (Nota: esto significa que ha regresado a su vértice inicial)
Ahora considere esto: Observe que los bordes / vértices no visitados constituirán subgrafos en el gráfico principal que tienen las mismas propiedades que el gráfico principal, es decir, que es posible un recorrido euleriano desde cualquiera de los vértices en el subgrafo comenzando y terminando en el mismo vértice.
Todos los bordes no visitados pueden ser visitados tomando recorridos eulerianos en estos subgrafos. Solo necesita fusionar estos sub-tours con la primera gira.
Siguiente:
Recorre todos los vértices del gráfico y construye una suburbanización en el mismo proceso que el listado para el recorrido principal si y solo si el grado reducido de este vértice no es cero
La forma en que estos recorridos se fusionarán con la lista de rutas calculada anteriormente es que reemplaza la posición del vértice que está considerando para comenzar una sutileza en la lista de rutas con la lista de salida de las sub-series y luego aplana esta lista de rutas.
¡Aún no hemos terminado! ¿Qué pasa arriba?
¿Qué sucede cuando obtienes un vértice de grado distinto de cero que NO HA SIDO VISITADO y no está presente en la lista de rutas?
Una advertencia: este es un caso excepcional.
Es posible que encuentre vértices no visitados anteriormente y, por lo tanto, no estarán presentes en la lista de rutas principales.
IGNORAR ESTOS mientras bucle! Uno de los vértices que ya ha visitado con un grado de reducción no nulo está GARANTIZADO para conducir a estos vértices en el subtilo que creará a partir de ellos.
¡¡¿¿Cómo es eso posible??!!
Dibuja un gráfico del caso de prueba dado en el enlace al código y lo entenderás. Haga un seguimiento de lo que está haciendo su algo en cada paso del proceso. ¡Dibujalo! Una imagen es log (N) complejidad para la comprensión y palabras O (n2).
Ah, y tenga en cuenta que esta garantía solo se cumple si todos los bordes en la lista de entrada forman un solo gráfico y no dos gráficos separados inconexos.
También estoy en la misma conferencia, la respuesta de WolframH no funciona para mí. Aquí está mi solución (ha sido aceptada por el clasificador):
Inserta todos los next node posibles en un montón ( search ) y luego busca en cada uno de ellos mientras grabas.
def next_node(edge, current):
return edge[0] if current == edge[1] else edge[1]
def remove_edge(raw_list, discard):
return [item for item in raw_list if item != discard]
def find_eulerian_tour(graph):
search = [[[], graph[0][0], graph]]
while search:
path, node, unexplore = search.pop()
path += [node]
if not unexplore:
return path
for edge in unexplore:
if node in edge:
search += [[path, next_node(edge, node), remove_edge(unexplore, edge)]]
if __name__ == ''__main__'':
graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
print find_eulerian_tour(graph)
[1, 3, 4, 3, 2, 1]
Aquí hay un caso válido donde falla su algoritmo:
graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
Usa el poder de la print para descubrir qué le sucede a graph y current_vertex .
Otra sugerencia: mueva el else hacia abajo para que pertenezca a for y se ejecute cuando el bucle for no esté roto. Como está ahora, nunca se puede ejecutar. Después de esa corrección, el algoritmo aún falla, por supuesto.
El algoritmo aún falla, por supuesto.
El algoritmo aún falla, por supuesto.
Por favor, no comentes diciendo que el código no funciona. No es así El algoritmo aún falla, incluso si el código siguiente hace lo que el OP tenía en mente. El objetivo era mostrar que el algoritmo del OP es incorrecto, lo que el OP no pudo determinar. Para eso, se necesita una implementación correcta del algoritmo de OP (ver más abajo). Una implementación correcta de un algoritmo incorrecto todavía no es una solución correcta.
Lamento empeorar esta respuesta escribiendo todas estas largas explicaciones, pero la gente sigue quejándose de que el código no funciona (por supuesto, el punto era mostrar que está mal). También rechazaron esta respuesta, probablemente porque esperan poder copiar el código como una solución. Pero este no es el punto, el punto es mostrar al OP que hay un error en su algoritmo.
El código a continuación no encuentra recorridos eulerianos. ¡Busca en otro lado para copiar el código para pasar tus evaluaciones!
def find_eulerian_tour(graph):
tour = []
current_vertex = graph[0][0]
tour.append(current_vertex)
while len(graph) > 0:
print(graph, current_vertex)
for edge in graph:
if current_vertex in edge:
if edge[0] == current_vertex:
current_vertex = edge[1]
else:
current_vertex = edge[0]
graph.remove(edge)
tour.append(current_vertex)
break
else:
# Edit to account for case no tour is possible
return False
return tour
graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
print(find_eulerian_tour(graph))
Salida:
[(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)] 1
[(2, 3), (3, 1), (3, 4), (4, 3)] 2
[(3, 1), (3, 4), (4, 3)] 3
[(3, 4), (4, 3)] 1
False
Puedes imitar el comportamiento del algoritmo BFS y aferrarse a él.
Nota: No he intentado escribir la respuesta usando listas enlazadas porque las listas enlazadas requieren la definición de 2 clases (una para definir los nodos y sus comportamientos, y otra para definir la lista enlazada completa y sus comportamientos). Sin embargo, para una mayor eficiencia en (adjuntar) y (eliminar) comportamientos, debe usar listas vinculadas en lugar de matrices:
def find_eulerian_tour(graph):
nodes = set()
for i in graph:
if not i[0] in nodes:
nodes.add(i[0])
if not i[1] in nodes:
nodes.add(i[1])
tour = []
tempstack = []
graphtemp = []
current_vertex = graph[0][0]
tour.append(current_vertex)
tempstack.append(current_vertex)
last_edge = ()
count = 0
while len(set(tempstack)) + 1 < len(nodes) or (count == 0 or tour[0] != tour[len(tour) - 1]):
count += 1
flag = False
for edge in graph:
if current_vertex in edge and edge != last_edge:
if current_vertex == edge[0]:
current_vertex = edge[1]
else:
current_vertex = edge[0]
last_edge = edge
graphtemp.append(edge)
graph.remove(edge)
tour.append(current_vertex)
tempstack.append(current_vertex)
flag = True
break
if flag == False:
tour.remove(current_vertex)
current_vertex = tempstack[0]
tempstack.remove(tempstack[0])
graph.append(graphtemp[0])
graphtemp.remove(graphtemp[0])
return tour
print find_eulerian_tour([(1,2), (2,3), (3,1)])
print(find_eulerian_tour([(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]))
print(find_eulerian_tour([(1, 13), (1, 6), (6, 11), (3, 13), (8, 13), (0, 6), (8, 9),(5, 9), (2, 6), (6, 10), (7, 9), (1, 12), (4, 12), (5, 14), (0, 1), (2, 3), (4, 11), (6, 9), (7, 14), (10, 13)]))
print(find_eulerian_tour([(8, 16), (8, 18), (16, 17), (18, 19), (3, 17), (13, 17), (5, 13),(3, 4), (0, 18), (3, 14), (11, 14), (1, 8), (1, 9), (4, 12), (2, 19),(1, 10), (7, 9), (13, 15), (6, 12), (0, 1), (2, 11), (3, 18), (5, 6), (7, 15), (8, 13), (10, 17)]))