Sorting array of elements that depend on each other

Question

I'm a bit stumped. I have an array of elements that will be used to calculate current element's value depending on an element that was in a chain before it. (Think of a timeline where element's date is +/- n days relative to some other element.) Problem is, only one element will have initial value [ie start date] and other elements that are before it (prtcxxx series) will subtract from it and then from each other, and elements after it (testxxxx, reportxxxx, issuexxxx) will add to it and then to each other in chain. I tried creating array.sort with rules to allow that kind of sorting, but it's not working. I also tried creating my own sort workflow witth if/elseif -> outputArr.splice, but no luck there either :/

// array columns:
// [elementID, I_depend_on_this_elementID, my_value, calculated_value]
let arrayMe = [
  ["report0700", "report0500"],
  ["issue0200", "report1000"],
  ["report1000", "report0900"],
  ["report0900", "report0800"],
  ["issue0230", "report1000"],
  ["issue0000", ""],
  ["issue0100", ""],
  ["issue0110", ""],
  ["issue0240", "issue0240"],
  ["test0100", "test0100",10,10], // this element will actually start the chain for everything else
  ["protc0000", ""],
  ["protc0300", "protc0500"],
  ["report0600", "protc0100"],
  ["report0800", "report0700"],
  ["issue0120", ""],
  ["issue0220", ""],
  ["protc0200", "protc0300"],
  ["protc0600", "protc0100"],
  ["protc0100", "protc0200"],
  ["protc0700", "protc0800"],
  ["protc0500", "protc0700"],
  ["protc0400", "protc0500"],
  ["protc1000", "test0100"],
  ["protc0900", "protc1000"],
  ["protc0800", "protc0900"],
  ["test0000", ""],
  ["test0400", "test0300"],
  ["test0300", "test0200"],
  ["test0200", "test0100"],
  ["test0600", "test0500"],
  ["test0700", "test0500"],
  ["test0500", "test0400"],
  ["report0000", ""],
  ["report0400", "report0300"],
  ["report0500", "report0300"],
  ["report0300", "report0200"],
  ["report0200", "report0100"],
  ["report0100", "test0400"],
];

arrayMe.sort((a, b) => {
  console.log(a[0], " -- ", b[1]);
  if (a[0] == b[1]) {return 1;} // a before b, because b depends on a
  if (a[1] == b[0]) {return -1;} // b before a, because a depends on b
  if (a[1] == a[0]) {return 1;} // a in front, because it depends only on itself and others will depend on it
  if (a[1] == "") {return 0;} // a can be wherever, because it doesn't depend on anyone, nor anyone will depend on it
  return 0;
});

console.log(arrayMe);

And my own sort attempt (I guess it would need several repeats/recursive to finish the sort?):

let ordered = [];
arrayMe.forEach(function (a) {
  if (a[0] === a[1] || a[1] === "" || a[1] === null || a[3]) {
    ordered.splice(0, 0, a); // element is a seed for others or independedt, put it at front
  } else if (ordered.findIndex((x) => x[1] === a[0]) !== -1) { // see if some x already in ordered array already depends on 'a' and then put the a in front of it
    let where = ordered.findIndex((x) => x[1] === a[0]) - 1;
    ordered.splice(where, 0, a);
  } else if (ordered.findIndex((x) => x[1] === a[1]) !== -1) { // see if 'a' depends on some x already in the array and if so, put a behind x 
    ordered.splice(
      ordered.findIndex((x) => x[1] === a[1]) + 1, 0, a
    );
  } else {
    ordered.splice(ordered.length, 0, a);
  }
});

None of the array elements cause circular reference.

The above model is simplified, in realyty I'll have a dynamic-ish object with elements like this, where due_date is to be calculated based on other elements:

        report0700: {
          title: "A task to be performed by specific date, 7 days after report0500",
          relative_to: "report0500",
          delta: +7,
          due_date: null // report0500.due_date = 03 DEC 2020 + delta, -> report0700.due_date = 10 DEC 2020
        },
        report0800: {
          title: "another to be performed by specific date, 14 days after report0700",
          relative_to: "report0700",
          delta: +14,
          due_date: null // report0700.due_date = 10 DEC 2020 + delta, -> report0800.due_date = 24 DEC 2020
        },

Any advice would be appreciated.

EDIT: There are two examples of attempted sorting above: arrayMe.sort((a, b) => { ... and arrayMe.forEach(function (a) { ...

Expected element order after being sorted by how they depend on each other looks like this.

let arrayMe = [
  ["test0100", "test0100", 10, 10], // this element will actually start the chain for everything else
  ["issue0240", "issue0240"], // depends on itself, just dump it in front
  ["issue0000", ""], // does not depend on any other, just dump it anywhere
  ["issue0100", ""], // does not depend on any other, just dump it anywhere
  ["issue0110", ""], // does not depend on any other, just dump it anywhere
  ["protc0000", ""], // does not depend on any other, just dump it anywhere
  ["issue0120", ""], // does not depend on any other, just dump it anywhere
  ["issue0220", ""], // does not depend on any other, just dump it anywhere
  ["test0000", ""], // does not depend on any other, just dump it anywhere
  ["report0000", ""], // does not depend on any other, just dump it anywhere
  // protcxxxx series, starts by depending on [test0100]
  // from here on, the rule is simple:
  // element with name in [column1] comes after element named in [column2]
  ["protc1000", "test0100"], // ie ["protc1000", "test0100"] needs to be positioned anywhere after element ["test0100", "test0100", 10, 10]
  ["protc0900", "protc1000"],
  ["protc0800", "protc0900"],
  ["protc0700", "protc0800"],
  ["protc0500", "protc0700"],
  ["protc0400", "protc0500"],
  ["protc0300", "protc0500"],
  ["protc0200", "protc0300"],
  ["protc0100", "protc0200"],
  ["protc0600", "protc0100"],
  ["report0600", "protc0100"],
  // testxxxx series, starts by depending on [test0100] and can be mangled in between protcxxxx nodes
  ["test0200", "test0100"],
  ["test0300", "test0200"],
  ["test0400", "test0300"],
  ["test0500", "test0400"],
  ["test0600", "test0500"],
  ["test0700", "test0500"],
  // reportxxxx series, starts by depending on [test0400]
  ["report0100", "test0400"],
  ["report0200", "report0100"],
  ["report0300", "report0200"],
  ["report0400", "report0300"],
  ["report0500", "report0300"],
  ["report0700", "report0500"],
  ["report0800", "report0700"],
  ["report0900", "report0800"],
  ["report1000", "report0900"],
  // issuetxxxx series, starts by depending on [report1000]
  ["issue0200", "report1000"],
  ["issue0230", "report1000"],
];

can you add a comment in the line where a sorting takes happen? please mark the parts who should be sorted together - and add the wanted result. — Nina Scholz, May 18 '20 at 17:29

score 2 · Accepted Answer · answered May 18 '20 at 18:49

The approach I would take would be to create a dependency index. The index would contain lists of all dependents recursively. Then sort parents before children.

let arrayMe = [
    ["report0700", "report0500"],
    ["issue0200", "report1000"],
    ["report1000", "report0900"],
    ["report0900", "report0800"],
    ["issue0230", "report1000"],
    ["issue0000", ""],
    ["issue0100", ""],
    ["issue0110", ""],
    ["issue0240", "issue0240"],
    ["test0100", "test0100", 10, 10], // this element will actually start the chain for everything else
    ["protc0000", ""],
    ["protc0300", "protc0500"],
    ["report0600", "protc0100"],
    ["report0800", "report0700"],
    ["issue0120", ""],
    ["issue0220", ""],
    ["protc0200", "protc0300"],
    ["protc0600", "protc0100"],
    ["protc0100", "protc0200"],
    ["protc0700", "protc0800"],
    ["protc0500", "protc0700"],
    ["protc0400", "protc0500"],
    ["protc1000", "test0100"],
    ["protc0900", "protc1000"],
    ["protc0800", "protc0900"],
    ["test0000", ""],
    ["test0400", "test0300"],
    ["test0300", "test0200"],
    ["test0200", "test0100"],
    ["test0600", "test0500"],
    ["test0700", "test0500"],
    ["test0500", "test0400"],
    ["report0000", ""],
    ["report0400", "report0300"],
    ["report0500", "report0300"],
    ["report0300", "report0200"],
    ["report0200", "report0100"],
    ["report0100", "test0400"],
];


// Calculate dependents
let dep1 = arrayMe.reduce((idx, item) => {
    if (item[1] != "") {
        idx[item[1]] = idx[item[1]] ? idx[item[1]] : [];
        idx[item[1]].push(item[0])
    };
    return idx
}, {});

// Calculate deep dependents
let m = true;
while (m) {
    m = false;
    for (const p in dep1) {
        let itemlen = dep1[p].length;
        for (let ix = 0; ix < itemlen; ix++) {
            if (undefined != dep1[dep1[p][ix]]) {
                let parent = dep1[dep1[p][ix]];
                for (let iy = 0; iy < parent.length; iy++) {
                    if (dep1[p].indexOf(parent[iy]) == -1) {
                        dep1[p].push(parent[iy]);
                        m = true;
                    }
                }

            }
        }
    }
}

arrayMe.sort((a, b) => {
    let da = dep1[a[0]];
    let db = dep1[b[0]];
    if (da != undefined && da.indexOf(b[0]) != -1) {
        return -1; // b is a dependent of a
    }
    if (db != undefined && db.indexOf(a[0]) != -1) {
        return 1; // a is a dependent of b
    }
    let ca = da ? da.length : 0;
    let cb = db ? db.length : 0;

    return cb - ca;
});

Thank you Ralph, your snippet does the job as advertised. Good to learn of the method for solvind this kind of problem. — Zir, May 19 '20 at 22:28

Scott Sauyet · Answer 2 · 2020-05-20T13:28:05.907

Updated to pull the fix for cyclic nodes into a separate function. This keeps the main code cleaner; and that fix is likely throw-away anyway.

I would probably turn this into a tree, or rather a forest, a collection of trees, and then do a preorder visitation of those trees. This is one way to do so:

const makeForest = (root, xs) =>
  xs .filter (([_, parent]) => parent === root)
     .map (
       ([id, parent, ...rest]) => [id, parent, makeForest (id, xs), ...rest]
     )

const preorder = ([id, parent, children, ...rest]) => 
  [[id, parent, ...rest], ...(children || []) .flatMap (preorder)]

const dependencyOrder = (xs) =>
  makeForest ('', xs) .flatMap (preorder)


let arrayMe = [["report0700", "report0500"], ["issue0200", "report1000"], ["report1000", "report0900"], ["report0900", "report0800"], ["issue0230", "report1000"], ["issue0000", ""], ["issue0100", ""], ["issue0110", ""], ["issue0240", "issue0240"], ["test0100", "test0100", 10, 10 /* this element will actually start the chain for everything else*/], ["protc0000", ""], ["protc0300", "protc0500"], ["report0600", "protc0100"], ["report0800", "report0700"], ["issue0120", ""], ["issue0220", ""], ["protc0200", "protc0300"], ["protc0600", "protc0100"], ["protc0100", "protc0200"], ["protc0700", "protc0800"], ["protc0500", "protc0700"], ["protc0400", "protc0500"], ["protc1000", "test0100"], ["protc0900", "protc1000"], ["protc0800", "protc0900"], ["test0000", ""], ["test0400", "test0300"], ["test0300", "test0200"], ["test0200", "test0100"], ["test0600", "test0500"], ["test0700", "test0500"], ["test0500", "test0400"], ["report0000", ""], ["report0400", "report0300"], ["report0500", "report0300"], ["report0300", "report0200"], ["report0200", "report0100"], ["report0100", "test0400"]];

// recasts self-dependent nodes (??!!) as root ones.
const fix = (xs) =>
   xs .map (([id, parent, ...rest]) => [id, parent === id ? '' : parent, ...rest])

console .log (dependencyOrder (fix (arrayMe)))

.as-console-wrapper {min-height: 100% !important; top: 0}

The main function is makeForest, a recursive -- and perhaps not particularly efficient -- way to build our forest, by scanning the list for elements with no parents, putting them at the first level, and then for each one of them, recursing on those elements whose parents match our current node's id, and so forth.

Note that at the end of makeForest('', arrayMe), we end up with a structure like this:

[
    ["issue0000", "", []],
    ["issue0100", "", []],
    ["issue0110", "", []],
    ["issue0240", "", []],
    ["test0100",  "", [
        ["protc1000","test0100", [
            ["protc0900", "protc1000", [
                ["protc0800", "protc0900", [
                    // ...
                ]
            ]
        ],
        ["test0200", "test0100", [
            ["test0300", "test0200",  [
                ["test0400", "test0300", [
                    // ...
                ]
            ]
        ], 10, 10
    ],
    ["protc0000", "", []],
    ["issue0120", "", []],
    // ...
]

That structure is easy to flatten, by visiting each tree with a preorder traversal, and then concatenating those lists.

Also important is the fact that the nodes which are their own parents -- this is very strange! -- are fixed up ~~in the xs .map line of dependencyOrder~~ [update]: in the fix function. But that alteration lasts all the way through. If you wanted to keep the original parent id, you could change it just a bit to carry that information through. This is a little fiddly because we're dealing with arrays; objects would make this change easier.

const makeForest = (root, xs) =>
  xs .filter (([_, parent]) => parent === root)
     .map (
       ([id, parent, orig, ...rest]) => [id, parent, orig, makeForest (id, xs), ...rest]
     )

const preorder = ([id, _, orig, children, ...rest]) => 
  [[id, orig, ...rest], ...(children || []) .flatMap (preorder)]

const dependencyOrder = (xs) =>
  makeForest ('', xs) .flatMap (preorder)


let arrayMe = [["report0700", "report0500"], ["issue0200", "report1000"], ["report1000", "report0900"], ["report0900", "report0800"], ["issue0230", "report1000"], ["issue0000", ""], ["issue0100", ""], ["issue0110", ""], ["issue0240", "issue0240"], ["test0100", "test0100", 10, 10 /* this element will actually start the chain for everything else*/], ["protc0000", ""], ["protc0300", "protc0500"], ["report0600", "protc0100"], ["report0800", "report0700"], ["issue0120", ""], ["issue0220", ""], ["protc0200", "protc0300"], ["protc0600", "protc0100"], ["protc0100", "protc0200"], ["protc0700", "protc0800"], ["protc0500", "protc0700"], ["protc0400", "protc0500"], ["protc1000", "test0100"], ["protc0900", "protc1000"], ["protc0800", "protc0900"], ["test0000", ""], ["test0400", "test0300"], ["test0300", "test0200"], ["test0200", "test0100"], ["test0600", "test0500"], ["test0700", "test0500"], ["test0500", "test0400"], ["report0000", ""], ["report0400", "report0300"], ["report0500", "report0300"], ["report0300", "report0200"], ["report0200", "report0100"], ["report0100", "test0400"]];

// recasts self-dependent nodes (??!!) as root ones.
const fix = (xs) =>
   xs .map (([id, parent, ...rest]) => [id, parent === id ? '' : parent, parent, ...rest])

console .log (dependencyOrder (fix (arrayMe)))

.as-console-wrapper {min-height: 100% !important; top: 0}

We don't do any further cycle-detection in here. If you have cycles beyond the trivial "I'm my own parent" one, this will probably enter an infinite loop.

Thank you Scott, yours and Ralph's forest/tree idea helped me solve the problem. The elements that depend on themselves was actually my way of marking them as master nodes (that will hold initial seed value starting dependent calculations for other nodes), but that's probably an antipattern and the forest solution will work just fine without that marker. Also, my actual data is an object, but I figured it would be easier to present/solve it as an array, with access to indexes and reliable ordering. Thanks for your solution - it's at a higher level to where I am at themoment, but I grasped it. — Zir, May 19 '20 at 22:43
Beautiful work Scott. As I was reading the question, I was imagining a very similar answer. I am wondering if `fold` and `preorder` presented in [this Q&A](https://stackoverflow.com/a/61842976/633183) can be adapted to work with your tree. — Mulan, May 20 '20 at 02:52
@Zir: yes, I think that's an anti-pattern, have them point to `0`, `null`, `undefined` or some such depending on your structure. It's funny, but I would have found an object substantially easier to deal with than the arrays here, but to each his own. Do check out the excellent alternative from Thankyou, who always sheds some incredible light in these situations. — Scott Sauyet, May 20 '20 at 13:59

Mulan · Answer 3 · 2020-05-20T06:09:47.873

Cool problem. Scott's answer is incredible and I was thinking of something similar. I'll share this because I personally find it useful to see many solutions to the same problem.

graph

From the way I see it, your arrayMe represents an array of edges, and when assembled they form an n-ary tree, or graph -

const graph = (edges = [], root = [ "", null ]) =>
  node
    ( root
    , edges
        .filter(([ _, p ]) => p == root[0])
        .map(e => graph(edges, e))
    )

Our graph function constructs and returns a root node which is just an ordinary data wrapper -

const node = ([ id = "", parent = null, ...data ], children = []) =>
  ({ id, parent, data, children })

We can implement fold for n-ary tree -

const fold = (g = node(), f = identity) =>
  f({ ...g, children: g.children.map(c => fold(c, f)) })

Now we can write dependencies function which is a simple graph traversal using fold -

const dependencies = (g = node()) =>
  fold
    ( g
    , ({ children = [], ...node }) =>
        [ node, ...children.flat(1) ]
    )

The techniques in this answer assume you remove the loop created by the self-referential edge -

// original
["test0100","test0100",10,10]  // <-- self-reference infinite loop

// change to
["test0100","",10,10]          // <-- root node, parent of ""

Our dependencies function outputs a flat array -

dependencies(graph(arrayMe))
// => ...

[ { id: "", parent: null, data: [] }
, { id: "issue0000", parent: "", data: [] }
, { id: "issue0100", parent: "", data: [] }
, { id: "issue0110", parent: "", data: [] }
, { id: "test0100", parent: "", data: [ 10, 10 ] }
, { id: "protc1000", parent: "test0100", data: [] }
, { id: "protc0900", parent: "protc1000", data: [] }
, { id: "protc0800", parent: "protc0900", data: [] }
, { id: "protc0700", parent: "protc0800", data: [] }
, { id: "protc0500", parent: "protc0700", data: [] }
, { id: "protc0300", parent: "protc0500", data: [] }
, { id: "protc0200", parent: "protc0300", data: [] }
, { id: "protc0100", parent: "protc0200", data: [] }
, { id: "report0600", parent: "protc0100", data: [] }
, { id: "protc0600", parent: "protc0100", data: [] }
, { id: "protc0400", parent: "protc0500", data: [] }
, { id: "test0200", parent: "test0100", data: [] }
, { id: "test0300", parent: "test0200", data: [] }
, { id: "test0400", parent: "test0300", data: [] }
, { id: "test0500", parent: "test0400", data: [] }
, { id: "test0600", parent: "test0500", data: [] }
, { id: "test0700", parent: "test0500", data: [] }
, { id: "report0100", parent: "test0400", data: [] }
, { id: "report0200", parent: "report0100", data: [] }
, { id: "report0300", parent: "report0200", data: [] }
, { id: "report0400", parent: "report0300", data: [] }
, { id: "report0500", parent: "report0300", data: [] }
, { id: "report0700", parent: "report0500", data: [] }
, { id: "report0800", parent: "report0700", data: [] }
, { id: "report0900", parent: "report0800", data: [] }
, { id: "report1000", parent: "report0900", data: [] }
, { id: "issue0200", parent: "report1000", data: [] }
, { id: "issue0230", parent: "report1000", data: [] }
, { id: "protc0000", parent: "", data: [] }
, { id: "issue0120", parent: "", data: [] }
, { id: "issue0220", parent: "", data: [] }
, { id: "test0000", parent: "", data: [] }
, { id: "report0000", parent: "", data: [] }
]

Because dependencies is implemented using a higher-order function, fold, it's easy to change the output, if we wish -

const dependencies = (g = node()) =>
  fold
    ( g
    , ({ children = [], ...node }) =>
        [ [ node.id || "_"
          , node.parent || "_"
          , ...node.data
          ].join(" ")
        , ...children.flat(1)
        ]
    )

dependencies(graph(arrayMe))
// => ...

[ "_ _"
, "issue0000 _"
, "issue0100 _"
, "issue0110 _"
, "test0100 _ 10 10"
, "protc1000 test0100"
, "protc0900 protc1000"
, "protc0800 protc0900"
, "protc0700 protc0800"
, "protc0500 protc0700"
, "protc0300 protc0500"
, "protc0200 protc0300"
, "protc0100 protc0200"
, "report0600 protc0100"
, "protc0600 protc0100"
, "protc0400 protc0500"
, "test0200 test0100"
, "test0300 test0200"
, "test0400 test0300"
, "test0500 test0400"
, "test0600 test0500"
, "test0700 test0500"
, "report0100 test0400"
, "report0200 report0100"
, "report0300 report0200"
, "report0400 report0300"
, "report0500 report0300"
, "report0700 report0500"
, "report0800 report0700"
, "report0900 report0800"
, "report1000 report0900"
, "issue0200 report1000"
, "issue0230 report1000"
, "protc0000 _"
, "issue0120 _"
, "issue0220 _"
, "test0000 _"
, "report0000 _"
]

generators

I think generators are a good solution for this as well. We even get convenient place to add functional sorting -

const compareNode = ({ id: a }, { id: b }) =>
  a.localeCompare(b)

const dependencies = function* ({ children = [], ...node })
{ yield node
  for (const c of children.sort(compareNode))
    yield* dependencies(c)
}

for (const { id, parent, data } of dependencies(graph(arrayMe)))
  console.log(id || "_", parent || "_", ...data)

_ _
issue0000 _
issue0100 _
issue0110 _
issue0120 _
issue0220 _
protc0000 _
report0000 _
test0000 _
test0100 _ 10 10
protc1000 test0100
protc0900 protc1000
protc0800 protc0900
protc0700 protc0800
protc0500 protc0700
protc0300 protc0500
protc0200 protc0300
protc0100 protc0200
protc0600 protc0100
report0600 protc0100
protc0400 protc0500
test0200 test0100
test0300 test0200
test0400 test0300
report0100 test0400
report0200 report0100
report0300 report0200
report0400 report0300
report0500 report0300
report0700 report0500
report0800 report0700
report0900 report0800
report1000 report0900
issue0200 report1000
issue0230 report1000
test0500 test0400
test0600 test0500
test0700 test0500

Map

If arrayMe contains a significantly large number of edges, we would benefit from swapping out the linear .filter used above.

Instead of passing arrayMe directly to graph we will pass index(arrayMe) to graph instead -

// before
dependencies(graph(arrayMe))

// after
dependencies(graph(index(arrayMe)))

This index will provide graph with fast lookup when resolving node dependencies -

import { empty, get, update } from "./Cache"

const index = (edges = []) =>
  edges.reduce
    ( (c, edge) =>
        update
          ( c                         // cache
          , edge[1]                   // parent
          , deps => [ ...deps, edge ] // dependents
          )
    , empty([])   // empty cache with default value
    )

Now we write cache.js. We will implement it using Map which gives us much faster lookup compared to .filter -

// Cache.js
const empty = orElse =>
  [ new Map, orElse ]

const get = ([ t, orElse ] = empty(), k = null) =>
  t.has(k) ? t.get(k) : orElse

const set = ([ t, orElse ] = empty(), k = null, v = null) =>
  [ t.set(k, v), orElse ]

const update = (t = empty(), k = null, f = identity) =>
  set(t, k, f(get(t, k)))

export { empty, get, set, update }

Finally update graph to use Cache.get -

const graph = (cache = empty([]), edge = [ "", null ]) =>
  node
    ( edge
    , get(cache, edge[0], [])       // <-- Cache.get fast lookup
        .map(e => graph(cache, e))
    )

Fascinating, as always. It's interesting to see the useful `fold` on trees. In Ramda we've resisted calls for a `foldObj`, because we think of them as *unordered* collections of properties, and thus a non-commutative function might give different answers for objects equal except for the ordering of their properties... not good! But I hadn't thought about how that goes away with the *ordered* children in trees. This is both powerful and elegant. — Scott Sauyet, May 20 '20 at 13:49

Sorting array of elements that depend on each other

3 Answers3