javascript - Async/Await para recorrer un árbol recursivamente en TypeScript

Tengo la estructura de árbol simple como la siguiente:

class Group {
  id: ObjectId;
  name: string;
  subGroups: [ObjectId]
}

Por ejemplo, el Grupo A tiene dos subgrupos: Grupo B y C, y el Grupo C tiene tres subgrupos: Grupo F, G, H, etc.

Necesito implementar un algoritmo para obtener todos los grupos recursivamente: Salida esperada=[Grupo A, Grupo B, Grupo C, Grupo D, Grupo E, Grupo F, Grupo G, Grupo H, Grupo I, Grupo J]

Pero necesito obtener los subgrupos de la base de datos, por lo que eso debería ser async/await.

Método 1

    const tr = async (group: Group, result: Group[]) => {
      console.log(group);
      result.push(group);
      for (const id of group.subGroups) {
        const groupId = id.toHexString();
        const subGroup = this.findGroup(groupId);
        tr(await subGroup, result);
      }
    };

    const result = [];
    await tr(user.group, result);
    console.log(result);

Método 2

  async transverse(group: Group, result: Group[]) {
    console.log(group);
    result.push(group);
    for (const id of group.subGroups) {
      const groupId = id.toHexString();
      const subGroup = await this.findGroup(groupId);
      await this.transverse(subGroup, result);
    }
  }

  const result = [];
  await transverse(user.group, result);
  console.log(result);

El Método 1 no puede generar el arreglo correcto, y no produce el Grupo A a J completado. El Método 2 puede obtener el arreglo correcto, pero el código no se ve limpio. ¿Alguien sabe cómo lograr este objetivo de manera elegante y puede explicarme por qué el método 1 no funciona?

Respuesta #1

Podrías hacer uso de algunas características modernas, como un generador asincrónico, para realizar un recorrido sobre tu árbol.

Como en el ejemplo que has dado, la exploración es en anchura; no optaría por la recursión, sino que iteraría con un bucle sobre cada nivel del árbol. Los objetos Group se pueden resolver en "paralelo" cuando están en el mismo nivel, ya que estos resultados no dependen unos de otros. Este es un buen caso de uso para emplear Promise.all en lugar de await individuales para cada nodo por separado.

Aquí está cómo podría verse -- he incluido un ejemplo para la parte de la base de datos:

class Group {
    constructor(id, subGroups) {
        this.id = id;
        this.subGroups = subGroups;
    }
}

// Mock of asynchronous DB
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));
const db = {
    _tree: {
        "A": ["B", "C"],
        "B": ["D", "E"],
        "C": ["F", "G", "H"],
        "D": [],
        "E": [],
        "F": ["I", "J"],
        "G": [],
        "H": [],
        "I": [],
        "J": []
    },
    async findGroup(groupId) {
        await delay(Math.random() * 1000);
        return new Group(groupId, db._tree[groupId]);
    }
};

// Make an async generator
async function* tr(groupId) {
    let result = [await db.findGroup(groupId)];
    while (result.length) {
        yield* result;
        // Use Breadth-first traversal order, and allow some parallellism
        result = await Promise.all(result.flatMap(group => group.subGroups.map(db.findGroup)));
    }
};

// Consume the async iterator you get from the above function. The call starts with the id of the tree's root:
(async () => {
    for await (const result of tr("A")) {
        console.log(result);
    }
})();

Respuesta #2

Ok, entonces tu clase se ve así

class Group {
  id: ObjectId;
  name: string;
  subGroups: [ObjectId]
} 

Necesitamos definir lo que necesitamos, por lo tanto, el resultado esperado es:

[Grupo A, Grupo B, Grupo C, Grupo D, Grupo E, Grupo F, Grupo G, Grupo H, Grupo I, Grupo J]

En otras palabras, necesitamos hacer un bucle de la siguiente manera: grupo -> todos los hijos y repetir.

Podemos usar una variable que contendrá los siguientes grupos y luego recorrerla en un bucle. Esta variable se inicializará con el primer grupo que obtengas (por ejemplo, el grupo A) y luego el bucle imprimirá su nombre, recorrerá sus hijos y guardará cada hijo para que sea el siguiente en la variable de impresión que acabamos de crear. Después de que terminemos de recorrer sus hijos, eliminaremos el grupo principal.

Usaremos un bucle while que se detendrá solo cuando la variable nextToPrint sea un arreglo vacío.

nextToPrint = []; // variable to hold the next groups to print so it will need to be initialized with groupA.


// some method that runs when your app starting, like mounted() on Vue, attached() on aureliaJS or ngOnInit on Angular
async someMethod() {
  const first = await getGroup(first) // get first group
  nextToPrint.push(first); // push to the queue-like variable


  // loop through the next to print 
  while(nextToPrint.length) {
      printGroup(nextToPrint[0]); // print first item in the next list
  }
}

async printGroup(group: Group) {
   console.log(group.name); // print Group name
   group.subGroups.forEach(g => {
       const child = await getGroup(g); // send it to get the next group
       nextToPrint.push(child); // add child to be the last one to print
       console.log(child.name); // print the child name
   });

   nextToPrint.shift(); // remove first element from the next to print
}

Espero que ayude, siéntete libre de comentar y hacer más preguntas hasta que lo consigamos