dependencies.js

// Resolve a dependency graph to sequence
// https://web.stanford.edu/~jurafsky/slp3/15.pdf


const resolve = (sentence, deps) => {
    let ops = [];
    while (sentence.length > 0) {
        let word = sentence.pop();
        if (deps.hasOwnProperty(word)) {
            console.log('Dependencies exist for', word);
            // Push to the beginning of the stack
            sentence.unshift(word);
        } else {
            console.log('No dependencies for', word);
            // No dependencies exist so add to the sequence of ops
            ops.push(word);
            Object.keys(deps).map(e => {
                let depss = deps[e];
                let loc = depss.indexOf(word);
                // console.log('Checking deps for word', e, depss, word, loc);
                if (loc !== -1) {
                    let _ = depss.splice(loc, 1);
                    if (depss.length === 0) {
                        console.log('Clearing', e)
                        delete deps[e];
                    } else {
                        deps[e] = depss;
                    }
                }
            });
        }

    }
    return ops;
};


const sentence = 'I prefer the morning flight through Denver'.split(' ');

let deps = {
    'prefer': ['I', 'flight'],
    'flight': ['the', 'morning', 'Denver'],
    'Denver': ['through']
};

console.log('Resolved ops', resolve(sentence, deps));

  const graph = buildGraph(sentence, deps);
  const roots = findRoots(graph);
  const sequence = [];
  for (let i = 0; i < roots.length; i++) {
    const root = roots[i];
    const node = graph[root];
    sequence.push(node.word);
    const children = node.children;
    for (let j = 0; j < children.length; j++) {
      const child = children[j];
      const childNode = graph[child];
      sequence.push(childNode.word);
    }
  }