Anonymous user
User:Margusmartsepp/Contributions/Java/Utils.java: Difference between revisions
User:Margusmartsepp/Contributions/Java/Utils.java (view source)
Revision as of 14:55, 11 November 2010
, 13 years agono edit summary
No edit summary |
No edit summary |
||
Line 56:
* 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. Every missing definition
* is considered as a leaf node.
* </p>
*
Line 79 ⟶ 80:
*
*/
public static <T> ArrayList<T> tSort(java.util.Map<T, ArrayList<T>> g)
/**
T n; // Current element.▼
* @param L
* Answer.
new ArrayList<T>(g.size());▼
* @param S
* Not visited leaf vertices.
* @param V
* Visited vertices.
new java.util.concurrent.LinkedBlockingDeque<T>();▼
* @param P
* Predefined vertices.
* @param n
*/
{
▲ java.util.ArrayList<T> L = new ArrayList<T>(g.size());
▲ java.util.Queue<T> S = new java.util.concurrent.LinkedBlockingDeque<T>();
java.util.HashSet<T> V = new java.util.HashSet<T>(), P = new java.util.HashSet<T>();
P.addAll(g.keySet());
T n;
// Find leaf nodes and missing leaf nodes.
for (T t : g.keySet())
if (g.get(t) == null || g.get(t).isEmpty())
S.add(t);
else
for (T m : g.get(t))
if (!P.contains(m))
S.add(t);
// Visit all leaf nodes.
| |||