Return-Path: Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: (qmail 84239 invoked from network); 10 Aug 2010 17:14:29 -0000 Received: from unknown (HELO mail.apache.org) (140.211.11.3) by 140.211.11.9 with SMTP; 10 Aug 2010 17:14:29 -0000 Received: (qmail 16139 invoked by uid 500); 10 Aug 2010 17:14:28 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 16063 invoked by uid 500); 10 Aug 2010 17:14:27 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 16056 invoked by uid 99); 10 Aug 2010 17:14:27 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 10 Aug 2010 17:14:27 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 10 Aug 2010 17:14:23 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id E60E72388A3B; Tue, 10 Aug 2010 17:13:06 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r984129 [2/3] - in /commons/sandbox/gsoc/2010/scxml-js/trunk: demo/hierarchical-layout-drag-and-drop/ demo/hierarchical_layout/ src/javascript/scxml/cgf/ src/javascript/scxml/cgf/backends/js/ src/javascript/scxml/cgf/layout/ src/javascript/... Date: Tue, 10 Aug 2010 17:13:06 -0000 To: commits@commons.apache.org From: jbeard@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20100810171306.E60E72388A3B@eris.apache.org> Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/HorizontalPositioner.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/HorizontalPositioner.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/HorizontalPositioner.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/HorizontalPositioner.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,190 @@ +/* +HorizontalPositioner.py + +Algorithms dealing with the third phase of Sugiyama-style hierarchical layout, +horizontal position assignment of each node (while respecting node order). + +By Denis Dube, Sept. 2005 +*/ + +require.def("src/javascript/scxml/cgf/layout/hierarchical/HorizontalPositioner", +["src/javascript/scxml/cgf/layout/hierarchical/NodeWrapper"], +function(NodeWrapper){ + + function priorityBarycenterPositioner(levelDictionary, maxIterations){ + /* + Given a layering & ordering of nodes, this will set them on a grid such + that they respect the layering && ordering but such that nodes are as + close as possible (horizontally) to their children && parents. + This is done by sweeping up/down using barycenters. + */ + var gridSize = 0 + + // Re-order each level so that self-loops are close to their node + // NOTE: self-loops are drawn on the level below their node + // This actually decreases the // of crossings although they're undetectable + // by the crossing counting algorithm + levelDictionary.forEach(function(level){ + __updateOrder(level) + level.forEach(function(node){ + if(NodeWrapper.SelfLoopList.indexOf(node) !== -1){ + var childParent = node.parents[0] + + // Get the orders of all the children of the self-loop's parent + var childOrders = childParent.children.map(function(child){ + return child.getOrder(); + }); + childOrders.sort() + + // Use the median order of all the children + var newOrder = childOrders[Math.ceil(childOrders.length / 2)] + level.splice(level.indexOf(node),1) + level.splice(newOrder, 0, node) + } + }) + }); + + + + // Set priorities for node placements according to fan in, fan out, edges + levelDictionary.forEach(function(level){ + var i = 0 + level.forEach(function(node){ + // Set initial grid position && calculate node priority + node.setGridPosition(i) + node.calculatePriority() + + // Get maximum horizontal grid size + i += 1 + gridSize = Math.max(gridSize , i) + }) + }); + + //maxIterations = self.__optionsDatabase.get('baryPlaceMax') + var movements = 1 + var iterations = 0 + // Iterate up/down, preserver order, but move to take advantage of barycenter + while(movements > 0 && iterations < maxIterations){ + movements = 0 + // Sweep down/up + for(var i = 0; i < levelDictionary.length - 1; i++){ + movements += __prettyNodeBarycenter(levelDictionary[i], true, gridSize) + movements += __prettyNodeBarycenter(levelDictionary[i + 1], false, gridSize) + } + iterations += 1 + } + + // Make sure we are globally flushed to the left + var minGridX = Number.MAX_VALUE; + levelDictionary.forEach(function(level){ + minGridX = Math.min(minGridX, level[0].getGridPosition()) + }); + if(minGridX != 0){ + levelDictionary.forEach(function(level){ + level.forEach(function(node){ + node.setGridPosition(node.getGridPosition() - minGridX) + }) + }) + } + } + + + function __prettyNodeBarycenter(levelList, isGoingDown, gridSize){ + /* + Submethod of the node placer, works on one level, in given direction + */ + var movements = 0 + var nodeInLevelIndex = 0 + // Iterate over all nodes, get their bary center, try to move them to it + levelList.forEach(function(node){ + var baryCenterFloat = node.getGridBarycenter(isGoingDown) + + // No children/parent + if(baryCenterFloat == null) return + + var desiredGridPosition = Math.round(baryCenterFloat) + var currentGridPosition = node.getGridPosition() + + // If not at desired spot, try to move there + if(currentGridPosition != desiredGridPosition){ + var isMovingRight = desiredGridPosition > currentGridPosition + movements += __move(levelList, nodeInLevelIndex, node, isMovingRight, gridSize) + } + + nodeInLevelIndex += 1 + }); + return movements + } + + + function __move(levelList, nodeInLevelIndex, moveNode, isMovingRight, gridSize){ + /* + Sub-submethod... this will recusively try to move a node horizontally + to the right or left. The recursion occurs if a node moving to a new + location must displace a node already occupying the spot. Move will + fail if a node being nudged away has priority or grid boundary reached + */ + var newGridPosition = moveNode.getGridPosition() + (isMovingRight ? 1 : -1) + + // Can we move there? Target in bounds? + if(newGridPosition < 0 || newGridPosition > gridSize) return 0 + + var neighborIndex = nodeInLevelIndex + (isMovingRight ? 1 : -1) // +/- 1 index + + var isMoving; + // No neighbor to the right! We can move there + if(isMovingRight && neighborIndex > levelList.length - 1){ + isMoving = true + } + + // No neighbor to the left! We can move there + else if(! isMovingRight && neighborIndex < 0){ + isMoving = true + } + + // Have to shove the neighbor out of his spot... + else { + isMoving = false + var neighborNode = levelList[neighborIndex] + var neighborGridPosition = neighborNode.getGridPosition() + // Neighbor definately in our spot... + if(neighborGridPosition == newGridPosition){ + var movePriority = moveNode.getPriority() + var neighborPriority = neighborNode.getPriority() + // Do we out-prioritize the neighbor? + if(movePriority > neighborPriority) + isMoving = __move(levelList, neighborIndex, neighborNode, isMovingRight, gridSize) + } + else{ + isMoving = true + } + } + + // We can move, set new grid position + if(isMoving){ + moveNode.setGridPosition(newGridPosition) + return 1 + } + return 0 + } + + + + + function __updateOrder(orderedLayer){ + /* + The ordering is implicit in the node sequence in the list + However to do a node sort, it's handy to have each node know its order + This order is used only within __barycentricOrdering() except for debug + */ + var i = 0 + orderedLayer.forEach(function(node){ + node.setOrder(i) + i += 1 + }); + } + + return { + priorityBarycenterPositioner : priorityBarycenterPositioner + } +}); Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/HorizontalPositioner.js ------------------------------------------------------------------------------ svn:eol-style = native Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/LayeringModule.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/LayeringModule.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/LayeringModule.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/LayeringModule.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,555 @@ +/* +LayeringModule.py + +This module is responsible for creating a proper layering of an arbitrary +directed graph. The optimal solution (minmal height and width layering) is an +NP-complete problem. + +Responsibilities: + 1) Eliminate cycles + 2) Assign each node to a layer + 3) Assign dummy nodes to layers wherever edges traverse multipler layers + +Known layering algorithms: + 1) Longest-path heuristic, minimizes height + 2) Coffman-Graham heuristic, minimizes width given an upperbound on the width + 3) Gansner et al. ILP, minimizes dummy edges + 4) Healy et al. ILP, minimizes width and dummy edges, given upperbound on + both the width and the height + 5) Tarassov et al. heuristic, minimizes width and width of dummy edges + +By Denis Dube, Sept. 2005 +*/ +require.def("src/javascript/scxml/cgf/layout/hierarchical/LayeringModule", +["src/javascript/scxml/cgf/layout/hierarchical/NodeWrapper"], +function(NodeWrapper){ + + + function longestPathLayeringTopDown(wrappedNodeList){ + /* + This algorithm assigns each node in the wrappedNodeList a layer, working + its way from the root nodes all the way to the leafs. + This algorithm is the simplest & fastest for layering, and minimizes height. + Unfortunately, it does not bound the width at all! + The algorithm works in O(n) + Requires approximately 0 seconds for 127 nodes, 135 edges on P4-3.2ghz + */ + + // Get roots in the acyclic graph (wrappedNodeList is topologically sorted) + var rootNodes = [] + wrappedNodeList.forEach(function(wrappedNode){ + if(wrappedNode.parents.length == 0) + rootNodes.push(wrappedNode) + }) + + console.log("rootNodes") + rootNodes.forEach(function(node){ + console.log(' ', node.getName()) + }) + + // Place each node on a layer + // NOTE: This may set a single node's layer more than once but since + // a topological sort is in effect, the last one is the "right" one... + var queuedNodes = rootNodes.slice() + var currentLevelInt = 0 + while(queuedNodes.length > 0){ + var tempQueue = [] + queuedNodes.forEach(function(node){ + node.setLayer(currentLevelInt) // Make each node aware of its layer + tempQueue = tempQueue.concat(node.children) // Children of this node + }); + queuedNodes = tempQueue + currentLevelInt += 1 + } + + return __buildLevelDictionary(wrappedNodeList) + } + + function longestPathLayeringBottomUp(wrappedNodeList){ + /* + This is a simple layering algorithm that places nodes in layers from the + leaves to the root. The height is no greater than the longest path from + a leaf to the root. + The implementation is provided for reference in the LNCS article: + A Heuristic for Minimum-Width Graph Layering with Consideration of Dummy + odes. + By: Alexandre Tarassov and Nikola S. Nikolov and Jurgen Branke + This algorithm is O(n^2) + Requires approximately 0.3 seconds for 127 nodes, 135 edges on P4-3.2ghz + */ + + var rejectedNodeList = [] + var unassignedNodeList = wrappedNodeList.slice() + var assignedNodesCurrentLayer = [] + var assignedNodesInSubLayers = [] + var currentLayerInt = 0 + console.log('-------------------- Layer 0 --------------') + while(unassignedNodeList.length){ + + // Choose an unassigned node + var wasNodeSelected = false + for(var i=0; i < unassignedNodeList.length; i++){ + var node = unassignedNodeList[i]; + + // Slight optimization: ignore already rejected nodes on current layer + if(rejectedNodeList.indexOf(node) !== -1) + continue; + + console.log('Node:', node, node.children) + + // Check if this node has a successor that is not already layer assigned + wasNodeSelected = true + for(var j=0; j < node.children.length; j++){ + var child = node.children[j]; + + if(assignedNodesInSubLayers.indexOf(child) === -1){ + wasNodeSelected = false + break; + } + } + + // If selected, no successor in unassigned layer, set the nodes layer! + if(wasNodeSelected){ + unassignedNodeList.splice(unassignedNodeList.indexOf(node),1); + node.setLayer(currentLayerInt) // Make each node aware of its layer + assignedNodesCurrentLayer.push(node) + break; + } + else{ + rejectedNodeList.push(node) + } + } + + if(! wasNodeSelected){ + currentLayerInt += 1 + assignedNodesInSubLayers = assignedNodesInSubLayers.concat(assignedNodesCurrentLayer) + rejectedNodeList = [] + console.log('-------------------- Layer ', currentLayerInt, ' --------------') + } + } + + + // // Re-order all the layers to be consistent with my other layering alg. + // wrappedNodeList.forEach(function(node){ + // node.setLayer(currentLayerInt - node.getLayer()) + + return __buildLevelDictionary(wrappedNodeList) + + } + + + + function greedyCycleRemover(wrappedNodeList){ + /* + Uses topological sort then reverses backward edges to eliminate cycles + Returns nodes in topological sort order + */ + + // TODO: implement this idea + // From: A Technique for Drawing Directed Graphs + // Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, Kiem-Phong Vo + // AT&T Bell Laboratories Murray Hill, New Jersey 07974 + //It seems reasonable to try to reverse a smaller or even minimal set of edges. + //One difficulty is that finding a minimal set (the feedback arc set problem) + //is NP-complete [EMW] [GJ]. More important, this would probably not improve the + //drawings. We implemented a heuristic to reverse edges that participate in many + //cycles. The heuristic takes one non-trivial strongly connected component at a + //time, in an arbitrary order. Within each component, it counts the number of + //times each edge forms a cycle in a depth-first traversal. An edge with a + //maximal count is reversed. This is repeated until there are no more + //non-trivial strongly connected components. + + + var topSort = __getTopologicalSort(wrappedNodeList) + + // Debug + console.log('Topological sorting') + wrappedNodeList.forEach(function(wrappedNode){ + console.log(' ', wrappedNode.getName()) + }) + + // Reverse backward arcs to eliminate cycles + for(var nodeIndex = 0; nodeIndex < topSort.length; nodeIndex++){ + var wrappedNode = topSort[nodeIndex] + var wrappedChildrenNodes = wrappedNode.children + + wrappedChildrenNodes.forEach(function(wrappedChildrenNode){ + // If the child has a smaller index than the current node it is left + // of the current node. That means it forms a cycle! + if(nodeIndex > topSort.indexOf(wrappedChildrenNode)){ + + // Get the link (or maybe more than one link) between parent + // wrappedNode and child wrappedChildrenNode + var linkFlagList = wrappedNode.childNodeToLinkFlagListMap[wrappedChildrenNode.id].slice() + + // Remove it + wrappedNode.children.splice( + wrappedNode.children.indexOf(wrappedChildrenNode),1); + delete wrappedNode.childNodeToLinkFlagListMap[wrappedChildrenNode.id] + + wrappedChildrenNode.parents.splice( + wrappedChildrenNode.parents.indexOf(wrappedNode),1); + delete wrappedChildrenNode.parentNodeToLinkFlagListMap[wrappedNode.id] + + // Reverse it + var tempList = [] + linkFlagList.forEach(function(linkFlag){ + tempList.push([linkFlag[0], true]) // Reverse flag set to true + }) + wrappedChildrenNode.childNodeToLinkFlagListMap[wrappedNode.id] + = tempList.slice() + wrappedNode.parentNodeToLinkFlagListMap[wrappedChildrenNode.id] + = tempList.slice() + } + + // Self-loop situation + else if(nodeIndex == topSort.indexOf(wrappedChildrenNode)){ + console.log('SELFLOOP', wrappedChildrenNode.getName()) + } + }) + } + + return topSort + } + + + + function addDummyNodes(levelDictionary, isGoingDown){ + /* + If an edge crosses more than 1 layer, a dummy node is added so the edge + can be bent around other nodes (thus avoiding overlap, min crossing) + */ + + isGoingDown = isGoingDown || true; + + + var uniqueID = 0 + // Add dummy nodes if an edge traverses > 1 layer + for(var currentLevelInt = 0; currentLevelInt < levelDictionary.length; currentLevelInt++){ + + var currentLevelNodeList = levelDictionary[currentLevelInt] || []; + + currentLevelNodeList.forEach(function(node){ + + // Go through each node connected to this node + node.children.forEach(function(targetNode){ + + // Is the connected node more than 1 layer distant? + var targetNodeLayer = targetNode.getLayer() + if(Math.abs(targetNodeLayer - currentLevelInt) > 1){ + + // Insert a dummy node here! One for each layer crossed + + var dummyParent = node + var linkFlagList = node.childNodeToLinkFlagListMap[targetNode.id].slice() + delete node.childNodeToLinkFlagListMap[targetNode.id] // Why did I do this? Mmm... + uniqueID += 1 + + var increment, stopLevel; + if(targetNodeLayer > currentLevelInt){ + console.log('HERE') + i = currentLevelInt - 1 + increment = 1 + stopLevel = targetNodeLayer + } + else{ + i = currentLevelInt - 1 + increment = -1 + stopLevel = targetNodeLayer + } + + //while(i != stopLevel): + var dummyNode; + for(var i = currentLevelInt+1; i < targetNode.getLayer(); i++){ + console.log('I need a dummy on level', i,'to',targetNode.getLayer(), 'for child', targetNode.getName()) + // Create the dummy node, add it to level dict + dummyNode = new NodeWrapper([uniqueID, linkFlagList], NodeWrapper.MULTI_LAYER_EDGE, i) + levelDictionary[i].push(dummyNode) + + // I need to be able to trace links back and forth + // Including the dummy nodes... + dummyParent.childNodeToLinkFlagListMap[dummyNode.id] = linkFlagList + dummyNode.parentNodeToLinkFlagListMap[dummyParent.id] = linkFlagList + dummyParent = dummyNode + i += increment + } + + if(dummyNode) + dummyNode.childNodeToLinkFlagListMap[targetNode.id] = linkFlagList + } + }) + }) + } + + return levelDictionary + } + + + //function addDummyNodes(levelDictionary): + // /* + // If an edge crosses more than 1 layer, a dummy node is added so the edge + // can be bent around other nodes (thus avoiding overlap, min crossing) + // */ + // uniqueID = 0 + // // Add dummy nodes if an edge traverses > 1 layer + // for currentLevelInt in levelDictionary.keys(): + // for node in levelDictionary[currentLevelInt]: + // + // children = node.children.keys() // Children of this node + // for child in children: + // + // // Child should be exactly 1 layer below the parent at current level + // if(currentLevelInt < child.getLayer() - 1): + // // Insert a dummy node here! One for each layer crossed + // + // dummyParent = node + // linkFlagList = node.children[child][:] + // del node.children[child] + // uniqueID += 1 + // + // for i in range(currentLevelInt+1, child.getLayer()): + // //console.log('I need a dummy on level', i, 'for child', child.getName()) + // // Create the dummy node, add it to level dict + // dummyNode = NodeWrapper((uniqueID, linkFlagList), + // NodeWrapper.MULTI_LAYER_EDGE, i) + // levelDictionary[i].push(dummyNode) + // + // // I need to be able to trace links back and forth + // // Including the dummy nodes... + // dummyParent.children[dummyNode] = linkFlagList + // dummyNode.parents[dummyParent] = linkFlagList + // dummyParent = dummyNode + // dummyNode.children[child] = linkFlagList + // + // return levelDictionary + + + + function __getTopologicalSort(wrappedNodeList){ + /* + Returns the node list as topologically sorted with forward arcs running + from left to right (if cycles exist, there will be backward arcs too) + */ + function DFSlookup(node, sortedNodeList){ + /* Sub-method for topological sort, does depth first search */ + node.children.forEach(function(childNode){ //node.getChildrenWrappers(): + if(!childNode.isVisited()){ + childNode.setVisited() + DFSlookup(childNode, sortedNodeList) + } + }) + sortedNodeList.push(node) + } + + sortedNodeList = [] + wrappedNodeList.forEach(function(node){ + if(!node.isVisited()){ + node.setVisited() + DFSlookup(node, sortedNodeList) + } + }) + sortedNodeList.reverse() + return sortedNodeList + } + + + function __buildLevelDictionary(wrappedNodeList){ + /* + wrappedNodeList assumed to contain nodes already assigned a layer + Returns a dictionary indexed by integer level of lists of nodes + */ + + // Build the level dictionary for easy access to node layers + var levelDictionary = [] + wrappedNodeList.forEach(function(node){ + var currentLevelInt = node.getLayer() + if(! levelDictionary[currentLevelInt]) + levelDictionary[currentLevelInt] = [node] + else + levelDictionary[currentLevelInt].push(node) + }) + + //debugLevelDict(levelDictionary) + + // Add dummy nodes as neccessary to finish the levelDictionary... + return levelDictionary + } + + + + function MinimumWidthLayering(wrappedNodeList){ + /* + This heuristic algorithm will attempt to create a layering such that + width is minimized (at the expense of height of course). This should + yield far more compact layouts, and speed up the crossing minimization + phase immensely. + The implementation is provided for reference in the LNCS article: + A Heuristic for Minimum-Width Graph Layering with Consideration of Dummy + odes. + By: Alexandre Tarassov and Nikola S. Nikolov and Jurgen Branke + This algorithm is O(n^2) but will be far slower than longestPathLayering + */ + + var self = this; + + //init + self.__wrappedNodeList = wrappedNodeList + + self.__unassignedNodeList = wrappedNodeList.slice() + self.__assignedNodesCurrentLayer = [] + self.__assignedNodesInSubLayers = [] + + self.__currentWidthInt = 0 + self.__widthUpInt = 0 + + + this.execute = function( UBW, cInteger){ + /* + Usage: + Execute the heuristic on the wrapped nodes provided in init call + + Parameters: + //todo: Parameters + + Returns: + levelDictionary, with all the nodes assigned to a layer in that dictionary + + WARNING: + If you change the nodes, then you must re-instantiate this class + + Example usage: + mwl = MinimumWidthLayering(wrappedNodeList) + levelDictionary = mwl() // Run the algorithm + */ + var currentLayerInt = 0 + console.log('-------------------- Layer ', currentLayerInt, ' --------------') + while(self.__unassignedNodeList.length){ + + var theChosenNode = __chooseNode() + + if(theChosenNode){ + // Make the node aware of its layer + theChosenNode.setLayer(currentLayerInt) + + // Update current width and the estimate of upper layer widths + var outDegree = theChosenNode.getOutDegree() + self.__currentWidthInt += + - MinimumWidthLayering.EdgeWidth * outDegree + + theChosenNode.getSize(giveExtraSpaceForLinks=false)[0] + + var inDegree = theChosenNode.parents.length + self.__widthUpInt += MinimumWidthLayering.EdgeWidth * inDegree + + + // Prevent the layer from getting too wide... + if(__conditionGoUp(outDegree, UBW, cInteger)) + theChosenNode = null + } + + if(theChosenNode == null){ + currentLayerInt += 1 + self.__assignedNodesInSubLayers = + self.__assignedNodesInSubLayers.concat(self.__assignedNodesCurrentLayer) + self.__currentWidthInt = self.__widthUpInt + self.__widthUpInt = 0 + + console.log('-------------------- Layer ', + currentLayerInt, ' --------------') + } + } + + + // Build the level dictionary for easy access to node layers + var maxLayerInt = currentLayerInt + var levelDictionary = [] + self.__wrappedNodeList.forEach(function(node){ + // Set them up by order of top nodes to bottom nodes + var currentLevelInt = node.getLayer() + currentLevelInt = maxLayerInt - node.getLayer() + node.setLayer(currentLevelInt) + if(! levelDictionary[currentLevelInt]) + levelDictionary[currentLevelInt] = [node] + else + levelDictionary[currentLevelInt].push(node) + }) + + //debugLevelDict(levelDictionary) + return levelDictionary + } + + function __chooseNode(){ + /* + Choose an unassigned node of maximum outdegree who has successors only in + assigned layers (or no successors) + */ + + var theChosenNode = null + var maxOutDegree = -1 + var rejectedNodeList = [] + + // Go through all unassigned nodes + self.__unassignedNodeList.forEach(function(node){ + + // Slight optimization: ignore already rejected nodes on current layer + if(rejectedNodeList.indexOf(node) !== -1) + return + + // console.log('Node:', node, ' OutDegree:', node.getOutDegree()) + + // Check if this node has a successor that is not already layer assigned + var isNodeInvalid = false + for(var i=0; i< node.children.length; i++){ + var child = node.children[i]; + + if(self.__assignedNodesInSubLayers.indexOf(child) === -1){ + isNodeInvalid = true + break; + } + } + // Node has successor in unassigned layer, we can't possibly pick it + if(isNodeInvalid){ + rejectedNodeList.push(node) + return + } + + // Does the node have maximum outdegree of all the candidates? + if(node.getOutDegree() > maxOutDegree){ + maxOutDegree = node.getOutDegree() + theChosenNode = node + } + }) + + + // Okay, we pick this node, shuffle it from unassigned to assigned! + if(theChosenNode){ + self.__unassignedNodeList.splice(self.__unassignedNodeList.indexOf(theChosenNode),1); + self.__assignedNodesCurrentLayer.push(theChosenNode) + } + + console.log('The chosen node:', theChosenNode) + return theChosenNode // Could be null + } + + + function __conditionGoUp( outDegree, UBW, cInteger){ + /* + Return true if we should skip to the next layer + */ + if(self.__currentWidthInt >= UBW && outDegree < 1) + return true + else if(self.__widthUpInt >= cInteger * UBW) + return true + return false + } + } + MinimumWidthLayering.EdgeWidth = 1 + + return { + greedyCycleRemover : greedyCycleRemover, + longestPathLayeringTopDown : longestPathLayeringTopDown, + longestPathLayeringBottomUp : longestPathLayeringBottomUp, + addDummyNodes : addDummyNodes, + MinimumWidthLayering : MinimumWidthLayering + } + +}); Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/LayeringModule.js ------------------------------------------------------------------------------ svn:eol-style = native Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/NodeWrapper.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/NodeWrapper.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/NodeWrapper.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/NodeWrapper.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,401 @@ +require.def("src/javascript/scxml/cgf/layout/hierarchical/NodeWrapper", +["src/javascript/scxml/cgf/util/svg"], +function(commonSVG){ + + function NodeWrapper(node, nodeType, layer){ + /* + The Hierarchical layout algorithm works exclusively on objects instantiated + from self class. For the most part, self is a wrapper around the real entity + nodes in the original diagram. However, special edges are also treated as + nodes to improve the final layout. + */ + layer = layer || 0; + + var self=this; + + // These need to be reset for each new run of HierarchicalLayout + // edge to target NodeWrapper + //init + self.id = ++NodeWrapper.idCounter; + + self.childNodeToLinkFlagListMap = {}; + self.parentNodeToLinkFlagListMap = {}; + + self.__visitedFlag = false // Used for DFS + self.__layer = layer // Layer node belongs to + self.__order = -1 // Node order on the layer + self.__gridPosition = -1 // Actual node pos on grid (cannot violate order) + self.__priority = 0 // Priority to push other nodes for new grid pos + self.__barycenterValue = 0 // Barycenter used for crossing minimization + + // Dict format: self.children[childNodeId] = [[linkNode, isReversed],...] + self.children = []; + self.parents = []; + + self.__outDegree = 0 + + self.__edgePosition = [0, 0] // Edge control point position (Dummy edges) + self.__nodeType = nodeType // Regular node or some type of edge node? + self.__node = node // AToM3 node, subclass of ASGnode + + NodeWrapper.Source2TargetListMap[self.id] = [] + + // Regular node tracker + if(nodeType == NodeWrapper.REGULAR_NODE){ + // node is an AToM3 entity, subclass of ASGNode + NodeWrapper.Node2WrapperDict[node.id] = self + } + + // Self loop tracker (Special kind of dummy edge) + else if(nodeType == NodeWrapper.SELF_LOOP_EDGE){ + NodeWrapper.SelfLoopList.push(self) + // NodeWrapper.Source2TargetListMap[self] = [self] + } + + // Multi-layer edge node tracker (Dummy edge) + else{ + //FIXME: Jake: self code here does not make any sense to me at all + self.__node = [] // self.__node = [linkNode,...] + linkFlagList = node[1] + for(var i = 0; i < linkFlagList.length; i++){ + self.__node.push(linkFlagList[i][0]) // The link node object/s + } + node = node[0] // A unique ID number for the dummy tracker + + // Add/push self to the tracker with key "node" which is an ID here + if(NodeWrapper.ID2LayerEdgeDict[node.id]) + NodeWrapper.ID2LayerEdgeDict[node].push(self) + else + NodeWrapper.ID2LayerEdgeDict[node] = [self] + } + + + + self.buildConnectivityMaps = function(){ + //uses semantic nodes + + /* + Creates dictionaries that provide rapid access to the wrapped children + and parent nodes that are connected with self node. + Also provides access to the actual link entity between the nodes + A flag is provided to indicate if the algorithm needed to reverse the link + Self-links are discarded (Hiearchical layout don't care none about those) + */ + // Children map + self.__node.outConnections.forEach(function(linkNode){ + var linkTraversesHierLevel = linkNode.lca !== self.__node.parent || + linkNode.outConnections.every(function(targetNode){return linkNode.lca !== targetNode.parent}) + var childNodes = linkTraversesHierLevel ? + linkNode.targetAncestorOrSelfAndChildOfLCA : + linkNode.outConnections; + + var sourceNodes = linkTraversesHierLevel ? + linkNode.sourceAncestorOrSelfAndChildOfLCA : + [self.__node]; + + sourceNodes.forEach(function(sourceNode){ + var wrappedSourceNode = NodeWrapper.Node2WrapperDict[sourceNode.id]; + + childNodes.forEach(function(childNode){ + var wrappedChildNode = NodeWrapper.Node2WrapperDict[childNode.id] + NodeWrapper.Source2TargetListMap[wrappedSourceNode.id].push(wrappedChildNode) + + //hierarchical layout ignores this kind of link + if(linkTraversesHierLevel && wrappedSourceNode == wrappedChildNode){ + return; + } + + // Is the child ourselves in an evil self-loop situation? + // If so, then create a "dummy" node for the loop itself + if(wrappedSourceNode == wrappedChildNode ){ + var newNode = new NodeWrapper(linkNode, NodeWrapper.SELF_LOOP_EDGE) + wrappedSourceNode.children.push(newNode); + wrappedSourceNode.parents.push(newNode); + wrappedSourceNode.childNodeToLinkFlagListMap[newNode.id] = [[linkNode, false]] + wrappedSourceNode.parentNodeToLinkFlagListMap[newNode.id] = [[linkNode, false]] + + newNode.children.push(wrappedSourceNode); + newNode.parents.push(wrappedSourceNode); + newNode.childNodeToLinkFlagListMap[wrappedSourceNode.id] = [[linkNode, false]] + newNode.parentNodeToLinkFlagListMap[wrappedSourceNode.id] = [[linkNode, false]] + }else{ + + // Could be more than one link between source and target + if(wrappedSourceNode.children.indexOf(wrappedChildNode) == -1){ + wrappedSourceNode.children.push(wrappedChildNode); + wrappedSourceNode.childNodeToLinkFlagListMap[wrappedChildNode.id] = [[linkNode, false]] + }else{ + wrappedSourceNode.childNodeToLinkFlagListMap[wrappedChildNode.id].push([linkNode, false]) + } + } + }) + + }) + + + }); + + // Out degree + self.__outDegree = self.children.length + + // Parent map + self.__node.inConnections.forEach(function(linkNode){ + + linkNode.sourceAncestorOrSelfAndChildOfLCA.forEach(function(parentNode){ + var wrappedParentNode = NodeWrapper.Node2WrapperDict[parentNode.id] + + // Is the parent ourselves in an evil self-loop situation? + // If so skip self, we handled self case already in the child map + if(self == wrappedParentNode) return + + // Could be more than one link between source and target + if(self.parents.indexOf(wrappedParentNode) == -1){ + self.parents.push(wrappedParentNode) + self.parentNodeToLinkFlagListMap[wrappedParentNode.id] = [[linkNode, false]] + } + else{ + self.parentNodeToLinkFlagListMap[wrappedParentNode.id].push([linkNode, false]); + } + }); + }); + } + + + self.getOutDegree = function(){ + /* Number of children */ + return self.__outDegree + } + + + self.setVisited = function(){ + // Depth first search has visited here + self.__visitedFlag = true + } + + self.isVisited = function(){ + // Return the visited flag + return self.__visitedFlag + } + + // def getChildrenWrappers(self): + // children = [] + // for link in self.__node.outConnections: + // for childNode in link.outConnections: + // children.push(NodeWrapper.Node2WrapperDict[childNode]) + // return children + + self.toString = function(){ + return self.getName() + } + + self.getName = function(){ + if(self.__nodeType == NodeWrapper.MULTI_LAYER_EDGE){ + var linkNode = self.__node[0] + var inConn = linkNode.inConnections[0] + var outConn = linkNode.outConnections[0] + var inWrappedNode = NodeWrapper.Node2WrapperDict[inConn.id] + var outWrappedNode = NodeWrapper.Node2WrapperDict[outConn.id] + return 'E_' + inWrappedNode.getName() + '_to_' + outWrappedNode.getName() + } + if(self.__node){ + return self.__node.id + } + else{ + return 'NO-NAME' + } + } + + self.moveTo = function(x, y, longEdgeOffset){ + if(self.__nodeType == NodeWrapper.REGULAR_NODE){ + self.__node.visualObject.moveTo(x, y); + } + else if(self.__nodeType == NodeWrapper.SELF_LOOP_EDGE){ + var bbox = self.__node.visualObject.getBBox(); + self.__edgePosition = [x + bbox.width / 2, y] + } + else{ + self.__edgePosition = [x + longEdgeOffset[0], y + longEdgeOffset[1]] + } + } + + self.getEdgePosition = function(){ + return self.__edgePosition + } + + self.setLayer = function(layer){ + self.__layer = layer + } + + self.getLayer = function(){ + return self.__layer + } + + self.setOrder = function(order){ + self.__order = order + } + + self.getOrder = function(){ + return self.__order + } + + self.computeBarycenter = function(isGoingDown){ + /* + Implements the barycenter heuristic. Basic idea: if a node in layer A is + connected to node1, node2, and node3 in layer B, then the node in layer + A should be placed at the average of the positions (order integers) of the + three nodes in layer B. This must be done from layer A to layer B and then + from layer B to layer A many times to converge on a global solution. + The isGoingDown parameter determines if we are moving from root layer to + leaf layer (true), or from leaf layer to root layer (false) + + Implementation according to: + http://etd.lib.fsu.edu/theses/available/etd-05062004-232310/unrestricted/Pitch_Patarasuk_Thesis.pdf + CROSSING REDUCTION FOR LAYERED HIERARCHICAL GRAPH DRAWING + By PITCH PATARASUK + */ + var nodeList; + if(isGoingDown) + nodeList = self.children + else + nodeList = self.parents + + numberOfNodes = nodeList.length; + + // No nodes in next layer? Just use the arbitrary original order value + if(numberOfNodes == 0){ + self.__barycenterValue = self.__order + return + } + + // Calculate the barycenter + var orderSum = 0 + nodeList.forEach(function(node){ + orderSum += node.__order + }); + self.__barycenterValue = orderSum / numberOfNodes + } + + self.getBarycenter = function(){ + // Retrieve the barycenter computed by computeBarycenter() + return self.__barycenterValue + } + + + self.calculatePriority = function(){ + // Priority = Fan in + Fan out, and max level priority for dummies + if(self.__nodeType == NodeWrapper.MULTI_LAYER_EDGE || self.__nodeType == NodeWrapper.SELF_LOOP_EDGE){ + self.__priority = 1000000 //sys.maxint + return self.__priority + } + else{ + self.__priority = self.children.length + self.parents.length + return self.__priority + } + } + + self.setPriority = function(priority){ + self.__priority = priority + } + + self.getPriority = function(){ + return self.__priority + } + + self.getASGNode = function(){ + return self.__node + } + + self.setGridPosition = function(pos){ + self.__gridPosition = pos + } + + self.getGridPosition = function(){ + return self.__gridPosition + } + + self.getGridBarycenter = function(isGoingDown){ + var nodeList; + if(isGoingDown) + nodeList = self.children + else + nodeList = self.parents + + numberOfNodes = nodeList.length + + if(numberOfNodes == 0) + return self.__gridPosition + + var orderSum = 0 + nodeList.forEach(function(node){ + orderSum += node.__gridPosition + }); + return orderSum / numberOfNodes + } + + //FIXME: need to add application logic here + self.getSize = function(giveExtraSpaceForLinks){ + giveExtraSpaceForLinks = giveExtraSpaceForLinks || true; + + var toReturn; + + // Long edge traversing multiple layers + var bbox; + if(self.__nodeType == NodeWrapper.MULTI_LAYER_EDGE){ + var bboxes = self.__node.map(function(n){return n.visualObject.getBBox()}); + var maxSize = [Math.max.apply(this,bboxes.map(function(bbox){return bbox.width})), + Math.max.apply(this,bboxes.map(function(bbox){return bbox.height}))] + toReturn = maxSize; + } + + // Check if single layer links have drawings that require additional space + else if(giveExtraSpaceForLinks){ + var maxSingleLayerLinkHeight = 0 + + function getMaxLinkHeight(linkFlagList, maxSingleLayerLinkHeight){ + return Math.max.apply(this, + linkFlagList.map(function(l){ + return l[0].visualObject.getBBox().height + }).concat(maxSingleLayerLinkHeight)); + } + + + // Children + self.children.forEach(function(wrappedChildNode){ + if(wrappedChildNode.__layer == self.__layer + 1) + maxSingleLayerLinkHeight = getMaxLinkHeight( self.childNodeToLinkFlagListMap[wrappedChildNode.id], maxSingleLayerLinkHeight) + }); + + // Parents (for links going in reverse direction) + self.parents.forEach(function(wrappedParentNode){ + if(wrappedParentNode.__layer == self.__layer - 1) + maxSingleLayerLinkHeight = getMaxLinkHeight( self.parentNodeToLinkFlagListMap[wrappedParentNode.id], maxSingleLayerLinkHeight) + }); + + bbox = self.__node.visualObject.getBBox(); + toReturn = [bbox.width , bbox.height + maxSingleLayerLinkHeight] + }else{ + bbox = self.__node.visualObject.getBBox(); + toReturn = [bbox.width, bbox.height] + } + return toReturn; + } + } + NodeWrapper.REGULAR_NODE = 0 + NodeWrapper.MULTI_LAYER_EDGE = 1 + NodeWrapper.SELF_LOOP_EDGE = 2 + + NodeWrapper.initilizeNodeWrapper = function(){ + //Utility method to reset the class attributes of NodeWrapper + + NodeWrapper.SelfLoopList = [] + NodeWrapper.Node2WrapperDict = {} + NodeWrapper.ID2LayerEdgeDict = {} + NodeWrapper.Source2TargetListMap = [] + NodeWrapper.idCounter = 0; + } + + NodeWrapper.initilizeNodeWrapper(); + + return NodeWrapper; + +}) Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/hierarchical/NodeWrapper.js ------------------------------------------------------------------------------ svn:eol-style = native Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/shrinkwrapLayout.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/shrinkwrapLayout.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/shrinkwrapLayout.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/shrinkwrapLayout.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,55 @@ +require.def("src/javascript/scxml/cgf/layout/shrinkwrapLayout", +function(){ + function shrinkwrapBoundingBoxGraphEntity(boundingBoxGraphEntity,options){ + + options = options || { + bboxPadding : 10, + labelPadding : 3 + } + + //get the aggregate of the bounding boxes of his children, or if he has no hier children, get his own bbox + var newBBox; + if(boundingBoxGraphEntity.children.length){ + var bboxes = boundingBoxGraphEntity.children.map(function(e){ + return e.visualObject.getBBoxInEntitySpace(boundingBoxGraphEntity.visualObject); + }); + + var newBBoxX0 = Math.min.apply(this,bboxes.map(function(bbox){ return bbox.x })) + var newBBoxY0 = Math.min.apply(this,bboxes.map(function(bbox){ return bbox.y })) + var newBBoxX1 = Math.max.apply(this,bboxes.map(function(bbox){return bbox.x+bbox.width})) + var newBBoxY1 = Math.max.apply(this,bboxes.map(function(bbox){ return bbox.y+bbox.height})) + + //apply padding option + newBBoxX0 -= options.bboxPadding; + newBBoxY0 -= options.bboxPadding; + newBBoxX1 += options.bboxPadding; + newBBoxY1 += options.bboxPadding; + + var newBBoxWidth = newBBoxX1 - newBBoxX0 + var newBBoxHeight = newBBoxY1 - newBBoxY0 + + newBBox = { + x : newBBoxX0, + y : newBBoxY0, + width : newBBoxWidth, + height : newBBoxHeight + }; + + boundingBoxGraphEntity.visualObject.resizeBBoxElementAndUpdateLabel(newBBox); + }else{ + newBBox = boundingBoxGraphEntity.visualObject.getBBox(); + boundingBoxGraphEntity.visualObject.resizeBBoxElement(newBBox,options); + } + + } + + function recursivelyApplyShrinkwrapLayout(boundingBoxGraphEntity,options){ + boundingBoxGraphEntity.children.filter(function(c){return c.visualObject.resizeBBoxElement}) + .forEach(function(c){recursivelyApplyShrinkwrapLayout(c,options)}); + shrinkwrapBoundingBoxGraphEntity(boundingBoxGraphEntity,options); + } + + return { + recursivelyApplyShrinkwrapLayout : recursivelyApplyShrinkwrapLayout + } +}) \ No newline at end of file Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/layout/shrinkwrapLayout.js ------------------------------------------------------------------------------ svn:eol-style = native Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/GraphicalSimulator.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/GraphicalSimulator.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/GraphicalSimulator.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/GraphicalSimulator.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,31 @@ +require.def("src/javascript/scxml/cgf/listener/GraphicalSimulator", +["src/javascript/scxml/cgf/util/svg"], +function(svg){ + return function(svgDoc){ + this.onEntry = function(stateId){ + var e = svgDoc.getElementById(stateId); + //console.log(e); + svg.addClass(e,"highlighted"); + e.ownerSVGElement.forceRedraw(); + } + + this.onExit = function(stateId){ + var e = svgDoc.getElementById(stateId); + //console.log(e); + svg.removeClass(e,"highlighted"); + e.ownerSVGElement.forceRedraw(); + } + + this.onTransition = function(sourceStateId,targetStateId,transitionId){ + var e = svgDoc.getElementById(transitionId); + //console.log(e); + svg.addClass(e,"highlighted"); + e.ownerSVGElement.forceRedraw(); + svg.removeClass(e,"highlighted"); + e.ownerSVGElement.forceRedraw(); + } + } + +}) + + Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/GraphicalSimulator.js ------------------------------------------------------------------------------ svn:eol-style = native Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/Logger.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/Logger.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/Logger.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/Logger.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,16 @@ +require.def("src/javascript/scxml/cgf/listener/Logger", +function(){ + return function(){ + this.onEntry = function(state){ + console.log("Entering ",state); + } + + this.onExit = function(state){ + console.log("Exiting ",state); + } + + this.onTransition = function(sourceStateId,targetStateId,transition){ + console.log("Taking transition ",transition); + } + } +}); Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/Logger.js ------------------------------------------------------------------------------ svn:eol-style = native Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/api.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/api.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/api.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/api.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,13 @@ +require.def("src/javascript/scxml/cgf/listener/api", +function(){ + return function(){ + this.onEntry = function(state){ + } + + this.onExit = function(state){ + } + + this.onTransition = function(sourceStateId,targetStateId,transition){ + } + } +}); Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/listener/api.js ------------------------------------------------------------------------------ svn:eol-style = native Modified: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/main.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/main.js?rev=984129&r1=984128&r2=984129&view=diff ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/main.js (original) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/main.js Tue Aug 10 17:13:04 2010 @@ -51,7 +51,8 @@ require.def("src/javascript/scxml/cgf/ma noForEach :true, beautify : true, log : true, - verbose : true + verbose : true, + genListenerHooks : true } var parsedOptionsMap = cmdLineUtil.parseCommandLine(optionsMap,args); parsedOptionsMap.inFiles = parsedOptionsMap.args.map(xmlUtil.parseFromPath); Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/geometry.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/geometry.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/geometry.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/geometry.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,22 @@ +require.def("src/javascript/scxml/cgf/util/geometry", +{ + + distance : function(p1x, p1y, p2x, p2y){ + /* + Calculates the distance between the two points given by (p1x, p1y) (p2x, p2y) + */ + return Math.sqrt((p1x-p2x)*(p1x-p2x)+(p1y-p2y)*(p1y-p2y)) + }, + getMidpoint2D : function( p1,p2 ){ + // Midpoint of 2 points in 2D + return { + x:( p1.x + p2.x ) / 2, + y:( p1.y + p2.y ) / 2 + } + }, + vectorLength2D : function( v ){ + // Calculates the length of the 2D vector v + return Math.sqrt( v[0] * v[0] + v[1] * v[1] ) + } + +}) Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/geometry.js ------------------------------------------------------------------------------ svn:eol-style = native Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/svg.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/svg.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/svg.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/svg.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,184 @@ +require.def("src/javascript/scxml/cgf/util/svg", +function(){ + + var scxmlJsNS = "http://commons.apache.org/scxml-js"; + var svgNS = "http://www.w3.org/2000/svg"; + var scxmlNS = "http://www.w3.org/2005/07/scxml"; + var xlinkNS = "http://www.w3.org/1999/xlink"; + + function getBoundingBoxInArbitrarySpace(element,mat){ + var svgRoot = element.ownerSVGElement; + var bbox = element.getBBox(); + + var cPt1 = svgRoot.createSVGPoint(); + cPt1.x = bbox.x; + cPt1.y = bbox.y; + cPt1 = cPt1.matrixTransform(mat); + + // repeat for other corner points and the new bbox is + // simply the minX/minY to maxX/maxY of the four points. + var cPt2 = svgRoot.createSVGPoint(); + cPt2.x = bbox.x + bbox.width; + cPt2.y = bbox.y; + cPt2 = cPt2.matrixTransform(mat); + + var cPt3 = svgRoot.createSVGPoint(); + cPt3.x = bbox.x; + cPt3.y = bbox.y + bbox.height; + cPt3 = cPt3.matrixTransform(mat); + + var cPt4 = svgRoot.createSVGPoint(); + cPt4.x = bbox.x + bbox.width; + cPt4.y = bbox.y + bbox.height; + cPt4 = cPt4.matrixTransform(mat); + + var points = [cPt1,cPt2,cPt3,cPt4] + + //find minX,minY,maxX,maxY + var minX=1000000000000 + var minY=1000000000000 + var maxX=0 + var maxY=0 + for(i=0;i maxX) + { + maxX = points[i].x + } + if (points[i].y > maxY) + { + maxY = points[i].y + } + } + + //instantiate new object that is like an SVGRect + var newBBox = {"x":minX,"y":minY,"width":maxX-minX,"height":maxY-minY} + return newBBox; + } + + function getBBoxInCanvasSpace(element){ + return getBoundingBoxInArbitrarySpace(element,element.getTransformToElement(element.ownerSVGElement)); + } + + function getBBoxInElementSpace(element,spaceElement){ + return getBoundingBoxInArbitrarySpace(element,element.getTransformToElement(spaceElement)); + } + + function getCenter(element){ + var bbox = element.getBBox(); + return [bbox.x + bbox.width/2, bbox.y+bbox.height/2]; + } + + function getCenterInCanvasSpace(element){ + var bbox = getBBoxInCanvasSpace(element); + return [bbox.x + bbox.width/2, bbox.y+bbox.height/2]; + } + + + function getCenterInElementSpace(element,spaceElement){ + var bbox = getBBoxInElementSpace(element,spaceElement); + return [bbox.x + bbox.width/2, bbox.y+bbox.height/2]; + } + + function translate(rawNode,dx,dy){ + var tl = rawNode.transform.baseVal; + var t = tl.numberOfItems ? tl.getItem(0) : rawNode.ownerSVGElement.createSVGTransform(); + var m = t.matrix; + var newM = rawNode.ownerSVGElement.createSVGMatrix().translate(dx,dy).multiply(m); + t.setMatrix(newM); + tl.initialize(t); + return newM; + } + + function translateTo(e,x,y){ + // Convenience method: Moves this entity to the new location + var bbox = e.getBBox(); + var curX = bbox.x, curY = bbox.y; + var dx = x - curX; + var dy = y - curY; + translate(e, {dx:dx, dy:dy}); + } + + //this code borrowed from jquery + var rtrim = /^(\s|\u00A0)+|(\s|\u00A0)+$/g; + var rclass = /[\n\t]/g, + rspace = /\s+/, + rreturn = /\r/g, + rspecialurl = /href|src|style/, + rtype = /(button|input)/i, + rfocusable = /(button|input|object|select|textarea)/i, + rclickable = /^(a|area)$/i, + rradiocheck = /radio|checkbox/; + + + function trim(text){ + return (text || "").replace( rtrim, "" ); + } + + function addClass( elem, value ) { + if ( value && typeof value === "string" ) { + var classNames = (value || "").split( rspace ); + + if ( elem.nodeType === 1 ) { + if ( !elem.className.baseVal ) { + elem.className.baseVal = value; + + } else { + var className = " " + elem.className.baseVal + " ", setClass = elem.className.baseVal; + for ( var c = 0, cl = classNames.length; c < cl; c++ ) { + if ( className.indexOf( " " + classNames[c] + " " ) < 0 ) { + setClass += " " + classNames[c]; + } + } + elem.className.baseVal = trim( setClass ); + } + } + } + + return elem; + } + + function removeClass(elem, value ) { + if ( (value && typeof value === "string") || value === undefined ) { + var classNames = (value || "").split(rspace); + + if ( elem.nodeType === 1 && elem.className.baseVal ) { + if ( value ) { + var className = (" " + elem.className.baseVal + " ").replace(rclass, " "); + for ( var c = 0, cl = classNames.length; c < cl; c++ ) { + className = className.replace(" " + classNames[c] + " ", " "); + } + elem.className.baseVal = trim( className ); + + } else { + elem.className.baseVal = ""; + } + } + } + + return elem; + } + + return { + SVG_NS: svgNS , + SCXML_NS : scxmlNS , + SCXML_JS_NS : scxmlJsNS , + XLINK_NS : xlinkNS, + + translate : translate, + translateTo : translateTo, + getBBoxInCanvasSpace : getBBoxInCanvasSpace, + getBBoxInElementSpace : getBBoxInElementSpace, + + addClass: addClass, + removeClass : removeClass + } +}) Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/svg.js ------------------------------------------------------------------------------ svn:eol-style = native Added: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/xpath.js URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/xpath.js?rev=984129&view=auto ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/xpath.js (added) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/xpath.js Tue Aug 10 17:13:04 2010 @@ -0,0 +1,86 @@ +require.def( +"src/javascript/scxml/cgf/util/xpath", +function(){ + + var scxmlJsNS = "http://commons.apache.org/scxml-js"; + var svgNS = "http://www.w3.org/2000/svg"; + var scxmlNS = "http://www.w3.org/2005/07/scxml"; + var xlinkNS = "http://www.w3.org/1999/xlink"; + + function nsResolver(prefix) { + var ns = { + svg: svgNS , + s: scxmlNS , + c: scxmlJsNS , + xlink: xlinkNS + }; + return ns[prefix] || null; + } + + var xpathSnapshotResultToJsArray = require.isBrowser ? + function(nodes){ + var toReturn = []; + + for (var i = 0; i < nodes.snapshotLength; i++) { + toReturn.push(nodes.snapshotItem(i)); + } + return toReturn; + } : + function(nodes){ + var toReturn = []; + for (var i = 0; i < nodes.getLength(); i++) { + toReturn.push(nodes.item(i)); + } + return toReturn; + }; + + var query = require.isBrowser ? + function(xpath,contextNode){ + contextNode = contextNode || document.documentElement; + return xpathSnapshotResultToJsArray( + contextNode.ownerDocument.evaluate(xpath, contextNode, nsResolver, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE,null)); + } : + (function(){ + var XPathFactory = javax.xml.xpath.XPathFactory, + XPathConstants = javax.xml.xpath.XPathConstants; + + var namespaceContext = new javax.xml.namespace.NamespaceContext({ + getNamespaceURI : function(prefix) { + return nsResolver(prefix) || javax.xml.XMLConstants.NULL_NS_URI; + }, + + // This method isn't necessary for XPath processing. + getPrefix : function(uri) { + throw new javax.xml.UnsupportedOperationException(); + }, + + // This method isn't necessary for XPath processing either. + getPrefixes : function(uri) { + throw new javax.xml.UnsupportedOperationException(); + } + + }); + + var factory = XPathFactory.newInstance(); + + var xpathExprCache = {}; + + return function(xpath,contextNode){ + var xpathObj = factory.newXPath(); + + xpathObj.setNamespaceContext(namespaceContext); + + //do a bit of caching of compiled expressions to improve performance + var expr = xpathExprCache[xpath] || + (xpathExprCache[xpath] = xpathObj.compile(xpath)); + + var result = expr.evaluate(contextNode, XPathConstants.NODESET); + return xpathSnapshotResultToJsArray(result); + }; + })() + + return { + query : query, + $q : query + } +}); Propchange: commons/sandbox/gsoc/2010/scxml-js/trunk/src/javascript/scxml/cgf/util/xpath.js ------------------------------------------------------------------------------ svn:eol-style = native Modified: commons/sandbox/gsoc/2010/scxml-js/trunk/src/xslt/backends/js/AbstractStatechartGenerator.xsl URL: http://svn.apache.org/viewvc/commons/sandbox/gsoc/2010/scxml-js/trunk/src/xslt/backends/js/AbstractStatechartGenerator.xsl?rev=984129&r1=984128&r2=984129&view=diff ============================================================================== --- commons/sandbox/gsoc/2010/scxml-js/trunk/src/xslt/backends/js/AbstractStatechartGenerator.xsl (original) +++ commons/sandbox/gsoc/2010/scxml-js/trunk/src/xslt/backends/js/AbstractStatechartGenerator.xsl Tue Aug 10 17:13:04 2010 @@ -22,6 +22,7 @@ + @@ -159,6 +160,10 @@ + + + + } @@ -641,6 +646,18 @@ + + listeners.forEach(function(l){ + //transition id + + l.onTransition( + "", + "", + "" ); + + }); + + var historyState = ; @@ -761,6 +778,13 @@ //execute actions for each of these states statesExited.forEach(function(state){ state.exitAction(); + + + listeners.forEach(function(l){ + //from + l.onExit(state.toString()); + }); + }); @@ -829,6 +853,13 @@ .exitAction(); + + + listeners.forEach(function(l){ + //from + l.onExit(""); + }); + @@ -840,12 +871,30 @@ //transition action + + listeners.forEach(function(l){ + //transition id + + l.onTransition( + "", + "", + "" ); + + }); + //enter states .enterAction(); + + + listeners.forEach(function(l){ + //to + l.onEntry(""); + }); + //update configuration @@ -938,6 +987,18 @@ } + + var listeners = []; + //TODO:listeners support adding listeners for a particular state + this.addListener = function(listener){ + listeners.push(listener); + } + + this.removeListener = function(listener){ + listeners.splice(listeners.indexOf(listener),1); + } + +