Anonymous user
User:Margusmartsepp/Contributions/Java/Utils.java: Difference between revisions
User:Margusmartsepp/Contributions/Java/Utils.java (view source)
Revision as of 13:02, 11 November 2010
, 13 years agono edit summary
No edit summary |
No edit summary |
||
Line 50:
} while (nextPerm(d));
return result;
}
/**
* <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>,
* vertex <i>i</i> is to the left of vertex <i>j</i>. (Skiena 2008, p. 481)
* </p>
*
* <p>
* Method is derived from of <a
* 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.
* </p>
*
* <pre>
* // Input:
* { 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 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]
* </pre>
*
* @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.
*
* @return Linear ordering of input nodes. If input map contains a
* prerequisite that is undefined or cyclic dependency is detected,
* then empty ArrayList will be returned.
*
*/
public <T> ArrayList<T> tSort(Map<T, ArrayList<T>> g) {
T n; // Current element.
ArrayList<T> L = new ArrayList<T>(g.size()); // Answer.
HashSet<T> V = new HashSet<T>(); // Visited elements.
Queue<T> S = new LinkedBlockingDeque<T>(); // !Visited leaf nodes
// Find leaf nodes.
for (T t : g.keySet())
if (g.get(t) == null || g.get(t).isEmpty())
S.add(t);
// Visit all leaf nodes.
while (!S.isEmpty()) {
// First time seeing this leaf node?
if (V.add(n = S.poll()))
L.add(n);
// If any vertex contains only visited vertices and
// contained current element n, add it to leaf nodes.
for (T t : g.keySet())
if (g.get(t) != null && V.containsAll(g.get(t))
&& !V.contains(t))
S.add(t);
}
// Return empty ArrayList if input is not valid DAG.
if (!L.containsAll(g.keySet()))
return new ArrayList<T>(0);
return L;
}
}
| |||