001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of LearnLib, http://www.learnlib.de/. 003 * 004 * LearnLib 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 * LearnLib 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 LearnLib; if not, see 015 * <http://www.gnu.de/documents/lgpl.en.html>. 016 */ 017package de.learnlib.algorithms.lstargeneric.closing; 018 019import java.util.ArrayList; 020import java.util.List; 021 022import net.automatalib.commons.util.comparison.CmpUtil; 023import net.automatalib.words.Alphabet; 024 025import de.learnlib.algorithms.lstargeneric.table.ObservationTable; 026import de.learnlib.algorithms.lstargeneric.table.Row; 027import de.learnlib.api.MembershipOracle; 028 029/** 030 * Collection of predefined observation table closing strategies. 031 * 032 * @see ClosingStrategy 033 * 034 * @author Malte Isberner <malte.isberner@gmail.com> 035 * 036 */ 037public class ClosingStrategies { 038 039 /** 040 * Closing strategy that randomly selects one representative row to close from each equivalence 041 * class. 042 */ 043 public static final ClosingStrategy<Object,Object> CLOSE_RANDOM 044 = new CloseRandomStrategy(); 045 046 /** 047 * Closing strategy that selects the first row from each equivalence class as representative. 048 */ 049 public static final ClosingStrategy<Object,Object> CLOSE_FIRST 050 = new ClosingStrategy<Object,Object>() { 051 @Override 052 public <RI, RO> List<Row<RI>> selectClosingRows( 053 List<List<Row<RI>>> unclosedClasses, 054 ObservationTable<RI, RO> table, 055 MembershipOracle<RI, RO> oracle) { 056 List<Row<RI>> result = new ArrayList<Row<RI>>(unclosedClasses.size()); 057 for(List<Row<RI>> clazz : unclosedClasses) 058 result.add(clazz.get(0)); 059 return result; 060 } 061 }; 062 063 /** 064 * Closing strategy that selects the shortest row of each equivalence class (more precisely: 065 * a row which's prefix has minimal length in the respective class) as representative. 066 */ 067 public static final ClosingStrategy<Object,Object> CLOSE_SHORTEST 068 = new ClosingStrategy<Object,Object>() { 069 @Override 070 public <RI, RO> List<Row<RI>> selectClosingRows( 071 List<List<Row<RI>>> unclosedClasses, 072 ObservationTable<RI, RO> table, 073 MembershipOracle<RI, RO> oracle) { 074 075 List<Row<RI>> result = new ArrayList<Row<RI>>(); 076 for(List<Row<RI>> clazz : unclosedClasses) { 077 Row<RI> shortest = null; 078 int shortestLen = Integer.MAX_VALUE; 079 for(Row<RI> row : clazz) { 080 int prefixLen = row.getPrefix().length(); 081 if(shortest == null || prefixLen < shortestLen) { 082 shortest = row; 083 shortestLen = prefixLen; 084 } 085 } 086 result.add(shortest); 087 } 088 return result; 089 } 090 }; 091 092 /** 093 * Closing strategy that selects the lexicographically minimal row (wrt. its prefix) 094 * of each equivalence class as representative. 095 */ 096 public static final ClosingStrategy<Object,Object> CLOSE_LEX_MIN 097 = new ClosingStrategy<Object,Object>() { 098 @Override 099 public <RI, RO> List<Row<RI>> selectClosingRows( 100 List<List<Row<RI>>> unclosedClasses, 101 ObservationTable<RI, RO> table, 102 MembershipOracle<RI, RO> oracle) { 103 List<Row<RI>> result = new ArrayList<Row<RI>>(unclosedClasses.size()); 104 Alphabet<RI> alphabet = table.getInputAlphabet(); 105 for(List<Row<RI>> clazz : unclosedClasses) { 106 Row<RI> lexMin = null; 107 for(Row<RI> row : clazz) { 108 if(lexMin == null) 109 lexMin = row; 110 else if(CmpUtil.lexCompare(row.getPrefix(), lexMin.getPrefix(), alphabet) < 0) 111 lexMin = row; 112 } 113 result.add(lexMin); 114 } 115 return result; 116 } 117 }; 118 119}