2 * Copyright 2000-2009 JetBrains s.r.o.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 package com
.intellij
.cyclicDependencies
;
19 import com
.intellij
.util
.graph
.Graph
;
27 public class CyclicGraphUtil
{
28 private CyclicGraphUtil() {
31 public static <Node
> Set
<List
<Node
>> getNodeCycles(final Graph
<Node
> graph
, final Node node
){
32 Set
<List
<Node
>> result
= new HashSet
<List
<Node
>>();
35 final Graph
<Node
> graphWithoutNode
= new Graph
<Node
>() {
36 public Collection
<Node
> getNodes() {
37 final Collection
<Node
> nodes
= graph
.getNodes();
42 public Iterator
<Node
> getIn(final Node n
) {
43 final HashSet
<Node
> nodes
= new HashSet
<Node
>();
44 final Iterator
<Node
> in
= graph
.getIn(n
);
49 return nodes
.iterator();
52 public Iterator
<Node
> getOut(final Node n
) {
53 final HashSet
<Node
> nodes
= new HashSet
<Node
>();
54 final Iterator
<Node
> out
= graph
.getOut(n
);
56 nodes
.add(out
.next());
59 return nodes
.iterator();
64 final HashSet
<Node
> inNodes
= new HashSet
<Node
>();
65 final Iterator
<Node
> in
= graph
.getIn(node
);
67 inNodes
.add(in
.next());
69 final HashSet
<Node
> outNodes
= new HashSet
<Node
>();
70 final Iterator
<Node
> out
= graph
.getOut(node
);
72 outNodes
.add(out
.next());
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
);
84 inNodes
.removeAll(retainNodes
);
85 outNodes
.removeAll(retainNodes
);
87 final ShortestPathUtil
<Node
> algorithm
= new ShortestPathUtil
<Node
>(graphWithoutNode
);
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
);