I\'m sorry the title is so vague ... I cannot think how to describe it any bette
ID: 648486 • Letter: I
Question
I'm sorry the title is so vague ... I cannot think how to describe it any better.
I have a collection in this format:
var myCollection = [{id:"a"}, {id:"b",excludes:["a"]}, {id:"c",excludes:["b"]}];
What I want after running my algorithm is to see this:
processedCollection = [{id:"a"}, {id:"c",excludes:["b"]});
Alternatively, if "c" hadn't existed, then only "b" would be visible. I hope that makes sense. It's further complicated by the possibility that any item in the collection could exclude multiple other items (hence why it's an array).
NOTE: I do NOT have to worry about circular references, as it is reasonable in this instance to expect only good data to come into my algorithm.
I've attempted to construct an appropriate function but am coming unstuck. I'd figured I would first run through the collection and create an excludedBy parameter on each item, and to then run through again, outputting the correct result, but it's not quite so simple.
Any help would be much appreciated. I'm hoping very much that this is a known problem with defined algorithm(s) to deal with it! Thank you in advance!
Explanation / Answer
Creating a topological sorting would give you a valid order to process the nodes in. Note there can be multiple topological sorts. Whether you need to worry about that depends on if you need one solution or all the solutions.
In this case, there is only one topological sort: c, b, a. You start with c, add it to the output, and remove all its direct children from the graph. The next non-removed node in the sorting is a, which has no children, so you just add it to the output. No nodes remain in the topo sort, so you're done.