text: /**
   * Copyright (c) 2006-2018, JGraph Ltd
   * Copyright (c) 2006-2018, Gaudenz Alder
   */
  /**
   * Class: mxGraphModel
   * 
   * Extends <mxEventSource> to implement a graph model. The graph model acts as
   * a wrapper around the cells which are in charge of storing the actual graph
   * datastructure. The model acts as a transactional wrapper with event
   * notification for all changes, whereas the cells contain the atomic
   * operations for updating the actual datastructure.
   * 
   * Layers:
   * 
   * The cell hierarchy in the model must have a top-level root cell which
   * contains the layers (typically one default layer), which in turn contain the
   * top-level cells of the layers. This means each cell is contained in a layer.
   * If no layers are required, then all new cells should be added to the default
   * layer.
   * 
   * Layers are useful for hiding and showing groups of cells, or for placing
   * groups of cells on top of other cells in the display. To identify a layer,
   * the <isLayer> function is used. It returns true if the parent of the given
   * cell is the root of the model.
   * 
   * Events:
   * 
   * See events section for more details. There is a new set of events for
   * tracking transactional changes as they happen. The events are called
   * startEdit for the initial beginUpdate, executed for each executed change
   * and endEdit for the terminal endUpdate. The executed event contains a
   * property called change which represents the change after execution.
   * 
   * Encoding the model:
   * 
   * To encode a graph model, use the following code:
   * 
   * (code)
   * var enc = new mxCodec();
   * var node = enc.encode(graph.getModel());
   * (end)
   * 
   * This will create an XML node that contains all the model information.
   * 
   * Encoding and decoding changes:
   * 
   * For the encoding of changes, a graph model listener is required that encodes
   * each change from the given array of changes.
   * 
   * (code)
   * model.addListener(mxEvent.CHANGE, function(sender, evt)
   * {
   *   var changes = evt.getProperty('edit').changes;
   *   var nodes = [];
   *   var codec = new mxCodec();
   * 
   *   for (var i = 0; i < changes.length; i++)
   *   {
   *     nodes.push(codec.encode(changes[i]));
   *   }
   *   // do something with the nodes
   * });
   * (end)
   * 
   * For the decoding and execution of changes, the codec needs a lookup function
   * that allows it to resolve cell IDs as follows:
   * 
   * (code)
   * var codec = new mxCodec();
   * codec.lookup = function(id)
   * {
   *   return model.getCell(id);
   * }
   * (end)
   * 
   * For each encoded change (represented by a node), the following code can be
   * used to carry out the decoding and create a change object.
   * 
   * (code)
   * var changes = [];
   * var change = codec.decode(node);
   * change.model = model;
   * change.execute();
   * changes.push(change);
   * (end)
   * 
   * The changes can then be dispatched using the model as follows.
   * 
   * (code)
   * var edit = new mxUndoableEdit(model, false);
   * edit.changes = changes;
   * 
   * edit.notify = function()
   * {
   *   edit.source.fireEvent(new mxEventObject(mxEvent.CHANGE,
   *   	'edit', edit, 'changes', edit.changes));
   *   edit.source.fireEvent(new mxEventObject(mxEvent.NOTIFY,
   *   	'edit', edit, 'changes', edit.changes));
   * }
   * 
   * model.fireEvent(new mxEventObject(mxEvent.UNDO, 'edit', edit));
   * model.fireEvent(new mxEventObject(mxEvent.CHANGE,
   * 		'edit', edit, 'changes', changes));
   * (end)
   *
   * Event: mxEvent.CHANGE
   *
   * Fires when an undoable edit is dispatched. The <code>edit</code> property
   * contains the <mxUndoableEdit>. The <code>changes</code> property contains
   * the array of atomic changes inside the undoable edit. The changes property
   * is <strong>deprecated</strong>, please use edit.changes instead.
   *
   * Example:
   * 
   * For finding newly inserted cells, the following code can be used:
   * 
   * (code)
   * graph.model.addListener(mxEvent.CHANGE, function(sender, evt)
   * {
   *   var changes = evt.getProperty('edit').changes;
   * 
   *   for (var i = 0; i < changes.length; i++)
   *   {
   *     var change = changes[i];
   *     
   *     if (change instanceof mxChildChange &&
   *       change.change.previous == null)
   *     {
   *       graph.startEditingAtCell(change.child);
   *       break;
   *     }
   *   }
   * });
   * (end)
   * 
   * 
   * Event: mxEvent.NOTIFY
   *
   * Same as <mxEvent.CHANGE>, this event can be used for classes that need to
   * implement a sync mechanism between this model and, say, a remote model. In
   * such a setup, only local changes should trigger a notify event and all
   * changes should trigger a change event.
   * 
   * Event: mxEvent.EXECUTE
   * 
   * Fires between begin- and endUpdate and after an atomic change was executed
   * in the model. The <code>change</code> property contains the atomic change
   * that was executed.
   * 
   * Event: mxEvent.EXECUTED
   * 
   * Fires between START_EDIT and END_EDIT after an atomic change was executed.
   * The <code>change</code> property contains the change that was executed.
   *
   * Event: mxEvent.BEGIN_UPDATE
   *
   * Fires after the <updateLevel> was incremented in <beginUpdate>. This event
   * contains no properties.
   * 
   * Event: mxEvent.START_EDIT
   *
   * Fires after the <updateLevel> was changed from 0 to 1. This event
   * contains no properties.
   * 
   * Event: mxEvent.END_UPDATE
   * 
   * Fires after the <updateLevel> was decreased in <endUpdate> but before any
   * notification or change dispatching. The <code>edit</code> property contains
   * the <currentEdit>.
   * 
   * Event: mxEvent.END_EDIT
   *
   * Fires after the <updateLevel> was changed from 1 to 0. This event
   * contains no properties.
   * 
   * Event: mxEvent.BEFORE_UNDO
   * 
   * Fires before the change is dispatched after the update level has reached 0
   * in <endUpdate>. The <code>edit</code> property contains the <curreneEdit>.
   * 
   * Event: mxEvent.UNDO
   * 
   * Fires after the change was dispatched in <endUpdate>. The <code>edit</code>
   * property contains the <currentEdit>.
   * 
   * Constructor: mxGraphModel
   * 
   * Constructs a new graph model. If no root is specified then a new root
   * <mxCell> with a default layer is created.
   * 
   * Parameters:
   * 
   * root - <mxCell> that represents the root cell.
   */
  function mxGraphModel(root)
  {
  	this.currentEdit = this.createUndoableEdit();
  	
  	if (root != null)
  	{
  		this.setRoot(root);
  	}
  	else
  	{
  		this.clear();
  	}
  };
  
  /**
   * Extends mxEventSource.
   */
  mxGraphModel.prototype = new mxEventSource();
  mxGraphModel.prototype.constructor = mxGraphModel;
  
  /**
   * Variable: root
   * 
   * Holds the root cell, which in turn contains the cells that represent the
   * layers of the diagram as child cells. That is, the actual elements of the
   * diagram are supposed to live in the third generation of cells and below.
   */
  mxGraphModel.prototype.root = null;
  
  /**
   * Variable: cells
   * 
   * Maps from Ids to cells.
   */
  mxGraphModel.prototype.cells = null;
  
  /**
   * Variable: maintainEdgeParent
   * 
   * Specifies if edges should automatically be moved into the nearest common
   * ancestor of their terminals. Default is true.
   */
  mxGraphModel.prototype.maintainEdgeParent = true;
  
  /**
   * Variable: ignoreRelativeEdgeParent
   * 
   * Specifies if relative edge parents should be ignored for finding the nearest
   * common ancestors of an edge's terminals. Default is true.
   */
  mxGraphModel.prototype.ignoreRelativeEdgeParent = true;
  
  /**
   * Variable: createIds
   * 
   * Specifies if the model should automatically create Ids for new cells.
   * Default is true.
   */
  mxGraphModel.prototype.createIds = true;
  
  /**
   * Variable: prefix
   * 
   * Defines the prefix of new Ids. Default is an empty string.
   */
  mxGraphModel.prototype.prefix = '';
  
  /**
   * Variable: postfix
   * 
   * Defines the postfix of new Ids. Default is an empty string.
   */
  mxGraphModel.prototype.postfix = '';
  
  /**
   * Variable: nextId
   * 
   * Specifies the next Id to be created. Initial value is 0.
   */
  mxGraphModel.prototype.nextId = 0;
  
  /**
   * Variable: currentEdit
   * 
   * Holds the changes for the current transaction. If the transaction is
   * closed then a new object is created for this variable using
   * <createUndoableEdit>.
   */
  mxGraphModel.prototype.currentEdit = null;
  
  /**
   * Variable: updateLevel
   * 
   * Counter for the depth of nested transactions. Each call to <beginUpdate>
   * will increment this number and each call to <endUpdate> will decrement
   * it. When the counter reaches 0, the transaction is closed and the
   * respective events are fired. Initial value is 0.
   */
  mxGraphModel.prototype.updateLevel = 0;
  
  /**
   * Variable: endingUpdate
   * 
   * True if the program flow is currently inside endUpdate.
   */
  mxGraphModel.prototype.endingUpdate = false;
  
  /**
   * Function: clear
   *
   * Sets a new root using <createRoot>.
   */
  mxGraphModel.prototype.clear = function()
  {
  	this.setRoot(this.createRoot());
  };
  
  /**
   * Function: isCreateIds
   *
   * Returns <createIds>.
   */
  mxGraphModel.prototype.isCreateIds = function()
  {
  	return this.createIds;
  };
  
  /**
   * Function: setCreateIds
   *
   * Sets <createIds>.
   */
  mxGraphModel.prototype.setCreateIds = function(value)
  {
  	this.createIds = value;
  };
  
  /**
   * Function: createRoot
   *
   * Creates a new root cell with a default layer (child 0).
   */
  mxGraphModel.prototype.createRoot = function()
  {
  	var cell = new mxCell();
  	cell.insert(new mxCell());
  	
  	return cell;
  };
  
  /**
   * Function: getCell
   *
   * Returns the <mxCell> for the specified Id or null if no cell can be
   * found for the given Id.
   *
   * Parameters:
   * 
   * id - A string representing the Id of the cell.
   */
  mxGraphModel.prototype.getCell = function(id)
  {
  	return (this.cells != null) ? this.cells[id] : null;
  };
  
  /**
   * Function: filterCells
   * 
   * Returns the cells from the given array where the given filter function
   * returns true.
   */
  mxGraphModel.prototype.filterCells = function(cells, filter)
  {
  	var result = null;
  	
  	if (cells != null)
  	{
  		result = [];
  		
  		for (var i = 0; i < cells.length; i++)
  		{
  			if (filter(cells[i]))
  			{
  				result.push(cells[i]);
  			}
  		}
  	}
  	
  	return result;
  };
  
  /**
   * Function: getDescendants
   * 
   * Returns all descendants of the given cell and the cell itself in an array.
   * 
   * Parameters:
   * 
   * parent - <mxCell> whose descendants should be returned.
   */
  mxGraphModel.prototype.getDescendants = function(parent)
  {
  	return this.filterDescendants(null, parent);
  };
  
  /**
   * Function: filterDescendants
   * 
   * Visits all cells recursively and applies the specified filter function
   * to each cell. If the function returns true then the cell is added
   * to the resulting array. The parent and result paramters are optional.
   * If parent is not specified then the recursion starts at <root>.
   * 
   * Example:
   * The following example extracts all vertices from a given model:
   * (code)
   * var filter = function(cell)
   * {
   * 	return model.isVertex(cell);
   * }
   * var vertices = model.filterDescendants(filter);
   * (end)
   * 
   * Parameters:
   * 
   * filter - JavaScript function that takes an <mxCell> as an argument
   * and returns a boolean.
   * parent - Optional <mxCell> that is used as the root of the recursion.
   */
  mxGraphModel.prototype.filterDescendants = function(filter, parent)
  {
  	// Creates a new array for storing the result
  	var result = [];
  
  	// Recursion starts at the root of the model
  	parent = parent || this.getRoot();
  	
  	// Checks if the filter returns true for the cell
  	// and adds it to the result array
  	if (filter == null || filter(parent))
  	{
  		result.push(parent);
  	}
  	
  	// Visits the children of the cell
  	var childCount = this.getChildCount(parent);
  	
  	for (var i = 0; i < childCount; i++)
  	{
  		var child = this.getChildAt(parent, i);
  		result = result.concat(this.filterDescendants(filter, child));
  	}
  
  	return result;
  };
  
  /**
   * Function: getRoot
   * 
   * Returns the root of the model or the topmost parent of the given cell.
   *
   * Parameters:
   * 
   * cell - Optional <mxCell> that specifies the child.
   */
  mxGraphModel.prototype.getRoot = function(cell)
  {
  	var root = cell || this.root;
  	
  	if (cell != null)
  	{
  		while (cell != null)
  		{
  			root = cell;
  			cell = this.getParent(cell);
  		}
  	}
  	
  	return root;
  };
  
  /**
   * Function: setRoot
   * 
   * Sets the <root> of the model using <mxRootChange> and adds the change to
   * the current transaction. This resets all datastructures in the model and
   * is the preferred way of clearing an existing model. Returns the new
   * root.
   * 
   * Example:
   * 
   * (code)
   * var root = new mxCell();
   * root.insert(new mxCell());
   * model.setRoot(root);
   * (end)
   *
   * Parameters:
   * 
   * root - <mxCell> that specifies the new root.
   */
  mxGraphModel.prototype.setRoot = function(root)
  {
  	this.execute(new mxRootChange(this, root));
  	
  	return root;
  };
  
  /**
   * Function: rootChanged
   * 
   * Inner callback to change the root of the model and update the internal
   * datastructures, such as <cells> and <nextId>. Returns the previous root.
   *
   * Parameters:
   * 
   * root - <mxCell> that specifies the new root.
   */
  mxGraphModel.prototype.rootChanged = function(root)
  {
  	var oldRoot = this.root;
  	this.root = root;
  	
  	// Resets counters and datastructures
  	this.nextId = 0;
  	this.cells = null;
  	this.cellAdded(root);
  	
  	return oldRoot;
  };
  
  /**
   * Function: isRoot
   * 
   * Returns true if the given cell is the root of the model and a non-null
   * value.
   *
   * Parameters:
   * 
   * cell - <mxCell> that represents the possible root.
   */
  mxGraphModel.prototype.isRoot = function(cell)
  {
  	return cell != null && this.root == cell;
  };
  
  /**
   * Function: isLayer
   * 
   * Returns true if <isRoot> returns true for the parent of the given cell.
   *
   * Parameters:
   * 
   * cell - <mxCell> that represents the possible layer.
   */
  mxGraphModel.prototype.isLayer = function(cell)
  {
  	return this.isRoot(this.getParent(cell));
  };
  
  /**
   * Function: isAncestor
   * 
   * Returns true if the given parent is an ancestor of the given child. Note 
   * returns true if child == parent.
   *
   * Parameters:
   * 
   * parent - <mxCell> that specifies the parent.
   * child - <mxCell> that specifies the child.
   */
  mxGraphModel.prototype.isAncestor = function(parent, child)
  {
  	while (child != null && child != parent)
  	{
  		child = this.getParent(child);
  	}
  	
  	return child == parent;
  };
  
  /**
   * Function: contains
   * 
   * Returns true if the model contains the given <mxCell>.
   *
   * Parameters:
   * 
   * cell - <mxCell> that specifies the cell.
   */
  mxGraphModel.prototype.contains = function(cell)
  {
  	return this.isAncestor(this.root, cell);
  };
  
  /**
   * Function: getParent
   * 
   * Returns the parent of the given cell.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose parent should be returned.
   */
  mxGraphModel.prototype.getParent = function(cell)
  {
  	return (cell != null) ? cell.getParent() : null;
  };
  
  /**
   * Function: add
   * 
   * Adds the specified child to the parent at the given index using
   * <mxChildChange> and adds the change to the current transaction. If no
   * index is specified then the child is appended to the parent's array of
   * children. Returns the inserted child.
   * 
   * Parameters:
   * 
   * parent - <mxCell> that specifies the parent to contain the child.
   * child - <mxCell> that specifies the child to be inserted.
   * index - Optional integer that specifies the index of the child.
   */
  mxGraphModel.prototype.add = function(parent, child, index)
  {
  	if (child != parent && parent != null && child != null)
  	{	
  		// Appends the child if no index was specified
  		if (index == null)
  		{
  			index = this.getChildCount(parent);
  		}
  		
  		var parentChanged = parent != this.getParent(child);
  		this.execute(new mxChildChange(this, parent, child, index));
  
  		// Maintains the edges parents by moving the edges
  		// into the nearest common ancestor of its terminals
  		if (this.maintainEdgeParent && parentChanged)
  		{
  			this.updateEdgeParents(child);
  		}
  	}
  	
  	return child;
  };
  
  /**
   * Function: cellAdded
   * 
   * Inner callback to update <cells> when a cell has been added. This
   * implementation resolves collisions by creating new Ids. To change the
   * ID of a cell after it was inserted into the model, use the following
   * code:
   * 
   * (code
   * delete model.cells[cell.getId()];
   * cell.setId(newId);
   * model.cells[cell.getId()] = cell;
   * (end)
   *
   * If the change of the ID should be part of the command history, then the
   * cell should be removed from the model and a clone with the new ID should
   * be reinserted into the model instead.
   *
   * Parameters:
   * 
   * cell - <mxCell> that specifies the cell that has been added.
   */
  mxGraphModel.prototype.cellAdded = function(cell)
  {
  	if (cell != null)
  	{
  		// Creates an Id for the cell if not Id exists
  		if (cell.getId() == null && this.createIds)
  		{
  			cell.setId(this.createId(cell));
  		}
  		
  		if (cell.getId() != null)
  		{
  			var collision = this.getCell(cell.getId());
  			
  			if (collision != cell)
  			{	
  				// Creates new Id for the cell
  				// as long as there is a collision
  				while (collision != null)
  				{
  					cell.setId(this.createId(cell));
  					collision = this.getCell(cell.getId());
  				}
  				
  				// Lazily creates the cells dictionary
  				if (this.cells == null)
  				{
  					this.cells = new Object();
  				}
  				
  				this.cells[cell.getId()] = cell;
  			}
  		}
  		
  		// Makes sure IDs of deleted cells are not reused
  		if (mxUtils.isNumeric(cell.getId()))
  		{
  			this.nextId = Math.max(this.nextId, cell.getId());
  		}
  		
  		// Recursively processes child cells
  		var childCount = this.getChildCount(cell);
  		
  		for (var i=0; i<childCount; i++)
  		{
  			this.cellAdded(this.getChildAt(cell, i));
  		}
  	}
  };
  
  /**
   * Function: createId
   * 
   * Hook method to create an Id for the specified cell. This implementation
   * concatenates <prefix>, id and <postfix> to create the Id and increments
   * <nextId>. The cell is ignored by this implementation, but can be used in
   * overridden methods to prefix the Ids with eg. the cell type.
   *
   * Parameters:
   *
   * cell - <mxCell> to create the Id for.
   */
  mxGraphModel.prototype.createId = function(cell)
  {
  	var id = this.nextId;
  	this.nextId++;
  	
  	return this.prefix + id + this.postfix;
  };
  
  /**
   * Function: updateEdgeParents
   * 
   * Updates the parent for all edges that are connected to cell or one of
   * its descendants using <updateEdgeParent>.
   */
  mxGraphModel.prototype.updateEdgeParents = function(cell, root)
  {
  	// Gets the topmost node of the hierarchy
  	root = root || this.getRoot(cell);
  	
  	// Updates edges on children first
  	var childCount = this.getChildCount(cell);
  	
  	for (var i = 0; i < childCount; i++)
  	{
  		var child = this.getChildAt(cell, i);
  		this.updateEdgeParents(child, root);
  	}
  	
  	// Updates the parents of all connected edges
  	var edgeCount = this.getEdgeCount(cell);
  	var edges = [];
  
  	for (var i = 0; i < edgeCount; i++)
  	{
  		edges.push(this.getEdgeAt(cell, i));
  	}
  	
  	for (var i = 0; i < edges.length; i++)
  	{
  		var edge = edges[i];
  		
  		// Updates edge parent if edge and child have
  		// a common root node (does not need to be the
  		// model root node)
  		if (this.isAncestor(root, edge))
  		{
  			this.updateEdgeParent(edge, root);
  		}
  	}
  };
  
  /**
   * Function: updateEdgeParent
   *
   * Inner callback to update the parent of the specified <mxCell> to the
   * nearest-common-ancestor of its two terminals.
   *
   * Parameters:
   * 
   * edge - <mxCell> that specifies the edge.
   * root - <mxCell> that represents the current root of the model.
   */
  mxGraphModel.prototype.updateEdgeParent = function(edge, root)
  {
  	var source = this.getTerminal(edge, true);
  	var target = this.getTerminal(edge, false);
  	var cell = null;
  	
  	// Uses the first non-relative descendants of the source terminal
  	while (source != null && !this.isEdge(source) &&
  		source.geometry != null && source.geometry.relative)
  	{
  		source = this.getParent(source);
  	}
  	
  	// Uses the first non-relative descendants of the target terminal
  	while (target != null && this.ignoreRelativeEdgeParent &&
  		!this.isEdge(target) && target.geometry != null && 
  		target.geometry.relative)
  	{
  		target = this.getParent(target);
  	}
  	
  	if (this.isAncestor(root, source) && this.isAncestor(root, target))
  	{
  		if (source == target)
  		{
  			cell = this.getParent(source);
  		}
  		else
  		{
  			cell = this.getNearestCommonAncestor(source, target);
  		}
  
  		if (cell != null && (this.getParent(cell) != this.root ||
  			this.isAncestor(cell, edge)) && this.getParent(edge) != cell)
  		{
  			var geo = this.getGeometry(edge);
  			
  			if (geo != null)
  			{
  				var origin1 = this.getOrigin(this.getParent(edge));
  				var origin2 = this.getOrigin(cell);
  				
  				var dx = origin2.x - origin1.x;
  				var dy = origin2.y - origin1.y;
  				
  				geo = geo.clone();
  				geo.translate(-dx, -dy);
  				this.setGeometry(edge, geo);
  			}
  
  			this.add(cell, edge, this.getChildCount(cell));
  		}
  	}
  };
  
  /**
   * Function: getOrigin
   * 
   * Returns the absolute, accumulated origin for the children inside the
   * given parent as an <mxPoint>.
   */
  mxGraphModel.prototype.getOrigin = function(cell)
  {
  	var result = null;
  	
  	if (cell != null)
  	{
  		result = this.getOrigin(this.getParent(cell));
  		
  		if (!this.isEdge(cell))
  		{
  			var geo = this.getGeometry(cell);
  			
  			if (geo != null)
  			{
  				result.x += geo.x;
  				result.y += geo.y;
  			}
  		}
  	}
  	else
  	{
  		result = new mxPoint();
  	}
  	
  	return result;
  };
  
  /**
   * Function: getNearestCommonAncestor
   * 
   * Returns the nearest common ancestor for the specified cells.
   *
   * Parameters:
   * 
   * cell1 - <mxCell> that specifies the first cell in the tree.
   * cell2 - <mxCell> that specifies the second cell in the tree.
   */
  mxGraphModel.prototype.getNearestCommonAncestor = function(cell1, cell2)
  {
  	if (cell1 != null && cell2 != null)
  	{		
  		// Creates the cell path for the second cell
  		var path = mxCellPath.create(cell2);
  
  		if (path != null && path.length > 0)
  		{
  			// Bubbles through the ancestors of the first
  			// cell to find the nearest common ancestor.
  			var cell = cell1;
  			var current = mxCellPath.create(cell);
  			
  			// Inverts arguments
  			if (path.length < current.length)
  			{
  				cell = cell2;
  				var tmp = current;
  				current = path;
  				path = tmp;
  			}
  			
  			while (cell != null)
  			{
  				var parent = this.getParent(cell);
  				
  				// Checks if the cell path is equal to the beginning of the given cell path
  				if (path.indexOf(current + mxCellPath.PATH_SEPARATOR) == 0 && parent != null)
  				{
  					return cell;
  				}
  				
  				current = mxCellPath.getParentPath(current);
  				cell = parent;
  			}
  		}
  	}
  	
  	return null;
  };
  
  /**
   * Function: remove
   * 
   * Removes the specified cell from the model using <mxChildChange> and adds
   * the change to the current transaction. This operation will remove the
   * cell and all of its children from the model. Returns the removed cell.
   *
   * Parameters:
   * 
   * cell - <mxCell> that should be removed.
   */
  mxGraphModel.prototype.remove = function(cell)
  {
  	if (cell == this.root)
  	{
  		this.setRoot(null);
  	}
  	else if (this.getParent(cell) != null)
  	{
  		this.execute(new mxChildChange(this, null, cell));
  	}
  	
  	return cell;
  };
  
  /**
   * Function: cellRemoved
   * 
   * Inner callback to update <cells> when a cell has been removed.
   *
   * Parameters:
   * 
   * cell - <mxCell> that specifies the cell that has been removed.
   */
  mxGraphModel.prototype.cellRemoved = function(cell)
  {
  	if (cell != null && this.cells != null)
  	{
  		// Recursively processes child cells
  		var childCount = this.getChildCount(cell);
  		
  		for (var i = childCount - 1; i >= 0; i--)
  		{
  			this.cellRemoved(this.getChildAt(cell, i));
  		}
  		
  		// Removes the dictionary entry for the cell
  		if (this.cells != null && cell.getId() != null)
  		{
  			delete this.cells[cell.getId()];
  		}
  	}
  };
  
  /**
   * Function: parentForCellChanged
   * 
   * Inner callback to update the parent of a cell using <mxCell.insert>
   * on the parent and return the previous parent.
   *
   * Parameters:
   * 
   * cell - <mxCell> to update the parent for.
   * parent - <mxCell> that specifies the new parent of the cell.
   * index - Optional integer that defines the index of the child
   * in the parent's child array.
   */
  mxGraphModel.prototype.parentForCellChanged = function(cell, parent, index)
  {
  	var previous = this.getParent(cell);
  	
  	if (parent != null)
  	{
  		if (parent != previous || previous.getIndex(cell) != index)
  		{
  			parent.insert(cell, index);
  		}
  	}
  	else if (previous != null)
  	{
  		var oldIndex = previous.getIndex(cell);
  		previous.remove(oldIndex);
  	}
  	
  	// Adds or removes the cell from the model
  	var par = this.contains(parent);
  	var pre = this.contains(previous);
  	
  	if (par && !pre)
  	{
  		this.cellAdded(cell);
  	}
  	else if (pre && !par)
  	{
  		this.cellRemoved(cell);
  	}
  	
  	return previous;
  };
  
  /**
   * Function: getChildCount
   *
   * Returns the number of children in the given cell.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose number of children should be returned.
   */
  mxGraphModel.prototype.getChildCount = function(cell)
  {
  	return (cell != null) ? cell.getChildCount() : 0;
  };
  
  /**
   * Function: getChildAt
   *
   * Returns the child of the given <mxCell> at the given index.
   * 
   * Parameters:
   * 
   * cell - <mxCell> that represents the parent.
   * index - Integer that specifies the index of the child to be returned.
   */
  mxGraphModel.prototype.getChildAt = function(cell, index)
  {
  	return (cell != null) ? cell.getChildAt(index) : null;
  };
  
  /**
   * Function: getChildren
   * 
   * Returns all children of the given <mxCell> as an array of <mxCells>. The
   * return value should be only be read.
   *
   * Parameters:
   * 
   * cell - <mxCell> the represents the parent.
   */
  mxGraphModel.prototype.getChildren = function(cell)
  {
  	return (cell != null) ? cell.children : null;
  };
  	
  /**
   * Function: getChildVertices
   * 
   * Returns the child vertices of the given parent.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose child vertices should be returned.
   */
  mxGraphModel.prototype.getChildVertices = function(parent)
  {
  	return this.getChildCells(parent, true, false);
  };
  		
  /**
   * Function: getChildEdges
   * 
   * Returns the child edges of the given parent.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose child edges should be returned.
   */
  mxGraphModel.prototype.getChildEdges = function(parent)
  {
  	return this.getChildCells(parent, false, true);
  };
  
  /**
   * Function: getChildCells
   * 
   * Returns the children of the given cell that are vertices and/or edges
   * depending on the arguments.
   *
   * Parameters:
   * 
   * cell - <mxCell> the represents the parent.
   * vertices - Boolean indicating if child vertices should be returned.
   * Default is false.
   * edges - Boolean indicating if child edges should be returned.
   * Default is false.
   */
  mxGraphModel.prototype.getChildCells = function(parent, vertices, edges)
  {
  	vertices = (vertices != null) ? vertices : false;
  	edges = (edges != null) ? edges : false;
  	
  	var childCount = this.getChildCount(parent);
  	var result = [];
  
  	for (var i = 0; i < childCount; i++)
  	{
  		var child = this.getChildAt(parent, i);
  
  		if ((!edges && !vertices) || (edges && this.isEdge(child)) ||
  			(vertices && this.isVertex(child)))
  		{
  			result.push(child);
  		}
  	}
  
  	return result;
  };
  		
  /**
   * Function: getTerminal
   * 
   * Returns the source or target <mxCell> of the given edge depending on the
   * value of the boolean parameter.
   *
   * Parameters:
   * 
   * edge - <mxCell> that specifies the edge.
   * isSource - Boolean indicating which end of the edge should be returned.
   */
  mxGraphModel.prototype.getTerminal = function(edge, isSource)
  {
  	return (edge != null) ? edge.getTerminal(isSource) : null;
  };
  
  /**
   * Function: setTerminal
   * 
   * Sets the source or target terminal of the given <mxCell> using
   * <mxTerminalChange> and adds the change to the current transaction.
   * This implementation updates the parent of the edge using <updateEdgeParent>
   * if required.
   *
   * Parameters:
   * 
   * edge - <mxCell> that specifies the edge.
   * terminal - <mxCell> that specifies the new terminal.
   * isSource - Boolean indicating if the terminal is the new source or
   * target terminal of the edge.
   */
  mxGraphModel.prototype.setTerminal = function(edge, terminal, isSource)
  {
  	var terminalChanged = terminal != this.getTerminal(edge, isSource);
  	this.execute(new mxTerminalChange(this, edge, terminal, isSource));
  	
  	if (this.maintainEdgeParent && terminalChanged)
  	{
  		this.updateEdgeParent(edge, this.getRoot());
  	}
  	
  	return terminal;
  };
  	
  /**
   * Function: setTerminals
   * 
   * Sets the source and target <mxCell> of the given <mxCell> in a single
   * transaction using <setTerminal> for each end of the edge.
   *
   * Parameters:
   * 
   * edge - <mxCell> that specifies the edge.
   * source - <mxCell> that specifies the new source terminal.
   * target - <mxCell> that specifies the new target terminal.
   */
  mxGraphModel.prototype.setTerminals = function(edge, source, target)
  {
  	this.beginUpdate();
  	try
  	{
  		this.setTerminal(edge, source, true);
  		this.setTerminal(edge, target, false);
  	}
  	finally
  	{
  		this.endUpdate();
  	}
  };
  
  /**
   * Function: terminalForCellChanged
   * 
   * Inner helper function to update the terminal of the edge using
   * <mxCell.insertEdge> and return the previous terminal.
   * 
   * Parameters:
   * 
   * edge - <mxCell> that specifies the edge to be updated.
   * terminal - <mxCell> that specifies the new terminal.
   * isSource - Boolean indicating if the terminal is the new source or
   * target terminal of the edge.
   */
  mxGraphModel.prototype.terminalForCellChanged = function(edge, terminal, isSource)
  {
  	var previous = this.getTerminal(edge, isSource);
  	
  	if (terminal != null)
  	{
  		terminal.insertEdge(edge, isSource);
  	}
  	else if (previous != null)
  	{
  		previous.removeEdge(edge, isSource);
  	}
  	
  	return previous;
  };
  
  /**
   * Function: getEdgeCount
   * 
   * Returns the number of distinct edges connected to the given cell.
   *
   * Parameters:
   * 
   * cell - <mxCell> that represents the vertex.
   */
  mxGraphModel.prototype.getEdgeCount = function(cell)
  {
  	return (cell != null) ? cell.getEdgeCount() : 0;
  };
  
  /**
   * Function: getEdgeAt
   * 
   * Returns the edge of cell at the given index.
   *
   * Parameters:
   * 
   * cell - <mxCell> that specifies the vertex.
   * index - Integer that specifies the index of the edge
   * to return.
   */
  mxGraphModel.prototype.getEdgeAt = function(cell, index)
  {
  	return (cell != null) ? cell.getEdgeAt(index) : null;
  };
  	
  /**
   * Function: getDirectedEdgeCount
   * 
   * Returns the number of incoming or outgoing edges, ignoring the given
   * edge.
   * 
   * Parameters:
   * 
   * cell - <mxCell> whose edge count should be returned.
   * outgoing - Boolean that specifies if the number of outgoing or
   * incoming edges should be returned.
   * ignoredEdge - <mxCell> that represents an edge to be ignored.
   */
  mxGraphModel.prototype.getDirectedEdgeCount = function(cell, outgoing, ignoredEdge)
  {
  	var count = 0;
  	var edgeCount = this.getEdgeCount(cell);
  
  	for (var i = 0; i < edgeCount; i++)
  	{
  		var edge = this.getEdgeAt(cell, i);
  
  		if (edge != ignoredEdge && this.getTerminal(edge, outgoing) == cell)
  		{
  			count++;
  		}
  	}
  
  	return count;
  };
  
  /**
   * Function: getConnections
   * 
   * Returns all edges of the given cell without loops.
   * 
   * Parameters:
   * 
   * cell - <mxCell> whose edges should be returned.
   * 
   */
  mxGraphModel.prototype.getConnections = function(cell)
  {
  	return this.getEdges(cell, true, true, false);
  };
  
  /**
   * Function: getIncomingEdges
   * 
   * Returns the incoming edges of the given cell without loops.
   * 
   * Parameters:
   * 
   * cell - <mxCell> whose incoming edges should be returned.
   * 
   */
  mxGraphModel.prototype.getIncomingEdges = function(cell)
  {
  	return this.getEdges(cell, true, false, false);
  };
  
  /**
   * Function: getOutgoingEdges
   * 
   * Returns the outgoing edges of the given cell without loops.
   * 
   * Parameters:
   * 
   * cell - <mxCell> whose outgoing edges should be returned.
   * 
   */
  mxGraphModel.prototype.getOutgoingEdges = function(cell)
  {
  	return this.getEdges(cell, false, true, false);
  };
  
  /**
   * Function: getEdges
   * 
   * Returns all distinct edges connected to this cell as a new array of
   * <mxCells>. If at least one of incoming or outgoing is true, then loops
   * are ignored, otherwise if both are false, then all edges connected to
   * the given cell are returned including loops.
   * 
   * Parameters:
   * 
   * cell - <mxCell> that specifies the cell.
   * incoming - Optional boolean that specifies if incoming edges should be
   * returned. Default is true.
   * outgoing - Optional boolean that specifies if outgoing edges should be
   * returned. Default is true.
   * includeLoops - Optional boolean that specifies if loops should be returned.
   * Default is true. 
   */
  mxGraphModel.prototype.getEdges = function(cell, incoming, outgoing, includeLoops)
  {
  	incoming = (incoming != null) ? incoming : true;
  	outgoing = (outgoing != null) ? outgoing : true;
  	includeLoops = (includeLoops != null) ? includeLoops : true;
  	
  	var edgeCount = this.getEdgeCount(cell);
  	var result = [];
  
  	for (var i = 0; i < edgeCount; i++)
  	{
  		var edge = this.getEdgeAt(cell, i);
  		var source = this.getTerminal(edge, true);
  		var target = this.getTerminal(edge, false);
  
  		if ((includeLoops && source == target) || ((source != target) && ((incoming && target == cell) ||
  			(outgoing && source == cell))))
  		{
  			result.push(edge);
  		}
  	}
  
  	return result;
  };
  
  /**
   * Function: getEdgesBetween
   * 
   * Returns all edges between the given source and target pair. If directed
   * is true, then only edges from the source to the target are returned,
   * otherwise, all edges between the two cells are returned.
   * 
   * Parameters:
   * 
   * source - <mxCell> that defines the source terminal of the edge to be
   * returned.
   * target - <mxCell> that defines the target terminal of the edge to be
   * returned.
   * directed - Optional boolean that specifies if the direction of the
   * edge should be taken into account. Default is false.
   */
  mxGraphModel.prototype.getEdgesBetween = function(source, target, directed)
  {
  	directed = (directed != null) ? directed : false;
  	
  	var tmp1 = this.getEdgeCount(source);
  	var tmp2 = this.getEdgeCount(target);
  	
  	// Assumes the source has less connected edges
  	var terminal = source;
  	var edgeCount = tmp1;
  	
  	// Uses the smaller array of connected edges
  	// for searching the edge
  	if (tmp2 < tmp1)
  	{
  		edgeCount = tmp2;
  		terminal = target;
  	}
  	
  	var result = [];
  	
  	// Checks if the edge is connected to the correct
  	// cell and returns the first match
  	for (var i = 0; i < edgeCount; i++)
  	{
  		var edge = this.getEdgeAt(terminal, i);
  		var src = this.getTerminal(edge, true);
  		var trg = this.getTerminal(edge, false);
  		var directedMatch = (src == source) && (trg == target);
  		var oppositeMatch = (trg == source) && (src == target);
  
  		if (directedMatch || (!directed && oppositeMatch))
  		{
  			result.push(edge);
  		}
  	}
  	
  	return result;
  };
  
  /**
   * Function: getOpposites
   * 
   * Returns all opposite vertices wrt terminal for the given edges, only
   * returning sources and/or targets as specified. The result is returned
   * as an array of <mxCells>.
   * 
   * Parameters:
   * 
   * edges - Array of <mxCells> that contain the edges to be examined.
   * terminal - <mxCell> that specifies the known end of the edges.
   * sources - Boolean that specifies if source terminals should be contained
   * in the result. Default is true.
   * targets - Boolean that specifies if target terminals should be contained
   * in the result. Default is true.
   */
  mxGraphModel.prototype.getOpposites = function(edges, terminal, sources, targets)
  {
  	sources = (sources != null) ? sources : true;
  	targets = (targets != null) ? targets : true;
  	
  	var terminals = [];
  	
  	if (edges != null)
  	{
  		for (var i = 0; i < edges.length; i++)
  		{
  			var source = this.getTerminal(edges[i], true);
  			var target = this.getTerminal(edges[i], false);
  			
  			// Checks if the terminal is the source of
  			// the edge and if the target should be
  			// stored in the result
  			if (source == terminal && target != null && target != terminal && targets)
  			{
  				terminals.push(target);
  			}
  			
  			// Checks if the terminal is the taget of
  			// the edge and if the source should be
  			// stored in the result
  			else if (target == terminal && source != null && source != terminal && sources)
  			{
  				terminals.push(source);
  			}
  		}
  	}
  	
  	return terminals;
  };
  
  /**
   * Function: getTopmostCells
   * 
   * Returns the topmost cells of the hierarchy in an array that contains no
   * descendants for each <mxCell> that it contains. Duplicates should be
   * removed in the cells array to improve performance.
   * 
   * Parameters:
   * 
   * cells - Array of <mxCells> whose topmost ancestors should be returned.
   */
  mxGraphModel.prototype.getTopmostCells = function(cells)
  {
  	var dict = new mxDictionary();
  	var tmp = [];
  	
  	for (var i = 0; i < cells.length; i++)
  	{
  		dict.put(cells[i], true);
  	}
  	
  	for (var i = 0; i < cells.length; i++)
  	{
  		var cell = cells[i];
  		var topmost = true;
  		var parent = this.getParent(cell);
  		
  		while (parent != null)
  		{
  			if (dict.get(parent))
  			{
  				topmost = false;
  				break;
  			}
  			
  			parent = this.getParent(parent);
  		}
  		
  		if (topmost)
  		{
  			tmp.push(cell);
  		}
  	}
  	
  	return tmp;
  };
  
  /**
   * Function: isVertex
   * 
   * Returns true if the given cell is a vertex.
   *
   * Parameters:
   * 
   * cell - <mxCell> that represents the possible vertex.
   */
  mxGraphModel.prototype.isVertex = function(cell)
  {
  	return (cell != null) ? cell.isVertex() : false;
  };
  
  /**
   * Function: isEdge
   * 
   * Returns true if the given cell is an edge.
   *
   * Parameters:
   * 
   * cell - <mxCell> that represents the possible edge.
   */
  mxGraphModel.prototype.isEdge = function(cell)
  {
  	return (cell != null) ? cell.isEdge() : false;
  };
  
  /**
   * Function: isConnectable
   * 
   * Returns true if the given <mxCell> is connectable. If <edgesConnectable>
   * is false, then this function returns false for all edges else it returns
   * the return value of <mxCell.isConnectable>.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose connectable state should be returned.
   */
  mxGraphModel.prototype.isConnectable = function(cell)
  {
  	return (cell != null) ? cell.isConnectable() : false;
  };
  
  /**
   * Function: getValue
   * 
   * Returns the user object of the given <mxCell> using <mxCell.getValue>.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose user object should be returned.
   */
  mxGraphModel.prototype.getValue = function(cell)
  {
  	return (cell != null) ? cell.getValue() : null;
  };
  
  /**
   * Function: setValue
   * 
   * Sets the user object of then given <mxCell> using <mxValueChange>
   * and adds the change to the current transaction.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose user object should be changed.
   * value - Object that defines the new user object.
   */
  mxGraphModel.prototype.setValue = function(cell, value)
  {
  	this.execute(new mxValueChange(this, cell, value));
  	
  	return value;
  };
  
  /**
   * Function: valueForCellChanged
   * 
   * Inner callback to update the user object of the given <mxCell>
   * using <mxCell.valueChanged> and return the previous value,
   * that is, the return value of <mxCell.valueChanged>.
   * 
   * To change a specific attribute in an XML node, the following code can be
   * used.
   * 
   * (code)
   * graph.getModel().valueForCellChanged = function(cell, value)
   * {
   *   var previous = cell.value.getAttribute('label');
   *   cell.value.setAttribute('label', value);
   *   
   *   return previous;
   * };
   * (end) 
   */
  mxGraphModel.prototype.valueForCellChanged = function(cell, value)
  {
  	return cell.valueChanged(value);
  };
  
  /**
   * Function: getGeometry
   * 
   * Returns the <mxGeometry> of the given <mxCell>.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose geometry should be returned.
   */
  mxGraphModel.prototype.getGeometry = function(cell)
  {
  	return (cell != null) ? cell.getGeometry() : null;
  };
  
  /**
   * Function: setGeometry
   * 
   * Sets the <mxGeometry> of the given <mxCell>. The actual update
   * of the cell is carried out in <geometryForCellChanged>. The
   * <mxGeometryChange> action is used to encapsulate the change.
   * 
   * Parameters:
   * 
   * cell - <mxCell> whose geometry should be changed.
   * geometry - <mxGeometry> that defines the new geometry.
   */
  mxGraphModel.prototype.setGeometry = function(cell, geometry)
  {
  	if (geometry != this.getGeometry(cell))
  	{
  		this.execute(new mxGeometryChange(this, cell, geometry));
  	}
  	
  	return geometry;
  };
  
  /**
   * Function: geometryForCellChanged
   * 
   * Inner callback to update the <mxGeometry> of the given <mxCell> using
   * <mxCell.setGeometry> and return the previous <mxGeometry>.
   */
  mxGraphModel.prototype.geometryForCellChanged = function(cell, geometry)
  {
  	var previous = this.getGeometry(cell);
  	cell.setGeometry(geometry);
  	
  	return previous;
  };
  
  /**
   * Function: getStyle
   * 
   * Returns the style of the given <mxCell>.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose style should be returned.
   */
  mxGraphModel.prototype.getStyle = function(cell)
  {
  	return (cell != null) ? cell.getStyle() : null;
  };
  
  /**
   * Function: setStyle
   * 
   * Sets the style of the given <mxCell> using <mxStyleChange> and
   * adds the change to the current transaction.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose style should be changed.
   * style - String of the form [stylename;|key=value;] to specify
   * the new cell style.
   */
  mxGraphModel.prototype.setStyle = function(cell, style)
  {
  	if (style != this.getStyle(cell))
  	{
  		this.execute(new mxStyleChange(this, cell, style));
  	}
  	
  	return style;
  };
  
  /**
   * Function: styleForCellChanged
   * 
   * Inner callback to update the style of the given <mxCell>
   * using <mxCell.setStyle> and return the previous style.
   *
   * Parameters:
   * 
   * cell - <mxCell> that specifies the cell to be updated.
   * style - String of the form [stylename;|key=value;] to specify
   * the new cell style.
   */
  mxGraphModel.prototype.styleForCellChanged = function(cell, style)
  {
  	var previous = this.getStyle(cell);
  	cell.setStyle(style);
  	
  	return previous;
  };
  
  /**
   * Function: isCollapsed
   * 
   * Returns true if the given <mxCell> is collapsed.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose collapsed state should be returned.
   */
  mxGraphModel.prototype.isCollapsed = function(cell)
  {
  	return (cell != null) ? cell.isCollapsed() : false;
  };
  
  /**
   * Function: setCollapsed
   * 
   * Sets the collapsed state of the given <mxCell> using <mxCollapseChange>
   * and adds the change to the current transaction.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose collapsed state should be changed.
   * collapsed - Boolean that specifies the new collpased state.
   */
  mxGraphModel.prototype.setCollapsed = function(cell, collapsed)
  {
  	if (collapsed != this.isCollapsed(cell))
  	{
  		this.execute(new mxCollapseChange(this, cell, collapsed));
  	}
  	
  	return collapsed;
  };
  	
  /**
   * Function: collapsedStateForCellChanged
   *
   * Inner callback to update the collapsed state of the
   * given <mxCell> using <mxCell.setCollapsed> and return
   * the previous collapsed state.
   *
   * Parameters:
   * 
   * cell - <mxCell> that specifies the cell to be updated.
   * collapsed - Boolean that specifies the new collpased state.
   */
  mxGraphModel.prototype.collapsedStateForCellChanged = function(cell, collapsed)
  {
  	var previous = this.isCollapsed(cell);
  	cell.setCollapsed(collapsed);
  	
  	return previous;
  };
  
  /**
   * Function: isVisible
   * 
   * Returns true if the given <mxCell> is visible.
   * 
   * Parameters:
   * 
   * cell - <mxCell> whose visible state should be returned.
   */
  mxGraphModel.prototype.isVisible = function(cell)
  {
  	return (cell != null) ? cell.isVisible() : false;
  };
  
  /**
   * Function: setVisible
   * 
   * Sets the visible state of the given <mxCell> using <mxVisibleChange> and
   * adds the change to the current transaction.
   *
   * Parameters:
   * 
   * cell - <mxCell> whose visible state should be changed.
   * visible - Boolean that specifies the new visible state.
   */
  mxGraphModel.prototype.setVisible = function(cell, visible)
  {
  	if (visible != this.isVisible(cell))
  	{
  		this.execute(new mxVisibleChange(this, cell, visible));
  	}
  	
  	return visible;
  };
  	
  /**
   * Function: visibleStateForCellChanged
   *
   * Inner callback to update the visible state of the
   * given <mxCell> using <mxCell.setCollapsed> and return
   * the previous visible state.
   *
   * Parameters:
   * 
   * cell - <mxCell> that specifies the cell to be updated.
   * visible - Boolean that specifies the new visible state.
   */
  mxGraphModel.prototype.visibleStateForCellChanged = function(cell, visible)
  {
  	var previous = this.isVisible(cell);
  	cell.setVisible(visible);
  	
  	return previous;
  };
  
  /**
   * Function: execute
   * 
   * Executes the given edit and fires events if required. The edit object
   * requires an execute function which is invoked. The edit is added to the
   * <currentEdit> between <beginUpdate> and <endUpdate> calls, so that
   * events will be fired if this execute is an individual transaction, that
   * is, if no previous <beginUpdate> calls have been made without calling
   * <endUpdate>. This implementation fires an <execute> event before
   * executing the given change.
   * 
   * Parameters:
   * 
   * change - Object that described the change.
   */
  mxGraphModel.prototype.execute = function(change)
  {
  	change.execute();
  	this.beginUpdate();
  	this.currentEdit.add(change);
  	this.fireEvent(new mxEventObject(mxEvent.EXECUTE, 'change', change));
  	// New global executed event
  	this.fireEvent(new mxEventObject(mxEvent.EXECUTED, 'change', change));
  	this.endUpdate();
  };
  
  /**
   * Function: beginUpdate
   * 
   * Increments the <updateLevel> by one. The event notification
   * is queued until <updateLevel> reaches 0 by use of
   * <endUpdate>.
   *
   * All changes on <mxGraphModel> are transactional,
   * that is, they are executed in a single undoable change
   * on the model (without transaction isolation).
   * Therefore, if you want to combine any
   * number of changes into a single undoable change,
   * you should group any two or more API calls that
   * modify the graph model between <beginUpdate>
   * and <endUpdate> calls as shown here:
   * 
   * (code)
   * var model = graph.getModel();
   * var parent = graph.getDefaultParent();
   * var index = model.getChildCount(parent);
   * model.beginUpdate();
   * try
   * {
   *   model.add(parent, v1, index);
   *   model.add(parent, v2, index+1);
   * }
   * finally
   * {
   *   model.endUpdate();
   * }
   * (end)
   * 
   * Of course there is a shortcut for appending a
   * sequence of cells into the default parent:
   * 
   * (code)
   * graph.addCells([v1, v2]).
   * (end)
   */
  mxGraphModel.prototype.beginUpdate = function()
  {
  	this.updateLevel++;
  	this.fireEvent(new mxEventObject(mxEvent.BEGIN_UPDATE));
  	
  	if (this.updateLevel == 1)
  	{
  		this.fireEvent(new mxEventObject(mxEvent.START_EDIT));
  	}
  };
  
  /**
   * Function: endUpdate
   * 
   * Decrements the <updateLevel> by one and fires an <undo>
   * event if the <updateLevel> reaches 0. This function
   * indirectly fires a <change> event by invoking the notify
   * function on the <currentEdit> und then creates a new
   * <currentEdit> using <createUndoableEdit>.
   *
   * The <undo> event is fired only once per edit, whereas
   * the <change> event is fired whenever the notify
   * function is invoked, that is, on undo and redo of
   * the edit.
   */
  mxGraphModel.prototype.endUpdate = function()
  {
  	this.updateLevel--;
  	
  	if (this.updateLevel == 0)
  	{
  		this.fireEvent(new mxEventObject(mxEvent.END_EDIT));
  	}
  	
  	if (!this.endingUpdate)
  	{
  		this.endingUpdate = this.updateLevel == 0;
  		this.fireEvent(new mxEventObject(mxEvent.END_UPDATE, 'edit', this.currentEdit));
  
  		try
  		{		
  			if (this.endingUpdate && !this.currentEdit.isEmpty())
  			{
  				this.fireEvent(new mxEventObject(mxEvent.BEFORE_UNDO, 'edit', this.currentEdit));
  				var tmp = this.currentEdit;
  				this.currentEdit = this.createUndoableEdit();
  				tmp.notify();
  				this.fireEvent(new mxEventObject(mxEvent.UNDO, 'edit', tmp));
  			}
  		}
  		finally
  		{
  			this.endingUpdate = false;
  		}
  	}
  };
  
  /**
   * Function: createUndoableEdit
   * 
   * Creates a new <mxUndoableEdit> that implements the
   * notify function to fire a <change> and <notify> event
   * through the <mxUndoableEdit>'s source.
   * 
   * Parameters:
   * 
   * significant - Optional boolean that specifies if the edit to be created is
   * significant. Default is true.
   */
  mxGraphModel.prototype.createUndoableEdit = function(significant)
  {
  	var edit = new mxUndoableEdit(this, (significant != null) ? significant : true);
  	
  	edit.notify = function()
  	{
  		// LATER: Remove changes property (deprecated)
  		edit.source.fireEvent(new mxEventObject(mxEvent.CHANGE,
  			'edit', edit, 'changes', edit.changes));
  		edit.source.fireEvent(new mxEventObject(mxEvent.NOTIFY,
  			'edit', edit, 'changes', edit.changes));
  	};
  	
  	return edit;
  };
  
  /**
   * Function: mergeChildren
   * 
   * Merges the children of the given cell into the given target cell inside
   * this model. All cells are cloned unless there is a corresponding cell in
   * the model with the same id, in which case the source cell is ignored and
   * all edges are connected to the corresponding cell in this model. Edges
   * are considered to have no identity and are always cloned unless the
   * cloneAllEdges flag is set to false, in which case edges with the same
   * id in the target model are reconnected to reflect the terminals of the
   * source edges.
   */
  mxGraphModel.prototype.mergeChildren = function(from, to, cloneAllEdges)
  {
  	cloneAllEdges = (cloneAllEdges != null) ? cloneAllEdges : true;
  	
  	this.beginUpdate();
  	try
  	{
  		var mapping = new Object();
  		this.mergeChildrenImpl(from, to, cloneAllEdges, mapping);
  		
  		// Post-processes all edges in the mapping and
  		// reconnects the terminals to the corresponding
  		// cells in the target model
  		for (var key in mapping)
  		{
  			var cell = mapping[key];
  			var terminal = this.getTerminal(cell, true);
  
  			if (terminal != null)
  			{
  				terminal = mapping[mxCellPath.create(terminal)];
  				this.setTerminal(cell, terminal, true);
  			}
  			
  			terminal = this.getTerminal(cell, false);
  			
  			if (terminal != null)
  			{
  				terminal = mapping[mxCellPath.create(terminal)];
  				this.setTerminal(cell, terminal, false);
  			}
  		}
  	}
  	finally
  	{
  		this.endUpdate();
  	}
  };
  
  /**
   * Function: mergeChildren
   * 
   * Clones the children of the source cell into the given target cell in
   * this model and adds an entry to the mapping that maps from the source
   * cell to the target cell with the same id or the clone of the source cell
   * that was inserted into this model.
   */
  mxGraphModel.prototype.mergeChildrenImpl = function(from, to, cloneAllEdges, mapping)
  {
  	this.beginUpdate();
  	try
  	{
  		var childCount = from.getChildCount();
  		
  		for (var i = 0; i < childCount; i++)
  		{
  			var cell = from.getChildAt(i);
  			
  			if (typeof(cell.getId) == 'function')
  			{
  				var id = cell.getId();
  				var target = (id != null && (!this.isEdge(cell) || !cloneAllEdges)) ?
  						this.getCell(id) : null;
  				
  				// Clones and adds the child if no cell exists for the id
  				if (target == null)
  				{
  					var clone = cell.clone();
  					clone.setId(id);
  					
  					// Sets the terminals from the original cell to the clone
  					// because the lookup uses strings not cells in JS
  					clone.setTerminal(cell.getTerminal(true), true);
  					clone.setTerminal(cell.getTerminal(false), false);
  					
  					// Do *NOT* use model.add as this will move the edge away
  					// from the parent in updateEdgeParent if maintainEdgeParent
  					// is enabled in the target model
  					target = to.insert(clone);
  					this.cellAdded(target);
  				}
  				
  				// Stores the mapping for later reconnecting edges
  				mapping[mxCellPath.create(cell)] = target;
  				
  				// Recurses
  				this.mergeChildrenImpl(cell, target, cloneAllEdges, mapping);
  			}
  		}
  	}
  	finally
  	{
  		this.endUpdate();
  	}
  };
  
  /**
   * Function: getParents
   * 
   * Returns an array that represents the set (no duplicates) of all parents
   * for the given array of cells.
   * 
   * Parameters:
   * 
   * cells - Array of cells whose parents should be returned.
   */
  mxGraphModel.prototype.getParents = function(cells)
  {
  	var parents = [];
  	
  	if (cells != null)
  	{
  		var dict = new mxDictionary();
  		
  		for (var i = 0; i < cells.length; i++)
  		{
  			var parent = this.getParent(cells[i]);
  			
  			if (parent != null && !dict.get(parent))
  			{
  				dict.put(parent, true);
  				parents.push(parent);
  			}
  		}
  	}
  	
  	return parents;
  };
  
  //
  // Cell Cloning
  //
  
  /**
   * Function: cloneCell
   * 
   * Returns a deep clone of the given <mxCell> (including
   * the children) which is created using <cloneCells>.
   *
   * Parameters:
   * 
   * cell - <mxCell> to be cloned.
   */
  mxGraphModel.prototype.cloneCell = function(cell)
  {
  	if (cell != null)
  	{
  		return this.cloneCells([cell], true)[0];
  	}
  	
  	return null;
  };
  
  /**
   * Function: cloneCells
   * 
   * Returns an array of clones for the given array of <mxCells>.
   * Depending on the value of includeChildren, a deep clone is created for
   * each cell. Connections are restored based if the corresponding
   * cell is contained in the passed in array.
   *
   * Parameters:
   * 
   * cells - Array of <mxCell> to be cloned.
   * includeChildren - Boolean indicating if the cells should be cloned
   * with all descendants.
   * mapping - Optional mapping for existing clones.
   */
  mxGraphModel.prototype.cloneCells = function(cells, includeChildren, mapping)
  {
  	mapping = (mapping != null) ? mapping : new Object();
  	var clones = [];
  	
  	for (var i = 0; i < cells.length; i++)
  	{
  		if (cells[i] != null)
  		{
  			clones.push(this.cloneCellImpl(cells[i], mapping, includeChildren));
  		}
  		else
  		{
  			clones.push(null);
  		}
  	}
  	
  	for (var i = 0; i < clones.length; i++)
  	{
  		if (clones[i] != null)
  		{
  			this.restoreClone(clones[i], cells[i], mapping);
  		}
  	}
  	
  	return clones;
  };
  			
  /**
   * Function: cloneCellImpl
   * 
   * Inner helper method for cloning cells recursively.
   */
  mxGraphModel.prototype.cloneCellImpl = function(cell, mapping, includeChildren)
  {
  	var ident = mxObjectIdentity.get(cell);
  	var clone = mapping[ident];
  	
  	if (clone == null)
  	{
  		clone = this.cellCloned(cell);
  		mapping[ident] = clone;
  
  		if (includeChildren)
  		{
  			var childCount = this.getChildCount(cell);
  			
  			for (var i = 0; i < childCount; i++)
  			{
  				var cloneChild = this.cloneCellImpl(
  					this.getChildAt(cell, i), mapping, true);
  				clone.insert(cloneChild);
  			}
  		}
  	}
  	
  	return clone;
  };
  
  /**
   * Function: cellCloned
   * 
   * Hook for cloning the cell. This returns cell.clone() or
   * any possible exceptions.
   */
  mxGraphModel.prototype.cellCloned = function(cell)
  {
  	return cell.clone();
  };
  
  /**
   * Function: restoreClone
   * 
   * Inner helper method for restoring the connections in
   * a network of cloned cells.
   */
  mxGraphModel.prototype.restoreClone = function(clone, cell, mapping)
  {
  	var source = this.getTerminal(cell, true);
  	
  	if (source != null)
  	{
  		var tmp = mapping[mxObjectIdentity.get(source)];
  		
  		if (tmp != null)
  		{
  			tmp.insertEdge(clone, true);
  		}
  	}
  	
  	var target = this.getTerminal(cell, false);
  	
  	if (target != null)
  	{
  		var tmp = mapping[mxObjectIdentity.get(target)];
  		
  		if (tmp != null)
  		{	
  			tmp.insertEdge(clone, false);
  		}
  	}
  	
  	var childCount = this.getChildCount(clone);
  	
  	for (var i = 0; i < childCount; i++)
  	{
  		this.restoreClone(this.getChildAt(clone, i),
  			this.getChildAt(cell, i), mapping);
  	}
  };
  
  //
  // Atomic changes
  //
  
  /**
   * Class: mxRootChange
   * 
   * Action to change the root in a model.
   *
   * Constructor: mxRootChange
   * 
   * Constructs a change of the root in the
   * specified model.
   */
  function mxRootChange(model, root)
  {
  	this.model = model;
  	this.root = root;
  	this.previous = root;
  };
  
  /**
   * Function: execute
   * 
   * Carries out a change of the root using
   * <mxGraphModel.rootChanged>.
   */
  mxRootChange.prototype.execute = function()
  {
  	this.root = this.previous;
  	this.previous = this.model.rootChanged(this.previous);
  };
  
  /**
   * Class: mxChildChange
   * 
   * Action to add or remove a child in a model.
   *
   * Constructor: mxChildChange
   * 
   * Constructs a change of a child in the
   * specified model.
   */
  function mxChildChange(model, parent, child, index)
  {
  	this.model = model;
  	this.parent = parent;
  	this.previous = parent;
  	this.child = child;
  	this.index = index;
  	this.previousIndex = index;
  };
  
  /**
   * Function: execute
   * 
   * Changes the parent of <child> using
   * <mxGraphModel.parentForCellChanged> and
   * removes or restores the cell's
   * connections.
   */
  mxChildChange.prototype.execute = function()
  {
  	if (this.child != null)
  	{
  		var tmp = this.model.getParent(this.child);
  		var tmp2 = (tmp != null) ? tmp.getIndex(this.child) : 0;
  		
  		if (this.previous == null)
  		{
  			this.connect(this.child, false);
  		}
  		
  		tmp = this.model.parentForCellChanged(
  			this.child, this.previous, this.previousIndex);
  			
  		if (this.previous != null)
  		{
  			this.connect(this.child, true);
  		}
  		
  		this.parent = this.previous;
  		this.previous = tmp;
  		this.index = this.previousIndex;
  		this.previousIndex = tmp2;
  	}
  };
  
  /**
   * Function: disconnect
   * 
   * Disconnects the given cell recursively from its
   * terminals and stores the previous terminal in the
   * cell's terminals.
   */
  mxChildChange.prototype.connect = function(cell, isConnect)
  {
  	isConnect = (isConnect != null) ? isConnect : true;
  	
  	var source = cell.getTerminal(true);
  	var target = cell.getTerminal(false);
  	
  	if (source != null)
  	{
  		if (isConnect)
  		{
  			this.model.terminalForCellChanged(cell, source, true);
  		}
  		else
  		{
  			this.model.terminalForCellChanged(cell, null, true);
  		}
  	}
  	
  	if (target != null)
  	{
  		if (isConnect)
  		{
  			this.model.terminalForCellChanged(cell, target, false);
  		}
  		else
  		{
  			this.model.terminalForCellChanged(cell, null, false);
  		}
  	}
  	
  	cell.setTerminal(source, true);
  	cell.setTerminal(target, false);
  	
  	var childCount = this.model.getChildCount(cell);
  	
  	for (var i=0; i<childCount; i++)
  	{
  		this.connect(this.model.getChildAt(cell, i), isConnect);
  	}
  };
  
  /**
   * Class: mxTerminalChange
   * 
   * Action to change a terminal in a model.
   *
   * Constructor: mxTerminalChange
   * 
   * Constructs a change of a terminal in the 
   * specified model.
   */
  function mxTerminalChange(model, cell, terminal, source)
  {
  	this.model = model;
  	this.cell = cell;
  	this.terminal = terminal;
  	this.previous = terminal;
  	this.source = source;
  };
  
  /**
   * Function: execute
   * 
   * Changes the terminal of <cell> to <previous> using
   * <mxGraphModel.terminalForCellChanged>.
   */
  mxTerminalChange.prototype.execute = function()
  {
  	if (this.cell != null)
  	{
  		this.terminal = this.previous;
  		this.previous = this.model.terminalForCellChanged(
  			this.cell, this.previous, this.source);
  	}
  };
  
  /**
   * Class: mxValueChange
   * 
   * Action to change a user object in a model.
   *
   * Constructor: mxValueChange
   * 
   * Constructs a change of a user object in the 
   * specified model.
   */
  function mxValueChange(model, cell, value)
  {
  	this.model = model;
  	this.cell = cell;
  	this.value = value;
  	this.previous = value;
  };
  
  /**
   * Function: execute
   * 
   * Changes the value of <cell> to <previous> using
   * <mxGraphModel.valueForCellChanged>.
   */
  mxValueChange.prototype.execute = function()
  {
  	if (this.cell != null)
  	{
  		this.value = this.previous;
  		this.previous = this.model.valueForCellChanged(
  			this.cell, this.previous);
  	}
  };
  
  /**
   * Class: mxStyleChange
   * 
   * Action to change a cell's style in a model.
   *
   * Constructor: mxStyleChange
   * 
   * Constructs a change of a style in the
   * specified model.
   */
  function mxStyleChange(model, cell, style)
  {
  	this.model = model;
  	this.cell = cell;
  	this.style = style;
  	this.previous = style;
  };
  
  /**
   * Function: execute
   * 
   * Changes the style of <cell> to <previous> using
   * <mxGraphModel.styleForCellChanged>.
   */
  mxStyleChange.prototype.execute = function()
  {
  	if (this.cell != null)
  	{
  		this.style = this.previous;
  		this.previous = this.model.styleForCellChanged(
  			this.cell, this.previous);
  	}
  };
  
  /**
   * Class: mxGeometryChange
   * 
   * Action to change a cell's geometry in a model.
   *
   * Constructor: mxGeometryChange
   * 
   * Constructs a change of a geometry in the
   * specified model.
   */
  function mxGeometryChange(model, cell, geometry)
  {
  	this.model = model;
  	this.cell = cell;
  	this.geometry = geometry;
  	this.previous = geometry;
  };
  
  /**
   * Function: execute
   * 
   * Changes the geometry of <cell> ro <previous> using
   * <mxGraphModel.geometryForCellChanged>.
   */
  mxGeometryChange.prototype.execute = function()
  {
  	if (this.cell != null)
  	{
  		this.geometry = this.previous;
  		this.previous = this.model.geometryForCellChanged(
  			this.cell, this.previous);
  	}
  };
  
  /**
   * Class: mxCollapseChange
   * 
   * Action to change a cell's collapsed state in a model.
   *
   * Constructor: mxCollapseChange
   * 
   * Constructs a change of a collapsed state in the
   * specified model.
   */
  function mxCollapseChange(model, cell, collapsed)
  {
  	this.model = model;
  	this.cell = cell;
  	this.collapsed = collapsed;
  	this.previous = collapsed;
  };
  
  /**
   * Function: execute
   * 
   * Changes the collapsed state of <cell> to <previous> using
   * <mxGraphModel.collapsedStateForCellChanged>.
   */
  mxCollapseChange.prototype.execute = function()
  {
  	if (this.cell != null)
  	{
  		this.collapsed = this.previous;
  		this.previous = this.model.collapsedStateForCellChanged(
  			this.cell, this.previous);
  	}
  };
  
  /**
   * Class: mxVisibleChange
   * 
   * Action to change a cell's visible state in a model.
   *
   * Constructor: mxVisibleChange
   * 
   * Constructs a change of a visible state in the
   * specified model.
   */
  function mxVisibleChange(model, cell, visible)
  {
  	this.model = model;
  	this.cell = cell;
  	this.visible = visible;
  	this.previous = visible;
  };
  
  /**
   * Function: execute
   * 
   * Changes the visible state of <cell> to <previous> using
   * <mxGraphModel.visibleStateForCellChanged>.
   */
  mxVisibleChange.prototype.execute = function()
  {
  	if (this.cell != null)
  	{
  		this.visible = this.previous;
  		this.previous = this.model.visibleStateForCellChanged(
  			this.cell, this.previous);
  	}
  };
  
  /**
   * Class: mxCellAttributeChange
   * 
   * Action to change the attribute of a cell's user object.
   * There is no method on the graph model that uses this
   * action. To use the action, you can use the code shown
   * in the example below.
   * 
   * Example:
   * 
   * To change the attributeName in the cell's user object
   * to attributeValue, use the following code:
   * 
   * (code)
   * model.beginUpdate();
   * try
   * {
   *   var edit = new mxCellAttributeChange(
   *     cell, attributeName, attributeValue);
   *   model.execute(edit);
   * }
   * finally
   * {
   *   model.endUpdate();
   * } 
   * (end)
   *
   * Constructor: mxCellAttributeChange
   * 
   * Constructs a change of a attribute of the DOM node
   * stored as the value of the given <mxCell>.
   */
  function mxCellAttributeChange(cell, attribute, value)
  {
  	this.cell = cell;
  	this.attribute = attribute;
  	this.value = value;
  	this.previous = value;
  };
  
  /**
   * Function: execute
   * 
   * Changes the attribute of the cell's user object by
   * using <mxCell.setAttribute>.
   */
  mxCellAttributeChange.prototype.execute = function()
  {
  	if (this.cell != null)
  	{
  		var tmp = this.cell.getAttribute(this.attribute);
  		
  		if (this.previous == null)
  		{
  			this.cell.value.removeAttribute(this.attribute);
  		}
  		else
  		{
  			this.cell.setAttribute(this.attribute, this.previous);
  		}
  		
  		this.previous = tmp;
  	}
  };
  
  __mxOutput.mxGraphModel = typeof mxGraphModel !== 'undefined' ? mxGraphModel : undefined;
  