StateGraphEditorTest xref


1   /*
2    * Copyright (C) 2006  Tom Gibara
3    *
4    * This library is free software; you can redistribute it and/or
5    * modify it under the terms of the GNU Lesser General Public
6    * License as published by the Free Software Foundation; either
7    * version 2.1 of the License, or (at your option) any later version.
8    *
9    * This library is distributed in the hope that it will be useful,
10   * but WITHOUT ANY WARRANTY; without even the implied warranty of
11   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   * Lesser General Public License for more details.
13   *
14   * You should have received a copy of the GNU Lesser General Public
15   * License along with this library; if not, write to the Free Software
16   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
17   */
18  
19  package com.tomgibara.pronto.state;
20  
21  import static com.tomgibara.pronto.state.PathType.strictlyUniqueStates;
22  import static com.tomgibara.pronto.state.PathType.uniqueStates;
23  import static com.tomgibara.pronto.state.PathType.uniqueTransitions;
24  import static com.tomgibara.pronto.state.TestUtil.labelSet;
25  import static com.tomgibara.pronto.state.TestUtil.makeGraph;
26  import static com.tomgibara.pronto.state.TestUtil.stateSet;
27  import static com.tomgibara.pronto.state.TestUtil.transitionSet;
28  
29  import java.util.Set;
30  
31  import junit.framework.TestCase;
32  
33  public class StateGraphEditorTest extends TestCase {
34  
35      private static final Trivial trivial = new Trivial();
36  
37      public void testCreateEditor() {
38          assertNotNull(StateFactory.getInstance().emptyStateGraph().newEditor());
39      }
40  
41      public void testCreateEmptyGraph() {
42          StateGraph graph = StateFactory.getInstance().emptyStateGraph().newEditor().getGraph();
43          assertEquals(0, graph.states().size());
44          assertEquals(0, graph.transitions().size());
45      }
46  
47      public void testRepeatEdit() {
48          StateGraph<String, Integer> graph1 = makeGraph("A->B;");
49          StateGraphEditor<String, Integer> editor = graph1.newEditor();
50          editor.addTransition("B", 0, "C");
51          StateGraph<String, Integer> graph2 = editor.getGraph();
52          editor.addTransition("C", 0, "D");
53          StateGraph<String, Integer> graph3 = editor.getGraph();
54          assertFalse(graph1.equals(graph2));
55          assertFalse(graph2.equals(graph3));
56          assertFalse(graph3.equals(graph1));
57      }
58  
59      public void testCreateTransitionlessGraphs() {
60          for (int i = 0; i < 10; i++) {
61              StateGraphEditor<Integer, Trivial> editor = StateFactory.getInstance().<Integer, Trivial> emptyStateGraph()
62                      .newEditor();
63              for (int j = 0; j < i; j++) {
64                  editor.addState(j);
65              }
66              StateGraph<Integer, Trivial> graph = editor.getGraph();
67              assertEquals(i, graph.states().size());
68              assertEquals(0, graph.transitions().size());
69          }
70      }
71  
72      public void testRemoveState() {
73          StateGraphEditor<Integer, Trivial> editor = StateFactory.getInstance().<Integer, Trivial> emptyStateGraph()
74                  .newEditor();
75          editor.addState(0);
76          editor.addState(1);
77          editor.addTransition(0, trivial, 1);
78          editor.removeState(0);
79          StateGraph<Integer, Trivial> graph = editor.getGraph();
80          assertEquals(1, graph.states().size());
81          assertEquals(0, graph.transitions().size());
82      }
83  
84      public void testAddSeparateTransitions() {
85          StateGraphEditor<Integer, Trivial> editor = StateFactory.getInstance().<Integer, Trivial> emptyStateGraph()
86                  .newEditor();
87          editor.addTransition(0, trivial, 1);
88          editor.addTransition(2, trivial, 3);
89          editor.addTransition(4, trivial, 5);
90          StateGraph<Integer, Trivial> graph = editor.getGraph();
91          assertEquals(6, graph.states().size());
92          assertEquals(3, graph.transitions().size());
93      }
94  
95      public void testAddStates() {
96          StateGraph<String, Integer> original = makeGraph("A->B;");
97          StateGraph<String, Integer> expected = makeGraph("A->B;C");
98          StateGraphEditor<String, Integer> editor = original.newEditor();
99          editor.addStates(stateSet("B;C"));
100         assertEquals(expected, editor.getGraph());
101     }
102 
103     public void testRemoveStates() {
104         StateGraph<String, Integer> original = makeGraph("A->B;B->C");
105         StateGraph<String, Integer> expected = makeGraph("A");
106         StateGraphEditor<String, Integer> editor = original.newEditor();
107         editor.removeStates(stateSet("B;C"));
108         assertEquals(expected, editor.getGraph());
109     }
110 
111     public void testRetainStates() {
112         StateGraph<String, Integer> original = makeGraph("A->B;B->C");
113         StateGraph<String, Integer> expected = makeGraph("A->B");
114         StateGraphEditor<String, Integer> editor = original.newEditor();
115         editor.retainStates(stateSet("A;B"));
116         assertEquals(expected, editor.getGraph());
117     }
118 
119     public void testAddTransitions() {
120         StateGraph<String, Integer> original = makeGraph("A->B");
121         StateGraph<String, Integer> expected = makeGraph("A->B;B->C;C->A");
122         StateGraphEditor<String, Integer> editor = original.newEditor();
123         editor.addTransitions(transitionSet("B->C;C->A"));
124         assertEquals(expected, editor.getGraph());
125     }
126 
127     public void testRemoveTransitions() {
128         StateGraph<String, Integer> original = makeGraph("A->B;B->C;C->A");
129         StateGraph<String, Integer> expected = makeGraph("A->B;C");
130         StateGraphEditor<String, Integer> editor = original.newEditor();
131         editor.removeTransitions(transitionSet("B->C;C->A"));
132         assertEquals(expected, editor.getGraph());
133     }
134 
135     public void testRetainTransitions() {
136         StateGraph<String, Integer> original = makeGraph("A->B;B->C;C->A");
137         StateGraph<String, Integer> expected = makeGraph("A->B;C");
138         StateGraphEditor<String, Integer> editor = original.newEditor();
139         editor.retainTransitions(transitionSet("A->B"));
140         assertEquals(expected, editor.getGraph());
141     }
142 
143     public void testRemoveTransitionsLabelled() {
144         StateGraph<String, Integer> original = makeGraph("A-1->B;B-2->C;C-1->A");
145         StateGraph<String, Integer> expected = makeGraph("B-2->C;A");
146         StateGraphEditor<String, Integer> editor = original.newEditor();
147         editor.removeTransitionsLabelled(labelSet("1"));
148         assertEquals(expected, editor.getGraph());
149     }
150 
151     public void testRetainTransitionsLabelled() {
152         StateGraph<String, Integer> original = makeGraph("A-1->B;B-2->C;C-1->A");
153         StateGraph<String, Integer> expected = makeGraph("C-1->A;A-1->B");
154         StateGraphEditor<String, Integer> editor = original.newEditor();
155         editor.retainTransitionsLabelled(labelSet("1"));
156         assertEquals(expected, editor.getGraph());
157     }
158 
159     public void testAddGraph() {
160         StateGraph<String, Integer> original = makeGraph("A->B;B->C");
161         StateGraph<String, Integer> second = makeGraph("A->B;A->C;C->D;E");
162         StateGraph<String, Integer> expected = makeGraph("A->B;B->C;A->C;C->D;E");
163         StateGraphEditor<String, Integer> editor = original.newEditor();
164         editor.addGraph(second);
165         assertEquals(expected, editor.getGraph());
166     }
167 
168     public void testRemoveGraph() {
169         StateGraph<String, Integer> original = makeGraph("A->B;B->C");
170         StateGraph<String, Integer> second = makeGraph("A->B;A->C;C->D;E");
171         StateGraph<String, Integer> expected = makeGraph("A->B;C");
172         StateGraphEditor<String, Integer> editor = original.newEditor();
173         editor.retainGraph(second);
174         assertEquals(expected, editor.getGraph());
175     }
176 
177     public void testReverseJoined() {
178         StateGraph<String, Integer> original = makeGraph("A->B;B->C;C->D");
179         StateGraph<String, Integer> expected = makeGraph("D->C;C->B;B->A");
180         StateGraphEditor<String, Integer> editor = original.newEditor();
181         editor.reverse();
182         StateGraph<String, Integer> reversed = editor.getGraph();
183         assertEquals(expected, reversed);
184     }
185 
186     public void testReverseSingular() {
187         StateGraph<String, Integer> original = makeGraph("A->A");
188         StateGraph<String, Integer> expected = original;
189         StateGraphEditor<String, Integer> editor = original.newEditor();
190         assertFalse(editor.reverse());
191         StateGraph<String, Integer> reversed = editor.getGraph();
192         assertEquals(expected, reversed);
193     }
194 
195     public void testReverseSymmetric() {
196         StateGraph<String, Integer> original = makeGraph("A->B;B->C;C->B;B->A;D");
197         StateGraphEditor<String, Integer> editor = original.newEditor();
198         assertFalse(editor.reverse());
199         StateGraph<String, Integer> reversed = editor.getGraph();
200         assertEquals(original, reversed);
201     }
202 
203     public void testSubstituteSingleState() {
204         StateGraph<String, Integer> original = makeGraph("A->B;B->C;C->D");
205         StateGraph<String, Integer> expected = makeGraph("A->E;E->C;C->D");
206         StateGraphEditor<String, Integer> editor = original.newEditor();
207         editor.substituteState("B", "E");
208         StateGraph<String, Integer> modified = editor.getGraph();
209         assertEquals(expected, modified);
210     }
211 
212     public void testSubstituteMultipleStates() {
213         StateGraph<String, Integer> original = makeGraph("A->B;B->C;C->D");
214         StateGraph<String, Integer> expected = makeGraph("E->E;E->D");
215         StateGraphEditor<String, Integer> editor = original.newEditor();
216         editor.substituteStates(stateSet("A;B;C"), "E");
217         StateGraph<String, Integer> modified = editor.getGraph();
218         assertEquals(expected, modified);
219     }
220 
221     public void testSubstituteIncludedState() {
222         StateGraph<String, Integer> original = makeGraph("A->B;B->C;C->D");
223         StateGraph<String, Integer> expected = makeGraph("A->A;A->C;C->D");
224         StateGraphEditor<String, Integer> editor = original.newEditor();
225         editor.substituteStates(stateSet("A;B"), "A");
226         StateGraph<String, Integer> modified = editor.getGraph();
227         assertEquals(expected, modified);
228     }
229 
230     public void testSubstituteSingleLabel() {
231         StateGraph<String, Integer> original = makeGraph("A-0->B;A-1->B;B-0->C");
232         StateGraph<String, Integer> expected = makeGraph("A-1->B;B-1->C");
233         StateGraphEditor<String, Integer> editor = original.newEditor();
234         editor.substituteLabel(0, 1);
235         StateGraph<String, Integer> modified = editor.getGraph();
236         assertEquals(expected, modified);
237     }
238 
239     public void testSubstituteMultipleLabels() {
240         StateGraph<String, Integer> original = makeGraph("A-0->A;A-1->A;A-2->A");
241         StateGraph<String, Integer> expected = makeGraph("A-0->A");
242         StateGraphEditor<String, Integer> editor = original.newEditor();
243         editor.substituteLabels(labelSet("0;1;2"), 0);
244         StateGraph<String, Integer> modified = editor.getGraph();
245         assertEquals(expected, modified);
246     }
247 
248     public void testSeparateInducedGraph() {
249         StateGraph<String, Integer> graph = makeGraph("A->B;C->D;E->F");
250         assertEquals(makeGraph("A->B"), getInducedGraph(graph, "A", "B", uniqueTransitions));
251         assertEquals(makeGraph(""), getInducedGraph(graph, "A", "D", uniqueTransitions));
252         assertEquals(makeGraph("A->B"), getInducedGraph(graph, "A", "B", uniqueStates));
253         assertEquals(makeGraph(""), getInducedGraph(graph, "A", "D", uniqueStates));
254     }
255 
256     public void testJoinedInducedGraph() {
257         StateGraph<String, Integer> graph = makeGraph("A->B;B->C;C->D");
258         assertEquals(graph, getInducedGraph(graph, "A", "D", uniqueTransitions));
259         assertEquals(makeGraph("B->C"), getInducedGraph(graph, "B", "C", uniqueTransitions));
260         assertEquals(graph, getInducedGraph(graph, "A", "D", uniqueStates));
261         assertEquals(makeGraph("B->C"), getInducedGraph(graph, "B", "C", uniqueStates));
262     }
263 
264     public void testCircularInducedGraph() {
265         StateGraph<String, Integer> graph = makeGraph("A->B;B->C;C->A");
266         assertEquals(graph, getInducedGraph(graph, "A", "A", uniqueTransitions));
267         assertEquals(graph, getInducedGraph(graph, "A", "A", uniqueStates));
268         assertEquals(makeGraph(""), getInducedGraph(graph, "A", "A", strictlyUniqueStates));
269     }
270 
271     public void testForkedInducedGraph() {
272         StateGraph<String, Integer> graph = makeGraph("A->D;B->D;C->D;D->E;E->F;E->G;E->H");
273         assertEquals(makeGraph("A->D;B->D;D->E;E->F;E->G"), getInducedGraph(graph, stateSet("A;B"), stateSet("F;G"), uniqueTransitions));
274         assertEquals(makeGraph("D->E"), getInducedGraph(graph, "D", "E", uniqueTransitions));
275     }
276 
277     public void testRemovePaths() {
278         StateGraph<String, Integer> graph = makeGraph("A->D;B->D;C->D;D->E;E->F;E->G;E->H");
279         StateGraph<String, Integer> expected = makeGraph("A;B->D;C->D;E->F;E->G;H");
280         StateGraphEditor<String, Integer> editor = graph.newEditor();
281         editor.removePaths("A", "H", uniqueTransitions);
282         StateGraph<String, Integer> modified = editor.getGraph();
283         assertEquals(expected, modified);
284     }
285     
286     public void testRemoveMultiPaths() {
287         StateGraph<String, Integer> graph = makeGraph("A->D;B->D;C->D;D->E;E->F;E->G;E->H");
288         StateGraph<String, Integer> expected = makeGraph("A;B;C->D;E->F;G;H");
289         StateGraphEditor<String, Integer> editor = graph.newEditor();
290         editor.removeMultiPaths(stateSet("A;B"), stateSet("G;H"), uniqueTransitions);
291         StateGraph<String, Integer> modified = editor.getGraph();
292         assertEquals(expected, modified);
293     }
294     
295     private StateGraph<String, Integer> getInducedGraph(StateGraph<String, Integer> graph, String initial,
296             String terminal, PathType type) {
297         StateGraphEditor<String, Integer> editor = graph.newEditor();
298         editor.retainPaths(initial, terminal, type);
299         return editor.getGraph();
300     }
301 
302     private StateGraph<String, Integer> getInducedGraph(StateGraph<String, Integer> graph, Set<String> initial,
303             Set<String> terminal, PathType type) {
304         StateGraphEditor<String, Integer> editor = graph.newEditor();
305         editor.retainMultiPaths(initial, terminal, type);
306         return editor.getGraph();
307     }
308     
309     private static class Trivial {
310     }
311 
312 }