Verbose minim

alib2algo/src/automaton/simplify/Minimize.cpp

@@ -9,6 +9,8 @@
#include <map>
#include <set>
+#include <iomanip>
+#include <sstream>
#include <alphabet/Symbol.h>
@@ -16,6 +18,8 @@
#include <automaton/Automaton.h>
+#include <common/GlobalData.h>
+
namespace automaton {
namespace simplify {
@@ -47,11 +51,14 @@ automaton::DFA Minimize::minimize(const automaton::DFA& dfa) {
std::map<automaton::State, automaton::State> toEquvivalentStates2;
std::map<std::pair<automaton::State, std::set<std::pair<alphabet::Symbol, automaton::State> > >, std::set<automaton::State> > minimizedTransitionFunction2;
+	const automaton::State *firstFinal = NULL, *firstNonfinal = NULL;
for(auto iter = dfa.getStates().begin(); iter != dfa.getStates().end(); iter++) {
if(dfa.getFinalStates().count(*iter) == 0) { // not a final state
-			toEquvivalentStates2.insert(std::pair<automaton::State, automaton::State>(*iter, automaton::State(0)));
+			if(!firstNonfinal) firstNonfinal = &(*iter);
+			toEquvivalentStates2.insert(std::pair<automaton::State, automaton::State>(*iter, *firstNonfinal));
} else {
-			toEquvivalentStates2.insert(std::pair<automaton::State, automaton::State>(*iter, automaton::State(1)));
+			if(!firstFinal) firstFinal = &(*iter);
+			toEquvivalentStates2.insert(std::pair<automaton::State, automaton::State>(*iter, *firstFinal));
}
}
@@ -71,6 +78,13 @@ automaton::DFA Minimize::minimize(const automaton::DFA& dfa) {
minimizedTransitionFunction2[key].insert(iter->first);
}
+	size_t delta_iter = 0;
+
+	if(common::GlobalData::verbose) {
+		print_progress(dfa, minimizedTransitionFunction2, delta_iter);
+	}
+	delta_iter += 1;
+
do {
toEquvivalentStates1 = toEquvivalentStates2;
minimizedTransitionFunction1 = minimizedTransitionFunction2;
@@ -81,7 +95,8 @@ automaton::DFA Minimize::minimize(const automaton::DFA& dfa) {
int number = 0;
for(auto iter = minimizedTransitionFunction1.begin(); iter != minimizedTransitionFunction1.end(); iter++) {
for(auto iter2 = iter->second.begin(); iter2 != iter->second.end(); iter2++) {
-				toEquvivalentStates2.insert(std::pair<automaton::State, automaton::State>(*iter2, automaton::State(number)));
+				//toEquvivalentStates2.insert(std::pair<automaton::State, automaton::State>(*iter2, automaton::State(number)));
+				toEquvivalentStates2.insert(std::pair<automaton::State, automaton::State>(*iter2, *(iter->second.begin())));
}
number++;
}
@@ -103,6 +118,11 @@ automaton::DFA Minimize::minimize(const automaton::DFA& dfa) {
minimizedTransitionFunction2[key].insert(iter->first);
}
+		if(common::GlobalData::verbose) {
+			print_progress(dfa, minimizedTransitionFunction2, delta_iter);
+		}
+		delta_iter += 1;
+
} while(minimizedTransitionFunction1.size() != minimizedTransitionFunction2.size());
const automaton::State* initialState = NULL;
@@ -133,6 +153,95 @@ automaton::DFA Minimize::minimize(const automaton::DFA& dfa) {
return result;
}
+#define RESETSS(x) {(x).clear(); (x).str("");}
+
+void Minimize::print_progress(const automaton::DFA& dfa, const std::map<std::pair<automaton::State, std::set<std::pair<alphabet::Symbol, automaton::State> > >, std::set<automaton::State> > minimizedTransitionFunction, size_t iter) {
+	std::clog << "delta " << iter << std::endl;
+
+	//std::map<std::pair<automaton::State, std::set<std::pair<alphabet::Symbol, automaton::State> > >, std::set<automaton::State> > minimizedTransitionFunction1; //mapped to the original state
+
+	/* need to restruct this first so we have table like:	orig state | new state | trans_symb_1 | trans_symb_2 | ... | trans_symb_n */
+	// we surely have DFA here (transition map hence)
+	std::map<std::pair<automaton::State, automaton::State>, std::map<alphabet::Symbol, automaton::State>> printMap;
+	for(const auto& kv: minimizedTransitionFunction) {
+		for(const auto& state : kv.second) {
+			std::map<alphabet::Symbol, automaton::State> stateTransMap;
+			for(const auto& transition : kv.first.second) {
+				stateTransMap.insert(std::make_pair(transition.first, transition.second));
+			}
+			printMap.insert(std::make_pair(std::make_pair(state, kv.first.first), stateTransMap));
+		}
+	}
+
+	size_t stateWidth = 1, stateMapWidth = 1;
+	std::map<alphabet::Symbol, size_t> colWidths;
+	std::ostringstream ss;
+
+	for(const alphabet::Symbol& symbol : dfa.getInputAlphabet()) {
+		ss << symbol;
+		colWidths[symbol] = ss.str().size();
+		RESETSS(ss);
+	}
+	for(const auto& kv : printMap) {
+		ss << kv.first.first;
+		stateWidth = std::max(stateWidth, ss.str().size());
+		RESETSS(ss);
+
+		ss << kv.first.second;
+		stateMapWidth = std::max(stateMapWidth, ss.str().size());
+		RESETSS(ss);
+
+		for(const alphabet::Symbol& symbol : dfa.getInputAlphabet()) {
+			auto it = kv.second.find(symbol);
+			if(it != kv.second.end())
+			{
+				ss << it -> second;
+				colWidths[symbol] = std::max(colWidths[symbol], ss.str().size());
+				RESETSS(ss);
+			}
+		}
+	}
+
+	std::clog << std::setw(stateWidth) << "";
+	std::clog << " | ";
+	std::clog << std::setw(stateMapWidth) << "";
+	std::clog << " | ";
+	for(const alphabet::Symbol& symbol : dfa.getInputAlphabet()) {
+		ss << symbol;
+		std::clog << std::setw(colWidths[symbol]) << ss.str() << " | ";
+		RESETSS(ss);
+	}
+	std::clog << std::endl;
+	for(const auto& kv : printMap) {
+		ss << kv.first.first;
+		std::clog << std::setw(stateWidth) << ss.str() << " | ";
+		RESETSS(ss);
+
+		ss << kv.first.second;
+		std::clog << std::setw(stateMapWidth) << ss.str() << " | ";
+		RESETSS(ss);
+
+		for(const auto& symbol : dfa.getInputAlphabet()) {
+			auto it = kv.second.find(symbol);
+			if(it != kv.second.end())
+			{
+				ss << it -> second;
+				std::clog << std::setw(colWidths[symbol]) << ss.str();
+				RESETSS(ss);
+			}
+			else
+			{
+				std::clog << std::setw(colWidths[symbol]) << "";
+			}
+			std::clog << " | ";
+		}
+		std::clog << std::endl;
+	}
+	std::clog << std::endl;
+}
+
+
+
auto MinimizeNFA = Minimize::RegistratorWrapper<automaton::DFA, automaton::DFA>(Minimize::getInstance(), Minimize::minimize);
} /* namespace simplify */