| /******************************************************************************* |
| * Copyright (c) 2004-2008 Akos Horvath, Gergely Varro and Daniel Varro |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * Akos Horvath, Gergely Varro - initial API and implementation |
| *******************************************************************************/ |
| |
| package org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.algorithms;
|
|
|
| import org.eclipse.viatra2.core.IModelManager;
|
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.EdgeTypeinAlgorithm; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.PseudoSearchGraphNode; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.SearchGraphEdge; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.SearchGraphNode; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.SearchGraphNodeComparator; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.VariableSearchGraphNode; |
|
|
| import java.util.ArrayList;
|
| import java.util.Collection;
|
| import java.util.NoSuchElementException;
|
| import java.util.TreeMap;
|
|
|
|
|
| /**
|
| * Implements a variant of the Chu-Edmonds algorithm to calculate a (possibly sub-) optimal search plan
|
| * @author Akos Horvath
|
| *
|
| */
|
| public class ChuiEdmonds {
|
| // private IModelManager manager;
|
| int min, finalizedVertexId=-1;
|
| ArrayList<SearchGraphNode> sSet = new ArrayList<SearchGraphNode>();
|
|
|
| public ChuiEdmonds(IModelManager manager){
|
| // this.manager = manager;
|
| sSet.clear();
|
| finalizedVertexId = -1;
|
| min = Integer.MAX_VALUE;;
|
| }
|
|
|
| /**
|
| * Initialises the Chu-Edmonds algorithm
|
| */
|
| public void init() {
|
| sSet.clear();
|
| finalizedVertexId = -1;
|
| min = Integer.MAX_VALUE;;
|
| }
|
|
|
|
|
|
|
| /** Returns the SearchPlan (traversal order of the node) of the input graph
|
| * @param iSearchGraph The search graph to work with
|
| * @return The array of the SearchGraph nodes in appropriate order
|
| */
|
| public SearchGraphNode[] evaluateSearchPlan(ISearchGraph iSearchGraph) {
|
| return evaluateSearchPlanInner(evaluateSearchTreeInner(iSearchGraph.getSearchNodes().values()));
|
| }
|
|
|
| // public Collection<SearchGraphNode> evaluateSearchTree(FlattenedPattern result) {
|
| //
|
| // return evaluateSearchTreeInner(result.getSearchGraph().getSearchNodes().values());
|
| // }
|
|
|
| /** Returns a lightest spanning tree of the input graph
|
| * @param nodes the nodes of the graph
|
| * @return The collection of the search graph's node with the defined spanning tree
|
| */
|
| private Collection<SearchGraphNode> evaluateSearchTreeInner(Collection<SearchGraphNode> nodes)
|
| {
|
| //set the treeEdge pointer to the minimum incoming edge for all SearchGraphNodes
|
| for (SearchGraphNode node : nodes)
|
| {
|
| if(node instanceof VariableSearchGraphNode && (!((VariableSearchGraphNode)node).isInput()))
|
| {min = Integer.MAX_VALUE;
|
| for( SearchGraphEdge edge :node.getSources())
|
| if(edge.getWeight() < min)
|
| { min = edge.getWeight();
|
| if(node.getTreeEdge() != null)
|
| {
|
| node.getTreeEdge().getSourceNode().decreaseOutgoingTreeEdgeNumber();
|
| node.getTreeEdge().setEdgeTypeinAlgorithm(EdgeTypeinAlgorithm.FREE);
|
| }
|
| node.setTreeEdge(edge);
|
| edge.getSourceNode().increaseOutgonigTreeEdgeNumber();
|
| edge.setEdgeTypeinAlgorithm(EdgeTypeinAlgorithm.TREE);
|
| }
|
| }
|
| }
|
| for(SearchGraphNode node : nodes)
|
| { if(!sSet.contains(node))
|
| findCircle(node);
|
| }
|
| eraseCircles();
|
| return nodes;
|
| }
|
|
|
| /** Evaluates the actual top most virtual vertex of the input node.
|
| * @param node the node who's virtualvertex is the return parameter
|
| * @return
|
| */
|
| SearchGraphNode getVirtualVertex(SearchGraphNode node)
|
| { if(node == null) return null;
|
|
|
| SearchGraphNode virtualnode = node;
|
| if(node.getVirtualSearchGraphNode() == null )
|
| return node;
|
| else
|
| { virtualnode = node;
|
| while(virtualnode.getVirtualSearchGraphNode() != null)
|
| virtualnode = virtualnode.getVirtualSearchGraphNode();
|
|
|
| return virtualnode;
|
| }
|
| }
|
|
|
| /** If node is in a circle, the edge weights are recalculated along the circle, and a new treeedge is selected
|
| * @param node The node to inspect
|
| */
|
| private void findCircle(SearchGraphNode node)
|
| {
|
| SearchGraphNode actualNode = node, previousNode= node;
|
| while( previousNode!=null && (!sSet.contains(previousNode) ))
|
| {
|
| sSet.add(previousNode);
|
| actualNode = previousNode;
|
| if(actualNode.getTreeEdge() != null)
|
| previousNode = getVirtualVertex(actualNode.getTreeEdge().getSourceNode());
|
| else
|
| previousNode = null;
|
| }
|
| //circle is found
|
| if(previousNode != null
|
| && finalizedVertexId < sSet.indexOf(previousNode))
|
| evaluateNewEdgeWeights(actualNode,previousNode);
|
| else
|
| //it is not a circle
|
| {finalizedVertexId = sSet.size()-1;}
|
|
|
| }
|
|
|
|
|
| /** Evaluates the new edge weights of a circle (starting with circleBeginNode and ends with circleEndNode) and selects a new tree edge
|
| * for one of the circle nodes, all information is captured by a newly created virtual vertexes
|
| * @param circleBeginNode The starter node of the circle
|
| * @param circleEndNode The end node of the circle
|
| */
|
| private void evaluateNewEdgeWeights(SearchGraphNode circleBeginNode, SearchGraphNode circleEndNode) {
|
| int minEdgeWeight = Integer.MAX_VALUE;
|
| int minIncomingEdgeWeight = Integer.MAX_VALUE;
|
| int pseudoNodeId = sSet.size();
|
|
|
| int smallestId = pseudoNodeId;
|
| PseudoSearchGraphNode pseudoNode = new PseudoSearchGraphNode();
|
| SearchGraphEdge minIncomingEdge = null;
|
| //SearchGraphEdge oldPseudoTreeEdge = null;
|
| SearchGraphNode actualNode = circleBeginNode;
|
| //CirclebiggestId is already known as it will be the next element in the sSet
|
| pseudoNode.setCircleBiggestId(pseudoNodeId-1);
|
|
|
| //selects the smallest tree edge in the circle and sets it's edges to "circle" type
|
| do{
|
| if(actualNode.getTreeEdge().getWeight() < minEdgeWeight)
|
| minEdgeWeight = actualNode.getTreeEdge().getWeight();
|
|
|
| if(sSet.indexOf(actualNode) < smallestId)
|
| smallestId = sSet.indexOf(actualNode);
|
|
|
| if(actualNode instanceof PseudoSearchGraphNode && ((PseudoSearchGraphNode)actualNode).getCircleSmallestId() < smallestId)
|
| smallestId = ((PseudoSearchGraphNode)actualNode).getCircleSmallestId();
|
|
|
| actualNode.getTreeEdge().setEdgeTypeinAlgorithm(EdgeTypeinAlgorithm.CIRCLE);
|
| actualNode = getVirtualVertex(actualNode.getTreeEdge().getSourceNode());
|
|
|
| }
|
| while(!actualNode.equals(circleBeginNode));
|
|
|
| actualNode = circleBeginNode;
|
| pseudoNode.setCircleSmallestId(smallestId);
|
| //update the edge weights and selects the smallest incoming to the pseudo node
|
| do{
|
| for (SearchGraphEdge edge :actualNode.getSources() ) {
|
| if(getVirtualVertex(edge.getSourceNode()).getTreeEdge() == null
|
| ||
|
| (edge.getEdgeTypeinAlgorithm()==EdgeTypeinAlgorithm.FREE &&
|
| getVirtualVertex(edge.getSourceNode()).getTreeEdge().getEdgeTypeinAlgorithm() != EdgeTypeinAlgorithm.CIRCLE))
|
| {
|
| edge.setWeight(edge.getWeight() + minEdgeWeight - actualNode.getTreeEdge().getWeight());
|
| //selects the smallest incoming edge into the pseudo node
|
| if(edge.getWeight() < minIncomingEdgeWeight)
|
| {
|
| minIncomingEdge = edge;
|
| minIncomingEdgeWeight = edge.getWeight();
|
| }
|
| //links the incoming edges to the pseudo node
|
| pseudoNode.addSource(edge);
|
| }
|
| }
|
| actualNode = getVirtualVertex(actualNode.getTreeEdge().getSourceNode());
|
|
|
| }while(!actualNode.equals(circleBeginNode));
|
|
|
| //Sets the virtual node to all circle elements
|
| actualNode = getVirtualVertex(circleBeginNode.getTreeEdge().getSourceNode());
|
| circleBeginNode.setVirtualSearchGraphNode(pseudoNode);
|
| circleBeginNode = pseudoNode;
|
| SearchGraphNode previousNode = null;
|
| while(!actualNode.equals(circleBeginNode)){
|
| previousNode= actualNode;
|
| actualNode = getVirtualVertex(actualNode.getTreeEdge().getSourceNode());
|
| previousNode.setVirtualSearchGraphNode(pseudoNode);
|
| }
|
| previousNode = null;
|
|
|
| if(minIncomingEdge != null)
|
| {//sets the tree edge of the target (not pseudo)
|
| pseudoNode.setTreeEdge(minIncomingEdge);
|
| // minIncomingEdge.getTargetNode().setTreeEdge(minIncomingEdge);
|
| minIncomingEdge.setEdgeTypeinAlgorithm(EdgeTypeinAlgorithm.TREE);
|
| // minIncomingEdge.getSourceNode().increaseOutgonigTreeEdgeNumber();
|
| }
|
| pseudoNode.setName("pseudo"+pseudoNodeId);
|
| findCircle(pseudoNode);
|
| }
|
|
|
| /**
|
| * Erases the circles of the spanning tree, by evaluating the references of the virtual vertexes and the concrete nodes.
|
| */
|
| private void eraseCircles(){
|
|
|
| for(int i = sSet.size()-1; i > -1; i--)
|
| {
|
| if(sSet.get(i) instanceof PseudoSearchGraphNode && (!((PseudoSearchGraphNode)sSet.get(i)).isBlocked()))
|
| {
|
| PseudoSearchGraphNode pnode = (PseudoSearchGraphNode)sSet.get(i);
|
| SearchGraphEdge pedge = pnode.getTreeEdge();
|
| //SearchGraphNode coverNode = pedge.getTargetNode();
|
| int coverNodeId = sSet.indexOf(pedge.getTargetNode());
|
| //erase the circle edge of the pseudo node which is
|
| //the treeedge of the Pseudo node's incoming tree edge target node
|
| pedge.getTargetNode().getTreeEdge().setEdgeTypeinAlgorithm(EdgeTypeinAlgorithm.FREE);
|
| pedge.getTargetNode().getTreeEdge().getSourceNode().decreaseOutgoingTreeEdgeNumber();
|
| pedge.getTargetNode().setTreeEdge(pedge);
|
| pedge.getSourceNode().increaseOutgonigTreeEdgeNumber();
|
| //set the cover pseudo nodes to Blocked
|
| for(int j = coverNodeId; j<i; j++)
|
| if(sSet.get(j) instanceof PseudoSearchGraphNode)
|
| {
|
| PseudoSearchGraphNode innerPseudoNode = (PseudoSearchGraphNode)sSet.get(j);
|
| if(coverNodeId >= innerPseudoNode.getCircleSmallestId()
|
| && coverNodeId <= innerPseudoNode.getCircleBiggestId())
|
| {
|
| innerPseudoNode.setBlocked(true);
|
| }
|
| }
|
| }
|
| }
|
| }
|
|
|
|
|
| /** Returns the SearchPlan (traversal order of the node) of the input graph (with already evaluated spanning tree)
|
| * @param nodes the graph with the appropriate spannning tree
|
| * @return
|
| */
|
| private SearchGraphNode[] evaluateSearchPlanInner(Collection<SearchGraphNode> nodes){
|
| //the leaves of the search tree will be in the leaves arraylist
|
| SearchGraphNode maxNode = null;
|
| int max = Integer.MIN_VALUE;
|
| int indexOfSearchPlan = nodes.size()-1;
|
| int indexOfInputParameters = -1;
|
| SearchGraphNode searchPlan[] = new SearchGraphNode[nodes.size()] ;
|
| SearchGraphNodeComparator comparator = new SearchGraphNodeComparator();
|
|
|
| //input parameters, their values are known, can be handled as Constant nodes
|
| for(SearchGraphNode node : nodes)
|
| if(node instanceof VariableSearchGraphNode && ((VariableSearchGraphNode)node).isInput())
|
| {
|
| indexOfInputParameters++;
|
| searchPlan[indexOfInputParameters]= node;
|
| node.setChecked(true);
|
| if(node.getTreeEdge() != null)
|
| node.getTreeEdge().getSourceNode().decreaseOutgoingTreeEdgeNumber();
|
| }
|
| //calculate the leaves of the SearchTree
|
| TreeMap<SearchGraphNode,Object> leaves = new TreeMap<SearchGraphNode, Object>(comparator);
|
| for(SearchGraphNode node : nodes){
|
| if(node.getOutgoingTreeEdgeNumber() == 0 &&
|
| (!(node instanceof VariableSearchGraphNode && ((VariableSearchGraphNode)node).isInput())))
|
| {leaves.put(node,null);
|
| if( node.getTreeEdge() != null && max < node.getTreeEdge().getOldWeight() )
|
| {
|
| max = node.getTreeEdge().getOldWeight();
|
| maxNode = node;
|
| }
|
| }
|
| }
|
| //there is no unbounded searchNode in the pattern
|
| if(maxNode == null)
|
| while(indexOfSearchPlan != indexOfInputParameters)
|
| {
|
| maxNode = leaves.lastKey();
|
| searchPlan[indexOfSearchPlan]= maxNode;
|
| indexOfSearchPlan--;
|
| }
|
|
|
| else
|
| //get the highest tree edge and put it to the search plan evaluation
|
| while(indexOfSearchPlan != indexOfInputParameters)
|
| {
|
| searchPlan[indexOfSearchPlan]= maxNode;
|
| //to "delete" the treeedge from the tree
|
| if(maxNode.getTreeEdge() != null)
|
| { maxNode.getTreeEdge().getSourceNode().decreaseOutgoingTreeEdgeNumber();
|
| //if it does not hold an other element by an edge or not an input parameter then it is a leaf
|
| if( maxNode.getTreeEdge().getSourceNode().getOutgoingTreeEdgeNumber() == 0 )
|
| if(!(maxNode.getTreeEdge().getSourceNode() instanceof VariableSearchGraphNode
|
| && ((VariableSearchGraphNode)maxNode.getTreeEdge().getSourceNode()).isInput()))
|
| leaves.put(maxNode.getTreeEdge().getSourceNode(),null);
|
| }
|
| leaves.remove(maxNode);
|
| try{
|
| if(leaves.isEmpty())
|
| break;
|
| else
|
| maxNode = leaves.lastKey();
|
| }
|
| catch(NoSuchElementException e){break;}
|
| indexOfSearchPlan--;
|
| }
|
| return searchPlan;
|
| }
|
| }
|
