View Javadoc
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      private Map<String, Vertex> vertexMap = new HashMap<String, Vertex>();
46  
47      /**
48       * Conatin list of all vertices
49       */
50      private List<Vertex> vertexList = new ArrayList<Vertex>();
51  
52      // ------------------------------------------------------------
53      // Constructors
54      // ------------------------------------------------------------
55  
56      /**
57       *
58       */
59      public DAG()
60      {
61          super();
62      }
63  
64      // ------------------------------------------------------------
65      // Accessors
66      // ------------------------------------------------------------
67  
68      /**
69       * @return
70       */
71      public List<Vertex> getVertices()
72      {
73          return vertexList;
74      }
75  
76      /**
77       * @deprecated instead use {@link #getVertices()}
78       */
79      @Deprecated
80      public List<Vertex> getVerticies()
81      {
82          return getVertices();
83      }
84  
85      public Set<String> getLabels()
86      {
87          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         Vertex retValue = null;
104 
105         // check if vertex is already in DAG
106         if ( vertexMap.containsKey( label ) )
107         {
108             retValue = vertexMap.get( label );
109         }
110         else
111         {
112             retValue = new Vertex( label );
113 
114             vertexMap.put( label, retValue );
115 
116             vertexList.add( retValue );
117         }
118 
119         return retValue;
120     }
121 
122     public void addEdge( final String from, final String to )
123         throws CycleDetectedException
124     {
125         final Vertex v1 = addVertex( from );
126 
127         final Vertex v2 = addVertex( to );
128 
129         addEdge( v1, v2 );
130     }
131 
132     public void addEdge( final Vertex from, final Vertex to )
133         throws CycleDetectedException
134     {
135 
136         from.addEdgeTo( to );
137 
138         to.addEdgeFrom( from );
139 
140         final List<String> cycle = CycleDetector.introducesCycle( to );
141 
142         if ( cycle != null )
143         {
144             // remove edge which introduced cycle
145 
146             removeEdge( from, to );
147 
148             final String msg = "Edge between '" + from + "' and '" + to + "' introduces to cycle in the graph";
149 
150             throw new CycleDetectedException( msg, cycle );
151         }
152     }
153 
154     public void removeEdge( final String from, final String to )
155     {
156         final Vertex v1 = addVertex( from );
157 
158         final Vertex v2 = addVertex( to );
159 
160         removeEdge( v1, v2 );
161     }
162 
163     public void removeEdge( final Vertex from, final Vertex to )
164     {
165         from.removeEdgeTo( to );
166 
167         to.removeEdgeFrom( from );
168     }
169 
170     public Vertex getVertex( final String label )
171     {
172         final Vertex retValue = (Vertex) vertexMap.get( label );
173 
174         return retValue;
175     }
176 
177     public boolean hasEdge( final String label1, final String label2 )
178     {
179         final Vertex v1 = getVertex( label1 );
180 
181         final Vertex v2 = getVertex( label2 );
182 
183         final boolean retValue = v1.getChildren().contains( v2 );
184 
185         return retValue;
186 
187     }
188 
189     /**
190      * @param label
191      * @return
192      */
193     public List<String> getChildLabels( final String label )
194     {
195         final Vertex vertex = getVertex( label );
196 
197         return vertex.getChildLabels();
198     }
199 
200     /**
201      * @param label
202      * @return
203      */
204     public List<String> getParentLabels( final String label )
205     {
206         final Vertex vertex = getVertex( label );
207 
208         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         final Object retValue = super.clone();
219 
220         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         final Vertex vertex = getVertex( label );
231 
232         final boolean retValue = vertex.isConnected();
233 
234         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         final Vertex vertex = getVertex( label );
248 
249         final List<String> retValue;
250 
251         // optimization.
252         if ( vertex.isLeaf() )
253         {
254             retValue = new ArrayList<String>( 1 );
255 
256             retValue.add( label );
257         }
258         else
259         {
260             retValue = TopologicalSorter.sort( vertex );
261         }
262 
263         return retValue;
264     }
265 
266 }