[T2] Duda de enunciado sobre la fase de Reduce

[ibgarrido]

Hola!

he estado probando el ejemplo dado para probar la detección de triángulos (x,11,y), (y,11,z), (z,11,x) siguiendo al pie de la letra las instrucciones de la parte 1 (Para explicarlo solo usaré los outputs que obtengo, para evitar mostrar código):

Map phase: Hashear nodos y luego emitir las llaves, que como fue explicado en clase, usando módulo 2 quedaría

Output:

[((1, 0, 0), (1, 11, 2)),
 ((1, 0, 1), (1, 11, 2)),
 ((1, 1, 0), (1, 11, 3)),
 ((1, 1, 1), (1, 11, 3)),
 ((0, 1, 0), (2, 11, 3)),
 ((0, 1, 1), (2, 11, 3)),
 ((1, 0, 0), (3, 11, 2)),
 ((1, 0, 1), (3, 11, 2)),
 ((1, 0, 0), (3, 11, 4)),
 ((1, 0, 1), (3, 11, 4)),
 ((0, 1, 0), (4, 11, 1)),
 ((0, 1, 1), (4, 11, 1)),
 ((0, 0, 0), (4, 11, 2)),
 ((0, 0, 1), (4, 11, 2)),
 ((0, 1, 0), (4, 11, 3)),
 ((0, 1, 1), (4, 11, 3))]

Sin embargo en la etapa de reduce dice lo siguiente: Los reducers reciben siempre los mensajes correspondientes a alguna llave (b1, b2, b3). Pero en el valor de esa llave se encuentran aristas. Todas estas aristas forman un pequeño grafo , y el reducer emite como respuesta todas las tuplas (n1, n2, n3) correspondientes a los triángulos que detecta en su grafo.

Lo que entiendo de esta parte es que debo hacer:

1. Agrupar las aristas bajo cierto criterio : Los reducers reciben siempre los mensajes correspondientes a alguna llave (b1, b2, b3). Pero en el valor de esa llave se encuentran aristas.

Pero al hacerlo obtengo los siguientes subgrafos:

output:

[
((1, 0, 0), [(1, 11, 2), (3, 11, 2), (3, 11, 4)]),
 ((1, 1, 1), [(1, 11, 3)]),
 ((0, 1, 0), [(2, 11, 3), (4, 11, 1), (4, 11, 3)]),
 ((0, 0, 1), [(4, 11, 2)]),
 ((1, 0, 1), [(1, 11, 2), (3, 11, 2), (3, 11, 4)]),
 ((1, 1, 0), [(1, 11, 3)]),
 ((0, 1, 1), [(2, 11, 3), (4, 11, 1), (4, 11, 3)]),
 ((0, 0, 0), [(4, 11, 2)])]

Sin embargo en los subgrafos es claro que no están las aristas que generan un triángulo.

Donde asumo un output esperado es (1,3,4) o (2,3,4).

Entonces mi pregunta es: ¿Está bien como estoy interpretando el enunciado?

[juanreutter]

Casi! el mapper que estas haciendo solo asume que la arista (1,11,2) puede contribuir a la parte de (x,11,y), por que generas llaves con (1,0,-) donde 1 es el hash del nodo 1 y 0 el hash del nodo 2. Pero la arista tb puede contribuir a la parte (y,11,z) del patron o a la (z,11x). Entpnces al recibir esta arista tb deberias generar llaves del tipo (-,1,0) o (0,-,1), asumiendo la convebcion de que la primera componente de la llave es el match de x, la segunda el de y y la tercera el de z