linaran
commented
5 years ago Hi,
Reduce and Irredundant phases rely on creating a matrix of ones and zeroes (BooleanMatrix) from a given Cover. I have to admit I no longer remember all the details but these phases require a lot of row/column removals. Each row/column removal is a linear operation (linear operation on a possible 2^n number of rows/columns) and to speed up these operations I simply decided to maintain a list of ignored rows/columns. In short, I do not delete a row or a column I ignore it. Someone using my class may not even be aware of it because indexes and iterations will adjust accordingly. When a matrix is fully ignored, that basically means it was completely deleted (by a combination of ignoring operations).
Be aware that the BooleanMatrix isn't representing a Boolean function. Cover is representing a Boolean function. BooleanMatrix is simply a Matrix generated from a given Cover using some generation rule (depending on what is needed).
Regarding maxClique functions, if a boolean matrix has the same number of rows and columns then it can represent a mathematical graph. Again, I don't remember all the details but at some point, I needed to take such a matrix and compute a maximum clique of that matrix (a very simple heuristic).
Be advised, Berkley University has an official implementation of the Espresso Algorithm in C++. In order to find it, you will need to dig around a bit but it should be available somewhere (binaries, not sure about the source).
I hope this helped you a bit.
Kind regards, Deni Munjas
On Fri, Feb 15, 2019 at 10:38 AM Edu Garcia notifications@github.com wrote:
Hello,
I know you mentioned you're done with this project, but maybe you can give me some input to be able to fix this issue. When using the Espresso minimizer and the following input:
4 1 0000 4 1000 4 0100 4 1100 4 0010 4 1010 4 0110 4 1110 4 0001 4 1001 4 0101 4 1101 4 0011 4 1011 4 1111 4
...a StackOverflowError is thrown:
Exception in thread "main" java.lang.StackOverflowError at espresso.minimizers.espressoMinimizer.utils.BooleanMatrix.getColumnCount(BooleanMatrix.java:120) at espresso.minimizers.espressoMinimizer.utils.BooleanMatrix.getTrueRowCount(BooleanMatrix.java:165) at espresso.minimizers.espressoMinimizer.irredundant.IndependencyMatrix.rowIndexWithMaxTrueCount(IndependencyMatrix.java:57) at espresso.minimizers.espressoMinimizer.irredundant.IndependencyMatrix.computeMaxClique(IndependencyMatrix.java:21) at espresso.minimizers.espressoMinimizer.minColCover.MaxCliqueHeuristic.calculateMinimumColumnCover(MaxCliqueHeuristic.java:24) at espresso.minimizers.espressoMinimizer.minColCover.MaxCliqueHeuristic.calculateMinimumColumnCover(MaxCliqueHeuristic.java:48) at espresso.minimizers.espressoMinimizer.minColCover.MaxCliqueHeuristic.calculateMinimumColumnCover(MaxCliqueHeuristic.java:48) ...
Do you have any idea of what the problem might be? Or can you explain what the MaxCliqueHeuristic class is supposed to be doing, and what does it entail for a matrix to be "fully ignored"?
From what I see, the offending code is trying to check if a matrix is "fully ignored", and said matrix has the columns "0,0,0,0", with an ignored column set of "0". The check to fully ignored is checking the size of both (and of the rows), but that will never be the same because the set will always be of size 1 in this situation, and the columns are always going to be of size 4. I guess this is the issue, as I fail to see when this comparison will ever be true, but it will be nice if you can confirm that.
Thanks in advance.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/linaran/EspressoMinimizer/issues/1, or mute the thread https://github.com/notifications/unsubscribe-auth/AHCTspols6XGLofP1VkcRPJN_inphYNwks5vNoAagaJpZM4a9Rz6 .
Arcnor
Hello,
I know you mentioned you're done with this project, but maybe you can give me some input to be able to fix this issue. When using the Espresso minimizer and the following input:
...a StackOverflowError is thrown:
Do you have any idea of what the problem might be? Or can you explain what the
MaxCliqueHeuristicclass is supposed to be doing, and what does it entail for a matrix to be "fully ignored"?From what I see, the offending code is trying to check if a matrix is "fully ignored", and said matrix has the columns "0,0,0,0", with an ignored column set of "0". The check to fully ignored is checking the size of both (and of the rows), but that will never be the same because the set will always be of size 1 in this situation, and the columns are always going to be of size 4. I guess this is the issue, as I fail to see when this comparison will ever be true, but it will be nice if you can confirm that.
Thanks in advance.