How to Sort Depended Objects by Dependency

How to sort depended objects by dependency

Perfect example to use a topological sort:

http://en.wikipedia.org/wiki/Topological_sorting

It will give you exactly what you need.

You can either use Kahn's algorithm:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

...or you can use Depth-first search:

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

How to sort depended objects by dependency for maximum concurrency

This looks a lot like https://en.wikipedia.org/wiki/Program_Evaluation_and_Review_Technique and https://en.wikipedia.org/wiki/Critical_path_method

Assuming that you want the maximum concurrency level to get the thing done as soon as possible, once you have organised things so that it takes no longer than the critical path you have something that does as well as the best possible solution - and if there is no limit on the amount of parallel tasks you can run, you can get the critical path just by scheduling every action as soon as all of its dependencies have completed.

JavaScript - Sort depending on dependency tree

You coult take a Set for added keys and check if the actual dependency has all elements added to the set. Then add this key, otherwise go on. Proceed until no more items are in the array.

var dependencies = { A: [], B: ['A'], C: ['A', 'B'], D: ['F'], E: ['D', 'C'], F: [], G: ['H'], H: ['G'] },    keys = Object.keys(dependencies),    used = new Set,    result = [],    i, item, length;    do {    length = keys.length;    i = 0;    while (i < keys.length) {        if (dependencies[keys[i]].every(Set.prototype.has, used)) {            item = keys.splice(i, 1)[0];            result.push(item);            used.add(item);            continue;        }        i++;    }} while (keys.length && keys.length !== length)
console.log('circle', ...keys);result.push(...keys);
console.log(result);

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

Order List By Dependencies

The problem you are describing is called topological sort: given a partial ordering, try to find a linear description that respects that ordering.

The typical algorithm to solve this problem takes O(|V| + |E|) time, where |V| is the number of vertices (modules in your example) and |E| is the number of edges (dependencies in your example).

The linked Wikipedia article also provides pseudo code. It will take some book keeping to convert the algorithm to your example, but it is relatively straightforward.

How to sort a list when certain values must appear later than others, potentially ignoring sort order for such items that need 'delaying'

This is called topological sorting. You can model "blocking" as edges of a directed graph. This should work if there are no circular "blockings".

Python: sorting a dependency list

What you want is called a topological sort. While it's possible to implement using the builtin sort(), it's rather awkward, and it's better to implement a topological sort directly in python.

Why is it going to be awkward? If you study the two algorithms on the wiki page, they both rely on a running set of "marked nodes", a concept that's hard to contort into a form sort() can use, since key=xxx (or even cmp=xxx) works best with stateless comparison functions, particularly because timsort doesn't guarantee the order the elements will be examined in. I'm (pretty) sure any solution which does use sort() is going to end up redundantly calculating some information for each call to the key/cmp function, in order to get around the statelessness issue.

The following is the alg I've been using (to sort some javascript library dependancies):

edit: reworked this greatly, based on Winston Ewert's solution

def topological_sort(source):
    """perform topo sort on elements.

    :arg source: list of ``(name, [list of dependancies])`` pairs
    :returns: list of names, with dependancies listed first
    """
    pending = [(name, set(deps)) for name, deps in source] # copy deps so we can modify set in-place       
    emitted = []        
    while pending:
        next_pending = []
        next_emitted = []
        for entry in pending:
            name, deps = entry
            deps.difference_update(emitted) # remove deps we emitted last pass
            if deps: # still has deps? recheck during next pass
                next_pending.append(entry) 
            else: # no more deps? time to emit
                yield name 
                emitted.append(name) # <-- not required, but helps preserve original ordering
                next_emitted.append(name) # remember what we emitted for difference_update() in next pass
        if not next_emitted: # all entries have unmet deps, one of two things is wrong...
            raise ValueError("cyclic or missing dependancy detected: %r" % (next_pending,))
        pending = next_pending
        emitted = next_emitted

Sidenote: it is possible to shoe-horn a cmp() function into key=xxx, as outlined in this python bug tracker message.

Short Solution to Sort a C++ Vector of Objects with Dependencies to Each Other?

Elaborating on my quick comment:

If you have already checked that there are no loops in your items, then what you have is a directed acyclic graph (DAG).

Sorting that is the problem known as Topological sorting:
(https://en.wikipedia.org/wiki/Topological_sorting) which has known efficient solutions, like Kahn's algorithm, though to take advantage of it's efficiency, you'll have to be careful how you store your nodes and edges, so that some operations (for example, finding a node with no incoming edges) is efficient (constant time)

Some well known libraries, like boost also provide implementations:
http://www.boost.org/doc/libs/1_33_1/libs/graph/doc/topological_sort.html

Sorting the dependencies tree in java

Your libraries form a graph of dependencies, where an arc from A to B means "A depends on B". You need to sort the graph so that no library depends on one later in the list. This order is a topological sorting

https://en.wikipedia.org/wiki/Topological_sorting

and can be achieved e.g. by Kahn's algorithm.

Topological sort with support for cyclic dependencies

First off, it is conceptually easier if you have a graph such that you can ask "what do you depend on"? I'm going to assume that we have a graph where a directed edge from A to B means "A depends on B", which is the opposite of your statement.

I am somewhat confused by your question since a topo sort that ignores cycles is virtually the same as a regular topo sort. I'll develop the algorithm so that you can handle cycles as you see fit; perhaps that will help.

The idea of the sort is:

A graph is a collection of nodes such that each node has a collection of neighbours. As I said, if a node A has a neighbour B then A depends on B, so B must happen before A.
The sort takes a graph and produces a sorted list of nodes.
During the operation of the sort a dictionary is maintained which maps every node onto one of three values: alive, dead and undead. An alive node has yet to be processed. A dead node is already processed. An undead node is being processed; it's no longer alive but not yet dead.
If you encounter a dead node you can skip it; it's already in the output list.
If you encounter a live node then you process it recursively.
If you encounter an undead node then it is part of a cycle. Do what you like. (Produce an error if cycles are illegal, treat it as dead if cycles are legal, etc.)

function topoSort(graph) 
  state = []
  list = []
  for each node in graph
    state[node] = alive
  for each node in graph
    visit(graph, node, list, state)
  return list

function visit(graph, node, list, state)
  if state[node] == dead
    return // We've done this one already.
  if state[node] == undead
    return // We have a cycle; if you have special cycle handling code do it here.
  // It's alive. Mark it as undead.
  state[node] = undead
  for each neighbour in getNeighbours(graph, node)
    visit(graph, neighbour, list, state)
  state[node] = dead
  append(list, node);

Make sense?