Nous construisons une application où le client pourra créer un flux de travail, représenté sous forme de DAG . Lors de la sortie à l'écran, cela ressemblera à ceci:
Le graphique ci-dessus est affiché à l'écran à l'aide d'un tableau à deux dimensions, et le modèle ressemble à ceci:
const start = [
{ isYesPath: undefined, name: 'Step 1', parentIds: [0], stepId: 1, type: DagBranchType.Normal },
{ isYesPath: undefined, name: 'Step 2', parentIds: [1], stepId: 2, type: DagBranchType.IfElse },
{ isYesPath: true, name: 'Step 3', parentIds: [2], stepId: 3, type: DagBranchType.Normal },
{ isYesPath: false, name: 'Step 4', parentIds: [2], stepId: 4, type: DagBranchType.Normal },
{ isYesPath: undefined, name: 'Step 5', parentIds: [3, 4], stepId: 5, type: DagBranchType.Normal },
]
const result = [
[{ isYesPath: undefined, name: 'Step 1', parentIds: [0], stepId: 1, type: DagBranchType.Normal }],
[{ isYesPath: undefined, name: 'Step 2', parentIds: [1], stepId: 2, type: DagBranchType.IfElse }],
[
{ isYesPath: true, name: 'Step 3', parentIds: [2], stepId: 3, type: DagBranchType.Normal },
{ isYesPath: false, name: 'Step 4', parentIds: [2], stepId: 4, type: DagBranchType.Normal }
],
[{ isYesPath: undefined, name: 'Step 5', parentIds: [3, 4], stepId: 5, type: DagBranchType.Normal }]
]
Le modèle de tableau à deux dimensions me permet de faire une boucle dessus et de sortir chaque ligne à l'écran; Ainsi, le premier élément du modèle dag est la première ligne avec un nœud, le deuxième élément du modèle dag est la deuxième ligne avec deux nœuds, et ainsi de suite.
Cette partie fonctionne, et j'ai même compris comment ajouter dynamiquement des nœuds au graphique à la volée. La partie avec laquelle je rencontre des problèmes consiste à créer le tableau à deux dimensions à partir d'un tableau à une seule dimension. Les données du graphique iront au serveur et seront renvoyées par le serveur sous la forme d'un tableau unidimensionnel, comme ceci:
// this is the end array, (two dimensions [][]), that will be used to draw the graph
const dag = [];
// this will create the first row of the array, with all the items that have a parentId of 0
const newRow = items
.filter((item) => item.parentId === 0)
.reduce((arr, item) => {
arr.push(item);
return arr;
}, []);
dag.push(newRow);
// Now I'm trying to move down the graph from top to bottom
dag.forEach((row) => {
// get the list of item IDs that are in this row
const itemIdsInRow = row.reduce((prev, row) => {
prev.push(row.id);
return prev;
}, []);
// use the itemIdsInRow to get the items from the single dimensional array that will go in the next row
const itemsForNextRow = itemIdsInRow.reduce((itemsArr, id) => {
const nextItems = items.filter((item) => item.parentId === id);
itemsArr.push(...nextItems);
return itemsArr;
}, []);
// push the new row onto the two dimension array
dag.push(itemsForNextRow);
});
Je dois prendre ce tableau d' items et le convertir dans le tableau multidimensionnel dag ci-dessus.
Voici ce que j'ai jusqu'à présent:
const items = [
{ id: 1, parentId: 0 },
{ id: 2, parentId: 1 },
{ id: 3, parentId: 1 },
{ id: 4, parentId: 3 },
{ id: 5, parentId: 3 },
{ id: 6, parentId: 2 },
]
Cela fonctionne pour les deux premières lignes du dag . Ca a du sens; alors que je pousse sur le modèle dag , le forEach ne me laisse pas continuer à parcourir la boucle pour construire la troisième ligne. Si je commence le tableau de dag avant le forEach avec les deux premières lignes, je peux construire la troisième ligne correctement, donc l'algorithme pour construire le dag est assez proche d'être là.
Si vous avez des suggestions ou des idées sur la façon de résoudre ce problème, je vous en serais très reconnaissant. Merci!
Nous avons également besoin maintenant que le parentId chaque élément soit un tableau de parentId . C'est parce que deux branches peuvent être combinées en un point, donc un nœud peut avoir deux (ou plus) parents. Imaginez dans l'image ci-dessus que les nœuds 4 et 5 ont un nœud enfant en dessous d'eux auquel chacun d'eux se connecte. Voici le tableau de départ et le tableau de résultat dans le code:
const dag = [
[
{ id: 1, parentId: 0 }
],
[
{ id: 2, parentId: 1 },
{ id: 3, parentId: 1 }
],
[
{ id: 6, parentId: 2 },
{ id: 4, parentId: 3 },
{ id: 5, parentId: 3 }
],
]
3 Réponses :
Une solution possible est la suivante. Je ne suis pas sûr que ce soit la meilleure façon de le faire, ou la plus efficace, mais cela fonctionne. Fondamentalement, je garde une trace des objets du tableau d' items ont été utilisés, et quand ils l'ont, je les pousse sur le tableau usedItems . Je boucle sur le code qui ajoute de nouvelles lignes au modèle dag pendant que usedItems.length !== items.length .
const items = [
{ id: 1, parentId: 0 },
{ id: 2, parentId: 1 },
{ id: 3, parentId: 1 },
{ id: 4, parentId: 3 },
{ id: 5, parentId: 3 },
{ id: 6, parentId: 2 },
];
// As items are used, push them on this array
const usedItems = [];
// this is the end array, (two dimensions [][]), that will be used to draw the graph
const dag = [];
// this will create the first row of the array, with all the items that have a parentId of 0
const newRow = items
.filter((item) => item.parentId === 0)
.reduce((arr, item) => {
arr.push(item);
return arr;
}, []);
dag.push(newRow);
usedItems.push(...newRow);
// go until the usedItems array is the same length as the original items array
while (usedItems.length !== items.length) {
// get the list of item IDs that are in this row
const row = dag[dag.length - 1];
const itemIdsInRow = row.reduce((prev, row) => {
prev.push(row.id);
return prev;
}, []);
// use the itemIdsInRow to get the items from the single dimensional array that will go in the next row
const itemsForNextRow = itemIdsInRow.reduce((itemsArr, id) => {
const nextItems = items.filter((item) => item.parentId === id);
itemsArr.push(...nextItems);
return itemsArr;
}, []);
// push the new row onto the two dimension array
dag.push(itemsForNextRow);
usedItems.push(...itemsForNextRow);
}
Vous pouvez obtenir le résultat souhaité en utilisant les méthodes forEach et filter pour créer une fonction récursive et transmettre l'ID parent et le niveau actuel. Vous pouvez ensuite utiliser level pour ajouter au tableau de résultats par index.
const items = [{"id":1,"parentId":0},{"id":2,"parentId":1},{"id":3,"parentId":1},{"id":4,"parentId":3},{"id":5,"parentId":3},{"id":6,"parentId":2}]
const result = []
const modify = (data, pid = 0, level = 0) => data
.filter(({ parentId }) => parentId === pid)
.forEach(e => {
if (!result[level]) result[level] = [e]
else result[level].push(e);
modify(data, e.id, level + 1)
})
modify(items)
console.log(result);savez-vous comment obtenir ce même résultat, mais avec parentId étant un tableau de parentIds au lieu d'un seul parentId? Ainsi, par exemple, l'élément avec l'ID 5, pourrait avoir comme parentIds 3 et 4? J'ai essayé de modifier la fonction mais cela ajoute plusieurs copies de l'élément 5 au tableau final.
@ pjlamb12 Quel serait le résultat souhaité dans ce cas?
C'est essentiellement l'opposé d'un nœud se ramifiant en deux nœuds distincts. L'idée est que deux nœuds, c'est-à-dire le nœud 3 et le nœud 4, pourraient se combiner avec le nœud 5. Ainsi, le nœud 5 a deux parents.
Pourriez-vous publier les données de résultat souhaitées pour ce cas, peut-être dans votre question ou dans jsfiddle.net
Je viens d'ajouter une modification à la question d'origine avec plus de détails. Il a un tableau de départ d'éléments et à quoi devrait ressembler le résultat.
Essayez quelque chose comme ceci jsfiddle.net/w8o3v6f2
Parfait, cela fonctionne très bien! Merci beaucoup pour l'aide!
Il existe déjà deux solutions, cependant, je voudrais en suggérer une sans mutations.
const items = [
{ id: 1, parentId: 0 },
{ id: 2, parentId: 1 },
{ id: 3, parentId: 1 },
{ id: 4, parentId: 3 },
{ id: 5, parentId: 3 },
{ id: 6, parentId: 2 },
];
const partition = predicate => list => [
list.filter (predicate),
list.filter (x => !predicate (x)),
];
const inLevel = nth => original => item => {
if (nth < 0) return false;
const parent = original.find (({id}) => id === item.parentId);
return !parent ? nth === 0 : inLevel (nth - 1) (original) (parent);
};
const buildTree = (original) => (list, nth = 0) => {
const [currentLevel, rest] = partition (inLevel (nth) (original)) (list);
return rest.length > 0
? [ currentLevel, ...buildTree (original) (rest, nth + 1) ]
: [ currentLevel ];
}
console.log (buildTree (items) (items));