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.util.minimizer; 018 019import java.util.Collection; 020 021import net.automatalib.commons.util.mappings.Mapping; 022 023 024 025/** 026 * The result structure of a minimization process. The result of a minimization 027 * process is a partition on the original set of states. This is represented 028 * by a collection of {@link Block}s containing states that are equivalent 029 * and thus can be merged. 030 * <p> 031 * Since all states in a block are equivalent (and thus especially have the 032 * same set of outgoing edge labels), a minimized automaton can be created 033 * from this partition by instantiating a state for each block. The edges 034 * between those states are created in the following way: For each state/block, 035 * an original state is chosen arbitrarily from this block. The edges are 036 * created according to the edges of this state, only that they point to 037 * the states representing the blocks the respective target states belong to 038 * (using {@link #getBlockForState(Object)}). 039 * <p> 040 * The blocks in the result partition are guaranteed to have contiguous IDs 041 * (see {@link Block#getId()}), starting at 0. This allows an efficient 042 * construction of the resulting automaton. 043 * <p> 044 * A more convenient way to obtain a representation of the resulting, minimized 045 * automaton is using a {@link BlockAutomaton}. 046 * 047 * @author Malte Isberner <malte.isberner@gmail.com> 048 * 049 * @param <S> state class. 050 * @param <L> transition label class. 051 */ 052public final class MinimizationResult<S, L> { 053 // the state storage, used for retrieving the State records 054 // for an original state 055 private final Mapping<S,State<S,L>> stateStorage; 056 // the blocks in the final partition 057 private final Collection<Block<S,L>> blocks; 058 059 /** 060 * Constructor. 061 * @param stateStorage the state storage, 062 * @param blocks the final partition. 063 */ 064 MinimizationResult(Mapping<S,State<S,L>> stateStorage, 065 Collection<Block<S,L>> blocks) { 066 this.stateStorage = stateStorage; 067 this.blocks = blocks; 068 } 069 070 /** 071 * Retrieves the number of blocks in the final partition. 072 * @return the number of blocks. 073 */ 074 public int getNumBlocks() { 075 return blocks.size(); 076 } 077 078 /** 079 * Retrieves all blocks in the final partition. 080 * @return the final partition. 081 */ 082 public Collection<Block<S,L>> getBlocks() { 083 return blocks; 084 } 085 086 087 /** 088 * Retrieves all (original) states in a block. 089 * @param block the block. 090 * @return a collection containing all original states in this 091 * block. 092 */ 093 public static <S,L> Collection<S> getStatesInBlock(Block<S,L> block) { 094 return new OriginalStateCollection<S>(block.getStates()); 095 } 096 097 /** 098 * Chooses a representative (i.e., an arbitrary element of the 099 * set of states) from a block. 100 * @param block the block. 101 * @return an arbitrary element of the state set of the given block. 102 */ 103 public S getRepresentative(Block<S,L> block) { 104 return block.getStates().choose().getOriginalState(); 105 } 106 107 /** 108 * Retrieves the block to which a given original state belongs. 109 * @param origState the original state. 110 * @return the corresponding block. 111 */ 112 public Block<S,L> getBlockForState(S origState) { 113 State<S,L> state = stateStorage.get(origState); 114 return state.getBlock(); 115 } 116 117 /** 118 * Creates a {@link BlockAutomaton} using this results structure. 119 * @return the block automaton. 120 */ 121 public BlockAutomaton<S,L> asBlockAutomaton() { 122 return new BlockAutomaton<S, L>(this); 123 } 124}