package signalFlowGraph;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class AnalyzeSFG {

	private int[][] adjMatrix;
	private int numberOfNodes;
	private String path = new String();
	private int forwardPathGain = 1;
	private int loopPathGain = 1;
	private ArrayList<String> loopsPath = new ArrayList<>();
	private ArrayList<String> forwardPath = new ArrayList<>();
	private ArrayList<Integer> forwardGains = new ArrayList<>();
	private ArrayList<Integer> loopsGains = new ArrayList<>();
	private ArrayList<Point> searchLoops = new ArrayList<>();

	public static void main(String[] args) {
		AnalyzeSFG g = new AnalyzeSFG();
		g.inputs();
		g.printMatrix();
		g.traverseForwardPath(0);
		// g.loops();
		g.print();
	}

	private void makeAllZeros(int[][] matrix) {
		for (int i = 0; i < matrix.length; i++)
			Arrays.fill(matrix[i], 0);
	}

	private void inputs() {
		Scanner scan = new Scanner(System.in);
		System.out.print("Enter The Number Of Nodes : ");
		numberOfNodes = scan.nextInt();
		adjMatrix = new int[numberOfNodes][numberOfNodes];
		makeAllZeros(adjMatrix);
		System.out.println("To Get Out From Entering Signal Flow Graph Representation");
		System.out.println("Put From = 0 ");
		while (true) {
			int from, to, gain;
			System.out.print("From : ");
			from = scan.nextInt() - 1;
			if (from < 0) {
				break;
			}
			System.out.print("To : ");
			to = scan.nextInt() - 1;
			System.out.print("gain : ");
			gain = scan.nextInt();
			adjMatrix[to][from] = gain;
		}
		addFinalNode();
	}

	private void printMatrix() {
		for (int i = 0; i < numberOfNodes; i++) {
			for (int j = 0; j < numberOfNodes; j++) {
				System.out.print(adjMatrix[i][j] + " ");
			}
			System.out.println();
		}

	}

	private void print() {
		for (int i = 0; i < this.forwardGains.size(); i++) {
			System.out.println(this.forwardGains.get(i));
			System.out.println(this.forwardPath.get(i));
		}
		for (int i = 0; i < this.loopsPath.size(); i++) {
			System.out.println(this.loopsPath.get(i));
		}
	}

	private int[][] copyMatrix(int[][] copyTo, int[][] copyFrom) {
		for (int i = 0; i < copyFrom.length; i++)
			for (int j = 0; j < copyFrom.length; j++)
				copyTo[i][j] = copyFrom[i][j];
		return copyTo;
	}

	private void addFinalNode() {
		boolean addColumn = false;
		for (int i = 0; i < this.adjMatrix.length; i++)
			if (this.adjMatrix[i][this.numberOfNodes - 1] != 0) {
				addColumn = true;
				break;
			}

		if (addColumn == true) {
			int newDimension = this.numberOfNodes + 1;
			int[][] copy = new int[newDimension][newDimension];
			makeAllZeros(copy);
			copy = copyMatrix(copy, adjMatrix);
			copy[newDimension - 1][newDimension - 2] = 1;
			adjMatrix = copy;
			this.numberOfNodes = newDimension;
		}
	}

	private void loops() {
		// searching for self loops
		for (int i = 0; i < numberOfNodes; i++) {
			if (adjMatrix[i][i] != 0) {
				String selfLoop = "x" + i + "x" + i;
				loopsPath.add(selfLoop);
				loopsGains.add(adjMatrix[i][i]);
			}
		}
		// finiding possible loops path
		for (int i = 1; i < numberOfNodes; i++) {
			for (int j = i - 1; j >= 0; j--) {
				if (adjMatrix[j][i] != 0) {
					// from i to j (reverse path) j <==== i
					Point x = new Point(j, i);
					searchLoops.add(x);
				}
			}
		}
		// search in the forwarc pathes for path from j to i
		// if found j ===> i then the is a loop j => i => j
		for (int i = 0; i < this.forwardPath.size(); i++) {
			String current = this.forwardPath.get(i);
			for (int j = 0; j < this.searchLoops.size(); j++) {
				int x = this.searchLoops.get(j).x;
				String from = "x" + x;
				if (current.contains(from)) {
					int y = this.searchLoops.get(j).y;
					String to = "x" + y;
					if (current.contains(to)) {
						// this is a loop we must calculate the gain and print
						// the loop path
						int start = current.lastIndexOf(from) - 1;
						int end = current.lastIndexOf(to);
						String loop = current.substring(start, end) + current.substring(start, start + 1);
						loopsPath.add(loop);
					}
				}
			}
		}

	}

	private void traverseForwardPath(int columnIndex) {

		if (isLastNode(columnIndex)) {
			addToForwardPath(columnIndex, 1);
			forwardPath.add(path);
			forwardGains.add(forwardPathGain);
			path = path.replace("x"+columnIndex, "");
			return;
		}

		int rowIndex = -1;
		rowIndex = getNextNode(rowIndex + 1, columnIndex);
		while (rowIndex != -1) {
			if (rowIndex < columnIndex) {
				rowIndex = getNextNode(rowIndex + 1, columnIndex);
				continue;
			}
			addToForwardPath(columnIndex, adjMatrix[rowIndex][columnIndex]);
			traverseForwardPath(rowIndex);
			removeFromForwardPath(columnIndex, adjMatrix[rowIndex][columnIndex]);
			rowIndex = getNextNode(rowIndex + 1, columnIndex);
		}
	}

	private void removeFromForwardPath(int currentNode, int gain) {
		String toBeRemoved = "x" + currentNode;
		if (path.contains(toBeRemoved))
			path = path.replace(toBeRemoved, "");
		forwardPathGain /= gain;

	}

	private void addToForwardPath(int currentNode, int gain) {
		path += "x" + currentNode;
		forwardPathGain *= gain;
	}

	private int getNextNode(int rowIndex, int columnIndex) {
		for (; rowIndex < this.numberOfNodes; rowIndex++)
			if (adjMatrix[rowIndex][columnIndex] != 0)
				return rowIndex;
		return -1;
	}

	private boolean isLastNode(int columnIndex) {
		for (int i = 0; i < this.numberOfNodes; i++)
			if (adjMatrix[i][columnIndex] != 0)
				return false;
		return true;
	}

}