001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.incremental.mealy; 018 019import java.util.ArrayDeque; 020import java.util.ArrayList; 021import java.util.Collection; 022import java.util.Collections; 023import java.util.HashMap; 024import java.util.List; 025import java.util.Map; 026import java.util.Objects; 027import java.util.Queue; 028 029import net.automatalib.automata.abstractimpl.AbstractDeterministicAutomaton; 030import net.automatalib.automata.concepts.StateIDs; 031import net.automatalib.automata.concepts.TransitionOutput; 032import net.automatalib.automata.graphs.AbstractAutomatonGraph; 033import net.automatalib.automata.graphs.TransitionEdge.Property; 034import net.automatalib.automata.transout.MealyMachine; 035import net.automatalib.automata.transout.impl.compact.CompactMealy; 036import net.automatalib.commons.util.UnionFind; 037import net.automatalib.commons.util.mappings.MutableMapping; 038import net.automatalib.graphs.UniversalGraph; 039import net.automatalib.graphs.concepts.NodeIDs; 040import net.automatalib.graphs.dot.DOTPlottableGraph; 041import net.automatalib.graphs.dot.GraphDOTHelper; 042import net.automatalib.incremental.ConflictException; 043import net.automatalib.incremental.IncrementalConstruction; 044import net.automatalib.words.Alphabet; 045import net.automatalib.words.Word; 046import net.automatalib.words.WordBuilder; 047 048/** 049 * Incrementally builds an (acyclic) Mealy machine, from a set of input and corresponding 050 * output words. 051 * 052 * @author Malte Isberner <malte.isberner@gmail.com> 053 * 054 * @param <I> input symbol class 055 * @param <O> output symbol class 056 */ 057public class IncrementalMealyBuilder<I, O> extends 058 AbstractDeterministicAutomaton<State, I, TransitionRecord> implements 059 TransitionOutput<TransitionRecord, O>, 060 UniversalGraph<State, TransitionRecord, Void, Property<I,O>>, 061 DOTPlottableGraph<State, TransitionRecord>, 062 IncrementalConstruction<MealyMachine<?,I,?,O>, I> { 063 064 065 private static final class SuffixInfo { 066 private final State last; 067 private final State end; 068 069 public SuffixInfo(State last, State end) { 070 this.last = last; 071 this.end = end; 072 } 073 074 public State getLast() { 075 return last; 076 } 077 078 public State getEnd() { 079 return end; 080 } 081 } 082 083 private final Map<StateSignature, State> register = new HashMap<>(); 084 085 private final Alphabet<I> inputAlphabet; 086 private final int alphabetSize; 087 private final State init; 088 089 /** 090 * Constructor. 091 * @param inputAlphabet the input alphabet to use 092 */ 093 public IncrementalMealyBuilder(Alphabet<I> inputAlphabet) { 094 this.inputAlphabet = inputAlphabet; 095 this.alphabetSize = inputAlphabet.size(); 096 StateSignature initSig = new StateSignature(alphabetSize); 097 this.init = new State(initSig); 098 register.put(null, init); 099 } 100 101 /* 102 * (non-Javadoc) 103 * @see net.automatalib.automata.abstractimpl.AbstractDeterministicAutomaton#size() 104 */ 105 @Override 106 public int size() { 107 return register.size(); 108 } 109 110 /** 111 * Retrieves the (internal) state reached by the given input word, 112 * or <tt>null</tt> if no information about the input word is present. 113 * @param word the input word 114 * @return the corresponding state 115 */ 116 private State getState(Word<I> word) { 117 State s = init; 118 119 for (I sym : word) { 120 int idx = inputAlphabet.getSymbolIndex(sym); 121 s = s.getSuccessor(idx); 122 if (s == null) 123 return null; 124 } 125 return s; 126 } 127 128 /** 129 * Checks whether there exists secured information about the output 130 * for the given word. 131 * @param word the input word 132 * @return a boolean indicating whether information about the output for the 133 * given input word exists. 134 */ 135 public boolean isComplete(Word<I> word) { 136 State s = getState(word); 137 return (s != null); 138 } 139 140 /** 141 * Retrieves the output word for the given input word. If no definitive information 142 * for the input word exists, the output for the longest known prefix will be returned. 143 * @param word the input word 144 * @param output a {@link WordBuilder} for constructing the output word 145 * @return <tt>true</tt> if the information contained was complete (in this case, 146 * <code>word.length() == output.size()</code> will hold), <tt>false</tt> otherwise. 147 */ 148 @SuppressWarnings("unchecked") 149 public boolean lookup(Word<I> word, WordBuilder<O> output) { 150 State curr = init; 151 for(I sym : word) { 152 int idx = inputAlphabet.getSymbolIndex(sym); 153 State succ = curr.getSuccessor(idx); 154 if(succ == null) 155 return false; 156 output.append((O)curr.getOutput(idx)); 157 curr = succ; 158 } 159 160 return true; 161 } 162 163 164 /** 165 * Incorporates a pair of input/output words into the stored information. 166 * @param word the input word 167 * @param outputWord the corresponding output word 168 * @throws ConflictException if this information conflicts with information already stored 169 */ 170 public void insert(Word<I> word, Word<O> outputWord) { 171 int len = word.length(); 172 173 State curr = init; 174 State conf = null; 175 176 int confIndex = -1; 177 178 int prefixLen = 0; 179 // Find the internal state in the automaton that can be reached by a 180 // maximal prefix of the word (i.e., a path of secured information) 181 for (I sym : word) { 182 // During this, store the *first* confluence state (i.e., state with 183 // multiple incoming edges). 184 if (conf == null && curr.isConfluence()) { 185 conf = curr; 186 confIndex = prefixLen; 187 } 188 189 int idx = inputAlphabet.getSymbolIndex(sym); 190 State succ = curr.getSuccessor(idx); 191 if (succ == null) 192 break; 193 // If a transition exists for the input symbol, it also has an output symbol. 194 // Check if this matches the provided one, otherwise there is a conflict 195 O outSym = outputWord.getSymbol(prefixLen); 196 if(!Objects.equals(outSym, curr.getOutput(idx))) 197 throw new ConflictException("Error inserting " + word + " / " + outputWord + ": Incompatible output symbols: " + outSym + " vs " + curr.getOutput(idx)); 198 curr = succ; 199 prefixLen++; 200 } 201 202 // The information was already present - we do not need to continue 203 if (prefixLen == len) 204 return; 205 206 207 // We then create a suffix path, i.e., a linear sequence of states corresponding to 208 // the suffix (more precisely: the suffix minus the first symbol, since this is the 209 // transition which is used for gluing the suffix path to the existing automaton). 210 Word<I> suffix = word.subWord(prefixLen); 211 Word<O> suffixOut = outputWord.subWord(prefixLen); 212 213 State last; 214 215 State suffixState; 216 State endpoint = null; 217 if(conf != null) { 218 // If we encountered a confluence state on a way, the whole path including 219 // the confluence state will have to be duplicated to separate it from 220 // other prefixes 221 suffixState = createSuffix(suffix.subWord(1), suffixOut.subWord(1)); 222 } 223 else { 224 // This is a dangerous corner case: If NO confluence state was found, it can happen 225 // that the last state of the suffix path is merged with the end of the prefix path 226 // (i.e., when both have no outgoing transitions - note that this is ALWAYS the case 227 // upon the first insert() call). Because there is no confluence we resolve by cloning 228 // part of the prefix path, we might accidentally introduce a cycle here. 229 // Storing the endpoint of the suffix path allows avoiding this later on. 230 SuffixInfo suffixRes = createSuffix2(suffix.subWord(1), suffixOut.subWord(1)); 231 suffixState = suffixRes.getLast(); 232 endpoint = suffixRes.getEnd(); 233 } 234 235 // Here we create the "gluing" transition 236 I sym = suffix.getSymbol(0); 237 int suffTransIdx = inputAlphabet.getSymbolIndex(sym); 238 O suffTransOut = suffixOut.getSymbol(0); 239 240 241 int currentIndex; 242 if (conf != null) { 243 // If there was a confluence state, we have to clone all nodes on 244 // the prefix path up to this state, in order to separate it from other 245 // prefixes reaching the confluence state (we do not now anything about them 246 // plus the suffix). 247 last = clone(curr, suffTransIdx, suffixState, suffTransOut); 248 249 for (int i = prefixLen - 1; i >= confIndex; i--) { 250 State s = getState(word.prefix(i)); 251 sym = word.getSymbol(i); 252 int idx = inputAlphabet.getSymbolIndex(sym); 253 last = clone(s, idx, last); 254 } 255 256 currentIndex = confIndex; 257 } else { 258 // Otherwise, we have to check for the above-mentioned corner case, and possibly 259 // also duplicate the last state on the prefix path 260 if(endpoint == curr) 261 last = clone(curr, suffTransIdx, suffixState, suffTransOut); 262 else if(curr != init) 263 last = updateSignature(curr, suffTransIdx, suffixState, suffTransOut); 264 else { 265 // The last state on the prefix path is the initial state. After updating 266 // its signature, we are done since we cannot backtrack any further. 267 updateInitSignature(suffTransIdx, suffixState, suffTransOut); 268 return; 269 } 270 currentIndex = prefixLen; 271 } 272 273 // Finally, we have to refresh all the signatures, iterating backwards 274 // until the updating becomes stable. 275 while (--currentIndex > 0) { 276 State state = getState(word.prefix(currentIndex)); 277 sym = word.getSymbol(currentIndex); 278 int idx = inputAlphabet.getSymbolIndex(sym); 279 last = updateSignature(state, idx, last); 280 281 if (state == last) 282 return; 283 } 284 285 sym = word.getSymbol(0); 286 int idx = inputAlphabet.getSymbolIndex(sym); 287 updateInitSignature(idx, last); 288 } 289 290 291 /** 292 * Update the signature of the initial state. This requires special handling, as the 293 * initial state is not stored in the register (since it can never legally act as a predecessor). 294 * @param idx the transition index being changed 295 * @param succ the new successor state 296 */ 297 private void updateInitSignature(int idx, State succ) { 298 StateSignature sig = init.getSignature(); 299 State oldSucc = sig.successors[idx]; 300 if(oldSucc == succ) 301 return; 302 if(oldSucc != null) 303 oldSucc.decreaseIncoming(); 304 sig.successors[idx] = succ; 305 succ.increaseIncoming(); 306 } 307 308 /** 309 * Update the signature of a state, changing only the successor state of a single transition 310 * index. 311 * @param state the state which's signature to update 312 * @param idx the transition index to modify 313 * @param succ the new successor state 314 * @return the resulting state, which can either be the same as the input state (if the new 315 * signature is unique), or the result of merging with another state. 316 */ 317 private State updateSignature(State state, int idx, State succ) { 318 StateSignature sig = state.getSignature(); 319 if (sig.successors[idx] == succ) 320 return state; 321 322 register.remove(sig); 323 if(sig.successors[idx] != null) 324 sig.successors[idx].decreaseIncoming(); 325 sig.successors[idx] = succ; 326 succ.increaseIncoming(); 327 sig.updateHashCode(); 328 return replaceOrRegister(state); 329 } 330 331 /** 332 * Updates the signature of the initial state, changing both the successor state 333 * and the output symbol. 334 * @param idx the transition index to change 335 * @param succ the new successor state 336 * @param out the output symbol 337 */ 338 private void updateInitSignature(int idx, State succ, O out) { 339 StateSignature sig = init.getSignature(); 340 State oldSucc = sig.successors[idx]; 341 if(oldSucc == succ && Objects.equals(out, sig.outputs[idx])) 342 return; 343 if(oldSucc != null) 344 oldSucc.decreaseIncoming(); 345 sig.successors[idx] = succ; 346 sig.outputs[idx] = out; 347 succ.increaseIncoming(); 348 } 349 350 /** 351 * Updates the signature of a state, changing both the successor state and the output 352 * symbol for a single transition index. 353 * @param state the state which's signature to change 354 * @param idx the transition index to change 355 * @param succ the new successor state 356 * @param out the output symbol 357 * @return the resulting state, which can either be the same as the input state (if the new 358 * signature is unique), or the result of merging with another state. 359 */ 360 private State updateSignature(State state, int idx, State succ, O out) { 361 StateSignature sig = state.getSignature(); 362 if (sig.successors[idx] == succ && Objects.equals(out, sig.outputs[idx])) 363 return state; 364 365 register.remove(sig); 366 if(sig.successors[idx] != null) 367 sig.successors[idx].decreaseIncoming(); 368 sig.successors[idx] = succ; 369 succ.increaseIncoming(); 370 sig.outputs[idx] = out; 371 sig.updateHashCode(); 372 return replaceOrRegister(state); 373 } 374 375 376 private State clone(State other, int idx, State succ) { 377 StateSignature sig = other.getSignature(); 378 if (sig.successors[idx] == succ) 379 return other; 380 sig = sig.clone(); 381 sig.successors[idx] = succ; 382 sig.updateHashCode(); 383 return replaceOrRegister(sig); 384 } 385 386 private State clone(State other, int idx, State succ, O out) { 387 StateSignature sig = other.getSignature(); 388 if (sig.successors[idx] == succ && Objects.equals(out, sig.outputs[idx])) 389 return other; 390 sig = sig.clone(); 391 sig.successors[idx] = succ; 392 sig.outputs[idx] = out; 393 sig.updateHashCode(); 394 return replaceOrRegister(sig); 395 } 396 397 private State replaceOrRegister(StateSignature sig) { 398 State state = register.get(sig); 399 if (state != null) 400 return state; 401 402 register.put(sig, state = new State(sig)); 403 for (int i = 0; i < sig.successors.length; i++) { 404 State succ = sig.successors[i]; 405 if (succ != null) 406 succ.increaseIncoming(); 407 } 408 return state; 409 } 410 411 private State replaceOrRegister(State state) { 412 StateSignature sig = state.getSignature(); 413 State other = register.get(sig); 414 if (other != null) { 415 if (state != other) { 416 for (int i = 0; i < sig.successors.length; i++) { 417 State succ = sig.successors[i]; 418 if(succ != null) 419 succ.decreaseIncoming(); 420 } 421 } 422 return other; 423 } 424 425 register.put(sig, state); 426 return state; 427 } 428 429 private State createSuffix(Word<I> suffix, Word<O> suffixOut) { 430 StateSignature sig = new StateSignature(alphabetSize); 431 sig.updateHashCode(); 432 State last = replaceOrRegister(sig); 433 434 int len = suffix.length(); 435 for (int i = len - 1; i >= 0; i--) { 436 sig = new StateSignature(alphabetSize); 437 I sym = suffix.getSymbol(i); 438 O outsym = suffixOut.getSymbol(i); 439 int idx = inputAlphabet.getSymbolIndex(sym); 440 sig.successors[idx] = last; 441 sig.outputs[idx] = outsym; 442 sig.updateHashCode(); 443 last = replaceOrRegister(sig); 444 } 445 446 return last; 447 } 448 449 private SuffixInfo createSuffix2(Word<I> suffix, Word<O> suffixOut) { 450 StateSignature sig = new StateSignature(alphabetSize); 451 sig.updateHashCode(); 452 State last = replaceOrRegister(sig); 453 State end = last; 454 455 int len = suffix.length(); 456 for (int i = len - 1; i >= 0; i--) { 457 sig = new StateSignature(alphabetSize); 458 I sym = suffix.getSymbol(i); 459 O outsym = suffixOut.getSymbol(i); 460 int idx = inputAlphabet.getSymbolIndex(sym); 461 sig.successors[idx] = last; 462 sig.outputs[idx] = outsym; 463 sig.updateHashCode(); 464 last = replaceOrRegister(sig); 465 } 466 467 return new SuffixInfo(last, end); 468 } 469 470 471 472 /* 473 * (non-Javadoc) 474 * @see net.automatalib.ts.TransitionSystem#getSuccessor(java.lang.Object) 475 */ 476 @Override 477 public State getSuccessor(TransitionRecord transition) { 478 return transition.source.getSuccessor(transition.transIdx); 479 } 480 481 /* 482 * (non-Javadoc) 483 * @see net.automatalib.ts.SimpleDTS#getInitialState() 484 */ 485 @Override 486 public State getInitialState() { 487 return init; 488 } 489 490 /* 491 * (non-Javadoc) 492 * @see net.automatalib.graphs.UniversalGraph#getNodeProperties(java.lang.Object) 493 */ 494 @Override 495 public Void getNodeProperty(State node) { 496 return null; 497 } 498 499 /* 500 * (non-Javadoc) 501 * @see net.automatalib.graphs.UniversalGraph#getEdgeProperties(java.lang.Object) 502 */ 503 @Override 504 @SuppressWarnings("unchecked") 505 public Property<I, O> getEdgeProperty(TransitionRecord edge) { 506 I input = inputAlphabet.getSymbol(edge.transIdx); 507 O out = (O)edge.source.getOutput(edge.transIdx); 508 return new Property<>(input, out); 509 } 510 511 /* 512 * (non-Javadoc) 513 * @see net.automatalib.graphs.IndefiniteGraph#getOutgoingEdges(java.lang.Object) 514 */ 515 @Override 516 public Collection<TransitionRecord> getOutgoingEdges(State node) { 517 List<TransitionRecord> edges = new ArrayList<TransitionRecord>(); 518 for(int i = 0; i < alphabetSize; i++) { 519 if(node.getSuccessor(i) != null) 520 edges.add(new TransitionRecord(node, i)); 521 } 522 return edges; 523 } 524 525 /* 526 * (non-Javadoc) 527 * @see net.automatalib.graphs.IndefiniteGraph#getTarget(java.lang.Object) 528 */ 529 @Override 530 public State getTarget(TransitionRecord edge) { 531 return edge.source.getSuccessor(edge.transIdx); 532 } 533 534 /* 535 * (non-Javadoc) 536 * @see net.automatalib.automata.concepts.TransitionOutput#getTransitionOutput(java.lang.Object) 537 */ 538 @Override 539 @SuppressWarnings("unchecked") 540 public O getTransitionOutput(TransitionRecord transition) { 541 return (O)transition.source.getOutput(transition.transIdx); 542 } 543 544 /* 545 * (non-Javadoc) 546 * @see net.automatalib.ts.DeterministicTransitionSystem#getTransition(java.lang.Object, java.lang.Object) 547 */ 548 @Override 549 public TransitionRecord getTransition(State state, I input) { 550 int idx = inputAlphabet.getSymbolIndex(input); 551 if(state.getSuccessor(idx) != null) 552 return new TransitionRecord(state, idx); 553 return null; 554 } 555 556 /* 557 * (non-Javadoc) 558 * @see net.automatalib.graphs.dot.DOTPlottableGraph#getHelper() 559 */ 560 @Override 561 public GraphDOTHelper<State, TransitionRecord> getGraphDOTHelper() { 562 return new DOTHelper(inputAlphabet, init); 563 } 564 565 /* 566 * (non-Javadoc) 567 * @see net.automatalib.ts.SimpleFiniteTS#getStates() 568 */ 569 @Override 570 public Collection<State> getStates() { 571 return Collections.unmodifiableCollection(register.values()); 572 } 573 574 /* 575 * (non-Javadoc) 576 * @see net.automatalib.graphs.FiniteGraph#getNodes() 577 */ 578 @Override 579 public Collection<State> getNodes() { 580 return Collections.unmodifiableCollection(register.values()); 581 } 582 583 /* 584 * (non-Javadoc) 585 * @see net.automatalib.incremental.IncrementalConstruction#getInputAlphabet() 586 */ 587 @Override 588 public Alphabet<I> getInputAlphabet() { 589 return inputAlphabet; 590 } 591 592 /* 593 * (non-Javadoc) 594 * @see net.automatalib.incremental.IncrementalConstruction#findSeparatingWord(java.lang.Object, java.util.Collection, boolean) 595 */ 596 @Override 597 public Word<I> findSeparatingWord(MealyMachine<?, I, ?, O> target, 598 Collection<? extends I> inputs, boolean omitUndefined) { 599 return doFindSeparatingWord(target, inputs, omitUndefined); 600 } 601 602 /* 603 * (non-Javadoc) 604 * @see net.automatalib.incremental.IncrementalConstruction#toAutomaton() 605 */ 606 @Override 607 @SuppressWarnings("unchecked") 608 public CompactMealy<I, O> toAutomaton() { 609 CompactMealy<I,O> result = new CompactMealy<I,O>(inputAlphabet, register.size()); 610 611 Map<State,Integer> stateMap = new HashMap<>(); 612 613 for(State s : register.values()) { 614 Integer id; 615 if(s == init) 616 id = result.addInitialState(); 617 else 618 id = result.addState(); 619 stateMap.put(s, id); 620 } 621 622 for(Map.Entry<State,Integer> e : stateMap.entrySet()) { 623 State s = e.getKey(); 624 Integer id = e.getValue(); 625 626 for(int i = 0; i < alphabetSize; i++) { 627 State succ = s.getSuccessor(i); 628 if(succ == null) 629 continue; 630 I sym = inputAlphabet.getSymbol(i); 631 O out = (O)s.getOutput(i); 632 Integer succId = stateMap.get(succ); 633 result.addTransition(id, sym, succId, out); 634 } 635 } 636 637 return result; 638 } 639 640 /* 641 * (non-Javadoc) 642 * @see net.automatalib.incremental.IncrementalConstruction#hasDefinitiveInformation(net.automatalib.words.Word) 643 */ 644 @Override 645 public boolean hasDefinitiveInformation(Word<I> word) { 646 State s = getState(word); 647 return (s != null); 648 } 649 650 /////////////////////////////////////////////////////////////////////// 651 // Equivalence test // 652 /////////////////////////////////////////////////////////////////////// 653 654 private static int getStateId(State state, Map<State,Integer> ids) { 655 Integer id = ids.get(state); 656 if(id == null) { 657 id = ids.size(); 658 ids.put(state, id); 659 } 660 return id.intValue(); 661 } 662 663 private static final class Record<S,I> { 664 private final State state1; 665 private final S state2; 666 private final I reachedVia; 667 private final Record<S,I> reachedFrom; 668 private final int depth; 669 670 public Record(State state1, S state2, Record<S,I> reachedFrom, I reachedVia) { 671 this.state1 = state1; 672 this.state2 = state2; 673 this.reachedFrom = reachedFrom; 674 this.reachedVia = reachedVia; 675 this.depth = (reachedFrom != null) ? reachedFrom.depth + 1 : 0; 676 } 677 678 public Record(State state1, S state2) { 679 this(state1, state2, null, null); 680 } 681 } 682 683 private <S,T> Word<I> doFindSeparatingWord(MealyMachine<S,I,T,O> mealy, Collection<? extends I> inputs, boolean omitUndefined) { 684 int thisStates = register.size(); 685 686 UnionFind uf = new UnionFind(thisStates + mealy.size()); 687 688 Map<State,Integer> ids = new HashMap<State,Integer>(); 689 690 State init1 = init; 691 S init2 = mealy.getInitialState(); 692 693 if(init2 == null) 694 return omitUndefined ? null : Word.<I>epsilon(); 695 696 StateIDs<S> mealyIds = mealy.stateIDs(); 697 698 int id1 = getStateId(init1, ids), id2 = mealyIds.getStateId(init2) + thisStates; 699 700 uf.link(id1, id2); 701 702 Queue<Record<S,I>> queue = new ArrayDeque<Record<S,I>>(); 703 704 queue.offer(new Record<S,I>(init1, init2)); 705 706 I lastSym = null; 707 708 Record<S,I> current; 709 710explore:while((current = queue.poll()) != null) { 711 State state1 = current.state1; 712 S state2 = current.state2; 713 714 for(I sym : inputs) { 715 int idx = inputAlphabet.getSymbolIndex(sym); 716 State succ1 = state1.getSuccessor(idx); 717 if(succ1 == null) 718 continue; 719 720 T trans2 = mealy.getTransition(state2, sym); 721 if(trans2 == null) { 722 if(omitUndefined) 723 continue; 724 lastSym = sym; 725 break explore; 726 } 727 728 Object out1 = state1.getOutput(idx); 729 Object out2 = mealy.getTransitionOutput(trans2); 730 if(!Objects.equals(out1, out2)) { 731 lastSym = sym; 732 break explore; 733 } 734 735 S succ2 = mealy.getSuccessor(trans2); 736 737 id1 = getStateId(succ1, ids); 738 id2 = mealyIds.getStateId(succ2) + thisStates; 739 740 int r1 = uf.find(id1), r2 = uf.find(id2); 741 742 if(r1 == r2) 743 continue; 744 745 uf.link(r1, r2); 746 747 queue.offer(new Record<>(succ1, succ2, current, sym)); 748 } 749 } 750 751 if(current == null) 752 return null; 753 754 int ceLength = current.depth; 755 if(lastSym != null) 756 ceLength++; 757 758 WordBuilder<I> wb = new WordBuilder<I>(null, ceLength); 759 760 int index = ceLength; 761 762 if(lastSym != null) 763 wb.setSymbol(--index, lastSym); 764 765 while(current.reachedFrom != null) { 766 wb.setSymbol(--index, current.reachedVia); 767 current = current.reachedFrom; 768 } 769 770 return wb.toWord(); 771 } 772 773 @Override 774 public NodeIDs<State> nodeIDs() { 775 return AbstractAutomatonGraph.nodeIDs(this); 776 } 777 778 @Override 779 public <V> MutableMapping<State, V> createStaticNodeMapping() { 780 return AbstractAutomatonGraph.createDynamicNodeMapping(this); 781 } 782 783 @Override 784 public <V> MutableMapping<State, V> createDynamicNodeMapping() { 785 return AbstractAutomatonGraph.createDynamicNodeMapping(this); 786 } 787 788 789}