platform/lang-impl/src/com/intellij/cyclicDependencies/CyclicGraphUtil.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
  21 import java.util.*;
  22
  23 /**
  24  * User: anna
  25  * Date: Feb 13, 2005
  26  */
  27 public class CyclicGraphUtil {
  28   private CyclicGraphUtil() {
  29   }
  30
  31   public static <Node> Set<List<Node>> getNodeCycles(final Graph<Node> graph, final Node node){
  32     Set<List<Node>> result = new HashSet<List<Node>>();
  33
  34
  35     final Graph<Node> graphWithoutNode = new Graph<Node>() {
  36       public Collection<Node> getNodes() {
  37         final Collection<Node> nodes = graph.getNodes();
  38         nodes.remove(node);
  39         return nodes;
  40       }
  41
  42       public Iterator<Node> getIn(final Node n) {
  43         final HashSet<Node> nodes = new HashSet<Node>();
  44         final Iterator<Node> in = graph.getIn(n);
  45         for(;in.hasNext();){
  46           nodes.add(in.next());
  47         }
  48         nodes.remove(node);
  49         return nodes.iterator();
  50       }
  51
  52       public Iterator<Node> getOut(final Node n) {
  53         final HashSet<Node> nodes = new HashSet<Node>();
  54         final Iterator<Node> out = graph.getOut(n);
  55         for(;out.hasNext();){
  56           nodes.add(out.next());
  57         }
  58         nodes.remove(node);
  59         return nodes.iterator();
  60       }
  61
  62     };
  63
  64     final HashSet<Node> inNodes = new HashSet<Node>();
  65     final Iterator<Node> in = graph.getIn(node);
  66     for(;in.hasNext();){
  67       inNodes.add(in.next());
  68     }
  69     final HashSet<Node> outNodes = new HashSet<Node>();
  70     final Iterator<Node> out = graph.getOut(node);
  71     for(;out.hasNext();){
  72       outNodes.add(out.next());
  73     }
  74
  75     final HashSet<Node> retainNodes = new HashSet<Node>(inNodes);
  76     retainNodes.retainAll(outNodes);
  77     for (Node node1 : retainNodes) {
  78       ArrayList<Node> oneNodeCycle = new ArrayList<Node>();
  79       oneNodeCycle.add(node1);
  80       oneNodeCycle.add(node);
  81       result.add(oneNodeCycle);
  82     }
  83
  84     inNodes.removeAll(retainNodes);
  85     outNodes.removeAll(retainNodes);
  86
  87     final ShortestPathUtil<Node> algorithm = new ShortestPathUtil<Node>(graphWithoutNode);
  88
  89     for (Node fromNode : outNodes) {
  90       for (Node toNode : inNodes) {
  91         final List<Node> shortestPath = algorithm.getShortestPath(toNode, fromNode);
  92         if (shortestPath != null) {
  93           ArrayList<Node> path = new ArrayList<Node>();
  94           path.addAll(shortestPath);
  95           path.add(node);
  96           result.add(path);
  97         }
  98       }
  99     }
 100     return result;
 101   }
 102 }