Directed specialized

1// edges {a, b, weight} of a connected undirected graph; returns the length of the shortest closed walk using every edge at least once
2static int chinesePostman(int n, int[][] edges) {
3    int inf = Integer.MAX_VALUE / 4, total = 0;
4    int[][] dist = new int[n][n];
5    for (int[] row : dist) Arrays.fill(row, inf);
6    for (int i = 0; i < n; i++) dist[i][i] = 0;
7    int[] degree = new int[n];
8    for (int[] e : edges) {
9        total += e[2];
10        degree[e[0]]++;
11        degree[e[1]]++;
12        dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);
13        dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);
14    }
15    for (int k = 0; k < n; k++)                                       // Floyd-Warshall: the cheapest way between any two vertices
16        for (int i = 0; i < n; i++)
17            for (int j = 0; j < n; j++)
18                if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];
19    List<Integer> odd = new ArrayList<>();
20    for (int v = 0; v < n; v++) if (degree[v] % 2 == 1) odd.add(v);
21    int m = odd.size();
22    int[] best = new int[1 << m];                                     // best[mask]: cheapest way to pair up the odd vertices in mask
23    Arrays.fill(best, inf);
24    best[0] = 0;
25    for (int mask = 0; mask < (1 << m); mask++) {
26        if (best[mask] >= inf) continue;
27        int i = 0;
28        while (i < m && (mask >> i & 1) == 1) i++;                    // pair the lowest unpaired odd vertex with some other one
29        if (i == m) continue;
30        for (int j = i + 1; j < m; j++)
31            if ((mask >> j & 1) == 0)
32                best[mask | 1 << i | 1 << j] = Math.min(best[mask | 1 << i | 1 << j], best[mask] + dist[odd.get(i)][odd.get(j)]);
33    }
34    return total + best[(1 << m) - 1];                                // every pairing duplicates a shortest path
35}

1static String deBruijn(int k, int n) {                                // a cyclic string in which every length-n word over k symbols appears once
2    int nodes = 1;
3    for (int i = 1; i < n; i++) nodes *= k;                           // a node is a word of length n - 1
4    int[] next = new int[nodes];                                      // next unused outgoing symbol of each node
5    Deque<int[]> stack = new ArrayDeque<>();
6    stack.push(new int[]{0, -1});                                     // {node, symbol of the edge that led here}
7    StringBuilder out = new StringBuilder();
8    while (!stack.isEmpty()) {                                        // Hierholzer on the de Bruijn graph: every node has in = out = k
9        int[] top = stack.peek();
10        if (next[top[0]] < k) {
11            int c = next[top[0]]++;
12            stack.push(new int[]{(top[0] * k + c) % nodes, c});       // follow an edge: drop the first symbol, append c
13        } else {
14            stack.pop();
15            if (top[1] >= 0) out.append(top[1]);                      // symbols come out in reverse order
16        }
17    }
18    return out.reverse().toString();
19}

1// true when every word of length n over the symbols 0 .. k-1 appears exactly once when s is read cyclically
2static boolean isUniversalCycle(String s, int k, int n) {
3    int words = 1;
4    for (int i = 0; i < n; i++) words *= k;
5    if (s.length() != words) return false;                            // k^n windows can hold at most k^n distinct words
6    for (char c : s.toCharArray()) if (c < '0' || c >= '0' + k) return false;
7    String doubled = s + s.substring(0, n - 1);                       // append the start so that windows can wrap round
8    Set<String> seen = new HashSet<>();
9    for (int i = 0; i < s.length(); i++) if (!seen.add(doubled.substring(i, i + n))) return false;
10    return true;
11}

1// recursive Hierholzer on a directed graph whose in-degree and out-degree agree everywhere and whose arcs are connected
2static List<Integer> eulerCircuitDirected(int n, List<Integer>[] out, int start) {
3    LinkedList<Integer> circuit = new LinkedList<>();
4    visit(start, out, new int[n], circuit);
5    return circuit;
6}
7static void visit(int v, List<Integer>[] out, int[] next, LinkedList<Integer> circuit) {
8    while (next[v] < out[v].size()) visit(out[v].get(next[v]++), out, next, circuit);   // follow every unused arc, depth first
9    circuit.addFirst(v);                                              // v is final once all its arcs are used
10}