Dependency Traversal

demo.js

const target = {
	"groupId": "main",
	"artifactId": "root",
	"parent": "main:parentOne",
	"dependencies": [
		"dependency:nine",
		"dependency:ten",
		"dependency:eleven"
	]
};

const traverser = DependencyTraverser(target);
traverser.traverseToRoot();
traverser.parseDependencies();


console.log("Processing Order: ", traverser.getProcessingOrder());
console.log("Number of Nodes: ", traverser.getNumberOfNodes());
console.log("Dependency Tree: ", traverser.getTree());

DependencyTraverser.js

const _ = require("lodash");
const fixtures = require("./fixtures.js");

/**
 * Simple object capable of demonstrating how to build a dependency tree
 *  from a POM-like structure; using BFS (queue based).
 */
function DependencyTraverser(targetObject = {})
{
	/** Queue containing dependencies to process */
	let queue = [];

	/** Internal Cache Object. */
	let seenDependencies = {};

	/** Object which will hold our final dependency tree */
	let dependencyTree = {}

	/** Demonstration/Debugging variables */
	let numberOfNodes = 0;
	let processingOrder = [];


	/**
	 * Every item on the queue must contain: (a) an indentifier for the 
	 *  target dependency, and (b) a "chain", signifying the location
	 *  of the dependency in the final tree.
	 */
	const generateDependencyQueueObject = (identifier, chain = []) => {
		return{
			identifier, chain
		}
	};


	/**
	 * Generate an indentifier for a given dependency; version is not
	 *  required at this level, as there will only ever be one version
	 *  present in a given tree.
	 */
	const getCoords = (dep) => {
		return dep.groupId + ':' + dep.artifactId;
	};


	const retrieveDependency = (identifier) => {
		// Demonstration - just grab the data fom our fixtures.
		if (seenDependencies[identifier] === undefined) {
			seenDependencies[identifier] = fixtures[identifier];
		}

		return seenDependencies[identifier];
	}


	const retrieveParent = (parentIdentifier) => {
		// Demonstration - just grab the data from our fixtures.
		return fixtures[ parentIdentifier ];
	}


	/**
	 * Given a dependency object, and a chain, place the dependency
	 *  in the correct location of the dependency tree.
	 */
	const addToTree = (dep, chain) => {
		// No chain, place dependency in the root
		if (chain.length < 1) {
			dependencyTree[ getCoords(dep) ] = dep;
		}

		/* todo: insert 'depencencies' for every 2nd element */
		const parentNode = _.get(dependencyTree, chain.join('.'), {});
		parentNode[ getCoords(dep) ] = dep;
	};


	/**
	 * Process the dependencies found in the dependency queue (FIFO), does so
	 *  by shifting off the first element and concatenating any subsequent
	 *  dependencies.
	 *
	 * Operates on the queue "in-place".
	 */
	const processDepQueue = () => {
		let queueEntry;
		while (queueEntry = queue.shift()) {
			let dep = retrieveDependency(queueEntry.identifier);

			// Iterate over the sub dependencies, adding them to our Queue for
			//  later processing.
			const currentCoords = getCoords(dep);
			if (dep.dependencies && dep.dependencies.length > 0) {
				queue = queue.concat(dep.dependencies.map( (innerDep) => {
					let newChain = queueEntry.chain.slice();
					newChain.push(currentCoords);

					return generateDependencyQueueObject(innerDep, newChain);
				}));

			}

			// Place in tree
			addToTree(dep, queueEntry.chain)

			// Increment Counter
			numberOfNodes++;

			// DEMONSTRATION: log the processing order to check this solves the issue
			processingOrder.push(currentCoords);
		}
	};


	return {
		/**
		 * Traverse to the root node, initialising queue as a list of
		 *  dependencies - ordered correctly with highest node first.
		 */
		traverseToRoot : () => {
			const recurseUp = (node) => {
				if (!node.parent) {
					return;
				}

				const parentNode = retrieveParent(node.parent);
				if (parentNode.dependencies && parentNode.dependencies.length > 0) {
					queue = parentNode.dependencies
						.map((dep) => {return generateDependencyQueueObject(dep) })
						.concat(queue)
				}

				return recurseUp(parentNode);
			};

			return recurseUp(targetObject);
		},


		/**
		 * Append the direct dependencies from the target object to those
		 *  discovered in the parent(s) object(s). Then begin processing 
		 *  our dependency queue.
		 */
		parseDependencies : () => {
			if (targetObject.dependencies && targetObject.dependencies.length > 0) {
				queue = queue.concat(targetObject.dependencies
					.map((dep) => {return generateDependencyQueueObject(dep) }));
			}

			processDepQueue();
		},


		getTree : () => {
			return dependencyTree;
		},

		getNumberOfNodes: () => {
			return numberOfNodes;
		},

		getProcessingOrder: () => {
			// For demonstration reasons; dump out the processing order.
			return processingOrder;
		}
	}
};

fixtures.js

var exports = module.exports = {
	"main:parentOne"    : {
		"parent": "main:parentTwo",
		"groupId": "main",
		"artifactId": "parentOne",
		"dependencies": [ "dependency:eight" ]
	},

	"main:parentTwo"    : {
		"parent": "main:parentThree",
		"groupId": "main",
		"artifactId": "parentTwo",
		"dependencies": [ "dependency:four", "dependency:five", "dependency:six", "dependency:seven" ]
	},

	"main:parentThree"    : {
		"groupId": "main",
		"artifactId": "parentThree",
		"dependencies": [ "dependency:one", "dependency:two", "dependency:three" ]
	},

	"dependency:one"      : { "groupId": "dependency", "artifactId": "one"   },
	"dependency:two"      : { "groupId": "dependency", "artifactId": "two"   },
	"dependency:three"    : { "groupId": "dependency", "artifactId": "three" },
	"dependency:four"     : { "groupId": "dependency", "artifactId": "four" },
	"dependency:five"     : { "groupId": "dependency", "artifactId": "five" },
	"dependency:six"      : { "groupId": "dependency", "artifactId": "six" },
	"dependency:seven"    : { "groupId": "dependency", "artifactId": "seven" },
	"dependency:eight"    : { "groupId": "dependency", "artifactId": "eight" },
	"dependency:nine"     : { "groupId": "dependency", "artifactId": "nine", "dependencies": [
		"dependency:twelve", "dependency:thirteen"
	]},
	"dependency:ten"      : { "groupId": "dependency", "artifactId": "ten", "dependencies": [
		"dependency:fourteen"
	]},
	"dependency:eleven"   : { "groupId": "dependency", "artifactId": "eleven" },
	"dependency:twelve"   : { "groupId": "dependency", "artifactId": "twelve" },
	"dependency:thirteen" : { "groupId": "dependency", "artifactId": "thirteen" },
	"dependency:fourteen" : { "groupId": "dependency", "artifactId": "fourteen", "dependencies": [
		"dependency:fifteen", "dependency:sixteen"
	]},
	"dependency:fifteen"  : { "groupId": "dependency", "artifactId": "fifteen" },
	"dependency:sixteen"  : { "groupId": "dependency", "artifactId": "sixteen" },
}

Output

Pay special attention to the Processing Order, and compare with the resulting Dependency Tree. Dependencies are processed closest first; regardless of nesting.

Processing Order:  [ 'dependency:one',
  'dependency:two',
  'dependency:three',
  'dependency:four',
  'dependency:five',
  'dependency:six',
  'dependency:seven',
  'dependency:eight',
  'dependency:nine',
  'dependency:ten',
  'dependency:eleven',
  'dependency:twelve',
  'dependency:thirteen',
  'dependency:fourteen',
  'dependency:fifteen',
  'dependency:sixteen' ]
Number of Nodes:  16
Dependency Tree:  { 'dependency:one': { groupId: 'dependency', artifactId: 'one' },
  'dependency:two': { groupId: 'dependency', artifactId: 'two' },
  'dependency:three': { groupId: 'dependency', artifactId: 'three' },
  'dependency:four': { groupId: 'dependency', artifactId: 'four' },
  'dependency:five': { groupId: 'dependency', artifactId: 'five' },
  'dependency:six': { groupId: 'dependency', artifactId: 'six' },
  'dependency:seven': { groupId: 'dependency', artifactId: 'seven' },
  'dependency:eight': { groupId: 'dependency', artifactId: 'eight' },
  'dependency:nine': 
   { groupId: 'dependency',
     artifactId: 'nine',
     dependencies: [ 'dependency:twelve', 'dependency:thirteen' ],
     'dependency:twelve': { groupId: 'dependency', artifactId: 'twelve' },
     'dependency:thirteen': { groupId: 'dependency', artifactId: 'thirteen' } },
  'dependency:ten': 
   { groupId: 'dependency',
     artifactId: 'ten',
     dependencies: [ 'dependency:fourteen' ],
     'dependency:fourteen': 
      { groupId: 'dependency',
        artifactId: 'fourteen',
        dependencies: [Object],
        'dependency:fifteen': [Object],
        'dependency:sixteen': [Object] } },
  'dependency:eleven': { groupId: 'dependency', artifactId: 'eleven' } }