Anonymous user
User:Margusmartsepp/Contributions/Java/Utils.java: Difference between revisions
User:Margusmartsepp/Contributions/Java/Utils.java (view source)
Revision as of 18:48, 11 November 2010
, 13 years agono edit summary
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
Line 45:
}
/** <p>
* <p>▼
* <b>Topological sort</b> solves a problem of - finding a linear ordering
* of the vertices of <i>V</i> such that for each edge <i>(i, j) ∈ E</i>,
Line 56 ⟶ 55:
* href="http://en.wikipedia.org/wiki/Topological_sort#Algorithms" > Kahn's
* pseudo code</a> and traverses over vertices as they are returned by input
* map. Leaf nodes can have null or empty values. This method assumes, that
* input is valid DAG, so if cyclic dependency is detected, error is thrown.
* tSortFix is a fix to remove self dependencies and add missing leaf nodes.
* </p>
*
* <pre>
* //
* { F1=[F2, F3, F4], F10=[F7, F4], F11=[F4], F2=[F3, F8, F4], F3=[F6],
* F4=null, F5=[F6, F4], F6=[F7, F8, F4], F7=[F4], F8=[F4], F9=[F4]}
*
* // Output based on input map type:
* HashMap: [F4, F11, F8, F9, F7, F10, F6, F5, F3, F2, F1]
* TreeMap: [F4, F11, F7, F8, F9, F10, F6, F3, F5, F2, F1]
Line 74 ⟶ 75:
* {@link java.util.HashMap HashMap} elements.
*
* @return Linear ordering of input nodes.
* @throws Exception
*
* contains elements in cycle.
*
*/
public static <T> ArrayList<T> tSort(java.util.Map<T, ArrayList<T>> g)
throws Exception
T n; // Current element.▼
/**
* @param L
new ArrayList<T>(g.size());▼
* Answer.
java.util.HashSet<T> V = /* ! Visited elements */▼
* @param S
new java.util.HashSet<T>();▼
* Not visited leaf vertices.
* @param V
new java.util.concurrent.LinkedBlockingDeque<T>();▼
* Visited vertices.
* @param P
* Defined vertices.
* @param n
*/
{
T n;
// for the first time. Add vertices to not visited leaf vertices S, if
L.add(n);
for (T t : g.keySet())
if (g.get(t) != null && !g.get(t).isEmpty() && !V.contains(t)
S.add(t);
}
// Return result.
▲ // contained current element n, add it to leaf nodes.
▲ for (T t : g.keySet())
▲ if (g.get(t) != null && V.containsAll(g.get(t))
// Throw exception.
&& !V.contains(t))▼
StringBuilder sb = new StringBuilder(
"\nInvalid DAG: a cyclic dependency detected :\n");
for (T t : P)
sb.append(t).append(" ");
throw new Exception(sb.append("\n").toString());
}
/**
* Method removes self dependencies and adds missing leaf nodes.
* @param g
* <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph"
* > Directed Acyclic Graph</a>, where vertices are stored as
* {@link java.util.HashMap HashMap} elements.
*/
public static <T> void tSortFix(java.util.Map<T, ArrayList<T>> g) {
java.util.ArrayList<T> tmp;
java.util.HashSet<T> P = new java.util.HashSet<T>();
P.addAll(g.keySet());
for (T t : P)
if (g.get(t) != null || !g.get(t).isEmpty()) {
▲ if (!L.containsAll(g.keySet()))
(tmp = g.get(t)).remove(t);
return new ArrayList<T>(0);▼
for (T m : tmp)
▲ return L;
if (!P.contains(m))
}
}
| |||