Coverage Report - org.codehaus.plexus.util.dag.CycleDetector
 
Classes in this File Line Coverage Branch Coverage Complexity
CycleDetector
75%
33/44
60%
12/20
3
 
 1  
 package org.codehaus.plexus.util.dag;
 2  
 
 3  
 /*
 4  
  * Copyright The Codehaus Foundation.
 5  
  *
 6  
  * Licensed under the Apache License, Version 2.0 (the "License");
 7  
  * you may not use this file except in compliance with the License.
 8  
  * You may obtain a copy of the License at
 9  
  *
 10  
  *     http://www.apache.org/licenses/LICENSE-2.0
 11  
  *
 12  
  * Unless required by applicable law or agreed to in writing, software
 13  
  * distributed under the License is distributed on an "AS IS" BASIS,
 14  
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 15  
  * See the License for the specific language governing permissions and
 16  
  * limitations under the License.
 17  
  */
 18  
 
 19  
 import java.util.Collections;
 20  
 import java.util.HashMap;
 21  
 import java.util.LinkedList;
 22  
 import java.util.List;
 23  
 import java.util.Map;
 24  
 
 25  
 /**
 26  
  * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
 27  
  * @version $Id$
 28  
  */
 29  0
 public class CycleDetector
 30  
 {
 31  
 
 32  1
     private final static Integer NOT_VISITED = 0;
 33  
 
 34  1
     private final static Integer VISITING = 1;
 35  
 
 36  1
     private final static Integer VISITED = 2;
 37  
 
 38  
     public static List<String> hasCycle( final DAG graph )
 39  
     {
 40  0
         final List<Vertex> vertices = graph.getVertices();
 41  
 
 42  0
         final Map<Vertex, Integer> vertexStateMap = new HashMap<Vertex, Integer>();
 43  
 
 44  0
         List<String> retValue = null;
 45  
 
 46  0
         for ( Vertex vertex : vertices )
 47  
         {
 48  0
             if ( isNotVisited( vertex, vertexStateMap ) )
 49  
             {
 50  0
                 retValue = introducesCycle( vertex, vertexStateMap );
 51  
 
 52  0
                 if ( retValue != null )
 53  
                 {
 54  0
                     break;
 55  
                 }
 56  
             }
 57  0
         }
 58  
 
 59  0
         return retValue;
 60  
     }
 61  
 
 62  
     /**
 63  
      * This method will be called when an edge leading to given vertex was added and we want to check if introduction of
 64  
      * this edge has not resulted in apparition of cycle in the graph
 65  
      *
 66  
      * @param vertex
 67  
      * @param vertexStateMap
 68  
      * @return
 69  
      */
 70  
     public static List<String> introducesCycle( final Vertex vertex, final Map<Vertex, Integer> vertexStateMap )
 71  
     {
 72  53
         final LinkedList<String> cycleStack = new LinkedList<String>();
 73  
 
 74  53
         final boolean hasCycle = dfsVisit( vertex, cycleStack, vertexStateMap );
 75  
 
 76  53
         if ( hasCycle )
 77  
         {
 78  
             // we have a situation like: [b, a, c, d, b, f, g, h].
 79  
             // Label of Vertex which introduced the cycle is at the first position in the list
 80  
             // We have to find second occurrence of this label and use its position in the list
 81  
             // for getting the sublist of vertex labels of cycle participants
 82  
             //
 83  
             // So in our case we are searching for [b, a, c, d, b]
 84  3
             final String label = cycleStack.getFirst();
 85  
 
 86  3
             final int pos = cycleStack.lastIndexOf( label );
 87  
 
 88  3
             final List<String> cycle = cycleStack.subList( 0, pos + 1 );
 89  
 
 90  3
             Collections.reverse( cycle );
 91  
 
 92  3
             return cycle;
 93  
         }
 94  
 
 95  50
         return null;
 96  
     }
 97  
 
 98  
     public static List<String> introducesCycle( final Vertex vertex )
 99  
     {
 100  53
         final Map<Vertex, Integer> vertexStateMap = new HashMap<Vertex, Integer>();
 101  
 
 102  53
         return introducesCycle( vertex, vertexStateMap );
 103  
     }
 104  
 
 105  
     /**
 106  
      * @param vertex
 107  
      * @param vertexStateMap
 108  
      * @return
 109  
      */
 110  
     private static boolean isNotVisited( final Vertex vertex, final Map<Vertex, Integer> vertexStateMap )
 111  
     {
 112  14
         final Integer state = vertexStateMap.get( vertex );
 113  
 
 114  14
         return ( state == null ) || NOT_VISITED.equals( state );
 115  
     }
 116  
 
 117  
     /**
 118  
      * @param vertex
 119  
      * @param vertexStateMap
 120  
      * @return
 121  
      */
 122  
     private static boolean isVisiting( final Vertex vertex, final Map<Vertex, Integer> vertexStateMap )
 123  
     {
 124  3
         final Integer state = vertexStateMap.get( vertex );
 125  
 
 126  3
         return VISITING.equals( state );
 127  
     }
 128  
 
 129  
     private static boolean dfsVisit( final Vertex vertex, final LinkedList<String> cycle,
 130  
                                      final Map<Vertex, Integer> vertexStateMap )
 131  
     {
 132  64
         cycle.addFirst( vertex.getLabel() );
 133  
 
 134  64
         vertexStateMap.put( vertex, VISITING );
 135  
 
 136  64
         for ( Vertex v : vertex.getChildren() )
 137  
         {
 138  14
             if ( isNotVisited( v, vertexStateMap ) )
 139  
             {
 140  11
                 final boolean hasCycle = dfsVisit( v, cycle, vertexStateMap );
 141  
 
 142  11
                 if ( hasCycle )
 143  
                 {
 144  7
                     return true;
 145  
                 }
 146  4
             }
 147  3
             else if ( isVisiting( v, vertexStateMap ) )
 148  
             {
 149  3
                 cycle.addFirst( v.getLabel() );
 150  
 
 151  3
                 return true;
 152  
             }
 153  4
         }
 154  54
         vertexStateMap.put( vertex, VISITED );
 155  
 
 156  54
         cycle.removeFirst();
 157  
 
 158  54
         return false;
 159  
     }
 160  
 
 161  
 }