algorithms on graphs rearranged: implemented efficient algorithm to find k shortest...
authornik <Nikolay.Chashnikov@jetbrains.com>
Tue, 7 Jun 2011 07:36:31 +0000 (11:36 +0400)
committernik <Nikolay.Chashnikov@jetbrains.com>
Tue, 7 Jun 2011 07:37:05 +0000 (11:37 +0400)
16 files changed:
java/java-impl/src/com/intellij/cyclicDependencies/CyclicDependenciesBuilder.java
platform/lang-impl/src/com/intellij/cyclicDependencies/ShortestPathUtil.java [deleted file]
platform/lang-impl/src/com/intellij/moduleDependencies/ModulesDependenciesPanel.java
platform/lang-impl/testSrc/com/intellij/dependencies/DijkstraAlgorithmTest.java [deleted file]
platform/lang-impl/testSrc/com/intellij/dependencies/SearchCyclesTest.java [deleted file]
platform/platform-impl/src/com/intellij/util/graph/GraphAlgorithms.java [new file with mode: 0644]
platform/platform-impl/src/com/intellij/util/graph/impl/CycleFinder.java [moved from platform/lang-impl/src/com/intellij/cyclicDependencies/CyclicGraphUtil.java with 71% similarity]
platform/platform-impl/src/com/intellij/util/graph/impl/GraphAlgorithmsImpl.java [new file with mode: 0644]
platform/platform-impl/src/com/intellij/util/graph/impl/GraphEdge.java [new file with mode: 0644]
platform/platform-impl/src/com/intellij/util/graph/impl/KShortestPathsFinder.java [new file with mode: 0644]
platform/platform-impl/src/com/intellij/util/graph/impl/ShortestPathFinder.java [new file with mode: 0644]
platform/platform-impl/testSrc/com/intellij/util/graph/GraphTestCase.java [new file with mode: 0644]
platform/platform-impl/testSrc/com/intellij/util/graph/KShortestPathsFinderTest.java [new file with mode: 0644]
platform/platform-impl/testSrc/com/intellij/util/graph/SearchCyclesTest.java [new file with mode: 0644]
platform/platform-impl/testSrc/com/intellij/util/graph/ShortestPathTest.java [new file with mode: 0644]
platform/platform-resources/src/META-INF/PlatformExtensions.xml

index 10f55f2dfadd66591291648254b9cbda36614ec4..a38a1485c606563c1c19eded84f201e26e22fbad 100644 (file)
@@ -28,6 +28,7 @@ import com.intellij.packageDependencies.ForwardDependenciesBuilder;
 import com.intellij.psi.*;
 import com.intellij.util.graph.CachingSemiGraph;
 import com.intellij.util.graph.Graph;
+import com.intellij.util.graph.GraphAlgorithms;
 import com.intellij.util.graph.GraphGenerator;
 
 import java.util.*;
@@ -217,7 +218,7 @@ public class CyclicDependenciesBuilder{
           paths2Pack = new HashSet<List<PsiPackage>>();
           result.put(psiPackage, paths2Pack);
         }
-        paths2Pack.addAll(CyclicGraphUtil.getNodeCycles(myGraph, psiPackage));
+        paths2Pack.addAll(GraphAlgorithms.getInstance().findCycles(myGraph, psiPackage));
     }
     return result;
   }
diff --git a/platform/lang-impl/src/com/intellij/cyclicDependencies/ShortestPathUtil.java b/platform/lang-impl/src/com/intellij/cyclicDependencies/ShortestPathUtil.java
deleted file mode 100644 (file)
index 338d2c4..0000000
+++ /dev/null
@@ -1,198 +0,0 @@
-/*
- * Copyright 2000-2009 JetBrains s.r.o.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.intellij.cyclicDependencies;
-
-import com.intellij.util.graph.Graph;
-import com.intellij.util.ui.tree.TreeUtil;
-
-import javax.swing.tree.DefaultMutableTreeNode;
-import javax.swing.tree.DefaultTreeModel;
-import javax.swing.tree.TreeModel;
-import javax.swing.tree.TreeNode;
-import java.util.*;
-
-/**
- * User: anna
- * Date: Feb 11, 2005
- */
-//DijkstraAlgorithm
-public class ShortestPathUtil <Node> {
-  private final HashSet<Node> myVisited;
-  private final Set<ProcessingNode> myProcessingNodes;
-
-  private DefaultTreeModel myShortestPathTree;
-
-  private final Graph<Node> myGraph;
-
-  public ShortestPathUtil(Graph<Node> graph) {
-    myVisited = new HashSet<Node>();
-    myProcessingNodes = new HashSet<ProcessingNode>();
-    myGraph = graph;
-  }
-
-  public List<Node> getShortestPath(Node from, Node to) {
-    ArrayList<Node> result = new ArrayList<Node>();
-    if (myShortestPathTree == null || ((DefaultMutableTreeNode)myShortestPathTree.getRoot()).getUserObject() != from) {
-      shortestPath(from);
-    }
-    final boolean flag = traverse(to, result);
-    return flag ? result : null;
-  }
-
-  private boolean traverse(Node to, List<Node> path){
-    DefaultMutableTreeNode treeNode = findNodeByUserObject(to);
-    if (treeNode == null){
-      return false;
-    }
-    while (treeNode != null){
-      path.add((Node)treeNode.getUserObject());
-      treeNode = (DefaultMutableTreeNode)treeNode.getParent();
-    }
-    return true;
-  }
-
-
-  private TreeModel shortestPath(Node from) {
-    myShortestPathTree = new DefaultTreeModel(new DefaultMutableTreeNode(from));
-
-    myProcessingNodes.add(new ProcessingNode(null, from, 0));
-
-    while (!myProcessingNodes.isEmpty()) {
-      moveToVisited();
-    }
-
-    myVisited.clear();
-    myProcessingNodes.clear();
-
-    return myShortestPathTree;
-  }
-
-  private DefaultMutableTreeNode findNodeByUserObject(final Node nodeToFind){
-      final ArrayList<DefaultMutableTreeNode> parent = new ArrayList<DefaultMutableTreeNode>();
-      TreeUtil.traverseDepth((TreeNode)myShortestPathTree.getRoot(), new TreeUtil.Traverse() {
-        public boolean accept(Object node) {
-          final DefaultMutableTreeNode treeNode = ((DefaultMutableTreeNode)node);
-          if (treeNode.getUserObject() != null && treeNode.getUserObject().equals(nodeToFind)) {
-            parent.add(treeNode);
-            return false;
-          }
-          return true;
-        }
-      });
-      return parent.size() > 0 ? parent.get(0) : null;
-  }
-
-  private void moveToVisited() {
-    ProcessingNode priorityNode = null;
-    for (Iterator<ProcessingNode> iterator = myProcessingNodes.iterator(); iterator.hasNext();) {
-      ProcessingNode processingNode = iterator.next();
-      if (priorityNode != null) {
-        if (priorityNode.getPriority() > processingNode.getPriority()) {
-          priorityNode = processingNode;
-        }
-      }
-      else {
-        priorityNode = processingNode;
-      }
-    }
-    myProcessingNodes.remove(priorityNode);
-    myVisited.add(priorityNode.myToNode);
-    if (priorityNode.myFromNode != null) {
-      final DefaultMutableTreeNode parentNode = findNodeByUserObject(priorityNode.myFromNode);
-      if (parentNode != null){
-        myShortestPathTree.insertNodeInto(new DefaultMutableTreeNode(priorityNode.myToNode), parentNode, 0);
-      }
-    }
-    moveAdjacentVerticesToProcessing(priorityNode);
-  }
-
-  private void moveAdjacentVerticesToProcessing(ProcessingNode priorityNode) {
-    Node fromNode = priorityNode.getToNode();
-    int priority = priorityNode.getPriority();
-    Iterator<Node> iterator = myGraph.getIn(fromNode);
-    Node toNode;
-    while (iterator.hasNext()) {
-      toNode = iterator.next();
-      if (myVisited.contains(toNode)){
-        continue;
-      }
-      final ProcessingNode processingNode = getProcessingNodeByFromNode(toNode);
-      if (processingNode == null) {
-        myProcessingNodes.add(new ProcessingNode(fromNode, toNode, priority + 1));
-      }
-      else {
-        if (processingNode.getPriority() > priority + 1) {
-          processingNode.setPriority(priority + 1);
-          processingNode.setFromNode(fromNode);
-        }
-      }
-    }
-  }
-
-  private ProcessingNode getProcessingNodeByFromNode(Node fromNode) {
-    for (Iterator<ProcessingNode> iterator = myProcessingNodes.iterator(); iterator.hasNext();) {
-      ProcessingNode processingNode = iterator.next();
-      if (processingNode.getFromNode() == fromNode) {
-        return processingNode;
-      }
-    }
-    return null;
-  }
-
-
-
-  private class ProcessingNode {
-    private Node myFromNode;
-    private Node myToNode;
-    private int myPriority;
-
-    public ProcessingNode(final Node fromNode, final Node toNode, final int priority) {
-      myFromNode = fromNode;
-      myToNode = toNode;
-      myPriority = priority;
-    }
-
-    public Node getFromNode() {
-      return myFromNode;
-    }
-
-    public Node getToNode() {
-      return myToNode;
-    }
-
-    public int getPriority() {
-      return myPriority;
-    }
-
-    public void setPriority(final int priority) {
-      myPriority = priority;
-    }
-
-    public void setFromNode(final Node fromNode) {
-      myFromNode = fromNode;
-    }
-
-    public void setToNode(final Node toNode) {
-      myToNode = toNode;
-    }
-  }
-
-}
-
-
-
-
index 6ff8ca6679b6d9f1157b9f99a6e3a9732c185184..53564cc8c00911c6ab5069710f63991ca2983c79 100644 (file)
@@ -19,7 +19,6 @@ package com.intellij.moduleDependencies;
 import com.intellij.CommonBundle;
 import com.intellij.ProjectTopics;
 import com.intellij.analysis.AnalysisScopeBundle;
-import com.intellij.cyclicDependencies.CyclicGraphUtil;
 import com.intellij.ide.CommonActionsManager;
 import com.intellij.ide.TreeExpander;
 import com.intellij.ide.actions.ContextHelpAction;
@@ -37,7 +36,6 @@ import com.intellij.openapi.roots.ui.configuration.ProjectSettingsService;
 import com.intellij.openapi.ui.Splitter;
 import com.intellij.openapi.util.IconLoader;
 import com.intellij.openapi.util.text.StringUtil;
-import com.intellij.pom.Navigatable;
 import com.intellij.pom.NavigatableWithText;
 import com.intellij.ui.*;
 import com.intellij.ui.content.Content;
@@ -47,6 +45,7 @@ import com.intellij.util.containers.Convertor;
 import com.intellij.util.containers.HashMap;
 import com.intellij.util.graph.DFSTBuilder;
 import com.intellij.util.graph.Graph;
+import com.intellij.util.graph.GraphAlgorithms;
 import com.intellij.util.ui.UIUtil;
 import com.intellij.util.ui.tree.TreeUtil;
 import org.jetbrains.annotations.NonNls;
@@ -191,7 +190,7 @@ public class ModulesDependenciesPanel extends JPanel implements ModuleRootListen
   private void buildRightTree(Module module){
     final DefaultMutableTreeNode root = (DefaultMutableTreeNode)myRightTreeModel.getRoot();
     root.removeAllChildren();
-    final Set<List<Module>> cycles = CyclicGraphUtil.getNodeCycles(myModulesGraph, module);
+    final Set<List<Module>> cycles = GraphAlgorithms.getInstance().findCycles(myModulesGraph, module);
     int index = 1;
     for (List<Module> modules : cycles) {
       final DefaultMutableTreeNode cycle = new DefaultMutableTreeNode(
@@ -223,7 +222,7 @@ public class ModulesDependenciesPanel extends JPanel implements ModuleRootListen
           if (!module.isDisposed()) {
             Boolean isInCycle = inCycle.get(module);
             if (isInCycle == null) {
-              isInCycle = !CyclicGraphUtil.getNodeCycles(myModulesGraph, module).isEmpty();
+              isInCycle = !GraphAlgorithms.getInstance().findCycles(myModulesGraph, module).isEmpty();
               inCycle.put(module, isInCycle);
             }
             final DefaultMutableTreeNode moduleNode = new DefaultMutableTreeNode(new MyUserObject(isInCycle.booleanValue(), module));
@@ -407,20 +406,7 @@ public class ModulesDependenciesPanel extends JPanel implements ModuleRootListen
       return graph;
     }
     else {
-      return new Graph<Module>() {
-        public Collection<Module> getNodes() {
-          return graph.getNodes();
-        }
-
-        public Iterator<Module> getIn(final Module n) {
-          return graph.getOut(n);
-        }
-
-        public Iterator<Module> getOut(final Module n) {
-          return graph.getIn(n);
-        }
-
-      };
+      return GraphAlgorithms.getInstance().invertEdgeDirections(graph);
     }
   }
 
diff --git a/platform/lang-impl/testSrc/com/intellij/dependencies/DijkstraAlgorithmTest.java b/platform/lang-impl/testSrc/com/intellij/dependencies/DijkstraAlgorithmTest.java
deleted file mode 100644 (file)
index 470b790..0000000
+++ /dev/null
@@ -1,147 +0,0 @@
-/*
- * Copyright 2000-2009 JetBrains s.r.o.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.intellij.dependencies;
-
-import com.intellij.cyclicDependencies.ShortestPathUtil;
-import com.intellij.util.ArrayUtil;
-import com.intellij.util.graph.Graph;
-import com.intellij.util.graph.GraphGenerator;
-import junit.framework.TestCase;
-
-import java.util.*;
-
-/**
- * User: anna
- * Date: Feb 11, 2005
- */
-public class DijkstraAlgorithmTest extends TestCase{
-  private Graph<String> myGraph;
-  public void test1() throws Exception{
-    final HashMap<String, String []> graph = new HashMap<String, String[]>();
-    graph.put("a", new String[]{"b","c", "d"});
-    graph.put("b", new String[]{"d", "c"});
-    graph.put("c", new String[]{"b"});
-    graph.put("d", ArrayUtil.EMPTY_STRING_ARRAY);
-    myGraph = new GraphGenerator<String>(new GraphGenerator.SemiGraph<String>() {
-      @Override
-      public Collection<String> getNodes() {
-        return graph.keySet();
-      }
-
-      @Override
-      public Iterator<String> getIn(final String n) {
-        String[] in = graph.get(n);
-        if (in == null){
-          in = ArrayUtil.EMPTY_STRING_ARRAY;
-        }
-        return Arrays.asList(in).iterator();
-      }
-    });
-    final ShortestPathUtil<String> algorithm = new ShortestPathUtil<String>(myGraph);
-    final List<String> shortestPath = algorithm.getShortestPath("a", "b");
-    checkResult(new String[]{"b","a"}, shortestPath);
-  }
-
-  public void test2() throws Exception{
-    final HashMap<String, String []> graph = new HashMap<String, String[]>();
-    graph.put("a", new String[]{"b", "d"});
-    graph.put("b", new String[]{"d"});
-    graph.put("c", new String[]{"a"});
-    graph.put("d", new String[]{"a", "c"});
-    myGraph = new GraphGenerator<String>(new GraphGenerator.SemiGraph<String>() {
-      @Override
-      public Collection<String> getNodes() {
-        return graph.keySet();
-      }
-
-      @Override
-      public Iterator<String> getIn(final String n) {
-        String[] in = graph.get(n);
-        if (in == null){
-          in = ArrayUtil.EMPTY_STRING_ARRAY;
-        }
-        return Arrays.asList(in).iterator();
-      }
-    });
-    final ShortestPathUtil<String> algorithm = new ShortestPathUtil<String>(myGraph);
-    final List<String> shortestPath = algorithm.getShortestPath("b", "c");
-    checkResult(new String[]{"c","d","b"}, shortestPath);
-  }
-
-  public void test3() throws Exception{
-    final HashMap<String, String []> graph = new HashMap<String, String[]>();
-    graph.put("a", new String[]{"c", "d"});
-    graph.put("b", new String[]{"a"});
-    graph.put("c", new String[]{"d"});
-    graph.put("d", new String[]{"a", "b"});
-    myGraph = new GraphGenerator<String>(new GraphGenerator.SemiGraph<String>() {
-      @Override
-      public Collection<String> getNodes() {
-        return graph.keySet();
-      }
-
-      @Override
-      public Iterator<String> getIn(final String n) {
-        String[] in = graph.get(n);
-        if (in == null){
-          in = ArrayUtil.EMPTY_STRING_ARRAY;
-        }
-        return Arrays.asList(in).iterator();
-      }
-    });
-    final ShortestPathUtil<String> algorithm = new ShortestPathUtil<String>(myGraph);
-    final List<String> shortestPath = algorithm.getShortestPath("c", "b");
-    checkResult(new String[]{"b","d","c"}, shortestPath);
-  }
-
-  public void test4() throws Exception{
-      final HashMap<String, String []> graph = new HashMap<String, String[]>();
-    graph.put("a", new String[]{"c"});
-    graph.put("b", new String[]{"a"});
-    graph.put("c", new String[]{"e"});
-    graph.put("d", new String[]{"b"});
-    graph.put("e", new String[]{"d", "f", "a"});
-    graph.put("f", new String[]{"d"});
-    myGraph = new GraphGenerator<String>(new GraphGenerator.SemiGraph<String>() {
-      @Override
-      public Collection<String> getNodes() {
-        return graph.keySet();
-      }
-
-      @Override
-      public Iterator<String> getIn(final String n) {
-        String[] in = graph.get(n);
-        if (in == null){
-          in = ArrayUtil.EMPTY_STRING_ARRAY;
-        }
-        return Arrays.asList(in).iterator();
-      }
-    });
-    final ShortestPathUtil<String> algorithm = new ShortestPathUtil<String>(myGraph);
-    final List<String> shortestPath = algorithm.getShortestPath("c", "b");
-    checkResult(new String[]{"b","d","e","c"}, shortestPath);
-  }
-
-  private static void checkResult(final String [] expectedPath, List<String> path){
-    assertNotNull(path);
-    assertEquals(expectedPath.length, path.size());
-    int index = 0;
-    for (String s : path) {
-      assertEquals(expectedPath[index++], s);
-    }
-  }
-}
diff --git a/platform/lang-impl/testSrc/com/intellij/dependencies/SearchCyclesTest.java b/platform/lang-impl/testSrc/com/intellij/dependencies/SearchCyclesTest.java
deleted file mode 100644 (file)
index 0c795b1..0000000
+++ /dev/null
@@ -1,177 +0,0 @@
-/*
- * Copyright 2000-2009 JetBrains s.r.o.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.intellij.dependencies;
-
-import com.intellij.cyclicDependencies.CyclicGraphUtil;
-import com.intellij.util.ArrayUtil;
-import com.intellij.util.graph.Graph;
-import com.intellij.util.graph.GraphGenerator;
-import junit.framework.TestCase;
-
-import java.util.*;
-
-/**
- * User: anna
- * Date: Feb 13, 2005
- */
-public class SearchCyclesTest extends TestCase{
-  public void test1() throws Exception{
-    final HashMap<String, String []> graph = new HashMap<String, String[]>();
-    graph.put("a", new String[]{"c", "d"});
-    graph.put("b", new String[]{"a"});
-    graph.put("c", new String[]{"d"});
-    graph.put("d", new String[]{"a", "b"});
-    Graph<String> graphToInvestigate = new GraphGenerator<String>(new GraphGenerator.SemiGraph<String>() {
-      @Override
-      public Collection<String> getNodes() {
-        return graph.keySet();
-      }
-
-      @Override
-      public Iterator<String> getIn(final String n) {
-        String[] in = graph.get(n);
-        if (in == null){
-          in = ArrayUtil.EMPTY_STRING_ARRAY;
-        }
-        return Arrays.asList(in).iterator();
-      }
-    });
-    final Set<List<String>> nodeCycles = CyclicGraphUtil.getNodeCycles(graphToInvestigate, "a");
-    checkResult(new String[][]{{"d","a"},{"b","d","c","a"}}, nodeCycles);
-  }
-
-  public void test2() throws Exception{
-    final HashMap<String, String []> graph = new HashMap<String, String[]>();
-    graph.put("a", new String[]{"c"});
-    graph.put("b", new String[]{"a"});
-    graph.put("c", new String[]{"d"});
-    graph.put("d", new String[]{"b","e"});
-    graph.put("e", new String[]{"d"});
-    Graph<String> graphToInvestigate = new GraphGenerator<String>(new GraphGenerator.SemiGraph<String>() {
-      @Override
-      public Collection<String> getNodes() {
-        return graph.keySet();
-      }
-
-      @Override
-      public Iterator<String> getIn(final String n) {
-        String[] in = graph.get(n);
-        if (in == null){
-          in = ArrayUtil.EMPTY_STRING_ARRAY;
-        }
-        return Arrays.asList(in).iterator();
-      }
-    });
-    final Set<List<String>> nodeCycles = CyclicGraphUtil.getNodeCycles(graphToInvestigate, "a");
-    checkResult(new String[][]{{"b","d","c","a"}}, nodeCycles);
-  }
-
-  public void test3() throws Exception{
-    final HashMap<String, String []> graph = new HashMap<String, String[]>();
-    graph.put("a", new String[]{"d"});
-    graph.put("b", new String[]{"a"});
-    graph.put("d", new String[]{"a", "b"});
-    Graph<String> graphToInvestigate = new GraphGenerator<String>(new GraphGenerator.SemiGraph<String>() {
-      @Override
-      public Collection<String> getNodes() {
-        return graph.keySet();
-      }
-
-      @Override
-      public Iterator<String> getIn(final String n) {
-        String[] in = graph.get(n);
-        if (in == null){
-          in = ArrayUtil.EMPTY_STRING_ARRAY;
-        }
-        return Arrays.asList(in).iterator();
-      }
-    });
-    final Set<List<String>> nodeCycles = CyclicGraphUtil.getNodeCycles(graphToInvestigate, "a");
-    checkResult(new String[][]{{"d","a"}}, nodeCycles);
-  }
-
-   public void test4() throws Exception{
-    final HashMap<String, String []> graph = new HashMap<String, String[]>();
-    graph.put("a", new String[]{"c"});
-    graph.put("b", new String[]{"a"});
-    graph.put("c", new String[]{"e"});
-    graph.put("d", new String[]{"b"});
-    graph.put("e", new String[]{"d", "f"});
-    graph.put("f", new String[]{"d"});
-    Graph<String> graphToInvestigate = new GraphGenerator<String>(new GraphGenerator.SemiGraph<String>() {
-      @Override
-      public Collection<String> getNodes() {
-        return graph.keySet();
-      }
-
-      @Override
-      public Iterator<String> getIn(final String n) {
-        String[] in = graph.get(n);
-        if (in == null){
-          in = ArrayUtil.EMPTY_STRING_ARRAY;
-        }
-        return Arrays.asList(in).iterator();
-      }
-    });
-    final Set<List<String>> nodeCycles = CyclicGraphUtil.getNodeCycles(graphToInvestigate, "a");
-    checkResult(new String[][]{{"b","d","e","c","a"}}, nodeCycles);
-  }
-
-   public void test5() throws Exception{
-    final HashMap<String, String []> graph = new HashMap<String, String[]>();
-    graph.put("a", new String[]{"c"});
-    graph.put("b", new String[]{"a"});
-    graph.put("c", new String[]{"e"});
-    graph.put("d", new String[]{"b"});
-    graph.put("e", new String[]{"d", "f", "a"});
-    graph.put("f", new String[]{"d"});
-    Graph<String> graphToInvestigate = new GraphGenerator<String>(new GraphGenerator.SemiGraph<String>() {
-      @Override
-      public Collection<String> getNodes() {
-        return graph.keySet();
-      }
-
-      @Override
-      public Iterator<String> getIn(final String n) {
-        String[] in = graph.get(n);
-        if (in == null){
-          in = ArrayUtil.EMPTY_STRING_ARRAY;
-        }
-        return Arrays.asList(in).iterator();
-      }
-    });
-    final Set<List<String>> nodeCycles = CyclicGraphUtil.getNodeCycles(graphToInvestigate, "a");
-    checkResult(new String[][]{{"b","d","e","c","a"}, {"e","c","a"}}, nodeCycles);
-  }
-
-  private static void checkResult(String[][] expected, Set<List<String>> cycles){
-    assertEquals(expected.length, cycles.size());
-    for (List<String> strings : cycles) {
-      assertTrue(findInMatrix(expected, ArrayUtil.toStringArray(strings)) > -1);
-    }
-  }
-
-  private static int findInMatrix(String [][] matrix, String [] string){
-    for (int i = 0; i < matrix.length; i++) {
-      String[] strings = matrix[i];
-      if (Arrays.equals(strings, string)){
-        return i;
-      }
-    }
-    return -1;
-  }
-}
diff --git a/platform/platform-impl/src/com/intellij/util/graph/GraphAlgorithms.java b/platform/platform-impl/src/com/intellij/util/graph/GraphAlgorithms.java
new file mode 100644 (file)
index 0000000..90cd66b
--- /dev/null
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2000-2011 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.intellij.util.graph;
+
+import com.intellij.openapi.components.ServiceManager;
+import com.intellij.openapi.progress.ProgressIndicator;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.Nullable;
+
+import java.util.List;
+import java.util.Set;
+
+/**
+ * @author nik
+ */
+public abstract class GraphAlgorithms {
+  public static GraphAlgorithms getInstance() {
+    return ServiceManager.getService(GraphAlgorithms.class);
+  }
+
+  @Nullable
+  public abstract <Node> List<Node> findShortestPath(@NotNull Graph<Node> graph, @NotNull Node start, @NotNull Node finish);
+
+  @NotNull
+  public abstract <Node> List<List<Node>> findKShortestPaths(@NotNull Graph<Node> graph, @NotNull Node start, @NotNull Node finish, int k,
+                                                             @NotNull ProgressIndicator progressIndicator);
+
+  @NotNull
+  public abstract <Node> Set<List<Node>> findCycles(@NotNull Graph<Node> graph, @NotNull Node node);
+
+  @NotNull
+  public abstract <Node> List<List<Node>> removePathsWithCycles(@NotNull List<List<Node>> paths);
+
+  @NotNull
+  public abstract <Node> Graph<Node> invertEdgeDirections(@NotNull Graph<Node> graph);
+}
similarity index 71%
rename from platform/lang-impl/src/com/intellij/cyclicDependencies/CyclicGraphUtil.java
rename to platform/platform-impl/src/com/intellij/util/graph/impl/CycleFinder.java
index eb97e63f984f1f223a3ce84e19d9db63a463ae64..fa8695c5c8bf1e73e15335be25129bb1c67620d8 100644 (file)
  * limitations under the License.
  */
 
-package com.intellij.cyclicDependencies;
+package com.intellij.util.graph.impl;
 
 import com.intellij.util.graph.Graph;
+import org.jetbrains.annotations.NotNull;
 
 import java.util.*;
 
@@ -24,25 +25,29 @@ import java.util.*;
  * User: anna
  * Date: Feb 13, 2005
  */
-public class CyclicGraphUtil {
-  private CyclicGraphUtil() {
+public class CycleFinder<Node> {
+  private final Graph<Node> myGraph;
+
+  public CycleFinder(Graph<Node> graph) {
+    myGraph = graph;
   }
 
-  public static <Node> Set<List<Node>> getNodeCycles(final Graph<Node> graph, final Node node){
-    Set<List<Node>> result = new HashSet<List<Node>>();
+  @NotNull
+  public Set<List<Node>> getNodeCycles(final Node node){
+    final Set<List<Node>> result = new HashSet<List<Node>>();
 
 
     final Graph<Node> graphWithoutNode = new Graph<Node>() {
       public Collection<Node> getNodes() {
-        final Collection<Node> nodes = graph.getNodes();
+        final Collection<Node> nodes = myGraph.getNodes();
         nodes.remove(node);
         return nodes;
       }
 
       public Iterator<Node> getIn(final Node n) {
         final HashSet<Node> nodes = new HashSet<Node>();
-        final Iterator<Node> in = graph.getIn(n);
-        for(;in.hasNext();){
+        final Iterator<Node> in = myGraph.getIn(n);
+        while (in.hasNext()) {
           nodes.add(in.next());
         }
         nodes.remove(node);
@@ -51,8 +56,8 @@ public class CyclicGraphUtil {
 
       public Iterator<Node> getOut(final Node n) {
         final HashSet<Node> nodes = new HashSet<Node>();
-        final Iterator<Node> out = graph.getOut(n);
-        for(;out.hasNext();){
+        final Iterator<Node> out = myGraph.getOut(n);
+        while (out.hasNext()) {
           nodes.add(out.next());
         }
         nodes.remove(node);
@@ -62,13 +67,13 @@ public class CyclicGraphUtil {
     };
 
     final HashSet<Node> inNodes = new HashSet<Node>();
-    final Iterator<Node> in = graph.getIn(node);
-    for(;in.hasNext();){
+    final Iterator<Node> in = myGraph.getIn(node);
+    while (in.hasNext()) {
       inNodes.add(in.next());
     }
     final HashSet<Node> outNodes = new HashSet<Node>();
-    final Iterator<Node> out = graph.getOut(node);
-    for(;out.hasNext();){
+    final Iterator<Node> out = myGraph.getOut(node);
+    while (out.hasNext()) {
       outNodes.add(out.next());
     }
 
@@ -84,11 +89,10 @@ public class CyclicGraphUtil {
     inNodes.removeAll(retainNodes);
     outNodes.removeAll(retainNodes);
 
-    final ShortestPathUtil<Node> algorithm = new ShortestPathUtil<Node>(graphWithoutNode);
-
+    ShortestPathFinder<Node> finder = new ShortestPathFinder<Node>(graphWithoutNode);
     for (Node fromNode : outNodes) {
       for (Node toNode : inNodes) {
-        final List<Node> shortestPath = algorithm.getShortestPath(toNode, fromNode);
+        final List<Node> shortestPath = finder.findPath(fromNode, toNode);
         if (shortestPath != null) {
           ArrayList<Node> path = new ArrayList<Node>();
           path.addAll(shortestPath);
diff --git a/platform/platform-impl/src/com/intellij/util/graph/impl/GraphAlgorithmsImpl.java b/platform/platform-impl/src/com/intellij/util/graph/impl/GraphAlgorithmsImpl.java
new file mode 100644 (file)
index 0000000..a8a45f1
--- /dev/null
@@ -0,0 +1,81 @@
+/*
+ * Copyright 2000-2011 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.intellij.util.graph.impl;
+
+import com.intellij.openapi.progress.ProgressIndicator;
+import com.intellij.util.graph.Graph;
+import com.intellij.util.graph.GraphAlgorithms;
+import org.jetbrains.annotations.NotNull;
+
+import java.util.*;
+
+/**
+ * @author nik
+ */
+public class GraphAlgorithmsImpl extends GraphAlgorithms {
+  @Override
+  public <Node> List<Node> findShortestPath(@NotNull Graph<Node> graph, @NotNull Node start, @NotNull Node finish) {
+    return new ShortestPathFinder<Node>(graph).findPath(start, finish);
+  }
+
+  @NotNull
+  @Override
+  public <Node> List<List<Node>> findKShortestPaths(@NotNull Graph<Node> graph, @NotNull Node start, @NotNull Node finish, int k,
+                                                    @NotNull ProgressIndicator progressIndicator) {
+    return new KShortestPathsFinder<Node>(graph, start, finish, progressIndicator).findShortestPaths(k);
+  }
+
+  @NotNull
+  @Override
+  public <Node> Set<List<Node>> findCycles(@NotNull Graph<Node> graph, @NotNull Node node) {
+    return new CycleFinder<Node>(graph).getNodeCycles(node);
+  }
+
+  @NotNull
+  @Override
+  public <Node> Graph<Node> invertEdgeDirections(@NotNull final Graph<Node> graph) {
+    return new Graph<Node>() {
+      public Collection<Node> getNodes() {
+        return graph.getNodes();
+      }
+
+      public Iterator<Node> getIn(final Node n) {
+        return graph.getOut(n);
+      }
+
+      public Iterator<Node> getOut(final Node n) {
+        return graph.getIn(n);
+      }
+
+    };
+  }
+
+  @NotNull
+  @Override
+  public <Node> List<List<Node>> removePathsWithCycles(@NotNull List<List<Node>> paths) {
+    final List<List<Node>> result = new ArrayList<List<Node>>();
+    for (List<Node> path : paths) {
+      if (!containsCycle(path)) {
+        result.add(path);
+      }
+    }
+    return result;
+  }
+
+  private static boolean containsCycle(List<?> path) {
+    return new HashSet<Object>(path).size() != path.size();
+  }
+}
diff --git a/platform/platform-impl/src/com/intellij/util/graph/impl/GraphEdge.java b/platform/platform-impl/src/com/intellij/util/graph/impl/GraphEdge.java
new file mode 100644 (file)
index 0000000..d7f977f
--- /dev/null
@@ -0,0 +1,59 @@
+/*
+ * Copyright 2000-2011 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.intellij.util.graph.impl;
+
+import org.jetbrains.annotations.NotNull;
+
+/**
+ * @author nik
+ */
+class GraphEdge<Node> {
+  private final Node myStart;
+  private final Node myFinish;
+  private final int myDelta;
+
+  GraphEdge(@NotNull Node start, @NotNull Node finish, int delta) {
+    myStart = start;
+    myFinish = finish;
+    myDelta = delta;
+  }
+
+  public Node getStart() {
+    return myStart;
+  }
+
+  public Node getFinish() {
+    return myFinish;
+  }
+
+  public int getDelta() {
+    return myDelta;
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) return true;
+    if (o == null || getClass() != o.getClass()) return false;
+
+    GraphEdge edge = (GraphEdge)o;
+    return myFinish.equals(edge.myFinish) && myStart.equals(edge.myStart);
+  }
+
+  @Override
+  public int hashCode() {
+    return 31 * myStart.hashCode() + myFinish.hashCode();
+  }
+}
diff --git a/platform/platform-impl/src/com/intellij/util/graph/impl/KShortestPathsFinder.java b/platform/platform-impl/src/com/intellij/util/graph/impl/KShortestPathsFinder.java
new file mode 100644 (file)
index 0000000..7e6e3d3
--- /dev/null
@@ -0,0 +1,331 @@
+/*
+ * Copyright 2000-2011 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.intellij.util.graph.impl;
+
+import com.intellij.openapi.diagnostic.Logger;
+import com.intellij.openapi.progress.ProcessCanceledException;
+import com.intellij.openapi.progress.ProgressIndicator;
+import com.intellij.util.containers.FList;
+import com.intellij.util.containers.MultiMap;
+import com.intellij.util.graph.Graph;
+import gnu.trove.TObjectIntHashMap;
+import org.jetbrains.annotations.NotNull;
+
+import java.util.*;
+
+/**
+ * Algorithm to search k shortest paths between to vertices in unweighted directed graph.
+ * Based on article "Finding the k shortest paths" by D. Eppstein, 1997.
+ *
+ * @author nik
+ */
+public class KShortestPathsFinder<Node> {
+  private static final Logger LOG = Logger.getInstance("#com.intellij.util.graph.impl.KShortestPathsFinder");
+  private final Graph<Node> myGraph;
+  private final Node myStart;
+  private final Node myFinish;
+  private final ProgressIndicator myProgressIndicator;
+  private MultiMap<Node, GraphEdge<Node>> myNonTreeEdges;
+  private List<Node> mySortedNodes;
+  private Map<Node, Node> myNextNodes;
+  private Map<Node, HeapNode<Node>> myOutRoots;
+  private Map<Node,Heap<Node>> myHeaps;
+
+  public KShortestPathsFinder(@NotNull Graph<Node> graph, @NotNull Node start, @NotNull Node finish, @NotNull ProgressIndicator progressIndicator) {
+    myGraph = graph;
+    myStart = start;
+    myFinish = finish;
+    myProgressIndicator = progressIndicator;
+  }
+
+  private void computeDistancesToTarget() {
+    myNonTreeEdges = new MultiMap<Node, GraphEdge<Node>>();
+    mySortedNodes = new ArrayList<Node>();
+    myNextNodes = new HashMap<Node, Node>();
+    TObjectIntHashMap<Node> distances = new TObjectIntHashMap<Node>();
+    Deque<Node> nodes = new ArrayDeque<Node>();
+    nodes.addLast(myFinish);
+    distances.put(myFinish, 0);
+    while (!nodes.isEmpty()) {
+      myProgressIndicator.checkCanceled();
+      Node node = nodes.removeFirst();
+      mySortedNodes.add(node);
+      int d = distances.get(node) + 1;
+      Iterator<Node> iterator = myGraph.getIn(node);
+      while (iterator.hasNext()) {
+        Node prev = iterator.next();
+        if (distances.containsKey(prev)) {
+          int dPrev = distances.get(prev);
+          myNonTreeEdges.putValue(prev, new GraphEdge<Node>(prev, node, d - dPrev));
+          continue;
+        }
+        distances.put(prev, d);
+        myNextNodes.put(prev, node);
+        nodes.addLast(prev);
+      }
+    }
+  }
+
+  private void buildOutHeaps() {
+    myOutRoots = new HashMap<Node, HeapNode<Node>>();
+    for (Node node : mySortedNodes) {
+      myProgressIndicator.checkCanceled();
+      List<HeapNode<Node>> heapNodes = new ArrayList<HeapNode<Node>>();
+      Collection<GraphEdge<Node>> edges = myNonTreeEdges.get(node);
+      if (edges.isEmpty()) continue;
+
+      HeapNode<Node> root = null;
+      for (GraphEdge<Node> edge : edges) {
+        HeapNode<Node> heapNode = new HeapNode<Node>(edge);
+        heapNodes.add(heapNode);
+        if (root == null || root.myEdge.getDelta() > heapNode.myEdge.getDelta()) {
+          root = heapNode;
+        }
+      }
+      LOG.assertTrue(root != null);
+      heapNodes.remove(root);
+      myOutRoots.put(node, root);
+      if (!heapNodes.isEmpty()) {
+        for (int j = 1; j < heapNodes.size(); j++) {
+          HeapNode<Node> heapNode = heapNodes.get(j);
+          HeapNode<Node> parent = heapNodes.get((j+1)/2 - 1);
+          heapNode.myParent = parent;
+          parent.myChildren[(j+1) % 2] = heapNode;
+        }
+        for (int j = heapNodes.size() / 2 - 1; j >= 0; j--) {
+          heapify(heapNodes.get(j));
+        }
+        root.myChildren[2] = heapNodes.get(0);
+        root.myChildren[2].myParent = root;
+      }
+    }
+  }
+
+  private void buildMainHeaps() {
+    myHeaps = new HashMap<Node, Heap<Node>>();
+    for (Node node : mySortedNodes) {
+      myProgressIndicator.checkCanceled();
+      HeapNode<Node> outRoot = myOutRoots.get(node);
+      Node next = myNextNodes.get(node);
+      if (outRoot == null) {
+        if (next != null) {
+          myHeaps.put(node, myHeaps.get(next));
+        }
+        continue;
+      }
+
+      final Heap<Node> nextHeap = myHeaps.get(next);
+      if (nextHeap == null) {
+        myHeaps.put(node, new Heap<Node>(outRoot));
+        continue;
+      }
+
+      final Heap<Node> tHeap = nextHeap.insert(outRoot);
+      myHeaps.put(node, tHeap);
+    }
+  }
+
+  private void heapify(HeapNode<Node> node) {
+    while (true) {
+      HeapNode<Node> min = node;
+      for (int i = 0; i < 2; i++) {
+        HeapNode<Node> child = node.myChildren[i];
+        if (child != null && child.myEdge.getDelta() < min.myEdge.getDelta()) {
+          min = child;
+        }
+      }
+      if (min != node) {
+        GraphEdge<Node> t = min.myEdge;
+        min.myEdge = node.myEdge;
+        node.myEdge = t;
+        node = min;
+      }
+      else {
+        break;
+      }
+    }
+  }
+
+  public List<List<Node>> findShortestPaths(int k) {
+    try {
+      if (myStart.equals(myFinish)) {
+        return Collections.singletonList(Collections.singletonList(myStart));
+      }
+      computeDistancesToTarget();
+      if (!myNextNodes.containsKey(myStart)) {
+        return Collections.emptyList();
+      }
+      buildOutHeaps();
+      buildMainHeaps();
+
+      PriorityQueue<Sidetracks<Node>> queue = new PriorityQueue<Sidetracks<Node>>();
+      List<FList<HeapNode<Node>>> sidetracks = new ArrayList<FList<HeapNode<Node>>>();
+      sidetracks.add(FList.<HeapNode<Node>>emptyList());
+
+      final Heap<Node> heap = myHeaps.get(myStart);
+      if (heap != null) {
+        queue.add(new Sidetracks<Node>(0, FList.<HeapNode<Node>>emptyList().prepend(heap.getRoot())));
+        for (int i = 2; i <= k; i++) {
+          if (queue.isEmpty()) break;
+          myProgressIndicator.checkCanceled();
+          final Sidetracks<Node> current = queue.remove();
+          sidetracks.add(current.myEdges);
+          final HeapNode<Node> e = current.myEdges.getHead();
+          final Heap<Node> next = myHeaps.get(e.myEdge.getFinish());
+          if (next != null) {
+            final HeapNode<Node> f = next.getRoot();
+            queue.add(new Sidetracks<Node>(current.myLength + f.myEdge.getDelta(), current.myEdges.prepend(f)));
+          }
+          for (HeapNode<Node> child : e.myChildren) {
+            if (child != null) {
+              queue.add(new Sidetracks<Node>(current.myLength - e.myEdge.getDelta() + child.myEdge.getDelta(),
+                                             current.myEdges.getTail().prepend(child)));
+            }
+          }
+        }
+      }
+
+      return computePathsBySidetracks(sidetracks);
+    }
+    catch (ProcessCanceledException e) {
+      return Collections.emptyList();
+    }
+  }
+
+  private List<List<Node>> computePathsBySidetracks(List<FList<HeapNode<Node>>> sidetracks) {
+    final List<List<Node>> result = new ArrayList<List<Node>>();
+    for (FList<HeapNode<Node>> sidetrack : sidetracks) {
+      myProgressIndicator.checkCanceled();
+      List<GraphEdge<Node>> edges = new ArrayList<GraphEdge<Node>>();
+      while (!sidetrack.isEmpty()) {
+        edges.add(sidetrack.getHead().myEdge);
+        sidetrack = sidetrack.getTail();
+      }
+      Node current = myStart;
+      final List<Node> path = new ArrayList<Node>();
+      path.add(current);
+      int i = edges.size() - 1;
+      while (!current.equals(myFinish) || i >= 0) {
+        if (i >= 0 && edges.get(i).getStart().equals(current)) {
+          current = edges.get(i).getFinish();
+          i--;
+        }
+        else {
+          current = myNextNodes.get(current);
+          LOG.assertTrue(current != null);
+        }
+        path.add(current);
+      }
+      result.add(path);
+    }
+
+    return result;
+  }
+
+  private static class Sidetracks<Node> implements Comparable<Sidetracks> {
+    private int myLength;
+    private final FList<HeapNode<Node>> myEdges;
+
+    private Sidetracks(int length, FList<HeapNode<Node>> edges) {
+      myLength = length;
+      myEdges = edges;
+    }
+
+    @Override
+    public int compareTo(Sidetracks o) {
+      return myLength - o.myLength;
+    }
+  }
+
+  private static class Heap<Node> {
+    private final int mySize;
+    private HeapNode<Node> myRoot;
+
+    public Heap(HeapNode<Node> root) {
+      myRoot = root;
+      mySize = 1;
+    }
+
+    private Heap(int size, HeapNode<Node> root) {
+      mySize = size;
+      myRoot = root;
+    }
+
+    public HeapNode<Node> getRoot() {
+      return myRoot;
+    }
+
+    public Heap<Node> insert(HeapNode<Node> node) {
+      int pos = mySize + 1;
+      int pow = 1;
+      while (pos > pow << 2) {
+        pow <<= 1;
+      }
+      HeapNode<Node> place = myRoot;
+      while (true) {
+        final int ind = (pos & pow) != 0 ? 1 : 0;
+        if (pow == 1) {
+          HeapNode<Node> placeCopy = place.copy();
+          placeCopy.myChildren[ind] = node;
+          node.myParent = placeCopy;
+          break;
+        }
+        place = place.myChildren[ind];
+        pow >>= 1;
+      }
+      while (true) {
+        final HeapNode<Node> parent = node.myParent;
+        if (parent == null || parent.myEdge.getDelta() < node.myEdge.getDelta()) {
+          break;
+        }
+        final HeapNode<Node> parentCopy = parent.copy();
+        final GraphEdge<Node> t = parentCopy.myEdge;
+        parentCopy.myEdge = node.myEdge;
+        node.myEdge = t;
+        final HeapNode<Node> t2 = parentCopy.myChildren[2];
+        parentCopy.myChildren[2] = node.myChildren[2];
+        node.myChildren[2] = t2;
+        node = parentCopy;
+      }
+      HeapNode<Node> newRoot = node;
+      while (newRoot.myParent != null) {
+        newRoot = newRoot.myParent;
+      }
+      return new Heap<Node>(mySize + 1, newRoot);
+    }
+  }
+
+  private static class HeapNode<Node> {
+    public HeapNode<Node>[] myChildren;
+    public HeapNode<Node> myParent;
+    public GraphEdge<Node> myEdge;
+
+    private HeapNode(GraphEdge<Node> edge) {
+      myEdge = edge;
+      myChildren = new HeapNode[3];
+    }
+
+    public HeapNode(HeapNode<Node> node) {
+      myEdge = node.myEdge;
+      myChildren = node.myChildren.clone();
+      myParent = node.myParent;
+    }
+
+    public HeapNode<Node> copy() {
+      return new HeapNode<Node>(this);
+    }
+  }
+}
diff --git a/platform/platform-impl/src/com/intellij/util/graph/impl/ShortestPathFinder.java b/platform/platform-impl/src/com/intellij/util/graph/impl/ShortestPathFinder.java
new file mode 100644 (file)
index 0000000..a676647
--- /dev/null
@@ -0,0 +1,70 @@
+/*
+ * Copyright 2000-2011 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.intellij.util.graph.impl;
+
+import com.intellij.util.graph.Graph;
+import org.jetbrains.annotations.Nullable;
+
+import java.util.*;
+
+/**
+ * @author nik
+ */
+public class ShortestPathFinder<Node> {
+  private final Graph<Node> myGraph;
+
+  public ShortestPathFinder(Graph<Node> graph) {
+    myGraph = graph;
+  }
+
+
+  @Nullable
+  public List<Node> findPath(Node start, Node finish) {
+    Map<Node, Node> nextNodes = new HashMap<Node, Node>();
+    Deque<Node> queue = new ArrayDeque<Node>();
+    queue.addLast(finish);
+
+    boolean found = false;
+    while (!queue.isEmpty()) {
+      final Node node = queue.removeFirst();
+      if (node.equals(start)) {
+        found = true;
+        break;
+      }
+
+      final Iterator<Node> in = myGraph.getIn(node);
+      while (in.hasNext()) {
+        Node prev = in.next();
+        if (!nextNodes.containsKey(prev)) {
+          nextNodes.put(prev, node);
+          queue.addLast(prev);
+        }
+      }
+    }
+
+    if (!found) {
+      return null;
+    }
+    List<Node> path = new ArrayList<Node>();
+    Node current = start;
+    while (!current.equals(finish)) {
+      path.add(current);
+      current = nextNodes.get(current);
+    }
+    path.add(finish);
+    return path;
+  }
+}
diff --git a/platform/platform-impl/testSrc/com/intellij/util/graph/GraphTestCase.java b/platform/platform-impl/testSrc/com/intellij/util/graph/GraphTestCase.java
new file mode 100644 (file)
index 0000000..ab14963
--- /dev/null
@@ -0,0 +1,58 @@
+/*
+ * Copyright 2000-2011 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.intellij.util.graph;
+
+import junit.framework.TestCase;
+
+import java.util.*;
+
+/**
+ * @author nik
+ */
+public abstract class GraphTestCase extends TestCase {
+  protected static Graph<String> initGraph(final Map<String, String> graph) {
+    final Map<String, List<String>> out = new HashMap<String, List<String>>();
+    final Map<String, List<String>> in = new HashMap<String, List<String>>();
+    for (String s : graph.keySet()) {
+      out.put(s, new ArrayList<String>());
+      in.put(s, new ArrayList<String>());
+    }
+    for (Map.Entry<String, String> entry : graph.entrySet()) {
+      String from = entry.getKey();
+      for (int i = 0; i < entry.getValue().length(); i++) {
+        String to = String.valueOf(entry.getValue().charAt(i));
+        out.get(from).add(to);
+        in.get(to).add(from);
+      }
+    }
+    return new Graph<String>() {
+      @Override
+      public Collection<String> getNodes() {
+        return graph.keySet();
+      }
+
+      @Override
+      public Iterator<String> getIn(final String n) {
+        return in.get(n).iterator();
+      }
+
+      @Override
+      public Iterator<String> getOut(String n) {
+        return out.get(n).iterator();
+      }
+    };
+  }
+}
diff --git a/platform/platform-impl/testSrc/com/intellij/util/graph/KShortestPathsFinderTest.java b/platform/platform-impl/testSrc/com/intellij/util/graph/KShortestPathsFinderTest.java
new file mode 100644 (file)
index 0000000..4750a7c
--- /dev/null
@@ -0,0 +1,168 @@
+/*
+ * Copyright 2000-2011 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.intellij.util.graph;
+
+import com.intellij.openapi.progress.EmptyProgressIndicator;
+import com.intellij.openapi.util.text.StringUtil;
+import com.intellij.testFramework.UsefulTestCase;
+import com.intellij.util.graph.impl.KShortestPathsFinder;
+
+import java.util.*;
+
+/**
+ * @author nik
+ */
+public class KShortestPathsFinderTest extends GraphTestCase {
+  public void testEmpty() {
+    Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "");
+    graph.put("t", "");
+    doTest(graph);
+  }
+
+  public void testOneEdge() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "t");
+    graph.put("t", "");
+    doTest(graph, "st");
+  }
+
+  public void testNoPaths() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "a");
+    graph.put("a", "s");
+    graph.put("b", "at");
+    graph.put("t", "sab");
+    doTest(graph);
+  }
+
+  public void testOneVertex() {
+    Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "");
+    doTest(graph, "s", "s", 5, "s");
+  }
+
+  public void testTwoPaths() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "ta");
+    graph.put("a", "t");
+    graph.put("t", "");
+    doTest(graph, "st", "sat");
+  }
+
+  public void testManyEdgesToTarget() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "a");
+    graph.put("a", "bt");
+    graph.put("b", "ct");
+    graph.put("c", "dt");
+    graph.put("d", "t");
+    graph.put("t", "");
+    doTest(graph, "sat", "sabt", "sabct", "sabcdt");
+  }
+
+  public void testManyEdgesFromSource() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "abcdt");
+    graph.put("a", "b");
+    graph.put("b", "c");
+    graph.put("c", "d");
+    graph.put("d", "t");
+    graph.put("t", "");
+    doTest(graph, "st", "sdt", "scdt", "sbcdt", "sabcdt");
+  }
+
+  public void testTwoParts() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "ab");
+    graph.put("a", "b");
+    graph.put("b", "cd");
+    graph.put("c", "t");
+    graph.put("d", "e");
+    graph.put("e", "t");
+    graph.put("t", "");
+    doTest(graph, "sbct", "sabct", "sbdet", "sabdet");
+  }
+
+  public void testHangingEdges() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "ae");
+    graph.put("a", "bc");
+    graph.put("b", "ac");
+    graph.put("c", "ab");
+    graph.put("d", "s");
+    graph.put("e", "t");
+    graph.put("t", "");
+    doTest(graph, "set");
+  }
+
+  public void testSimpleCycle() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "t");
+    graph.put("t", "s");
+    doTest(graph, 4, "st", "stst", "ststst", "stststst");
+  }
+
+  public void testComplexCycle() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "p");
+    graph.put("p", "qt");
+    graph.put("q", "vt");
+    graph.put("v", "p");
+    graph.put("t", "");
+    doTest(graph, 5, "spt", "spqt", "spqvpt", "spqvpqt", "spqvpqvpt");
+  }
+
+  public void testHeap() {
+    final Map<String, String> graph = new HashMap<String, String>();
+    graph.put("s", "a");
+    graph.put("a", "bd");
+    graph.put("b", "cd");
+    graph.put("c", "td");
+    graph.put("d", "e");
+    graph.put("e", "f");
+    graph.put("f", "t");
+    graph.put("t", "");
+    doTest(graph, "sabct", "sadeft", "sabdeft", "sabcdeft");
+
+  }
+
+  private static void doTest(Map<String, String> graph, String... expectedPaths) {
+    doTest(graph, 10, expectedPaths);
+  }
+
+  private static void doTest(Map<String, String> graph, final int k, String... expectedPaths) {
+    doTest(graph, "s", "t", k, expectedPaths);
+  }
+
+  private static void doTest(Map<String, String> graph, final String start, final String finish, final int k, String... expectedPaths) {
+    final Graph<String> generator = initGraph(graph);
+    final KShortestPathsFinder<String> finder = new KShortestPathsFinder<String>(generator, start, finish, new EmptyProgressIndicator());
+    final List<List<String>> paths = finder.findShortestPaths(k);
+    List<String> pathStrings = new ArrayList<String>();
+    Set<Integer> sizes = new HashSet<Integer>();
+    for (List<String> path : paths) {
+      pathStrings.add(StringUtil.join(path, ""));
+      sizes.add(path.size());
+    }
+    if (sizes.size() != paths.size()) {
+      UsefulTestCase.assertSameElements(pathStrings, expectedPaths);
+    }
+    else {
+      UsefulTestCase.assertOrderedEquals(pathStrings, expectedPaths);
+    }
+  }
+}
diff --git a/platform/platform-impl/testSrc/com/intellij/util/graph/SearchCyclesTest.java b/platform/platform-impl/testSrc/com/intellij/util/graph/SearchCyclesTest.java
new file mode 100644 (file)
index 0000000..2fce8b6
--- /dev/null
@@ -0,0 +1,96 @@
+/*
+ * Copyright 2000-2009 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.intellij.util.graph;
+
+import com.intellij.util.graph.impl.CycleFinder;
+import com.intellij.openapi.util.text.StringUtil;
+import com.intellij.testFramework.UsefulTestCase;
+
+import java.util.*;
+
+/**
+ * User: anna
+ * Date: Feb 13, 2005
+ */
+public class SearchCyclesTest extends GraphTestCase {
+  public void test1() throws Exception{
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "bd");
+    graph.put("b", "d");
+    graph.put("c", "a");
+    graph.put("d", "ac");
+
+    doTest(graph, "a", "da", "bdca");
+  }
+
+  public void test2() throws Exception{
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "b");
+    graph.put("b", "d");
+    graph.put("c", "a");
+    graph.put("d", "ce");
+    graph.put("e", "d");
+
+    doTest(graph, "a", "bdca");
+  }
+
+  public void test3() throws Exception{
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "bd");
+    graph.put("b", "d");
+    graph.put("d", "a");
+
+    doTest(graph, "a", "da");
+  }
+
+  public void test4() throws Exception {
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "b");
+    graph.put("b", "d");
+    graph.put("c", "a");
+    graph.put("d", "ef");
+    graph.put("e", "c");
+    graph.put("f", "e");
+
+    doTest(graph, "a", "bdeca");
+  }
+
+  public void test5() throws Exception{
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "be");
+    graph.put("b", "d");
+    graph.put("c", "a");
+    graph.put("d", "ef");
+    graph.put("e", "c");
+    graph.put("f", "e");
+    doTest(graph, "a", "bdeca", "eca");
+  }
+
+  private static void doTest(HashMap<String, String> graph, final String node, String... expected) {
+    Graph<String> stringGraph = initGraph(graph);
+    final Set<List<String>> nodeCycles = new CycleFinder<String>(stringGraph).getNodeCycles(node);
+    checkResult(expected, nodeCycles);
+  }
+
+  private static void checkResult(String[] expected, Set<List<String>> cycles) {
+    Set<String> cycleStrings = new HashSet<String>();
+    for (List<String> cycle : cycles) {
+      cycleStrings.add(StringUtil.join(cycle, ""));
+    }
+    UsefulTestCase.assertSameElements(cycleStrings, expected);
+  }
+}
diff --git a/platform/platform-impl/testSrc/com/intellij/util/graph/ShortestPathTest.java b/platform/platform-impl/testSrc/com/intellij/util/graph/ShortestPathTest.java
new file mode 100644 (file)
index 0000000..d5db1b8
--- /dev/null
@@ -0,0 +1,96 @@
+/*
+ * Copyright 2000-2009 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.intellij.util.graph;
+
+import com.intellij.openapi.util.text.StringUtil;
+import com.intellij.util.graph.impl.ShortestPathFinder;
+import org.jetbrains.annotations.Nullable;
+
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * User: anna
+ * Date: Feb 11, 2005
+ */
+public class ShortestPathTest extends GraphTestCase {
+  public void testEmptyPath() {
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "");
+    graph.put("b", "");
+    doTest(graph, "a", "a", "a");
+  }
+
+  public void testNoPath() {
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "c");
+    graph.put("b", "a");
+    graph.put("c", "a");
+    assertNull(getShortestPath(graph, "a", "b"));
+  }
+
+  public void test1() {
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "");
+    graph.put("b", "ac");
+    graph.put("c", "ab");
+    graph.put("d", "a");
+    doTest(graph, "b", "a", "ba");
+  }
+
+  public void test2() {
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "cd");
+    graph.put("b", "a");
+    graph.put("c", "d");
+    graph.put("d", "ab");
+    doTest(graph, "c", "b", "cdb");
+  }
+
+  public void test3() {
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "bd");
+    graph.put("b", "d");
+    graph.put("c", "a");
+    graph.put("d", "ac");
+    doTest(graph, "b", "c", "bdc");
+  }
+
+  public void test4() {
+    final HashMap<String, String> graph = new HashMap<String, String>();
+    graph.put("a", "be");
+    graph.put("b", "d");
+    graph.put("c", "a");
+    graph.put("d", "ef");
+    graph.put("e", "c");
+    graph.put("f", "e");
+    doTest(graph, "b", "c", "bdec");
+  }
+
+  private static void doTest(HashMap<String, String> graph, final String from, final String to, final String expectedPath) {
+    final List<String> shortestPath = getShortestPath(graph, from, to);
+    assertNotNull(shortestPath);
+    assertEquals(expectedPath, StringUtil.join(shortestPath, ""));
+  }
+
+  @Nullable
+  private static List<String> getShortestPath(Map<String, String> graph, final String from, final String to) {
+    Graph<String> graphGenerator = initGraph(graph);
+    return new ShortestPathFinder<String>(graphGenerator).findPath(from, to);
+  }
+}
index e86bcebba2cfff47ed8849459bceac8eabb5ef46..a3db039882deb40d286e100e6028410a180f244d 100644 (file)
@@ -96,6 +96,9 @@
   <applicationService serviceInterface="com.intellij.internal.psiView.PsiViewerSettings"
                   serviceImplementation="com.intellij.internal.psiView.PsiViewerSettings"/>
 
+  <applicationService serviceInterface="com.intellij.util.graph.GraphAlgorithms"
+                      serviceImplementation="com.intellij.util.graph.impl.GraphAlgorithmsImpl"/>
+
   <applicationService serviceInterface="com.intellij.openapi.keymap.impl.DefaultKeymap"
                       serviceImplementation="com.intellij.openapi.keymap.impl.DefaultKeymap"/>