platform/lang-impl/src/com/intellij/cyclicDependencies/ShortestPathUtil.java

   1 /*
   2  * Copyright 2000-2009 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package com.intellij.cyclicDependencies;
  18
  19 import com.intellij.util.graph.Graph;
  20 import com.intellij.util.ui.tree.TreeUtil;
  21
  22 import javax.swing.tree.DefaultMutableTreeNode;
  23 import javax.swing.tree.DefaultTreeModel;
  24 import javax.swing.tree.TreeModel;
  25 import javax.swing.tree.TreeNode;
  26 import java.util.*;
  27
  28 /**
  29  * User: anna
  30  * Date: Feb 11, 2005
  31  */
  32 //DijkstraAlgorithm
  33 public class ShortestPathUtil <Node> {
  34   private final HashSet<Node> myVisited;
  35   private final Set<ProcessingNode> myProcessingNodes;
  36
  37   private DefaultTreeModel myShortestPathTree;
  38
  39   private final Graph<Node> myGraph;
  40
  41   public ShortestPathUtil(Graph<Node> graph) {
  42     myVisited = new HashSet<Node>();
  43     myProcessingNodes = new HashSet<ProcessingNode>();
  44     myGraph = graph;
  45   }
  46
  47   public List<Node> getShortestPath(Node from, Node to) {
  48     ArrayList<Node> result = new ArrayList<Node>();
  49     if (myShortestPathTree == null || ((DefaultMutableTreeNode)myShortestPathTree.getRoot()).getUserObject() != from) {
  50       shortestPath(from);
  51     }
  52     final boolean flag = traverse(to, result);
  53     return flag ? result : null;
  54   }
  55
  56   private boolean traverse(Node to, List<Node> path){
  57     DefaultMutableTreeNode treeNode = findNodeByUserObject(to);
  58     if (treeNode == null){
  59       return false;
  60     }
  61     while (treeNode != null){
  62       path.add((Node)treeNode.getUserObject());
  63       treeNode = (DefaultMutableTreeNode)treeNode.getParent();
  64     }
  65     return true;
  66   }
  67
  68
  69   private TreeModel shortestPath(Node from) {
  70     myShortestPathTree = new DefaultTreeModel(new DefaultMutableTreeNode(from));
  71
  72     myProcessingNodes.add(new ProcessingNode(null, from, 0));
  73
  74     while (!myProcessingNodes.isEmpty()) {
  75       moveToVisited();
  76     }
  77
  78     myVisited.clear();
  79     myProcessingNodes.clear();
  80
  81     return myShortestPathTree;
  82   }
  83
  84   private DefaultMutableTreeNode findNodeByUserObject(final Node nodeToFind){
  85       final ArrayList<DefaultMutableTreeNode> parent = new ArrayList<DefaultMutableTreeNode>();
  86       TreeUtil.traverseDepth((TreeNode)myShortestPathTree.getRoot(), new TreeUtil.Traverse() {
  87         public boolean accept(Object node) {
  88           final DefaultMutableTreeNode treeNode = ((DefaultMutableTreeNode)node);
  89           if (treeNode.getUserObject() != null && treeNode.getUserObject().equals(nodeToFind)) {
  90             parent.add(treeNode);
  91             return false;
  92           }
  93           return true;
  94         }
  95       });
  96       return parent.size() > 0 ? parent.get(0) : null;
  97   }
  98
  99   private void moveToVisited() {
 100     ProcessingNode priorityNode = null;
 101     for (Iterator<ProcessingNode> iterator = myProcessingNodes.iterator(); iterator.hasNext();) {
 102       ProcessingNode processingNode = iterator.next();
 103       if (priorityNode != null) {
 104         if (priorityNode.getPriority() > processingNode.getPriority()) {
 105           priorityNode = processingNode;
 106         }
 107       }
 108       else {
 109         priorityNode = processingNode;
 110       }
 111     }
 112     myProcessingNodes.remove(priorityNode);
 113     myVisited.add(priorityNode.myToNode);
 114     if (priorityNode.myFromNode != null) {
 115       final DefaultMutableTreeNode parentNode = findNodeByUserObject(priorityNode.myFromNode);
 116       if (parentNode != null){
 117         myShortestPathTree.insertNodeInto(new DefaultMutableTreeNode(priorityNode.myToNode), parentNode, 0);
 118       }
 119     }
 120     moveAdjacentVerticesToProcessing(priorityNode);
 121   }
 122
 123   private void moveAdjacentVerticesToProcessing(ProcessingNode priorityNode) {
 124     Node fromNode = priorityNode.getToNode();
 125     int priority = priorityNode.getPriority();
 126     Iterator<Node> iterator = myGraph.getIn(fromNode);
 127     Node toNode;
 128     while (iterator.hasNext()) {
 129       toNode = iterator.next();
 130       if (myVisited.contains(toNode)){
 131         continue;
 132       }
 133       final ProcessingNode processingNode = getProcessingNodeByFromNode(toNode);
 134       if (processingNode == null) {
 135         myProcessingNodes.add(new ProcessingNode(fromNode, toNode, priority + 1));
 136       }
 137       else {
 138         if (processingNode.getPriority() > priority + 1) {
 139           processingNode.setPriority(priority + 1);
 140           processingNode.setFromNode(fromNode);
 141         }
 142       }
 143     }
 144   }
 145
 146   private ProcessingNode getProcessingNodeByFromNode(Node fromNode) {
 147     for (Iterator<ProcessingNode> iterator = myProcessingNodes.iterator(); iterator.hasNext();) {
 148       ProcessingNode processingNode = iterator.next();
 149       if (processingNode.getFromNode() == fromNode) {
 150         return processingNode;
 151       }
 152     }
 153     return null;
 154   }
 155
 156
 157
 158   private class ProcessingNode {
 159     private Node myFromNode;
 160     private Node myToNode;
 161     private int myPriority;
 162
 163     public ProcessingNode(final Node fromNode, final Node toNode, final int priority) {
 164       myFromNode = fromNode;
 165       myToNode = toNode;
 166       myPriority = priority;
 167     }
 168
 169     public Node getFromNode() {
 170       return myFromNode;
 171     }
 172
 173     public Node getToNode() {
 174       return myToNode;
 175     }
 176
 177     public int getPriority() {
 178       return myPriority;
 179     }
 180
 181     public void setPriority(final int priority) {
 182       myPriority = priority;
 183     }
 184
 185     public void setFromNode(final Node fromNode) {
 186       myFromNode = fromNode;
 187     }
 188
 189     public void setToNode(final Node toNode) {
 190       myToNode = toNode;
 191     }
 192   }
 193
 194 }
 195
 196
 197
 198