Debian Codegraph @

morfologik-fsa-builders/src/main/java/morfologik/fsa/builders/FSAUtils.java

raw
1 package morfologik.fsa.builders;
2
3 import java.io.IOException;
4 import java.io.StringWriter;
5 import java.io.Writer;
6 import java.util.BitSet;
7 import java.util.TreeMap;
8
9 import morfologik.fsa.FSA;
10 import morfologik.fsa.FSA5;
11 import morfologik.fsa.FSAFlags;
12 import morfologik.fsa.StateVisitor;
13
14 import com.carrotsearch.hppc.IntIntHashMap;
15
16 /**
17 * Other FSA-related utilities not directly associated with the class hierarchy.
18 */
19 public final class FSAUtils {
20 public final static class IntIntHolder {
21 public int a;
22 public int b;
23
24 public IntIntHolder(int a, int b) {
25 this.a = a;
26 this.b = b;
27 }
28
29 public IntIntHolder() {
30 }
31 }
32
33 /**
34 * Returns the right-language reachable from a given FSA node, formatted as an
35 * input for the graphviz package (expressed in the <code>dot</code>
36 * language).
37 *
38 * @param fsa The automaton to visualize.
39 * @param node Starting node (subgraph will be visualized unless it's the automaton's root node).
40 * @return Returns the dot language description of the automaton.
41 */
42 public static String toDot(FSA fsa, int node) {
43 try {
44 StringWriter w = new StringWriter();
45 toDot(w, fsa, node);
46 return w.toString();
47 } catch (IOException e) {
48 throw new RuntimeException(e);
49 }
50 }
51
52 /**
53 * Saves the right-language reachable from a given FSA node, formatted as an
54 * input for the graphviz package (expressed in the <code>dot</code>
55 * language), to the given writer.
56 *
57 * @param w The writer to write dot language description of the automaton.
58 * @param fsa The automaton to visualize.
59 * @param node Starting node (subgraph will be visualized unless it's the automaton's root node).
60 * @throws IOException Rethrown if an I/O exception occurs.
61 */
62 public static void toDot(Writer w, FSA fsa, int node) throws IOException {
63 w.write("digraph Automaton {\n");
64 w.write(" rankdir = LR;\n");
65
66 final BitSet visited = new BitSet();
67
68 w.write(" stop [shape=doublecircle,label=\"\"];\n");
69 w.write(" initial [shape=plaintext,label=\"\"];\n");
70 w.write(" initial -> " + node + "\n\n");
71
72 visitNode(w, 0, fsa, node, visited);
73 w.write("}\n");
74 }
75
76 private static void visitNode(Writer w, int d, FSA fsa, int s, BitSet visited) throws IOException {
77 visited.set(s);
78 w.write(" ");
79 w.write(Integer.toString(s));
80
81 if (fsa.getFlags().contains(FSAFlags.NUMBERS)) {
82 int nodeNumber = fsa.getRightLanguageCount(s);
83 w.write(" [shape=circle,label=\"" + nodeNumber + "\"];\n");
84 } else {
85 w.write(" [shape=circle,label=\"\"];\n");
86 }
87
88 for (int arc = fsa.getFirstArc(s); arc != 0; arc = fsa.getNextArc(arc)) {
89 w.write(" ");
90 w.write(Integer.toString(s));
91 w.write(" -> ");
92 if (fsa.isArcTerminal(arc)) {
93 w.write("stop");
94 } else {
95 w.write(Integer.toString(fsa.getEndNode(arc)));
96 }
97
98 final byte label = fsa.getArcLabel(arc);
99 w.write(" [label=\"");
100 if (Character.isLetterOrDigit(label))
101 w.write((char) label);
102 else {
103 w.write("0x");
104 w.write(Integer.toHexString(label & 0xFF));
105 }
106 w.write("\"");
107 if (fsa.isArcFinal(arc))
108 w.write(" arrowhead=\"tee\"");
109 if (fsa instanceof FSA5) {
110 if (((FSA5) fsa).isNextSet(arc)) {
111 w.write(" color=\"blue\"");
112 }
113 }
114
115 w.write("]\n");
116 }
117
118 for (int arc = fsa.getFirstArc(s); arc != 0; arc = fsa.getNextArc(arc)) {
119 if (!fsa.isArcTerminal(arc)) {
120 int endNode = fsa.getEndNode(arc);
121 if (!visited.get(endNode)) {
122 visitNode(w, d + 1, fsa, endNode, visited);
123 }
124 }
125 }
126 }
127
128 /**
129 * Calculate fan-out ratio (how many nodes have a given number of outgoing arcs).
130 *
131 * @param fsa The automaton to calculate fanout for.
132 * @param root The starting node for calculations.
133 *
134 * @return The returned map contains keys for the number of outgoing arcs and
135 * an associated value being the number of nodes with that arc number.
136 */
137 public static TreeMap<Integer, Integer> calculateFanOuts(final FSA fsa, int root) {
138 final int[] result = new int[256];
139 fsa.visitInPreOrder(new StateVisitor() {
140 public boolean accept(int state) {
141 int count = 0;
142 for (int arc = fsa.getFirstArc(state); arc != 0; arc = fsa.getNextArc(arc)) {
143 count++;
144 }
145 result[count]++;
146 return true;
147 }
148 });
149
150 TreeMap<Integer, Integer> output = new TreeMap<Integer, Integer>();
151
152 int low = 1; // Omit #0, there is always a single node like that (dummy).
153 while (low < result.length && result[low] == 0) {
154 low++;
155 }
156
157 int high = result.length - 1;
158 while (high >= 0 && result[high] == 0) {
159 high--;
160 }
161
162 for (int i = low; i <= high; i++) {
163 output.put(i, result[i]);
164 }
165
166 return output;
167 }
168
169 /**
170 * Calculate the size of "right language" for each state in an FSA. The right
171 * language is the number of sequences encoded from a given node in the automaton.
172 *
173 * @param fsa The automaton to calculate right language for.
174 * @return Returns a map with node identifiers as keys and their right language
175 * counts as associated values.
176 */
177 public static IntIntHashMap rightLanguageForAllStates(final FSA fsa) {
178 final IntIntHashMap numbers = new IntIntHashMap();
179
180 fsa.visitInPostOrder(new StateVisitor() {
181 public boolean accept(int state) {
182 int thisNodeNumber = 0;
183 for (int arc = fsa.getFirstArc(state); arc != 0; arc = fsa.getNextArc(arc)) {
184 thisNodeNumber += (fsa.isArcFinal(arc) ? 1 : 0)
185 + (fsa.isArcTerminal(arc) ? 0 : numbers.get(fsa.getEndNode(arc)));
186 }
187 numbers.put(state, thisNodeNumber);
188
189 return true;
190 }
191 });
192
193 return numbers;
194 }
195 }