Coverage Report - org.codehaus.plexus.util.dag.DAG
 
Classes in this File Line Coverage Branch Coverage Complexity
DAG
70%
38/54
83%
5/6
1.25
 
 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.io.Serializable;
 20  
 import java.util.ArrayList;
 21  
 import java.util.HashMap;
 22  
 import java.util.List;
 23  
 import java.util.Map;
 24  
 import java.util.Set;
 25  
 
 26  
 /**
 27  
  * DAG = Directed Acyclic Graph
 28  
  *
 29  
  * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
 30  
  * @version $Id$
 31  
  * @todo this class should be renamed from DAG to Dag
 32  
  */
 33  
 public class DAG
 34  
     implements Cloneable, Serializable
 35  
 {
 36  
     // ------------------------------------------------------------
 37  
     // Fields
 38  
     // ------------------------------------------------------------
 39  
     /**
 40  
      * Nodes will be kept in two data structures at the same time for faster processing
 41  
      */
 42  
     /**
 43  
      * Maps vertex's label to vertex
 44  
      */
 45  11
     private Map<String, Vertex> vertexMap = new HashMap<String, Vertex>();
 46  
 
 47  
     /**
 48  
      * Conatin list of all vertices
 49  
      */
 50  11
     private List<Vertex> vertexList = new ArrayList<Vertex>();
 51  
 
 52  
     // ------------------------------------------------------------
 53  
     // Constructors
 54  
     // ------------------------------------------------------------
 55  
 
 56  
     /**
 57  
      *
 58  
      */
 59  
     public DAG()
 60  
     {
 61  11
         super();
 62  11
     }
 63  
 
 64  
     // ------------------------------------------------------------
 65  
     // Accessors
 66  
     // ------------------------------------------------------------
 67  
 
 68  
     /**
 69  
      * @return
 70  
      */
 71  
     public List<Vertex> getVertices()
 72  
     {
 73  8
         return vertexList;
 74  
     }
 75  
 
 76  
     /**
 77  
      * @deprecated instead use {@link #getVertices()}
 78  
      */
 79  
     @Deprecated
 80  
     public List<Vertex> getVerticies()
 81  
     {
 82  0
         return getVertices();
 83  
     }
 84  
 
 85  
     public Set<String> getLabels()
 86  
     {
 87  1
         return vertexMap.keySet();
 88  
     }
 89  
 
 90  
     // ------------------------------------------------------------
 91  
     // Implementation
 92  
     // ------------------------------------------------------------
 93  
 
 94  
     /**
 95  
      * Adds vertex to DAG. If vertex of given label already exist in DAG no vertex is added
 96  
      *
 97  
      * @param label The label of the Vertex
 98  
      * @return New vertex if vertex of given label was not present in the DAG or existing vertex if vertex of given
 99  
      *         label was already added to DAG
 100  
      */
 101  
     public Vertex addVertex( final String label )
 102  
     {
 103  126
         Vertex retValue = null;
 104  
 
 105  
         // check if vertex is already in DAG
 106  126
         if ( vertexMap.containsKey( label ) )
 107  
         {
 108  74
             retValue = vertexMap.get( label );
 109  
         }
 110  
         else
 111  
         {
 112  52
             retValue = new Vertex( label );
 113  
 
 114  52
             vertexMap.put( label, retValue );
 115  
 
 116  52
             vertexList.add( retValue );
 117  
         }
 118  
 
 119  126
         return retValue;
 120  
     }
 121  
 
 122  
     public void addEdge( final String from, final String to )
 123  
         throws CycleDetectedException
 124  
     {
 125  53
         final Vertex v1 = addVertex( from );
 126  
 
 127  53
         final Vertex v2 = addVertex( to );
 128  
 
 129  53
         addEdge( v1, v2 );
 130  50
     }
 131  
 
 132  
     public void addEdge( final Vertex from, final Vertex to )
 133  
         throws CycleDetectedException
 134  
     {
 135  
 
 136  53
         from.addEdgeTo( to );
 137  
 
 138  53
         to.addEdgeFrom( from );
 139  
 
 140  53
         final List<String> cycle = CycleDetector.introducesCycle( to );
 141  
 
 142  53
         if ( cycle != null )
 143  
         {
 144  
             // remove edge which introduced cycle
 145  
 
 146  3
             removeEdge( from, to );
 147  
 
 148  3
             final String msg = "Edge between '" + from + "' and '" + to + "' introduces to cycle in the graph";
 149  
 
 150  3
             throw new CycleDetectedException( msg, cycle );
 151  
         }
 152  50
     }
 153  
 
 154  
     public void removeEdge( final String from, final String to )
 155  
     {
 156  0
         final Vertex v1 = addVertex( from );
 157  
 
 158  0
         final Vertex v2 = addVertex( to );
 159  
 
 160  0
         removeEdge( v1, v2 );
 161  0
     }
 162  
 
 163  
     public void removeEdge( final Vertex from, final Vertex to )
 164  
     {
 165  3
         from.removeEdgeTo( to );
 166  
 
 167  3
         to.removeEdgeFrom( from );
 168  3
     }
 169  
 
 170  
     public Vertex getVertex( final String label )
 171  
     {
 172  41
         final Vertex retValue = (Vertex) vertexMap.get( label );
 173  
 
 174  41
         return retValue;
 175  
     }
 176  
 
 177  
     public boolean hasEdge( final String label1, final String label2 )
 178  
     {
 179  17
         final Vertex v1 = getVertex( label1 );
 180  
 
 181  17
         final Vertex v2 = getVertex( label2 );
 182  
 
 183  17
         final boolean retValue = v1.getChildren().contains( v2 );
 184  
 
 185  17
         return retValue;
 186  
 
 187  
     }
 188  
 
 189  
     /**
 190  
      * @param label
 191  
      * @return
 192  
      */
 193  
     public List<String> getChildLabels( final String label )
 194  
     {
 195  0
         final Vertex vertex = getVertex( label );
 196  
 
 197  0
         return vertex.getChildLabels();
 198  
     }
 199  
 
 200  
     /**
 201  
      * @param label
 202  
      * @return
 203  
      */
 204  
     public List<String> getParentLabels( final String label )
 205  
     {
 206  0
         final Vertex vertex = getVertex( label );
 207  
 
 208  0
         return vertex.getParentLabels();
 209  
     }
 210  
 
 211  
     /**
 212  
      * @see java.lang.Object#clone()
 213  
      */
 214  
     public Object clone()
 215  
         throws CloneNotSupportedException
 216  
     {
 217  
         // this is what's failing..
 218  0
         final Object retValue = super.clone();
 219  
 
 220  0
         return retValue;
 221  
     }
 222  
 
 223  
     /**
 224  
      * Indicates if there is at least one edge leading to or from vertex of given label
 225  
      *
 226  
      * @return <code>true</true> if this vertex is connected with other vertex,<code>false</code> otherwise
 227  
      */
 228  
     public boolean isConnected( final String label )
 229  
     {
 230  0
         final Vertex vertex = getVertex( label );
 231  
 
 232  0
         final boolean retValue = vertex.isConnected();
 233  
 
 234  0
         return retValue;
 235  
 
 236  
     }
 237  
 
 238  
     /**
 239  
      * Return the list of labels of successor in order decided by topological sort
 240  
      *
 241  
      * @param label The label of the vertex whose predecessors are searched
 242  
      * @return The list of labels. Returned list contains also the label passed as parameter to this method. This label
 243  
      *         should always be the last item in the list.
 244  
      */
 245  
     public List<String> getSuccessorLabels( final String label )
 246  
     {
 247  1
         final Vertex vertex = getVertex( label );
 248  
 
 249  
         final List<String> retValue;
 250  
 
 251  
         // optimization.
 252  1
         if ( vertex.isLeaf() )
 253  
         {
 254  0
             retValue = new ArrayList<String>( 1 );
 255  
 
 256  0
             retValue.add( label );
 257  
         }
 258  
         else
 259  
         {
 260  1
             retValue = TopologicalSorter.sort( vertex );
 261  
         }
 262  
 
 263  1
         return retValue;
 264  
     }
 265  
 
 266  
 }