User:Margusmartsepp/Contributions/Java/Utils.java: Difference between revisions
Content added Content deleted
No edit summary |
No edit summary |
||
Line 50: | Line 50: | ||
} while (nextPerm(d)); |
} while (nextPerm(d)); |
||
return result; |
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; |
|||
} |
} |
||
} |
} |