plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/utilities/ReachabilityForest.java - mmt/org.eclipse.qvtd - Git at Google

 /*******************************************************************************
  * Copyright (c) 2015, 2018 Willink Transformations and others.
  * All rights reserved.   This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v2.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v20.html
  *
  * Contributors:
  *   E.D.Willink - Initial API and implementation
  *******************************************************************************/
 package org.eclipse.qvtd.compiler.internal.qvts2qvts.utilities;

 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;

 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.jdt.annotation.Nullable;
 import org.eclipse.ocl.pivot.utilities.ClassUtil;
 import org.eclipse.qvtd.pivot.qvtschedule.Edge;
 import org.eclipse.qvtd.pivot.qvtschedule.NavigableEdge;
 import org.eclipse.qvtd.pivot.qvtschedule.NavigationEdge;
 import org.eclipse.qvtd.pivot.qvtschedule.Node;
 import org.eclipse.qvtd.pivot.qvtschedule.SharedEdge;
 import org.eclipse.qvtd.pivot.qvtschedule.utilities.QVTscheduleUtil;
 import com.google.common.collect.Lists;

 /**
  * The ReachabilityForest comprises a tree of preferred edge paths from each head/leaf-constant root node to the
  * nodes that can be reached from them. It answers the question: what preceding nodes are necessary to ensure
  * that a given node is reachable.
  */
 public class ReachabilityForest
 {
 	private static final int FORWARD_NAVIGATION_COST = 1;
 	private static final int INVERSE_MANY_NAVIGATION_COST = 5;
 	private static final int INVERSE_NAVIGATION_COST = 3;
 	private static final int ITERATOR_COST = 1;
 	private static final int OPERATION_COST = 10;
 	private static final int RESULT_COST = 1;
 	private static final int SHARED_NAVIGATION_COST = 10;

 	/**
 	 * The preferred non-secondary edges to be used in the tree.
 	 */
 	private final @NonNull Set<@NonNull NavigationEdge> forwardEdges = new HashSet<>();

 	/**
 	 * The shared edges to be used in the tree.
 	 */
 	private @Nullable List<@NonNull SharedEdge> sharedEdges = null;

 	/**
 	 * Edges that have no opposite.
 	 */
 	private final @NonNull Set<@NonNull Edge> manyToOneEdges = new HashSet<>();

 	/**
 	 * The incoming edge for each node in the traversal forest, null at a root.
 	 */
 	private final @NonNull Map<@NonNull Node, @Nullable Edge> node2reachingEdge = new HashMap<>();

 	/**
 	 * The cost for each node from the root in the traversal forest, 0 at a root. The cost is equal
 	 * to the sum of the costs of each edge on the lowest cost path from the root.
 	 */
 	private @NonNull Map<@NonNull Node, @NonNull Integer> node2cost = new HashMap<>();

 	/**
 	 * Lazily created compartor to order nodes lowest cost first.
 	 */
 	private @Nullable Comparator<@NonNull Edge> edgeCostComparator = null;

 	/**
 	 * Lazily created compartor to order nodes lowest cost first.
 	 */
 	private @Nullable Comparator<@NonNull Node> nodeCostComparator = null;


 	/**
 	 * Construct the Reachability forest for the specified rootNodes using the availableNavigableEdges to locate
 	 * paths to further nodes and also any old computation edges.
 	 */
 	public ReachabilityForest(@NonNull Iterable<@NonNull Node> rootNodes, @NonNull Iterable<@NonNull NavigableEdge> availableNavigableEdges) {
 		for (@NonNull Node rootNode : rootNodes) {
 			node2reachingEdge.put(rootNode, null);
 		}
 		for (@NonNull NavigableEdge edge : availableNavigableEdges) {
 			addEdge(edge);
 		}
 		//
 		//	Analyze the descendants of the roots to identify the most simply navigated forest.
 		//
 		analyze(node2reachingEdge.keySet());
 	}

 	protected void addEdge(@NonNull NavigableEdge edge) {
 		if (edge instanceof NavigationEdge) {
 			NavigationEdge navigationEdge = (NavigationEdge)edge;
 			if (!navigationEdge.isSecondary()) {
 				forwardEdges.add(navigationEdge);
 				if ((navigationEdge.getEdgeSource().isClass()) && (navigationEdge.getOppositeEdge() == null)) {
 					manyToOneEdges.add(navigationEdge);
 				}
 			}
 		}
 		else if (edge instanceof SharedEdge) {
 			List<@NonNull SharedEdge> sharedEdges2 = sharedEdges;
 			if (sharedEdges2 == null) {
 				sharedEdges = sharedEdges2 = new ArrayList<>();
 			}
 			sharedEdges2.add((SharedEdge)edge);
 		}
 	}

 	/**
 	 * Identify the forest from the given roots.
 	 */
 	protected void analyze(@NonNull Iterable<@NonNull Node> rootNodes) {
 		List<@Nullable List<@NonNull Node>> costs2nodes = new ArrayList<>();
 		for (@NonNull Node rootNode : rootNodes) {
 			node2cost.put(rootNode, 0);
 		}
 		costs2nodes.add(Lists.newArrayList(rootNodes));
 		//
 		//	Advance breadth first, one cost at a time, accumulating all edges that make one stage of progress.
 		//
 		for (int thisCost = 0; thisCost < costs2nodes.size(); thisCost++) {
 			List<@NonNull Node> thisCostNodes = costs2nodes.get(thisCost);
 			if (thisCostNodes != null) {
 				//
 				//	Add the forward edges that make progress to moreMoreNodes and remember the
 				//	backward and inverse edges in case forward egdes alone are inadequate.
 				//
 				for (@NonNull Node sourceNode : thisCostNodes) {
 					assert node2cost.get(sourceNode) == thisCost;
 					for (@NonNull Edge edge : QVTscheduleUtil.getOutgoingEdges(sourceNode)) {
 						assert !edge.isCast();
 						Node targetNode = edge.getEdgeTarget();
 						if (!node2reachingEdge.containsKey(targetNode)) {
 							Integer targetCost = node2cost.get(targetNode);
 							assert (targetCost == null) || (thisCost < targetCost);
 							if (edge.isNavigation()) {
 								NavigationEdge navigationEdge = (NavigationEdge) edge;
 								if (forwardEdges.contains(navigationEdge)) {
 									int nextCost = thisCost + FORWARD_NAVIGATION_COST;
 									if ((targetCost == null) || (nextCost < targetCost)) {
 										node2cost.put(targetNode, nextCost);
 										node2reachingEdge.put(targetNode, edge);
 										putCosts(costs2nodes, nextCost, targetNode);
 									}
 								}
 								else {
 									NavigationEdge oppositeEdge = navigationEdge.getOppositeEdge();
 									if (forwardEdges.contains(oppositeEdge)) {
 										boolean isImplicit = QVTscheduleUtil.getReferredProperty(oppositeEdge).isIsImplicit();
 										int nextCost = thisCost + (isImplicit ? INVERSE_NAVIGATION_COST : FORWARD_NAVIGATION_COST);
 										if ((targetCost == null) || (nextCost < targetCost)) {
 											node2cost.put(targetNode, nextCost);
 											node2reachingEdge.put(targetNode, oppositeEdge);
 											putCosts(costs2nodes, nextCost, targetNode);
 										}
 									}
 									else if (manyToOneEdges.contains(oppositeEdge)) {
 										int nextCost = thisCost + INVERSE_MANY_NAVIGATION_COST;
 										if ((targetCost == null) || (nextCost < targetCost)) {
 											node2cost.put(targetNode, nextCost);
 											node2reachingEdge.put(targetNode, oppositeEdge);
 											putCosts(costs2nodes, nextCost, targetNode);
 										}
 									}
 								}
 							}
 							else if (edge.isComputation() /*&& edge.isUnconditional()*/) {
 								int nextCost = thisCost + OPERATION_COST;
 								if (targetNode.isOperation()) {
 									for (@NonNull Edge incomingEdge : QVTscheduleUtil.getIncomingEdges(targetNode)) {
 										if (incomingEdge.isOld() && incomingEdge.isComputation()) {
 											Node node = QVTscheduleUtil.getSourceNode(incomingEdge);
 											Integer cost = node2cost.get(node);
 											if ((cost == null) || (cost > thisCost)) {
 												nextCost = -1;
 												break;
 											}
 										}
 									}
 								}
 								else if (targetNode.isIterator()) {
 									nextCost = thisCost + ITERATOR_COST;
 								}
 								else {
 									nextCost = thisCost + RESULT_COST;
 								}
 								if (nextCost > 0) {
 									if ((targetCost == null) || (nextCost < targetCost)) {
 										node2cost.put(targetNode, nextCost);
 										node2reachingEdge.put(targetNode, edge);
 										putCosts(costs2nodes, nextCost, targetNode);
 									}
 								}
 							}
 						}
 					}
 				}
 			}
 		}
 		if (sharedEdges != null) {
 			for (@NonNull SharedEdge sharedEdge : sharedEdges) {
 				Node targetNode = sharedEdge.getEdgeTarget();
 				if (!node2reachingEdge.containsKey(targetNode)) {
 					Integer targetCost = node2cost.get(targetNode);
 					assert targetCost == null;
 					Node sourceNode = sharedEdge.getEdgeSource();
 					Integer sourceCost = node2cost.get(sourceNode);
 					if (sourceCost != null) {
 						int nextCost = sourceCost + SHARED_NAVIGATION_COST;
 						node2cost.put(targetNode, nextCost);
 						node2reachingEdge.put(targetNode, sharedEdge);
 					}
 				}
 			}
 		}
 	}

 	public @Nullable Integer getCost(@NonNull Node node) {
 		return node2cost.get(node);
 	}

 	/**
 	 * Return a comparator to sort edges source cost first then target cost then alphabetically.
 	 */
 	public @NonNull Comparator<@NonNull Edge> getEdgeCostComparator() {
 		Comparator<@NonNull Edge> edgeCostComparator2 = edgeCostComparator;
 		if (edgeCostComparator2 == null) {
 			edgeCostComparator = edgeCostComparator2 = new Comparator<@NonNull Edge>()
 			{
 				@Override
 				public int compare(@NonNull Edge e1, @NonNull Edge e2) {
 					Node s1 = QVTscheduleUtil.getSourceNode(e1);
 					Node t1 = QVTscheduleUtil.getTargetNode(e1);
 					Node s2 = QVTscheduleUtil.getSourceNode(e2);
 					Node t2 = QVTscheduleUtil.getTargetNode(e2);
 					Integer d1s = node2cost.get(s1);
 					Integer d1t = node2cost.get(t1);
 					Integer d2s = node2cost.get(s2);
 					Integer d2t = node2cost.get(t2);
 					assert d1s != null : s1 + " is not reachable within " + s1.getOwningRegion();		// FIXME chnage to PartitionProblem
 					assert d1t != null : t1 + " is not reachable within " + t1.getOwningRegion();
 					assert d2s != null : s2 + " is not reachable within " + s2.getOwningRegion();
 					assert d2t != null : t2 + " is not reachable within " + t2.getOwningRegion();
 					int d1 = Math.max(d1s,  d1t);
 					int d2 = Math.max(d2s,  d2t);
 					if (d1 != d2) {
 						return d1 - d2;
 					}
 					if (d1s != d2s) {
 						return d1s - d2s;
 					}
 					String n1 = e1.getDisplayName();
 					String n2 = e2.getDisplayName();
 					int d = ClassUtil.safeCompareTo(n1, n2);
 					if (d != 0) {
 						return d;
 					}
 					n1 = s1.getDisplayName();
 					n2 = s2.getDisplayName();
 					d = ClassUtil.safeCompareTo(n1, n2);
 					if (d != 0) {
 						return d;
 					}
 					n1 = t1.getDisplayName();
 					n2 = t2.getDisplayName();
 					d = ClassUtil.safeCompareTo(n1, n2);
 					return d;
 				}
 			};
 		}
 		return edgeCostComparator2;
 	}

 	/**
 	 * Return a comparator to sort nodes cost first then alphabetically.
 	 */
 	public @NonNull Comparator<@NonNull Node> getNodeCostComparator() {
 		Comparator<@NonNull Node> nodeCostComparator2 = nodeCostComparator;
 		if (nodeCostComparator2 == null) {
 			nodeCostComparator = nodeCostComparator2 = new Comparator<@NonNull Node>()
 			{
 				@Override
 				public int compare(@NonNull Node o1, @NonNull Node o2) {
 					Integer c1 = node2cost.get(o1);
 					Integer c2 = node2cost.get(o2);
 					assert (c1 != null) && (c2 != null);
 					int diff = c1 - c2;
 					if (diff != 0) {
 						return diff;
 					}
 					return ClassUtil.safeCompareTo(o1.getName(), o2.getName());
 				}
 			};
 		}
 		return nodeCostComparator2;
 	}

 	public @NonNull Iterable<@NonNull Node> getNodes() {
 		return node2reachingEdge.keySet();
 	}

 	public @NonNull Iterable<@NonNull Node> getPredecessors(@NonNull Node targetNode) {
 		Set<@NonNull Node> precedingNodes = new HashSet<@NonNull Node>();
 		getPredecessors(precedingNodes, targetNode);
 		precedingNodes.remove(targetNode);
 		return precedingNodes;
 	}
 	private void getPredecessors(@NonNull Set<@NonNull Node> precedingNodes, @NonNull Node targetNode) {
 		if (precedingNodes.add(targetNode)) {
 			Edge parentEdge = null;
 			if (targetNode.isOperation()) {
 				Edge reachingEdge = getReachingEdge(targetNode);
 				if ((reachingEdge != null) && reachingEdge.isNavigation()) {
 					parentEdge = reachingEdge;
 				}
 				else {
 					for (@NonNull Edge edge : QVTscheduleUtil.getIncomingEdges(targetNode)) {
 						assert !edge.isCast();
 						if (edge.isComputation() || (edge.isNavigation() && !edge.isRealized())) {
 							getPredecessors(precedingNodes, edge.getEdgeSource());
 						}
 					}
 				}
 			}
 			else {
 				parentEdge = getReachingEdge(targetNode);
 			}
 			if (parentEdge != null) {
 				Node sourceNode = parentEdge.getEdgeSource();
 				if (sourceNode == targetNode) {		// invert a backward edge
 					sourceNode = parentEdge.getEdgeTarget();
 				}
 				getPredecessors(precedingNodes, sourceNode);
 			}
 		}
 	}

 	/**
 	 * Return the edge from the preceding reachable node to the given reachable node. Null if none.
 	 */
 	public @Nullable Edge getReachingEdge(@NonNull Node node) {
 		return node2reachingEdge.get(node);
 	}

 	private void putCosts(@NonNull List<@Nullable List<@NonNull Node>> costs2nodes, int cost, @NonNull Node node) {
 		while (costs2nodes.size() <= cost) {
 			costs2nodes.add(null);
 		}
 		List<@NonNull Node> nodes = costs2nodes.get(cost);
 		if (nodes == null) {
 			nodes = new ArrayList<>();
 			costs2nodes.set(cost, nodes);
 		}
 		if (!nodes.contains(node)) {
 			nodes.add(node);
 		}
 	}

 	@Override
 	public @NonNull String toString() {
 		Comparator<@NonNull Node> nodeComparator = getNodeCostComparator();
 		StringBuilder s = new StringBuilder();
 		List<@NonNull Node> nodes = new ArrayList<>(node2cost.keySet());
 		Collections.sort(nodes, nodeComparator);
 		for (@NonNull Node node : nodes) {
 			if (s.length() > 0) {
 				s.append("\n");
 			}
 			s.append(node2cost.get(node));
 			s.append(": ");
 			s.append(node.getName());
 			s.append(" : ");
 			s.append(node2reachingEdge.get(node));
 		}
 		return s.toString();
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2015, 2018 Willink Transformations and others.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v2.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v20.html
	*
	* Contributors:
	* E.D.Willink - Initial API and implementation
	*******************************************************************************/
	package org.eclipse.qvtd.compiler.internal.qvts2qvts.utilities;

	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;

	import org.eclipse.jdt.annotation.NonNull;
	import org.eclipse.jdt.annotation.Nullable;
	import org.eclipse.ocl.pivot.utilities.ClassUtil;
	import org.eclipse.qvtd.pivot.qvtschedule.Edge;
	import org.eclipse.qvtd.pivot.qvtschedule.NavigableEdge;
	import org.eclipse.qvtd.pivot.qvtschedule.NavigationEdge;
	import org.eclipse.qvtd.pivot.qvtschedule.Node;
	import org.eclipse.qvtd.pivot.qvtschedule.SharedEdge;
	import org.eclipse.qvtd.pivot.qvtschedule.utilities.QVTscheduleUtil;
	import com.google.common.collect.Lists;

	/**
	* The ReachabilityForest comprises a tree of preferred edge paths from each head/leaf-constant root node to the
	* nodes that can be reached from them. It answers the question: what preceding nodes are necessary to ensure
	* that a given node is reachable.
	*/
	public class ReachabilityForest
	{
	private static final int FORWARD_NAVIGATION_COST = 1;
	private static final int INVERSE_MANY_NAVIGATION_COST = 5;
	private static final int INVERSE_NAVIGATION_COST = 3;
	private static final int ITERATOR_COST = 1;
	private static final int OPERATION_COST = 10;
	private static final int RESULT_COST = 1;
	private static final int SHARED_NAVIGATION_COST = 10;

	/**
	* The preferred non-secondary edges to be used in the tree.
	*/
	private final @NonNull Set<@NonNull NavigationEdge> forwardEdges = new HashSet<>();

	/**
	* The shared edges to be used in the tree.
	*/
	private @Nullable List<@NonNull SharedEdge> sharedEdges = null;

	/**
	* Edges that have no opposite.
	*/
	private final @NonNull Set<@NonNull Edge> manyToOneEdges = new HashSet<>();

	/**
	* The incoming edge for each node in the traversal forest, null at a root.
	*/
	private final @NonNull Map<@NonNull Node, @Nullable Edge> node2reachingEdge = new HashMap<>();

	/**
	* The cost for each node from the root in the traversal forest, 0 at a root. The cost is equal
	* to the sum of the costs of each edge on the lowest cost path from the root.
	*/
	private @NonNull Map<@NonNull Node, @NonNull Integer> node2cost = new HashMap<>();

	/**
	* Lazily created compartor to order nodes lowest cost first.
	*/
	private @Nullable Comparator<@NonNull Edge> edgeCostComparator = null;

	/**
	* Lazily created compartor to order nodes lowest cost first.
	*/
	private @Nullable Comparator<@NonNull Node> nodeCostComparator = null;


	/**
	* Construct the Reachability forest for the specified rootNodes using the availableNavigableEdges to locate
	* paths to further nodes and also any old computation edges.
	*/
	public ReachabilityForest(@NonNull Iterable<@NonNull Node> rootNodes, @NonNull Iterable<@NonNull NavigableEdge> availableNavigableEdges) {
	for (@NonNull Node rootNode : rootNodes) {
	node2reachingEdge.put(rootNode, null);
	}
	for (@NonNull NavigableEdge edge : availableNavigableEdges) {
	addEdge(edge);
	}
	//
	// Analyze the descendants of the roots to identify the most simply navigated forest.
	//
	analyze(node2reachingEdge.keySet());
	}

	protected void addEdge(@NonNull NavigableEdge edge) {
	if (edge instanceof NavigationEdge) {
	NavigationEdge navigationEdge = (NavigationEdge)edge;
	if (!navigationEdge.isSecondary()) {
	forwardEdges.add(navigationEdge);
	if ((navigationEdge.getEdgeSource().isClass()) && (navigationEdge.getOppositeEdge() == null)) {
	manyToOneEdges.add(navigationEdge);
	}
	}
	}
	else if (edge instanceof SharedEdge) {
	List<@NonNull SharedEdge> sharedEdges2 = sharedEdges;
	if (sharedEdges2 == null) {
	sharedEdges = sharedEdges2 = new ArrayList<>();
	}
	sharedEdges2.add((SharedEdge)edge);
	}
	}

	/**
	* Identify the forest from the given roots.
	*/
	protected void analyze(@NonNull Iterable<@NonNull Node> rootNodes) {
	List<@Nullable List<@NonNull Node>> costs2nodes = new ArrayList<>();
	for (@NonNull Node rootNode : rootNodes) {
	node2cost.put(rootNode, 0);
	}
	costs2nodes.add(Lists.newArrayList(rootNodes));
	//
	// Advance breadth first, one cost at a time, accumulating all edges that make one stage of progress.
	//
	for (int thisCost = 0; thisCost < costs2nodes.size(); thisCost++) {
	List<@NonNull Node> thisCostNodes = costs2nodes.get(thisCost);
	if (thisCostNodes != null) {
	//
	// Add the forward edges that make progress to moreMoreNodes and remember the
	// backward and inverse edges in case forward egdes alone are inadequate.
	//
	for (@NonNull Node sourceNode : thisCostNodes) {
	assert node2cost.get(sourceNode) == thisCost;
	for (@NonNull Edge edge : QVTscheduleUtil.getOutgoingEdges(sourceNode)) {
	assert !edge.isCast();
	Node targetNode = edge.getEdgeTarget();
	if (!node2reachingEdge.containsKey(targetNode)) {
	Integer targetCost = node2cost.get(targetNode);
	assert (targetCost == null) \|\| (thisCost < targetCost);
	if (edge.isNavigation()) {
	NavigationEdge navigationEdge = (NavigationEdge) edge;
	if (forwardEdges.contains(navigationEdge)) {
	int nextCost = thisCost + FORWARD_NAVIGATION_COST;
	if ((targetCost == null) \|\| (nextCost < targetCost)) {
	node2cost.put(targetNode, nextCost);
	node2reachingEdge.put(targetNode, edge);
	putCosts(costs2nodes, nextCost, targetNode);
	}
	}
	else {
	NavigationEdge oppositeEdge = navigationEdge.getOppositeEdge();
	if (forwardEdges.contains(oppositeEdge)) {
	boolean isImplicit = QVTscheduleUtil.getReferredProperty(oppositeEdge).isIsImplicit();
	int nextCost = thisCost + (isImplicit ? INVERSE_NAVIGATION_COST : FORWARD_NAVIGATION_COST);
	if ((targetCost == null) \|\| (nextCost < targetCost)) {
	node2cost.put(targetNode, nextCost);
	node2reachingEdge.put(targetNode, oppositeEdge);
	putCosts(costs2nodes, nextCost, targetNode);
	}
	}
	else if (manyToOneEdges.contains(oppositeEdge)) {
	int nextCost = thisCost + INVERSE_MANY_NAVIGATION_COST;
	if ((targetCost == null) \|\| (nextCost < targetCost)) {
	node2cost.put(targetNode, nextCost);
	node2reachingEdge.put(targetNode, oppositeEdge);
	putCosts(costs2nodes, nextCost, targetNode);
	}
	}
	}
	}
	else if (edge.isComputation() /&& edge.isUnconditional()/) {
	int nextCost = thisCost + OPERATION_COST;
	if (targetNode.isOperation()) {
	for (@NonNull Edge incomingEdge : QVTscheduleUtil.getIncomingEdges(targetNode)) {
	if (incomingEdge.isOld() && incomingEdge.isComputation()) {
	Node node = QVTscheduleUtil.getSourceNode(incomingEdge);
	Integer cost = node2cost.get(node);
	if ((cost == null) \|\| (cost > thisCost)) {
	nextCost = -1;
	break;
	}
	}
	}
	}
	else if (targetNode.isIterator()) {
	nextCost = thisCost + ITERATOR_COST;
	}
	else {
	nextCost = thisCost + RESULT_COST;
	}
	if (nextCost > 0) {
	if ((targetCost == null) \|\| (nextCost < targetCost)) {
	node2cost.put(targetNode, nextCost);
	node2reachingEdge.put(targetNode, edge);
	putCosts(costs2nodes, nextCost, targetNode);
	}
	}
	}
	}
	}
	}
	}
	}
	if (sharedEdges != null) {
	for (@NonNull SharedEdge sharedEdge : sharedEdges) {
	Node targetNode = sharedEdge.getEdgeTarget();
	if (!node2reachingEdge.containsKey(targetNode)) {
	Integer targetCost = node2cost.get(targetNode);
	assert targetCost == null;
	Node sourceNode = sharedEdge.getEdgeSource();
	Integer sourceCost = node2cost.get(sourceNode);
	if (sourceCost != null) {
	int nextCost = sourceCost + SHARED_NAVIGATION_COST;
	node2cost.put(targetNode, nextCost);
	node2reachingEdge.put(targetNode, sharedEdge);
	}
	}
	}
	}
	}

	public @Nullable Integer getCost(@NonNull Node node) {
	return node2cost.get(node);
	}

	/**
	* Return a comparator to sort edges source cost first then target cost then alphabetically.
	*/
	public @NonNull Comparator<@NonNull Edge> getEdgeCostComparator() {
	Comparator<@NonNull Edge> edgeCostComparator2 = edgeCostComparator;
	if (edgeCostComparator2 == null) {
	edgeCostComparator = edgeCostComparator2 = new Comparator<@NonNull Edge>()
	{
	@Override
	public int compare(@NonNull Edge e1, @NonNull Edge e2) {
	Node s1 = QVTscheduleUtil.getSourceNode(e1);
	Node t1 = QVTscheduleUtil.getTargetNode(e1);
	Node s2 = QVTscheduleUtil.getSourceNode(e2);
	Node t2 = QVTscheduleUtil.getTargetNode(e2);
	Integer d1s = node2cost.get(s1);
	Integer d1t = node2cost.get(t1);
	Integer d2s = node2cost.get(s2);
	Integer d2t = node2cost.get(t2);
	assert d1s != null : s1 + " is not reachable within " + s1.getOwningRegion(); // FIXME chnage to PartitionProblem
	assert d1t != null : t1 + " is not reachable within " + t1.getOwningRegion();
	assert d2s != null : s2 + " is not reachable within " + s2.getOwningRegion();
	assert d2t != null : t2 + " is not reachable within " + t2.getOwningRegion();
	int d1 = Math.max(d1s, d1t);
	int d2 = Math.max(d2s, d2t);
	if (d1 != d2) {
	return d1 - d2;
	}
	if (d1s != d2s) {
	return d1s - d2s;
	}
	String n1 = e1.getDisplayName();
	String n2 = e2.getDisplayName();
	int d = ClassUtil.safeCompareTo(n1, n2);
	if (d != 0) {
	return d;
	}
	n1 = s1.getDisplayName();
	n2 = s2.getDisplayName();
	d = ClassUtil.safeCompareTo(n1, n2);
	if (d != 0) {
	return d;
	}
	n1 = t1.getDisplayName();
	n2 = t2.getDisplayName();
	d = ClassUtil.safeCompareTo(n1, n2);
	return d;
	}
	};
	}
	return edgeCostComparator2;
	}

	/**
	* Return a comparator to sort nodes cost first then alphabetically.
	*/
	public @NonNull Comparator<@NonNull Node> getNodeCostComparator() {
	Comparator<@NonNull Node> nodeCostComparator2 = nodeCostComparator;
	if (nodeCostComparator2 == null) {
	nodeCostComparator = nodeCostComparator2 = new Comparator<@NonNull Node>()
	{
	@Override
	public int compare(@NonNull Node o1, @NonNull Node o2) {
	Integer c1 = node2cost.get(o1);
	Integer c2 = node2cost.get(o2);
	assert (c1 != null) && (c2 != null);
	int diff = c1 - c2;
	if (diff != 0) {
	return diff;
	}
	return ClassUtil.safeCompareTo(o1.getName(), o2.getName());
	}
	};
	}
	return nodeCostComparator2;
	}

	public @NonNull Iterable<@NonNull Node> getNodes() {
	return node2reachingEdge.keySet();
	}

	public @NonNull Iterable<@NonNull Node> getPredecessors(@NonNull Node targetNode) {
	Set<@NonNull Node> precedingNodes = new HashSet<@NonNull Node>();
	getPredecessors(precedingNodes, targetNode);
	precedingNodes.remove(targetNode);
	return precedingNodes;
	}
	private void getPredecessors(@NonNull Set<@NonNull Node> precedingNodes, @NonNull Node targetNode) {
	if (precedingNodes.add(targetNode)) {
	Edge parentEdge = null;
	if (targetNode.isOperation()) {
	Edge reachingEdge = getReachingEdge(targetNode);
	if ((reachingEdge != null) && reachingEdge.isNavigation()) {
	parentEdge = reachingEdge;
	}
	else {
	for (@NonNull Edge edge : QVTscheduleUtil.getIncomingEdges(targetNode)) {
	assert !edge.isCast();
	if (edge.isComputation() \|\| (edge.isNavigation() && !edge.isRealized())) {
	getPredecessors(precedingNodes, edge.getEdgeSource());
	}
	}
	}
	}
	else {
	parentEdge = getReachingEdge(targetNode);
	}
	if (parentEdge != null) {
	Node sourceNode = parentEdge.getEdgeSource();
	if (sourceNode == targetNode) { // invert a backward edge
	sourceNode = parentEdge.getEdgeTarget();
	}
	getPredecessors(precedingNodes, sourceNode);
	}
	}
	}

	/**
	* Return the edge from the preceding reachable node to the given reachable node. Null if none.
	*/
	public @Nullable Edge getReachingEdge(@NonNull Node node) {
	return node2reachingEdge.get(node);
	}

	private void putCosts(@NonNull List<@Nullable List<@NonNull Node>> costs2nodes, int cost, @NonNull Node node) {
	while (costs2nodes.size() <= cost) {
	costs2nodes.add(null);
	}
	List<@NonNull Node> nodes = costs2nodes.get(cost);
	if (nodes == null) {
	nodes = new ArrayList<>();
	costs2nodes.set(cost, nodes);
	}
	if (!nodes.contains(node)) {
	nodes.add(node);
	}
	}

	@Override
	public @NonNull String toString() {
	Comparator<@NonNull Node> nodeComparator = getNodeCostComparator();
	StringBuilder s = new StringBuilder();
	List<@NonNull Node> nodes = new ArrayList<>(node2cost.keySet());
	Collections.sort(nodes, nodeComparator);
	for (@NonNull Node node : nodes) {
	if (s.length() > 0) {
	s.append("\n");
	}
	s.append(node2cost.get(node));
	s.append(": ");
	s.append(node.getName());
	s.append(" : ");
	s.append(node2reachingEdge.get(node));
	}
	return s.toString();
	}
	}