Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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 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<>();
- private ArrayList<ArrayList<String>> nonTouchingLoopsPath = new ArrayList<>();
- private ArrayList<ArrayList<Integer>> nonTouchingLoopsGains = new ArrayList<>();
- private ArrayList<Integer> nonTouchedLoopsWithPathGains = new ArrayList<>();
- private Scanner scan;
- public static void main(String[] args) {
- AnalyzeSFG g = new AnalyzeSFG();
- g.inputs();
- g.printMatrix();
- g.traverseForwardPath(0);
- g.loops();
- g.nonTouchingLoops();
- g.print();
- // System.out.println("mason value = " + g.masonValue());
- }
- private void makeAllZeros(int[][] matrix) {
- for (int i = 0; i < matrix.length; i++)
- Arrays.fill(matrix[i], 0);
- }
- private void inputs() {
- 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() {
- System.out.println("Forward Paths");
- for (int i = 0; i < this.forwardGains.size(); i++) {
- System.out.println(this.forwardGains.get(i));
- System.out.println(this.forwardPath.get(i));
- }
- System.out.println("\nLoops");
- for (int i = 0; i < this.loopsPath.size(); i++) {
- System.out.println(this.loopsPath.get(i));
- System.out.println(this.loopsGains.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 int[] getLoopPathArray(String gainString) {
- gainString = gainString.substring(1, gainString.length()).replace("x", " ");
- String[] arrayString = gainString.split(" ");
- int[] array = new int[arrayString.length];
- for (int i = 0; i < arrayString.length; i++) {
- array[i] = Integer.parseInt(arrayString[i]);
- }
- return array;
- }
- private int getSimpleLoopGain(String gainString) {
- int[] array = getLoopPathArray(gainString);
- int column, row;
- int gain = 1;
- for (int i = 1; i < array.length; i++) {
- column = array[i - 1];
- row = array[i];
- gain *= adjMatrix[row][column];
- }
- return gain;
- // x1x2x3x4x1
- }
- private int getSimpleLoopGain(int[] array) {
- int column, row;
- int gain = 1;
- for (int i = 1; i < array.length; i++) {
- column = array[i - 1];
- row = array[i];
- gain *= adjMatrix[row][column];
- }
- return gain;
- // x1x2x3x4x1
- }
- 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]);
- }
- }
- // finding 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 forwardPathes 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);
- int end = current.lastIndexOf(to) + 1;
- String loop = current.substring(start, end + 1) + current.substring(start, start + 2);
- // Check that this loop isn't already taken
- boolean exist = false;
- for (int k = 0; k < this.loopsPath.size(); k++) {
- if (loop.equals(this.loopsPath.get(k))) {
- exist = true;
- }
- }
- if (!exist) {
- loopsPath.add(loop);
- loopsGains.add(getSimpleLoopGain(loop));
- }
- }
- }
- }
- }
- }
- private void nonTouchingLoops() {
- ArrayList<String> pathes = new ArrayList<>();
- ArrayList<Integer> gains = new ArrayList<>();
- // search for the two non-touching loops
- for (int i = 0; i < this.loopsPath.size(); i++) {
- pathes.add(loopsPath.get(i));
- gains.add(loopsGains.get(i));
- }
- this.nonTouchingLoopsPath.add(pathes);
- this.nonTouchingLoopsGains.add(gains);
- pathes = new ArrayList<>();
- gains = new ArrayList<>();
- for (int i = 0; i < this.nonTouchingLoopsPath.get(0).size(); i++) {
- for (int j = i + 1; j < this.nonTouchingLoopsPath.get(0).size(); j++) {
- if (!areTouching(this.nonTouchingLoopsPath.get(0).get(i), this.nonTouchingLoopsPath.get(0).get(j))) {
- String nonTouchingLoop = this.nonTouchingLoopsPath.get(0).get(i)
- + this.nonTouchingLoopsPath.get(0).get(j);
- int gain = this.nonTouchingLoopsGains.get(0).get(i) * this.nonTouchingLoopsGains.get(0).get(j);
- pathes.add(nonTouchingLoop);
- gains.add(gain);
- }
- }
- }
- if (pathes.size() > 0) {
- this.nonTouchingLoopsPath.add(pathes);
- this.nonTouchingLoopsGains.add(gains);
- }
- // search for more than two non touching loops
- int k = 1;
- while (nonTouchingLoopsPath.size() == k + 1) {
- pathes = new ArrayList<>();
- gains = new ArrayList<>();
- for (int i = 0; i < this.nonTouchingLoopsPath.get(k).size(); i++) {
- for (int j = 0; j < this.nonTouchingLoopsPath.get(k - 1).size(); j++) {
- if (!areTouching(this.nonTouchingLoopsPath.get(k).get(i),
- this.nonTouchingLoopsPath.get(k - 1).get(j))) {
- String nonTouchingLoop = this.nonTouchingLoopsPath.get(k).get(i)
- + this.nonTouchingLoopsPath.get(k - 1).get(j);
- int gain = this.nonTouchingLoopsGains.get(k).get(i)
- * this.nonTouchingLoopsGains.get(k - 1).get(j);
- pathes.add(nonTouchingLoop);
- gains.add(gain);
- }
- }
- }
- if (pathes.size() > 0) {
- this.nonTouchingLoopsPath.add(pathes);
- this.nonTouchingLoopsGains.add(gains);
- k++;
- } else {
- k++;
- }
- }
- // printing the nonTouched loops
- if (nonTouchingLoopsPath.size() > 1) {
- System.out.println("nonTouching");
- for (int i = 1; i < this.nonTouchingLoopsPath.size(); i++) {
- for (int j = 0; j < this.nonTouchingLoopsPath.get(i).size(); j++) {
- System.out.println(this.nonTouchingLoopsPath.get(i).get(j));
- System.out.println(this.nonTouchingLoopsGains.get(i).get(j));
- }
- }
- }
- }
- private void nonTouchingWithPathGain() {
- ArrayList<ArrayList<Integer>> nonTouchedLoopsWithPathGain = new ArrayList<>();
- ArrayList<Integer> gains;
- for (int i = 0; i < forwardPath.size(); i++) {
- gains = new ArrayList<>();
- for (int j = 0; j < this.nonTouchingLoopsPath.size(); j++) {
- int sum = 0;
- for (int k = 0; k < this.nonTouchingLoopsPath.get(j).size(); k++) {
- if (!areTouching(forwardPath.get(i), this.nonTouchingLoopsPath.get(j).get(k))) {
- sum += this.nonTouchingLoopsGains.get(j).get(k);
- }
- }
- gains.add(sum);
- }
- nonTouchedLoopsWithPathGain.add(gains);
- }
- for (int i = 0; i < nonTouchedLoopsWithPathGain.size(); i++) {
- int gainSum = 1;
- for (int j = 0; j < nonTouchedLoopsWithPathGain.get(i).size(); j++) {
- if (j % 2 == 0) {
- gainSum -= nonTouchedLoopsWithPathGain.get(i).get(j);
- } else {
- gainSum += nonTouchedLoopsWithPathGain.get(i).get(j);
- }
- }
- this.nonTouchedLoopsWithPathGains.add(gainSum);
- }
- }
- private double numerator() {
- nonTouchingWithPathGain();
- int numerator = 0;
- for (int i = 0; i < forwardPath.size(); i++) {
- numerator += this.forwardGains.get(i) * this.nonTouchedLoopsWithPathGains.get(i);
- }
- return numerator;
- }
- private double denominator() {
- // 1 - (sum gains individual) + (sum gain of two non touching)
- ArrayList<Integer> sumGains = new ArrayList<>();
- for (int i = 0; i < this.nonTouchingLoopsPath.size(); i++) {
- int sum = 0;
- for (int j = 0; j < this.nonTouchingLoopsPath.get(i).size(); j++) {
- sum += this.nonTouchingLoopsGains.get(i).get(j);
- }
- sumGains.add(sum);
- }
- int denominator = 1;
- for (int k = 0; k < sumGains.size(); k++) {
- if (k % 2 == 0) {
- denominator -= sumGains.get(k);
- } else {
- denominator += sumGains.get(k);
- }
- }
- return denominator;
- }
- private double masonValue() {
- return numerator() / denominator();
- }
- private boolean areTouching(String loopPath1, String loopPath2) {
- return compareTwoLoops(getLoopPathArray(loopPath1), getLoopPathArray(loopPath2));
- }
- private boolean compareTwoLoops(int[] loopPath1, int[] loopPath2) {
- for (int i = 0; i < loopPath1.length; i++)
- for (int j = 0; j < loopPath2.length; j++)
- if (loopPath1[i] == loopPath2[j])
- return true;
- return false;
- }
- 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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement