Coverage Report - org.codehaus.plexus.util.dag.TopologicalSorter
 
Classes in this File Line Coverage Branch Coverage Complexity
TopologicalSorter
96%
24/25
91%
11/12
2
 
 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.HashMap;
 20  
 import java.util.LinkedList;
 21  
 import java.util.List;
 22  
 import java.util.Map;
 23  
 
 24  
 /**
 25  
  * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
 26  
  * @version $Id$
 27  
  */
 28  0
 public class TopologicalSorter
 29  
 {
 30  
 
 31  1
     private final static Integer NOT_VISITED = 0;
 32  
 
 33  1
     private final static Integer VISITING = 1;
 34  
 
 35  1
     private final static Integer VISITED = 2;
 36  
 
 37  
     /**
 38  
      * @param graph
 39  
      * @return List of String (vertex labels)
 40  
      */
 41  
 
 42  
     public static List<String> sort( final DAG graph )
 43  
     {
 44  4
         return dfs( graph );
 45  
     }
 46  
 
 47  
     public static List<String> sort( final Vertex vertex )
 48  
     {
 49  
         // we need to use addFirst method so we will use LinkedList explicitly
 50  1
         final List<String> retValue = new LinkedList<String>();
 51  
 
 52  1
         dfsVisit( vertex, new HashMap<Vertex, Integer>(), retValue );
 53  
 
 54  1
         return retValue;
 55  
     }
 56  
 
 57  
     private static List<String> dfs( final DAG graph )
 58  
     {
 59  
         // we need to use addFirst method so we will use LinkedList explicitly
 60  4
         final List<String> retValue = new LinkedList<String>();
 61  4
         final Map<Vertex, Integer> vertexStateMap = new HashMap<Vertex, Integer>();
 62  
 
 63  4
         for ( Vertex vertex : graph.getVertices() )
 64  
         {
 65  19
             if ( isNotVisited( vertex, vertexStateMap ) )
 66  
             {
 67  9
                 dfsVisit( vertex, vertexStateMap, retValue );
 68  
             }
 69  19
         }
 70  
 
 71  4
         return retValue;
 72  
     }
 73  
 
 74  
     /**
 75  
      * @param vertex
 76  
      * @param vertexStateMap
 77  
      * @return
 78  
      */
 79  
     private static boolean isNotVisited( final Vertex vertex, final Map<Vertex, Integer> vertexStateMap )
 80  
     {
 81  45
         final Integer state = vertexStateMap.get( vertex );
 82  
 
 83  45
         return ( state == null ) || NOT_VISITED.equals( state );
 84  
     }
 85  
 
 86  
     private static void dfsVisit( final Vertex vertex, final Map<Vertex, Integer> vertexStateMap,
 87  
                                   final List<String> list )
 88  
     {
 89  25
         vertexStateMap.put( vertex, VISITING );
 90  
 
 91  25
         for ( Vertex v : vertex.getChildren() )
 92  
         {
 93  26
             if ( isNotVisited( v, vertexStateMap ) )
 94  
             {
 95  15
                 dfsVisit( v, vertexStateMap, list );
 96  
             }
 97  26
         }
 98  
 
 99  25
         vertexStateMap.put( vertex, VISITED );
 100  
 
 101  25
         list.add( vertex.getLabel() );
 102  25
     }
 103  
 
 104  
 }