1 /*
2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package optkl.util;
26 import optkl.jdot.ui.JDot;
27 import optkl.util.carriers.LookupCarrier;
28
29 import java.lang.invoke.MethodHandles;
30 import java.util.ArrayList;
31 import java.util.Collections;
32 import java.util.HashMap;
33 import java.util.HashSet;
34 import java.util.LinkedList;
35 import java.util.List;
36 import java.util.Map;
37 import java.util.Queue;
38 import java.util.Set;
39 import java.util.function.Consumer;
40 import java.util.function.Function;
41
42 public class Dag<N> implements LookupCarrier {
43
44 final public MethodHandles.Lookup lookup;
45
46 @Override
47 public MethodHandles.Lookup lookup() {
48 return lookup;
49 }
50
51 protected final Set<N> nodeSet = new HashSet<>();
52 public final List<N> rankOrdered = new LinkedList<>();
53
54 protected final Map<N, Set<N>> fromToNodes = new HashMap<>();
55 public void view(String name, Function<N,String> dotNodeLabelRenderer) {
56 JDot.digraph(name, $ ->
57 fromToNodes.forEach((l, r) ->
58 r.forEach(e ->
59 $.edge(dotNodeLabelRenderer.apply(l), dotNodeLabelRenderer.apply(e))
60 )
61 ));
62 }
63
64 public boolean isDag() {
65 return fromToNodes.size()>1;
66 }
67
68
69 protected Dag(MethodHandles.Lookup lookup) {
70 this.lookup = lookup;
71 }
72
73 protected void computeIfAbsent(N from, N to, Consumer<N> ifAbsent){
74 if (!nodeSet.contains(to)) {
75 nodeSet.add(to);
76 fromToNodes.put(to, new HashSet<>());
77 ifAbsent.accept(to);
78 }
79 fromToNodes.get(from).add(to);
80 }
81
82
83 public void closeRanks() {
84 Map<N, Integer> outDegree = new HashMap<>();
85 Map<N, List<N>> reverseEdges = new HashMap<>();
86
87 for (N parent : fromToNodes.keySet()) {
88 outDegree.put(parent, fromToNodes.get(parent).size());
89 for (N child : fromToNodes.get(parent)) {
90 reverseEdges.computeIfAbsent(child, k -> new ArrayList<>()).add(parent);
91 outDegree.putIfAbsent(child, 0);
92 }
93 }
94 final Queue<N> queue = new LinkedList<>();
95 for (Map.Entry<N, Integer> entry : outDegree.entrySet()) {
96 if (entry.getValue() == 0) {
97 queue.add(entry.getKey());
98 }
99 }
100
101 while (!queue.isEmpty()) {
102 N current = queue.poll();
103 rankOrdered.add(current);
104 List<N> parents = reverseEdges.getOrDefault(current, Collections.emptyList());
105 for (N parent : parents) {
106 int remainingChildren = outDegree.get(parent) - 1;
107 outDegree.put(parent, remainingChildren);
108 if (remainingChildren == 0) {
109 queue.add(parent);
110 }
111 }
112 }
113 }
114 }