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