How to reorder an array to have a key in ascending order, based on an array of values?-CodePudding

I'm trying to run a database migration, and I've run into a chronological issue. I can't change the behaviour, so I have to deal with it somehow.

Suppose I have the following array,

const arr = [
  { model: 'modelE', associations: ['modelA'], order: 1 },
  { model: 'modelA', associations: [ 'modelB' ], order: 2 },
  { model: 'modelB', associations: [], order: 3 },
  { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
  { model: 'modelD', associations: ['modelA'], order: 5 },
  { model: 'modelF', associations: [], order: 6 },
]

As we know, we have to create these tables in order, otherwise the foreign keys cannot be created and, therefore, an error will be thrown.

In this case, we have modelE, modelC and modelD that depend on modelA, but modelA depends on modelB, so modelB must be the first element in this array, because it has to be the first table to be created.

The resulting array should look like this:

const arr = [
  { model: 'modelB', associations: [], order: 1 },
  { model: 'modelF', associations: [], order: 2 },
  { model: 'modelA', associations: [ 'modelB' ], order: 3 },
  { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
  { model: 'modelE', associations: ['modelC'], order: 5 },
  { model: 'modelD', associations: ['modelA'], order: 6 },
]

Is there an effective way of doing this? All I can think of is running a sort function with arr.finds inside it. Not sure if this is too performant or even readable.

CodePudding user response：

You are looking for a topological ordering.

You can use a depth-first algorithm for that:

function topoSort(arr) {
    const visited = new Set;
    const map = new Map(arr.map(({model, associations}) => [model, associations]));
    
    function dfs(models) {
        for (let model of models) {
            if (visited.has(model)) continue;
            dfs(map.get(model));
            visited.add(model);
        }
    }
    
    dfs([...map.keys()]);
    return Array.from(visited, (model, i) => 
        ({model, associations: map.get(model), order: i 1})
    );
}

const arr = [
  { model: 'modelE', associations: ['modelA'], order: 1 },
  { model: 'modelA', associations: [ 'modelB' ], order: 2 },
  { model: 'modelB', associations: [], order: 3 },
  { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
  { model: 'modelD', associations: ['modelA'], order: 5 },
  { model: 'modelF', associations: [], order: 6 },
]
const result = topoSort(arr);
console.log(...result);

CodePudding user response：

const sortArrayByDependency = (arr) => {
  const sorted = [];
  const foundSet = new Set();
  const maxLoop = arr.length;
  let loopCount = 0;
  
  while(arr.length > 0 && loopCount < maxLoop) {
    loopCount  = 1;
    const first = arr.shift();
    if(first.associations.every(ele => foundSet.has(ele))){
      sorted.push({...first, order: sorted.length   1 });
      foundSet.add(first.model)
    }
    else {
      arr.push(first)
    }
  }
  
  return sorted;
}

const arr = [
  { model: 'modelB', associations: [], order: 1 },
  { model: 'modelF', associations: [], order: 2 },
  { model: 'modelA', associations: [ 'modelB' ], order: 3 },
  { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
  { model: 'modelE', associations: ['modelC'], order: 5 },
  { model: 'modelD', associations: ['modelA'], order: 6 },
]

console.log(sortArrayByDependency(arr))