airavata-kubernetes/web-console/src/assets/js/layout/hierarchical/stage/mxMedianHybridCrossingReduction.js - airavata-sandbox - Git at Google

 /**
  * Copyright (c) 2006-2015, JGraph Ltd
  * Copyright (c) 2006-2015, Gaudenz Alder
  */
 /**
  * Class: mxMedianHybridCrossingReduction
  *
  * Sets the horizontal locations of node and edge dummy nodes on each layer.
  * Uses median down and up weighings as well heuristic to straighten edges as
  * far as possible.
  *
  * Constructor: mxMedianHybridCrossingReduction
  *
  * Creates a coordinate assignment.
  *
  * Arguments:
  *
  * intraCellSpacing - the minimum buffer between cells on the same rank
  * interRankCellSpacing - the minimum distance between cells on adjacent ranks
  * orientation - the position of the root node(s) relative to the graph
  * initialX - the leftmost coordinate node placement starts at
  */
 function mxMedianHybridCrossingReduction(layout)
 {
 	this.layout = layout;
 };

 /**
  * Extends mxMedianHybridCrossingReduction.
  */
 mxMedianHybridCrossingReduction.prototype = new mxHierarchicalLayoutStage();
 mxMedianHybridCrossingReduction.prototype.constructor = mxMedianHybridCrossingReduction;

 /**
  * Variable: layout
  *
  * Reference to the enclosing <mxHierarchicalLayout>.
  */
 mxMedianHybridCrossingReduction.prototype.layout = null;

 /**
  * Variable: maxIterations
  *
  * The maximum number of iterations to perform whilst reducing edge
  * crossings. Default is 24.
  */
 mxMedianHybridCrossingReduction.prototype.maxIterations = 24;

 /**
  * Variable: nestedBestRanks
  *
  * Stores each rank as a collection of cells in the best order found for
  * each layer so far
  */
 mxMedianHybridCrossingReduction.prototype.nestedBestRanks = null;

 /**
  * Variable: currentBestCrossings
  *
  * The total number of crossings found in the best configuration so far
  */
 mxMedianHybridCrossingReduction.prototype.currentBestCrossings = 0;

 /**
  * Variable: iterationsWithoutImprovement
  *
  * The total number of crossings found in the best configuration so far
  */
 mxMedianHybridCrossingReduction.prototype.iterationsWithoutImprovement = 0;

 /**
  * Variable: maxNoImprovementIterations
  *
  * The total number of crossings found in the best configuration so far
  */
 mxMedianHybridCrossingReduction.prototype.maxNoImprovementIterations = 2;

 /**
  * Function: execute
  *
  * Performs a vertex ordering within ranks as described by Gansner et al
  * 1993
  */
 mxMedianHybridCrossingReduction.prototype.execute = function(parent)
 {
 	var model = this.layout.getModel();

 	// Stores initial ordering as being the best one found so far
 	this.nestedBestRanks = [];

 	for (var i = 0; i < model.ranks.length; i++)
 	{
 		this.nestedBestRanks[i] = model.ranks[i].slice();
 	}

 	var iterationsWithoutImprovement = 0;
 	var currentBestCrossings = this.calculateCrossings(model);

 	for (var i = 0; i < this.maxIterations &&
 		iterationsWithoutImprovement < this.maxNoImprovementIterations; i++)
 	{
 		this.weightedMedian(i, model);
 		this.transpose(i, model);
 		var candidateCrossings = this.calculateCrossings(model);

 		if (candidateCrossings < currentBestCrossings)
 		{
 			currentBestCrossings = candidateCrossings;
 			iterationsWithoutImprovement = 0;

 			// Store the current rankings as the best ones
 			for (var j = 0; j < this.nestedBestRanks.length; j++)
 			{
 				var rank = model.ranks[j];

 				for (var k = 0; k < rank.length; k++)
 				{
 					var cell = rank[k];
 					this.nestedBestRanks[j][cell.getGeneralPurposeVariable(j)] = cell;
 				}
 			}
 		}
 		else
 		{
 			// Increase count of iterations where we haven't improved the
 			// layout
 			iterationsWithoutImprovement++;

 			// Restore the best values to the cells
 			for (var j = 0; j < this.nestedBestRanks.length; j++)
 			{
 				var rank = model.ranks[j];

 				for (var k = 0; k < rank.length; k++)
 				{
 					var cell = rank[k];
 					cell.setGeneralPurposeVariable(j, k);
 				}
 			}
 		}

 		if (currentBestCrossings == 0)
 		{
 			// Do nothing further
 			break;
 		}
 	}

 	// Store the best rankings but in the model
 	var ranks = [];
 	var rankList = [];

 	for (var i = 0; i < model.maxRank + 1; i++)
 	{
 		rankList[i] = [];
 		ranks[i] = rankList[i];
 	}

 	for (var i = 0; i < this.nestedBestRanks.length; i++)
 	{
 		for (var j = 0; j < this.nestedBestRanks[i].length; j++)
 		{
 			rankList[i].push(this.nestedBestRanks[i][j]);
 		}
 	}

 	model.ranks = ranks;
 };


 /**
  * Function: calculateCrossings
  *
  * Calculates the total number of edge crossing in the current graph.
  * Returns the current number of edge crossings in the hierarchy graph
  * model in the current candidate layout
  *
  * Parameters:
  *
  * model - the internal model describing the hierarchy
  */
 mxMedianHybridCrossingReduction.prototype.calculateCrossings = function(model)
 {
 	var numRanks = model.ranks.length;
 	var totalCrossings = 0;

 	for (var i = 1; i < numRanks; i++)
 	{
 		totalCrossings += this.calculateRankCrossing(i, model);
 	}

 	return totalCrossings;
 };

 /**
  * Function: calculateRankCrossing
  *
  * Calculates the number of edges crossings between the specified rank and
  * the rank below it. Returns the number of edges crossings with the rank
  * beneath
  *
  * Parameters:
  *
  * i -  the topmost rank of the pair ( higher rank value )
  * model - the internal model describing the hierarchy
  */
 mxMedianHybridCrossingReduction.prototype.calculateRankCrossing = function(i, model)
 {
 	var totalCrossings = 0;
 	var rank = model.ranks[i];
 	var previousRank = model.ranks[i - 1];

 	var tmpIndices = [];

 	// Iterate over the top rank and fill in the connection information
 	for (var j = 0; j < rank.length; j++)
 	{
 		var node = rank[j];
 		var rankPosition = node.getGeneralPurposeVariable(i);
 		var connectedCells = node.getPreviousLayerConnectedCells(i);
 		var nodeIndices = [];

 		for (var k = 0; k < connectedCells.length; k++)
 		{
 			var connectedNode = connectedCells[k];
 			var otherCellRankPosition = connectedNode.getGeneralPurposeVariable(i - 1);
 			nodeIndices.push(otherCellRankPosition);
 		}

 		nodeIndices.sort(function(x, y) { return x - y; });
 		tmpIndices[rankPosition] = nodeIndices;
 	}

 	var indices = [];

 	for (var j = 0; j < tmpIndices.length; j++)
 	{
 		indices = indices.concat(tmpIndices[j]);
 	}

 	var firstIndex = 1;

 	while (firstIndex < previousRank.length)
 	{
 		firstIndex <<= 1;
 	}

 	var treeSize = 2 * firstIndex - 1;
 	firstIndex -= 1;

 	var tree = [];

 	for (var j = 0; j < treeSize; ++j)
 	{
 		tree[j] = 0;
 	}

 	for (var j = 0; j < indices.length; j++)
 	{
 		var index = indices[j];
 	    var treeIndex = index + firstIndex;
 	    ++tree[treeIndex];

 	    while (treeIndex > 0)
 	    {
 	    	if (treeIndex % 2)
 	    	{
 	    		totalCrossings += tree[treeIndex + 1];
 	    	}

 	    	treeIndex = (treeIndex - 1) >> 1;
 	    	++tree[treeIndex];
 	    }
 	}

 	return totalCrossings;
 };

 /**
  * Function: transpose
  *
  * Takes each possible adjacent cell pair on each rank and checks if
  * swapping them around reduces the number of crossing
  *
  * Parameters:
  *
  * mainLoopIteration - the iteration number of the main loop
  * model - the internal model describing the hierarchy
  */
 mxMedianHybridCrossingReduction.prototype.transpose = function(mainLoopIteration, model)
 {
 	var improved = true;

 	// Track the number of iterations in case of looping
 	var count = 0;
 	var maxCount = 10;
 	while (improved && count++ < maxCount)
 	{
 		// On certain iterations allow allow swapping of cell pairs with
 		// equal edge crossings switched or not switched. This help to
 		// nudge a stuck layout into a lower crossing total.
 		var nudge = mainLoopIteration % 2 == 1 && count % 2 == 1;
 		improved = false;

 		for (var i = 0; i < model.ranks.length; i++)
 		{
 			var rank = model.ranks[i];
 			var orderedCells = [];

 			for (var j = 0; j < rank.length; j++)
 			{
 				var cell = rank[j];
 				var tempRank = cell.getGeneralPurposeVariable(i);

 				// FIXME: Workaround to avoid negative tempRanks
 				if (tempRank < 0)
 				{
 					tempRank = j;
 				}
 				orderedCells[tempRank] = cell;
 			}

 			var leftCellAboveConnections = null;
 			var leftCellBelowConnections = null;
 			var rightCellAboveConnections = null;
 			var rightCellBelowConnections = null;

 			var leftAbovePositions = null;
 			var leftBelowPositions = null;
 			var rightAbovePositions = null;
 			var rightBelowPositions = null;

 			var leftCell = null;
 			var rightCell = null;

 			for (var j = 0; j < (rank.length - 1); j++)
 			{
 				// For each intra-rank adjacent pair of cells
 				// see if swapping them around would reduce the
 				// number of edges crossing they cause in total
 				// On every cell pair except the first on each rank, we
 				// can save processing using the previous values for the
 				// right cell on the new left cell
 				if (j == 0)
 				{
 					leftCell = orderedCells[j];
 					leftCellAboveConnections = leftCell
 							.getNextLayerConnectedCells(i);
 					leftCellBelowConnections = leftCell
 							.getPreviousLayerConnectedCells(i);
 					leftAbovePositions = [];
 					leftBelowPositions = [];

 					for (var k = 0; k < leftCellAboveConnections.length; k++)
 					{
 						leftAbovePositions[k] = leftCellAboveConnections[k].getGeneralPurposeVariable(i + 1);
 					}

 					for (var k = 0; k < leftCellBelowConnections.length; k++)
 					{
 						leftBelowPositions[k] = leftCellBelowConnections[k].getGeneralPurposeVariable(i - 1);
 					}
 				}
 				else
 				{
 					leftCellAboveConnections = rightCellAboveConnections;
 					leftCellBelowConnections = rightCellBelowConnections;
 					leftAbovePositions = rightAbovePositions;
 					leftBelowPositions = rightBelowPositions;
 					leftCell = rightCell;
 				}

 				rightCell = orderedCells[j + 1];
 				rightCellAboveConnections = rightCell
 						.getNextLayerConnectedCells(i);
 				rightCellBelowConnections = rightCell
 						.getPreviousLayerConnectedCells(i);

 				rightAbovePositions = [];
 				rightBelowPositions = [];

 				for (var k = 0; k < rightCellAboveConnections.length; k++)
 				{
 					rightAbovePositions[k] = rightCellAboveConnections[k].getGeneralPurposeVariable(i + 1);
 				}

 				for (var k = 0; k < rightCellBelowConnections.length; k++)
 				{
 					rightBelowPositions[k] = rightCellBelowConnections[k].getGeneralPurposeVariable(i - 1);
 				}

 				var totalCurrentCrossings = 0;
 				var totalSwitchedCrossings = 0;

 				for (var k = 0; k < leftAbovePositions.length; k++)
 				{
 					for (var ik = 0; ik < rightAbovePositions.length; ik++)
 					{
 						if (leftAbovePositions[k] > rightAbovePositions[ik])
 						{
 							totalCurrentCrossings++;
 						}

 						if (leftAbovePositions[k] < rightAbovePositions[ik])
 						{
 							totalSwitchedCrossings++;
 						}
 					}
 				}

 				for (var k = 0; k < leftBelowPositions.length; k++)
 				{
 					for (var ik = 0; ik < rightBelowPositions.length; ik++)
 					{
 						if (leftBelowPositions[k] > rightBelowPositions[ik])
 						{
 							totalCurrentCrossings++;
 						}

 						if (leftBelowPositions[k] < rightBelowPositions[ik])
 						{
 							totalSwitchedCrossings++;
 						}
 					}
 				}

 				if ((totalSwitchedCrossings < totalCurrentCrossings) ||
 					(totalSwitchedCrossings == totalCurrentCrossings &&
 					nudge))
 				{
 					var temp = leftCell.getGeneralPurposeVariable(i);
 					leftCell.setGeneralPurposeVariable(i, rightCell
 							.getGeneralPurposeVariable(i));
 					rightCell.setGeneralPurposeVariable(i, temp);

 					// With this pair exchanged we have to switch all of
 					// values for the left cell to the right cell so the
 					// next iteration for this rank uses it as the left
 					// cell again
 					rightCellAboveConnections = leftCellAboveConnections;
 					rightCellBelowConnections = leftCellBelowConnections;
 					rightAbovePositions = leftAbovePositions;
 					rightBelowPositions = leftBelowPositions;
 					rightCell = leftCell;

 					if (!nudge)
 					{
 						// Don't count nudges as improvement or we'll end
 						// up stuck in two combinations and not finishing
 						// as early as we should
 						improved = true;
 					}
 				}
 			}
 		}
 	}
 };

 /**
  * Function: weightedMedian
  *
  * Sweeps up or down the layout attempting to minimise the median placement
  * of connected cells on adjacent ranks
  *
  * Parameters:
  *
  * iteration - the iteration number of the main loop
  * model - the internal model describing the hierarchy
  */
 mxMedianHybridCrossingReduction.prototype.weightedMedian = function(iteration, model)
 {
 	// Reverse sweep direction each time through this method
 	var downwardSweep = (iteration % 2 == 0);
 	if (downwardSweep)
 	{
 		for (var j = model.maxRank - 1; j >= 0; j--)
 		{
 			this.medianRank(j, downwardSweep);
 		}
 	}
 	else
 	{
 		for (var j = 1; j < model.maxRank; j++)
 		{
 			this.medianRank(j, downwardSweep);
 		}
 	}
 };

 /**
  * Function: medianRank
  *
  * Attempts to minimise the median placement of connected cells on this rank
  * and one of the adjacent ranks
  *
  * Parameters:
  *
  * rankValue - the layer number of this rank
  * downwardSweep - whether or not this is a downward sweep through the graph
  */
 mxMedianHybridCrossingReduction.prototype.medianRank = function(rankValue, downwardSweep)
 {
 	var numCellsForRank = this.nestedBestRanks[rankValue].length;
 	var medianValues = [];
 	var reservedPositions = [];

 	for (var i = 0; i < numCellsForRank; i++)
 	{
 		var cell = this.nestedBestRanks[rankValue][i];
 		var sorterEntry = new MedianCellSorter();
 		sorterEntry.cell = cell;

 		// Flip whether or not equal medians are flipped on up and down
 		// sweeps
 		// TODO re-implement some kind of nudge
 		// medianValues[i].nudge = !downwardSweep;
 		var nextLevelConnectedCells;

 		if (downwardSweep)
 		{
 			nextLevelConnectedCells = cell
 					.getNextLayerConnectedCells(rankValue);
 		}
 		else
 		{
 			nextLevelConnectedCells = cell
 					.getPreviousLayerConnectedCells(rankValue);
 		}

 		var nextRankValue;

 		if (downwardSweep)
 		{
 			nextRankValue = rankValue + 1;
 		}
 		else
 		{
 			nextRankValue = rankValue - 1;
 		}

 		if (nextLevelConnectedCells != null
 				&& nextLevelConnectedCells.length != 0)
 		{
 			sorterEntry.medianValue = this.medianValue(
 					nextLevelConnectedCells, nextRankValue);
 			medianValues.push(sorterEntry);
 		}
 		else
 		{
 			// Nodes with no adjacent vertices are flagged in the reserved array
 			// to indicate they should be left in their current position.
 			reservedPositions[cell.getGeneralPurposeVariable(rankValue)] = true;
 		}
 	}

 	medianValues.sort(MedianCellSorter.prototype.compare);

 	// Set the new position of each node within the rank using
 	// its temp variable
 	for (var i = 0; i < numCellsForRank; i++)
 	{
 		if (reservedPositions[i] == null)
 		{
 			var cell = medianValues.shift().cell;
 			cell.setGeneralPurposeVariable(rankValue, i);
 		}
 	}
 };

 /**
  * Function: medianValue
  *
  * Calculates the median rank order positioning for the specified cell using
  * the connected cells on the specified rank. Returns the median rank
  * ordering value of the connected cells
  *
  * Parameters:
  *
  * connectedCells - the cells on the specified rank connected to the
  * specified cell
  * rankValue - the rank that the connected cell lie upon
  */
 mxMedianHybridCrossingReduction.prototype.medianValue = function(connectedCells, rankValue)
 {
 	var medianValues = [];
 	var arrayCount = 0;

 	for (var i = 0; i < connectedCells.length; i++)
 	{
 		var cell = connectedCells[i];
 		medianValues[arrayCount++] = cell.getGeneralPurposeVariable(rankValue);
 	}

 	// Sort() sorts lexicographically by default (i.e. 11 before 9) so force
 	// numerical order sort
 	medianValues.sort(function(a,b){return a - b;});

 	if (arrayCount % 2 == 1)
 	{
 		// For odd numbers of adjacent vertices return the median
 		return medianValues[Math.floor(arrayCount / 2)];
 	}
 	else if (arrayCount == 2)
 	{
 		return ((medianValues[0] + medianValues[1]) / 2.0);
 	}
 	else
 	{
 		var medianPoint = arrayCount / 2;
 		var leftMedian = medianValues[medianPoint - 1] - medianValues[0];
 		var rightMedian = medianValues[arrayCount - 1]
 				- medianValues[medianPoint];

 		return (medianValues[medianPoint - 1] * rightMedian + medianValues[medianPoint]
 				* leftMedian)
 				/ (leftMedian + rightMedian);
 	}
 };

 /**
  * Class: MedianCellSorter
  *
  * A utility class used to track cells whilst sorting occurs on the median
  * values. Does not violate (x.compareTo(y)==0) == (x.equals(y))
  *
  * Constructor: MedianCellSorter
  *
  * Constructs a new median cell sorter.
  */
 function MedianCellSorter()
 {
 	// empty
 };

 /**
  * Variable: medianValue
  *
  * The weighted value of the cell stored.
  */
 MedianCellSorter.prototype.medianValue = 0;

 /**
  * Variable: cell
  *
  * The cell whose median value is being calculated
  */
 MedianCellSorter.prototype.cell = false;

 /**
  * Function: compare
  *
  * Compares two MedianCellSorters.
  */
 MedianCellSorter.prototype.compare = function(a, b)
 {
 	if (a != null && b != null)
 	{
 		if (b.medianValue > a.medianValue)
 		{
 			return -1;
 		}
 		else if (b.medianValue < a.medianValue)
 		{
 			return 1;
 		}
 		else
 		{
 			return 0;
 		}
 	}
 	else
 	{
 		return 0;
 	}
 };
	/**
	* Copyright (c) 2006-2015, JGraph Ltd
	* Copyright (c) 2006-2015, Gaudenz Alder
	*/
	/**
	* Class: mxMedianHybridCrossingReduction
	*
	* Sets the horizontal locations of node and edge dummy nodes on each layer.
	* Uses median down and up weighings as well heuristic to straighten edges as
	* far as possible.
	*
	* Constructor: mxMedianHybridCrossingReduction
	*
	* Creates a coordinate assignment.
	*
	* Arguments:
	*
	* intraCellSpacing - the minimum buffer between cells on the same rank
	* interRankCellSpacing - the minimum distance between cells on adjacent ranks
	* orientation - the position of the root node(s) relative to the graph
	* initialX - the leftmost coordinate node placement starts at
	*/
	function mxMedianHybridCrossingReduction(layout)
	{
	this.layout = layout;
	};

	/**
	* Extends mxMedianHybridCrossingReduction.
	*/
	mxMedianHybridCrossingReduction.prototype = new mxHierarchicalLayoutStage();
	mxMedianHybridCrossingReduction.prototype.constructor = mxMedianHybridCrossingReduction;

	/**
	* Variable: layout
	*
	* Reference to the enclosing <mxHierarchicalLayout>.
	*/
	mxMedianHybridCrossingReduction.prototype.layout = null;

	/**
	* Variable: maxIterations
	*
	* The maximum number of iterations to perform whilst reducing edge
	* crossings. Default is 24.
	*/
	mxMedianHybridCrossingReduction.prototype.maxIterations = 24;

	/**
	* Variable: nestedBestRanks
	*
	* Stores each rank as a collection of cells in the best order found for
	* each layer so far
	*/
	mxMedianHybridCrossingReduction.prototype.nestedBestRanks = null;

	/**
	* Variable: currentBestCrossings
	*
	* The total number of crossings found in the best configuration so far
	*/
	mxMedianHybridCrossingReduction.prototype.currentBestCrossings = 0;

	/**
	* Variable: iterationsWithoutImprovement
	*
	* The total number of crossings found in the best configuration so far
	*/
	mxMedianHybridCrossingReduction.prototype.iterationsWithoutImprovement = 0;

	/**
	* Variable: maxNoImprovementIterations
	*
	* The total number of crossings found in the best configuration so far
	*/
	mxMedianHybridCrossingReduction.prototype.maxNoImprovementIterations = 2;

	/**
	* Function: execute
	*
	* Performs a vertex ordering within ranks as described by Gansner et al
	* 1993
	*/
	mxMedianHybridCrossingReduction.prototype.execute = function(parent)
	{
	var model = this.layout.getModel();

	// Stores initial ordering as being the best one found so far
	this.nestedBestRanks = [];

	for (var i = 0; i < model.ranks.length; i++)
	{
	this.nestedBestRanks[i] = model.ranks[i].slice();
	}

	var iterationsWithoutImprovement = 0;
	var currentBestCrossings = this.calculateCrossings(model);

	for (var i = 0; i < this.maxIterations &&
	iterationsWithoutImprovement < this.maxNoImprovementIterations; i++)
	{
	this.weightedMedian(i, model);
	this.transpose(i, model);
	var candidateCrossings = this.calculateCrossings(model);

	if (candidateCrossings < currentBestCrossings)
	{
	currentBestCrossings = candidateCrossings;
	iterationsWithoutImprovement = 0;

	// Store the current rankings as the best ones
	for (var j = 0; j < this.nestedBestRanks.length; j++)
	{
	var rank = model.ranks[j];

	for (var k = 0; k < rank.length; k++)
	{
	var cell = rank[k];
	this.nestedBestRanks[j][cell.getGeneralPurposeVariable(j)] = cell;
	}
	}
	}
	else
	{
	// Increase count of iterations where we haven't improved the
	// layout
	iterationsWithoutImprovement++;

	// Restore the best values to the cells
	for (var j = 0; j < this.nestedBestRanks.length; j++)
	{
	var rank = model.ranks[j];

	for (var k = 0; k < rank.length; k++)
	{
	var cell = rank[k];
	cell.setGeneralPurposeVariable(j, k);
	}
	}
	}

	if (currentBestCrossings == 0)
	{
	// Do nothing further
	break;
	}
	}

	// Store the best rankings but in the model
	var ranks = [];
	var rankList = [];

	for (var i = 0; i < model.maxRank + 1; i++)
	{
	rankList[i] = [];
	ranks[i] = rankList[i];
	}

	for (var i = 0; i < this.nestedBestRanks.length; i++)
	{
	for (var j = 0; j < this.nestedBestRanks[i].length; j++)
	{
	rankList[i].push(this.nestedBestRanks[i][j]);
	}
	}

	model.ranks = ranks;
	};


	/**
	* Function: calculateCrossings
	*
	* Calculates the total number of edge crossing in the current graph.
	* Returns the current number of edge crossings in the hierarchy graph
	* model in the current candidate layout
	*
	* Parameters:
	*
	* model - the internal model describing the hierarchy
	*/
	mxMedianHybridCrossingReduction.prototype.calculateCrossings = function(model)
	{
	var numRanks = model.ranks.length;
	var totalCrossings = 0;

	for (var i = 1; i < numRanks; i++)
	{
	totalCrossings += this.calculateRankCrossing(i, model);
	}

	return totalCrossings;
	};

	/**
	* Function: calculateRankCrossing
	*
	* Calculates the number of edges crossings between the specified rank and
	* the rank below it. Returns the number of edges crossings with the rank
	* beneath
	*
	* Parameters:
	*
	* i - the topmost rank of the pair ( higher rank value )
	* model - the internal model describing the hierarchy
	*/
	mxMedianHybridCrossingReduction.prototype.calculateRankCrossing = function(i, model)
	{
	var totalCrossings = 0;
	var rank = model.ranks[i];
	var previousRank = model.ranks[i - 1];

	var tmpIndices = [];

	// Iterate over the top rank and fill in the connection information
	for (var j = 0; j < rank.length; j++)
	{
	var node = rank[j];
	var rankPosition = node.getGeneralPurposeVariable(i);
	var connectedCells = node.getPreviousLayerConnectedCells(i);
	var nodeIndices = [];

	for (var k = 0; k < connectedCells.length; k++)
	{
	var connectedNode = connectedCells[k];
	var otherCellRankPosition = connectedNode.getGeneralPurposeVariable(i - 1);
	nodeIndices.push(otherCellRankPosition);
	}

	nodeIndices.sort(function(x, y) { return x - y; });
	tmpIndices[rankPosition] = nodeIndices;
	}

	var indices = [];

	for (var j = 0; j < tmpIndices.length; j++)
	{
	indices = indices.concat(tmpIndices[j]);
	}

	var firstIndex = 1;

	while (firstIndex < previousRank.length)
	{
	firstIndex <<= 1;
	}

	var treeSize = 2 * firstIndex - 1;
	firstIndex -= 1;

	var tree = [];

	for (var j = 0; j < treeSize; ++j)
	{
	tree[j] = 0;
	}

	for (var j = 0; j < indices.length; j++)
	{
	var index = indices[j];
	var treeIndex = index + firstIndex;
	++tree[treeIndex];

	while (treeIndex > 0)
	{
	if (treeIndex % 2)
	{
	totalCrossings += tree[treeIndex + 1];
	}

	treeIndex = (treeIndex - 1) >> 1;
	++tree[treeIndex];
	}
	}

	return totalCrossings;
	};

	/**
	* Function: transpose
	*
	* Takes each possible adjacent cell pair on each rank and checks if
	* swapping them around reduces the number of crossing
	*
	* Parameters:
	*
	* mainLoopIteration - the iteration number of the main loop
	* model - the internal model describing the hierarchy
	*/
	mxMedianHybridCrossingReduction.prototype.transpose = function(mainLoopIteration, model)
	{
	var improved = true;

	// Track the number of iterations in case of looping
	var count = 0;
	var maxCount = 10;
	while (improved && count++ < maxCount)
	{
	// On certain iterations allow allow swapping of cell pairs with
	// equal edge crossings switched or not switched. This help to
	// nudge a stuck layout into a lower crossing total.
	var nudge = mainLoopIteration % 2 == 1 && count % 2 == 1;
	improved = false;

	for (var i = 0; i < model.ranks.length; i++)
	{
	var rank = model.ranks[i];
	var orderedCells = [];

	for (var j = 0; j < rank.length; j++)
	{
	var cell = rank[j];
	var tempRank = cell.getGeneralPurposeVariable(i);

	// FIXME: Workaround to avoid negative tempRanks
	if (tempRank < 0)
	{
	tempRank = j;
	}
	orderedCells[tempRank] = cell;
	}

	var leftCellAboveConnections = null;
	var leftCellBelowConnections = null;
	var rightCellAboveConnections = null;
	var rightCellBelowConnections = null;

	var leftAbovePositions = null;
	var leftBelowPositions = null;
	var rightAbovePositions = null;
	var rightBelowPositions = null;

	var leftCell = null;
	var rightCell = null;

	for (var j = 0; j < (rank.length - 1); j++)
	{
	// For each intra-rank adjacent pair of cells
	// see if swapping them around would reduce the
	// number of edges crossing they cause in total
	// On every cell pair except the first on each rank, we
	// can save processing using the previous values for the
	// right cell on the new left cell
	if (j == 0)
	{
	leftCell = orderedCells[j];
	leftCellAboveConnections = leftCell
	.getNextLayerConnectedCells(i);
	leftCellBelowConnections = leftCell
	.getPreviousLayerConnectedCells(i);
	leftAbovePositions = [];
	leftBelowPositions = [];

	for (var k = 0; k < leftCellAboveConnections.length; k++)
	{
	leftAbovePositions[k] = leftCellAboveConnections[k].getGeneralPurposeVariable(i + 1);
	}

	for (var k = 0; k < leftCellBelowConnections.length; k++)
	{
	leftBelowPositions[k] = leftCellBelowConnections[k].getGeneralPurposeVariable(i - 1);
	}
	}
	else
	{
	leftCellAboveConnections = rightCellAboveConnections;
	leftCellBelowConnections = rightCellBelowConnections;
	leftAbovePositions = rightAbovePositions;
	leftBelowPositions = rightBelowPositions;
	leftCell = rightCell;
	}

	rightCell = orderedCells[j + 1];
	rightCellAboveConnections = rightCell
	.getNextLayerConnectedCells(i);
	rightCellBelowConnections = rightCell
	.getPreviousLayerConnectedCells(i);

	rightAbovePositions = [];
	rightBelowPositions = [];

	for (var k = 0; k < rightCellAboveConnections.length; k++)
	{
	rightAbovePositions[k] = rightCellAboveConnections[k].getGeneralPurposeVariable(i + 1);
	}

	for (var k = 0; k < rightCellBelowConnections.length; k++)
	{
	rightBelowPositions[k] = rightCellBelowConnections[k].getGeneralPurposeVariable(i - 1);
	}

	var totalCurrentCrossings = 0;
	var totalSwitchedCrossings = 0;

	for (var k = 0; k < leftAbovePositions.length; k++)
	{
	for (var ik = 0; ik < rightAbovePositions.length; ik++)
	{
	if (leftAbovePositions[k] > rightAbovePositions[ik])
	{
	totalCurrentCrossings++;
	}

	if (leftAbovePositions[k] < rightAbovePositions[ik])
	{
	totalSwitchedCrossings++;
	}
	}
	}

	for (var k = 0; k < leftBelowPositions.length; k++)
	{
	for (var ik = 0; ik < rightBelowPositions.length; ik++)
	{
	if (leftBelowPositions[k] > rightBelowPositions[ik])
	{
	totalCurrentCrossings++;
	}

	if (leftBelowPositions[k] < rightBelowPositions[ik])
	{
	totalSwitchedCrossings++;
	}
	}
	}

	if ((totalSwitchedCrossings < totalCurrentCrossings) \|\|
	(totalSwitchedCrossings == totalCurrentCrossings &&
	nudge))
	{
	var temp = leftCell.getGeneralPurposeVariable(i);
	leftCell.setGeneralPurposeVariable(i, rightCell
	.getGeneralPurposeVariable(i));
	rightCell.setGeneralPurposeVariable(i, temp);

	// With this pair exchanged we have to switch all of
	// values for the left cell to the right cell so the
	// next iteration for this rank uses it as the left
	// cell again
	rightCellAboveConnections = leftCellAboveConnections;
	rightCellBelowConnections = leftCellBelowConnections;
	rightAbovePositions = leftAbovePositions;
	rightBelowPositions = leftBelowPositions;
	rightCell = leftCell;

	if (!nudge)
	{
	// Don't count nudges as improvement or we'll end
	// up stuck in two combinations and not finishing
	// as early as we should
	improved = true;
	}
	}
	}
	}
	}
	};

	/**
	* Function: weightedMedian
	*
	* Sweeps up or down the layout attempting to minimise the median placement
	* of connected cells on adjacent ranks
	*
	* Parameters:
	*
	* iteration - the iteration number of the main loop
	* model - the internal model describing the hierarchy
	*/
	mxMedianHybridCrossingReduction.prototype.weightedMedian = function(iteration, model)
	{
	// Reverse sweep direction each time through this method
	var downwardSweep = (iteration % 2 == 0);
	if (downwardSweep)
	{
	for (var j = model.maxRank - 1; j >= 0; j--)
	{
	this.medianRank(j, downwardSweep);
	}
	}
	else
	{
	for (var j = 1; j < model.maxRank; j++)
	{
	this.medianRank(j, downwardSweep);
	}
	}
	};

	/**
	* Function: medianRank
	*
	* Attempts to minimise the median placement of connected cells on this rank
	* and one of the adjacent ranks
	*
	* Parameters:
	*
	* rankValue - the layer number of this rank
	* downwardSweep - whether or not this is a downward sweep through the graph
	*/
	mxMedianHybridCrossingReduction.prototype.medianRank = function(rankValue, downwardSweep)
	{
	var numCellsForRank = this.nestedBestRanks[rankValue].length;
	var medianValues = [];
	var reservedPositions = [];

	for (var i = 0; i < numCellsForRank; i++)
	{
	var cell = this.nestedBestRanks[rankValue][i];
	var sorterEntry = new MedianCellSorter();
	sorterEntry.cell = cell;

	// Flip whether or not equal medians are flipped on up and down
	// sweeps
	// TODO re-implement some kind of nudge
	// medianValues[i].nudge = !downwardSweep;
	var nextLevelConnectedCells;

	if (downwardSweep)
	{
	nextLevelConnectedCells = cell
	.getNextLayerConnectedCells(rankValue);
	}
	else
	{
	nextLevelConnectedCells = cell
	.getPreviousLayerConnectedCells(rankValue);
	}

	var nextRankValue;

	if (downwardSweep)
	{
	nextRankValue = rankValue + 1;
	}
	else
	{
	nextRankValue = rankValue - 1;
	}

	if (nextLevelConnectedCells != null
	&& nextLevelConnectedCells.length != 0)
	{
	sorterEntry.medianValue = this.medianValue(
	nextLevelConnectedCells, nextRankValue);
	medianValues.push(sorterEntry);
	}
	else
	{
	// Nodes with no adjacent vertices are flagged in the reserved array
	// to indicate they should be left in their current position.
	reservedPositions[cell.getGeneralPurposeVariable(rankValue)] = true;
	}
	}

	medianValues.sort(MedianCellSorter.prototype.compare);

	// Set the new position of each node within the rank using
	// its temp variable
	for (var i = 0; i < numCellsForRank; i++)
	{
	if (reservedPositions[i] == null)
	{
	var cell = medianValues.shift().cell;
	cell.setGeneralPurposeVariable(rankValue, i);
	}
	}
	};

	/**
	* Function: medianValue
	*
	* Calculates the median rank order positioning for the specified cell using
	* the connected cells on the specified rank. Returns the median rank
	* ordering value of the connected cells
	*
	* Parameters:
	*
	* connectedCells - the cells on the specified rank connected to the
	* specified cell
	* rankValue - the rank that the connected cell lie upon
	*/
	mxMedianHybridCrossingReduction.prototype.medianValue = function(connectedCells, rankValue)
	{
	var medianValues = [];
	var arrayCount = 0;

	for (var i = 0; i < connectedCells.length; i++)
	{
	var cell = connectedCells[i];
	medianValues[arrayCount++] = cell.getGeneralPurposeVariable(rankValue);
	}

	// Sort() sorts lexicographically by default (i.e. 11 before 9) so force
	// numerical order sort
	medianValues.sort(function(a,b){return a - b;});

	if (arrayCount % 2 == 1)
	{
	// For odd numbers of adjacent vertices return the median
	return medianValues[Math.floor(arrayCount / 2)];
	}
	else if (arrayCount == 2)
	{
	return ((medianValues[0] + medianValues[1]) / 2.0);
	}
	else
	{
	var medianPoint = arrayCount / 2;
	var leftMedian = medianValues[medianPoint - 1] - medianValues[0];
	var rightMedian = medianValues[arrayCount - 1]
	- medianValues[medianPoint];

	return (medianValues[medianPoint - 1] * rightMedian + medianValues[medianPoint]
	* leftMedian)
	/ (leftMedian + rightMedian);
	}
	};

	/**
	* Class: MedianCellSorter
	*
	* A utility class used to track cells whilst sorting occurs on the median
	* values. Does not violate (x.compareTo(y)==0) == (x.equals(y))
	*
	* Constructor: MedianCellSorter
	*
	* Constructs a new median cell sorter.
	*/
	function MedianCellSorter()
	{
	// empty
	};

	/**
	* Variable: medianValue
	*
	* The weighted value of the cell stored.
	*/
	MedianCellSorter.prototype.medianValue = 0;

	/**
	* Variable: cell
	*
	* The cell whose median value is being calculated
	*/
	MedianCellSorter.prototype.cell = false;

	/**
	* Function: compare
	*
	* Compares two MedianCellSorters.
	*/
	MedianCellSorter.prototype.compare = function(a, b)
	{
	if (a != null && b != null)
	{
	if (b.medianValue > a.medianValue)
	{
	return -1;
	}
	else if (b.medianValue < a.medianValue)
	{
	return 1;
	}
	else
	{
	return 0;
	}
	}
	else
	{
	return 0;
	}
	};