ConflictReducer Java

package aim4.util;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

public class ConflictReducer {

protected boolean MultiSolutionsSupported;
public int conflictMatrix[][];
public int n;

public int conflictReduced[][];
public int conflictCounter[];
public int confirmed[];

public HashMap<ArrayList<Integer>, Integer> confirmedSeqSet;
public int nConfirmedMaxCurr;
public HashMap<Long, Integer> visited;

public ConflictReducer(int conflictMatrix[][], int n) {
this.MultiSolutionsSupported = true;
this.conflictMatrix = conflictMatrix;
this.n = n;
}

private void init() {
this.conflictReduced = new int[n][n];
this.conflictCounter = new int[n];
this.confirmed = new int[n];
this.confirmedSeqSet = new HashMap<ArrayList<Integer>, Integer>();
this.nConfirmedMaxCurr = 0;
this.visited = new HashMap<Long, Integer>();

for (int i = 0; i < n; i++) {
this.conflictCounter[i] = 0;
this.confirmed[i] = 1;
for (int j = 0; j < n; j++) {
this.conflictReduced[i][j] = 0;
if (this.conflictMatrix[i][j] > 0) {
this.conflictCounter[i] += 1;
}
}

}

}

private ArrayList<Integer> findRowsConflictMax() {
ArrayList<Integer> rows = new ArrayList<Integer>();
int conflictMax = 0;
for (int i = 0; i < n; i++) {
if (conflictCounter[i] > conflictMax) {
conflictMax = conflictCounter[i];
}
}
for (int i = 0; i < n; i++) {
if (conflictCounter[i] > 0 && conflictCounter[i] == conflictMax) {
rows.add(i);
}
}
return MultiSolutionsSupported? rows: (rows.size() > 0? new ArrayList<Integer>(rows.subList(0, 1)): rows);
}

private HashMap<ArrayList<Integer>, Integer> filterInvalidSeq() {
Iterator<ArrayList<Integer>> iter =
confirmedSeqSet.keySet().iterator();
int nConfirmedMax = 0;
while (iter.hasNext()) {
ArrayList<Integer> seq = iter.next();
int size = confirmedSeqSet.get(seq);
if (size > nConfirmedMax) {
nConfirmedMax = size;
}
}
HashMap<ArrayList<Integer>, Integer> filteredSeqSet =
new HashMap<ArrayList<Integer>, Integer>();
iter = confirmedSeqSet.keySet().iterator();
while (iter.hasNext()) {
ArrayList<Integer> seq = iter.next();
int size = confirmedSeqSet.get(seq);
if (size == nConfirmedMax) {
filteredSeqSet.put(seq, size);
}
}
return filteredSeqSet;
}

private ArrayList<Integer> findConfirmedSeq() {
ArrayList<Integer> confirmedSeq = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
if (confirmed[i] > 0) {
confirmedSeq.add(i);
}
}
return confirmedSeq;
}

private ArrayList<Integer> findRemainingSeq() {
ArrayList<Integer> remainingSeq = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
if (confirmed[i] > 0) {
remainingSeq.add(i);
}
}
return remainingSeq;
}

private boolean conflictReduceDone(ArrayList<Integer> rowsConflictMax) {
for (int i = 0; i < n; i++) {
if (conflictCounter[i] > 0) {
return false;
}
}
return rowsConflictMax.isEmpty();
}

private ArrayList<int[]> reduceRow(int row) {
ArrayList<int[]> reducedRowCells = new ArrayList<int[]>();
for (int j = 0; j < n; j++) {
int conflict = conflictMatrix[row][j];
int reduced = conflictReduced[row][j];
if (reduced <= 0) {
int tuple[] = new int[3];
tuple[0] = row;
tuple[1] = j;
tuple[2] = conflict;
reducedRowCells.add(tuple);
conflictReduced[row][j] = 1;
if (conflict > 0) {
conflictCounter[row] -= 1;
assert conflictCounter[row] >= 0;
}
}
}
return reducedRowCells;
}

private ArrayList<int[]> reduceCol(int col) {
ArrayList<int[]> reducedColCells = new ArrayList<int[]>();
for (int i = 0; i < n; i++) {
int conflict = conflictMatrix[i][col];
int reduced = conflictReduced[i][col];
if (reduced <= 0) {
int tuple[] = new int[3];
tuple[0] = i;
tuple[1] = col;
tuple[2] = conflict;
reducedColCells.add(tuple);
conflictReduced[i][col] = 1;
if (conflict > 0) {
conflictCounter[i] -= 1;
assert conflictCounter[i] >= 0;
}
}
}
return reducedColCells;

}

private void recovRow(ArrayList<int[]> reducedRowCells) {
int size = reducedRowCells.size();
for (int i = 0; i < size; i++) {
int[] tuple = reducedRowCells.get(i);
int row = tuple[0];
int col = tuple[1];
int conflict = tuple[2];
conflictReduced[row][col] = 0;
if (conflict > 0) {
conflictCounter[row] += 1;
assert conflictCounter[row] <= n;
}
}
}

private void recovCol(ArrayList<int[]> reducedColCells) {
int size = reducedColCells.size();
for (int i = 0; i < size; i++) {
int[] tuple = reducedColCells.get(i);
int row = tuple[0];
int col = tuple[1];
int conflict = tuple[2];
conflictReduced[row][col] = 0;
if (conflict > 0) {
conflictCounter[row] += 1;
assert conflictCounter[row] <= n;
}
}
}

private boolean reducedRow(int row) {
return confirmed[row] == 0;
}

private boolean conflictSaturated(int nRemainingRows) {
for (int i = 0; i < n; i++) {
if (reducedRow(i)) {
continue;
}
if (conflictCounter[i] != nRemainingRows - 1) {
return false;
}
}
return true;
}

private long getSearchingStat() {
long retval = 0L;
for (int i = 0; i < n; i++) {
retval = (retval<<1) + confirmed[i];
}
return retval;
}

public void conflictReduce() {
ArrayList<Integer> remainingRows = findRemainingSeq();
int nRemainingRows = remainingRows.size();
if (conflictSaturated(nRemainingRows)) {
for (int i = 0; i < nRemainingRows; i++) {
ArrayList<Integer> seq = new ArrayList<Integer>();
seq.add(remainingRows.get(i));
if (!confirmedSeqSet.containsKey(seq)) {
confirmedSeqSet.put(seq, 1);
}
}
return;
}

if (nRemainingRows < nConfirmedMaxCurr) {
return;
}

ArrayList<Integer> rowsConflictMax = findRowsConflictMax();
if (conflictReduceDone(rowsConflictMax)) {
ArrayList<Integer> confirmedSeq = findConfirmedSeq();
int size = confirmedSeq.size();
if (!confirmedSeqSet.containsKey(confirmedSeq)) {
confirmedSeqSet.put(confirmedSeq, size);
}
if (size > nConfirmedMaxCurr) {
nConfirmedMaxCurr = size;
}
return;
}

int nRowsConflictMax = rowsConflictMax.size();
for (int i = 0; i < nRowsConflictMax; i++) {
int row = rowsConflictMax.get(i);
int col = rowsConflictMax.get(i);
confirmed[row] = 0;

long stat = getSearchingStat();
if (visited.containsKey(stat)){
confirmed[row] = 1;
continue;
}
ArrayList<int[]> reducedRowCells = reduceRow(row);
ArrayList<int[]> reducedColCells = reduceCol(col);
visited.put(stat, 1);

conflictReduce();

confirmed[row] = 1;
recovRow(reducedRowCells);
recovCol(reducedColCells);

}

}

public ArrayList<Integer> work() {
ArrayList<Integer> seq = new ArrayList<Integer>();
if (n <= 0) {
return seq;
}
init();
conflictReduce();
HashMap<ArrayList<Integer>, Integer> filteredSeqSet =
filterInvalidSeq();
Iterator<ArrayList<Integer>> iter =
filteredSeqSet.keySet().iterator();
/*
while (iter.hasNext()) {
seq = iter.next();
for (int i = 0; i < seq.size() - 1; i++) {
System.out.print(seq.get(i)+" ");
}
System.out.println(seq.get(seq.size()-1));
}
*/
if (iter.hasNext()) {
seq = iter.next();
}
return seq;

}

public static void main(String args[]) {
int conflictMatrix[][] = {
{0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0}
};
int n = 20;
ConflictReducer conflictReducer = new ConflictReducer(conflictMatrix, n);
conflictReducer.work();

}

}

AllStuffON

ConflictReducer Java

Learn More :

AllStuffON

ConflictReducer Java

Learn More :

Share this