TopologicalSortException


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  package org.openide.util;
20  
21  import java.util.*;
22  
23  
24  /** Exception that signals that a topological sort failed due to
25  * unsortable nature of the graph and that provides support for
26  * reporting and recovering from that state.
27  *
28  * @author Jaroslav Tulach
29  * @since 3.30
30  * @see Utilities#topologicalSort
31  */
32  public final class TopologicalSortException extends Exception   {
33      /** all vertexes */
34      private Collection vertexes;
35  
36      /** map with edges */
37      private Map edges;
38  
39      /** result if called twice */
40      private Set[] result;
41  
42      /** counter to number the vertexes */
43      private int counter;
44  
45      /** vertexes sorted by increasing value of y */
46      private Stack<Vertex> dualGraph = new Stack<Vertex>();
47  
48      TopologicalSortException(Collection vertexes, Map edges) {
49          this.vertexes = vertexes;
50          this.edges = edges;
51      }
52  
53      /** Because the full sort was not possible, this methods
54       * returns the best possible substitute for it that is available.
55       *
56       * @return list of partially sorted objects, the list can be freely modified
57       */
58      public final List partialSort() {
59          Set[] all = topologicalSets();
60  
61          ArrayList<Object  > res = new ArrayList<Object  >(vertexes.size());
62  
63          for (int i = 0; i < all.length; i++) {
64              for (Object   e : all[i]) {
65                  res.add(e);
66              }
67          }
68  
69          return res;
70      }
71  
72      /** The topological sort could not be finished as there
73       * are some objects that are mutually refering to each other.
74       * This methods finds such objects and partition them into
75       * separate sets. All objects in one set (transitively) refer to
76       * each other and thus prevent the sort from succeding. As
77       * there can be more of such "unsortable sets" an array
78       * of them is returned.
79       *
80       * @return array of sets that contain some of the original objects, result
81       *   shall not be modified
82       */
83      public final Set[] unsortableSets() {
84          Set[] all = topologicalSets();
85  
86          ArrayList<Set> unsort = new ArrayList<Set>();
87  
88          for (int i = 0; i < all.length; i++) {
89              if ((all[i].size() > 1) || !(all[i] instanceof HashSet)) {
90                  unsort.add(all[i]);
91              }
92          }
93  
94          return unsort.toArray(new Set[0]);
95      }
96  
97      /** Adds description why the graph cannot be sorted.
98       * @param w writer to write to
99       */
100     public final void printStackTrace(java.io.PrintWriter   w) {
101         w.print("TopologicalSortException - Collection: "); // NOI18N
102         w.print(vertexes);
103         w.print(" with edges "); // NOI18N
104         w.print(edges);
105         w.println(" cannot be sorted"); // NOI18N
106 
107         Set[] bad = unsortableSets();
108 
109         for (int i = 0; i < bad.length; i++) {
110             w.print(" Conflict #"); // NOI18N
111             w.print(i);
112             w.print(": "); // NOI18N
113             w.println(bad[i]);
114         }
115 
116         super.printStackTrace(w);
117     }
118 
119     /** Adds description why the graph cannot be sorted.
120      * @param s stream to write to
121      */
122     public final void printStackTrace(java.io.PrintStream   s) {
123         java.io.PrintWriter   w = new java.io.PrintWriter  (s);
124         this.printStackTrace(w);
125         w.flush();
126     }
127 
128     /** As the full topological sort cannot be finished due to cycles
129      * in the graph this methods performs a partition topological sort.
130      * <P>
131      * First of all it identifies unsortable parts of the graph and
132      * partitions the graph into sets of original objects. Each set contains
133      * objects that are mutually unsortable (there is a cycle between them).
134      * Then the topological sort is performed again on those sets, this
135      * sort succeeds because the graph of sets is DAG (all problematic edges
136      * were only between objects now grouped inside the sets) and the
137      * result forms the return value of this method.
138      *
139      * @return array of sorted sets that contain the original objects, each
140      *   object from the original collection is exactly in one set, result
141      *   shall not be modified
142      */
143     public final Set[] topologicalSets() {
144         if (result != null) {
145             return result;
146         }
147 
148         HashMap<Object  ,Vertex> vertexInfo = new HashMap<Object  ,Vertex>();
149 
150         // computes value X and Y for each vertex
151         counter = 0;
152 
153         Iterator it = vertexes.iterator();
154 
155         while (it.hasNext()) {
156             constructDualGraph(counter, it.next(), vertexInfo);
157         }
158 
159         // now connect vertexes that cannot be sorted into own
160         // sets
161         // map from the original objects to 
162         Map<Object  ,Set> objectsToSets = new HashMap<Object  ,Set>();
163 
164         ArrayList<Set> sets = new ArrayList<Set>();
165 
166         while (!dualGraph.isEmpty()) {
167             Vertex v = dualGraph.pop();
168 
169             if (!v.visited) {
170                 Set<Object  > set = new HashSet<Object  >();
171                 visitDualGraph(v, set);
172 
173                 if ((set.size() == 1) && v.edgesFrom.contains(v)) {
174                     // mark if there is a self reference and the
175                     // set is only one element big, it means that there
176                     // is a self cycle
177                     //
178                     // do not use HashSet but Collections.singleton
179                     // to recognize such cycles
180                     set = Collections.singleton(v.object);
181                 }
182 
183                 sets.add(set);
184 
185                 // fill the objectsToSets mapping
186                 it = set.iterator();
187 
188                 while (it.hasNext()) {
189                     objectsToSets.put(it.next(), set);
190                 }
191             }
192         }
193 
194         // now topologically sort the sets
195         // 1. prepare the map
196         HashMap<Set,Collection<Set>> edgesBetweenSets = new HashMap<Set,Collection<Set>>();
197         it = edges.entrySet().iterator();
198 
199         while (it.hasNext()) {
200             Map.Entry entry = (Map.Entry) it.next();
201             Collection leadsTo = (Collection) entry.getValue();
202 
203             if ((leadsTo == null) || leadsTo.isEmpty()) {
204                 continue;
205             }
206 
207             Set from = objectsToSets.get(entry.getKey());
208 
209             Collection<Set> setsTo = edgesBetweenSets.get(from);
210 
211             if (setsTo == null) {
212                 setsTo = new ArrayList<Set>();
213                 edgesBetweenSets.put(from, setsTo);
214             }
215 
216             Iterator convert = leadsTo.iterator();
217 
218             while (convert.hasNext()) {
219                 Set to = objectsToSets.get(convert.next());
220 
221                 if (from != to) {
222                     // avoid self cycles
223                     setsTo.add(to);
224                 }
225             }
226         }
227 
228         // 2. do the sort
229         try {
230             List<Set> listResult = Utilities.topologicalSort(sets, edgesBetweenSets);
231             result = listResult.toArray(new Set[0]);
232         } catch (TopologicalSortException ex) {
233             throw new IllegalStateException  ("Cannot happen"); // NOI18N
234         }
235 
236         return result;
237     }
238 
239     /** Traverses the tree
240      * @param counter current value
241      * @param vertex current vertex
242      * @param vertexInfo the info
243      */
244     private Vertex constructDualGraph(int counter, Object   vertex, HashMap<Object  ,Vertex> vertexInfo) {
245         Vertex info = vertexInfo.get(vertex);
246 
247         if (info == null) {
248             info = new Vertex(vertex, counter++);
249             vertexInfo.put(vertex, info);
250         } else {
251             // already (being) processed
252             return info;
253         }
254 
255         // process children
256         Collection c = (Collection) edges.get(vertex);
257 
258         if (c != null) {
259             Iterator it = c.iterator();
260 
261             while (it.hasNext()) {
262                 Vertex next = constructDualGraph(counter, it.next(), vertexInfo);
263                 next.edgesFrom.add(info);
264             }
265         }
266 
267         // leaving the vertex
268         info.y = counter++;
269 
270         dualGraph.push(info);
271 
272         return info;
273     }
274 
275     /** Visit dual graph. Decreasing value of Y gives the order.
276      * Number
277      *
278      * @param vertex vertex to start from
279      * @param visited list of all objects that we've been to
280      */
281     private void visitDualGraph(Vertex vertex, Collection<Object  > visited) {
282         if (vertex.visited) {
283             return;
284         }
285 
286         visited.add(vertex.object);
287         vertex.visited = true;
288 
289         Iterator it = vertex.edges();
290 
291         while (it.hasNext()) {
292             Vertex v = (Vertex) it.next();
293             visitDualGraph(v, visited);
294         }
295     }
296 
297     /** Represents info about a vertex in the graph. Vertexes are
298      * comparable by the value of Y, but only after the value is set,
299      * so the sort has to be done latelly.
300      */
301     private static final class Vertex implements Comparable  <Vertex> {
302         /** the found object */
303         public Object   object;
304 
305         /** list of vertexes that point to this one */
306         public List<Vertex> edgesFrom = new ArrayList<Vertex>();
307 
308         /** the counter state when we entered the vertex */
309         public final int x;
310 
311         /** the counter when we exited the vertex */
312         public int y;
313 
314         /** already sorted, true if the edges has been sorted */
315         public boolean sorted;
316 
317         /** true if visited in dual graph */
318         public boolean visited;
319 
320         public Vertex(Object   obj, int x) {
321             this.x = x;
322             this.object = obj;
323         }
324 
325         /** Iterator over edges
326          * @return iterator of Vertex items
327          */
328         public Iterator edges() {
329             if (!sorted) {
330                 Collections.sort(edgesFrom);
331                 sorted = true;
332             }
333 
334             return edgesFrom.iterator();
335         }
336 
337         /** Comparing based on value of Y.
338          *
339          * @param   o the Object to be compared.
340          * @return  a negative integer, zero, or a positive integer as this object
341          *                 is less than, equal to, or greater than the specified object.
342          */
343         public int compareTo(Vertex o) {
344             return o.y - y;
345         }
346     }
347 }
348
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags