User:Margusmartsepp/Contributions/Java/Utils.java: Difference between revisions
No edit summary |
No edit summary |
||
(2 intermediate revisions by the same user not shown) | |||
Line 45: | Line 45: | ||
} |
} |
||
/** |
/** <p> |
||
⚫ | |||
* <b>Topological sort</b> solves a problem of - finding a linear ordering |
* <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>, |
* of the vertices of <i>V</i> such that for each edge <i>(i, j) ∈ E</i>, |
||
Line 56: | Line 55: | ||
* href="http://en.wikipedia.org/wiki/Topological_sort#Algorithms" > Kahn's |
* href="http://en.wikipedia.org/wiki/Topological_sort#Algorithms" > Kahn's |
||
* pseudo code</a> and traverses over vertices as they are returned by input |
* pseudo code</a> and traverses over vertices as they are returned by input |
||
* map. Leaf nodes can have null or empty values. |
* 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> |
* </p> |
||
* |
* |
||
* <pre> |
* <pre> |
||
* // |
* // For input with elements: |
||
* { F1=[F2, F3, F4], F10=[F7, F4], F11=[F4], F2=[F3, F8, F4], F3=[F6], |
* { 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]} |
* F4=null, F5=[F6, F4], F6=[F7, F8, F4], F7=[F4], F8=[F4], F9=[F4]} |
||
* |
* |
||
* // Output based on input type: |
* // Output based on input map type: |
||
* HashMap: [F4, F11, F8, F9, F7, F10, F6, F5, F3, F2, F1] |
* HashMap: [F4, F11, F8, F9, F7, F10, F6, F5, F3, F2, F1] |
||
* TreeMap: [F4, F11, F7, F8, F9, F10, F6, F3, F5, F2, F1] |
* TreeMap: [F4, F11, F7, F8, F9, F10, F6, F3, F5, F2, F1] |
||
Line 74: | Line 75: | ||
* {@link java.util.HashMap HashMap} elements. |
* {@link java.util.HashMap HashMap} elements. |
||
* |
* |
||
* @return Linear ordering of input nodes. |
* @return Linear ordering of input nodes. |
||
* @throws Exception |
|||
* |
* Thrown when cyclic dependency is detected, error message also |
||
* then empty ArrayList will be returned. |
|||
* contains elements in cycle. |
|||
* |
* |
||
*/ |
*/ |
||
public <T> ArrayList<T> tSort(Map<T, ArrayList<T>> g) |
public static <T> ArrayList<T> tSort(java.util.Map<T, ArrayList<T>> g) |
||
throws Exception |
|||
⚫ | |||
/** |
|||
ArrayList<T> L = /* Answer */ |
|||
* @param L |
|||
⚫ | |||
* Answer. |
|||
⚫ | |||
* @param S |
|||
⚫ | |||
* Not visited leaf vertices. |
|||
java.util.Queue<T> S = /* ! Visited leaf nodes */ |
|||
* @param V |
|||
⚫ | |||
* Visited vertices. |
|||
* @param P |
|||
* Defined vertices. |
|||
* @param n |
|||
⚫ | |||
*/ |
|||
{ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
T n; |
|||
// Find leaf nodes. |
|||
for (T t : P) |
|||
if (g.get(t) == null || g.get(t).isEmpty()) |
|||
S.add(t); |
|||
// Visit all leaf nodes. Build result from vertices, that are visited |
|||
// for the first time. Add vertices to not visited leaf vertices S, if |
|||
while (!S.isEmpty()) { |
|||
⚫ | |||
// First time seeing this leaf node? |
|||
while (!S.isEmpty()) { |
|||
if (V.add(n = S.poll())) |
|||
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. |
|||
// If any vertex contains only visited vertices and |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
// Throw exception. |
|||
⚫ | |||
StringBuilder sb = new StringBuilder( |
|||
S.add(t); |
|||
"\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) |
|||
// Return empty ArrayList if input is not valid DAG. |
|||
if (g.get(t) != null || !g.get(t).isEmpty()) { |
|||
⚫ | |||
(tmp = g.get(t)).remove(t); |
|||
⚫ | |||
for (T m : tmp) |
|||
⚫ | |||
if (!P.contains(m)) |
|||
⚫ | |||
} |
|||
} |
} |
||
Latest revision as of 18:48, 11 November 2010
<lang java> import java.util.ArrayList; import java.util.Collections;
public class Utils { private static <T> void swap(ArrayList<T> data, int i, int j) { T t = data.get(i); data.set(i, data.get(j)); data.set(j, t); }
public static <T extends Comparable<? super T>> boolean nextPerm(ArrayList<T> data) { // find the swaps int c = -1, d = data.size(); for (int i = d - 2; i >= 0; i--) if (data.get(i).compareTo(data.get(i + 1)) < 0) { c = i; break; }
if (c < 0) return false;
int s = c + 1; for (int j = c + 2; j < d; j++) if (data.get(j).compareTo(data.get(s)) < 0 && // data.get(j).compareTo(data.get(c)) > 0) s = j;
// do the swaps swap(data, c, s); while (--d > ++c) swap(data, c, d);
return true; }
public static <T extends Comparable<? super T>> ArrayList<ArrayList<T>> Permutations(ArrayList<T> d) { ArrayList<ArrayList<T>> result = new ArrayList<ArrayList<T>>(); Collections.sort(d); do { result.add(new ArrayList<T>(d)); } while (nextPerm(d)); return result; }
/**
* Topological sort solves a problem of - finding a linear ordering * of the vertices of V such that for each edge (i, j) ∈ E, * vertex i is to the left of vertex j. (Skiena 2008, p. 481) *
*
*
* 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. 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. *
*
*
* // For input with elements: * { 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] *
* * @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. * @throws Exception * Thrown when cyclic dependency is detected, error message also * contains elements in cycle. * */ public static <T> ArrayList<T> tSort(java.util.Map<T, ArrayList<T>> g) throws Exception /** * @param L * Answer. * @param S * Not visited leaf vertices. * @param V * Visited vertices. * @param P * Defined vertices. * @param n * Current element. */ { 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. for (T t : P) if (g.get(t) == null || g.get(t).isEmpty()) S.add(t);
// Visit all leaf nodes. Build result from vertices, that are visited // for the first time. Add vertices to not visited leaf vertices S, if // it contains current element n an all of it's values are visited. while (!S.isEmpty()) { if (V.add(n = S.poll())) L.add(n); for (T t : g.keySet()) if (g.get(t) != null && !g.get(t).isEmpty() && !V.contains(t) && V.containsAll(g.get(t))) S.add(t); }
// Return result. if (L.containsAll(P)) return L;
// Throw exception. StringBuilder sb = new StringBuilder( "\nInvalid DAG: a cyclic dependency detected :\n"); for (T t : P) if (!L.contains(t)) 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()) { (tmp = g.get(t)).remove(t); for (T m : tmp) if (!P.contains(m)) g.put(m, new ArrayList<T>(0)); } }
/** * Creates a new {@code ArrayList} instance, containing input data. * * @param data * List of mutable input elements. * @return New {@link ArrayList} with input elements. */ public static <T> ArrayList<T> aList(T... data) { if (data == null) return new ArrayList<T>(0); int capacity = 8 + data.length + (data.length >> 3); ArrayList<T> list = new ArrayList<T>(capacity); Collections.addAll(list, data); return list; }
/** * Creates a new {@code ArrayList} instance, containing integer sequence * between form and to. Sequence can be negative. * * @param from * Integer with what sequence starts. * @param to * Integer with what sequence ends. * @return List of mutable integer sequence. {@code if (from == to)}, then * empty ArrayList is returned. */ public static ArrayList<Integer> mRange(int from, int to) { if (from == to) return new ArrayList<Integer>(0); if (from < to) { ArrayList<Integer> result = new ArrayList<Integer>(// Math.abs(from - to) + 1); for (int i = from; i <= to; i++) result.add(i); return result; } ArrayList<Integer> result = new ArrayList<Integer>( Math.abs(from - to) + 1); for (int i = from; i >= to; i--) result.add(i); return result; } } </lang>