Find Transitive relations in a graph represented via adjacency matrix using Java....

Problem:-Using the Java language, have the function TransitivityRelations(strArr) read the strArr parameter being passed which will make up an NxN matrix where the rows are separated by each pair of parentheses (the matrix will range from 2x2 to 5x5). The matrix represents connections between nodes in a graph where each node corresponds to the Nth element in the matrix (with 0 being the first node). If a connection exists from one node to another, it will be represented by a 1, if not it will be represented by a 0. For example: suppose strArr were a 3x3 matrix with input 

["(1,1,1)","(1,0,0)","(0,1,0)"], this means that there is a connection from node 0->0, 0->1, and 0->2. For node 1 the connections are 1->0, and for node 2 the connections are 2->1. This can be interpreted as a connection existing from node X to node Y if there is a 1 in the Xth row and Yth column. Note: a connection from X->Y does not imply a connection from Y->X. 

What your program should determine is whether or not the matrix, which represents connections among the nodes, is transitive. A transitive relationmeans that if the connections 0->1 and 1->2 exist for example, then there must exist the connection 0->2. More generally, if there is a relation xRy and yRz, then xRz should exist within the matrix. If a matrix is completely transitive, return the string transitive. If it isn't, your program should return the connections needed, in the following format, in order for the matrix to be transitive: (N1,N2)-(N3,N4)-(...). So for the example above, your program should return (1,2)-(2,0). You can ignore the reflexive property of nodes in your answers. Return the connections needed in lexicographical order [e.g. (0,1)-(0,4)-(1,4)-(2,3)-(4,1)]. 

Note:-This program is only for 3x3 matrix ,but you can extend to a program generic for any size matrix .

here is the code for it .....

       

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Transitive {

 public static void main(String[] args) throws Exception {
  // TODO Auto-generated method stub

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String matrix = br.readLine();
  //String mat="[\"(1,1,1)\",\"(1,1,1)\",\"(1,1,0)\"]";
  System.out.println("the desired result is " + TransitiveRelations(matrix));

 }

 public static ArrayList < String > TransitiveRelations(String strArr) {

  int[][] mat = new int[3][3];

  ArrayList < String > aka = new ArrayList < String > ();
  String[] arr = strArr.split("\\)");

  String[] a1 = arr[0].split("\\(");
  String[] a2 = arr[1].split("\\(");
  String[] a3 = arr[2].split("\\(");

  String[] r1 = a1[1].split(",");
  String[] r2 = a2[1].split(",");
  String[] r3 = a3[1].split(",");

  for (int k = 0; k < 3; k++)
   mat[0][k] = Integer.parseInt(r1[k]);


  for (int s = 0; s < 3; s++)
   mat[1][s] = Integer.parseInt(r2[s]);


  for (int p = 0; p < 3; p++)
   mat[2][p] = Integer.parseInt(r3[p]);


  for (int h = 0; h < 3; h++) {
   for (int q = 0; q < 3; q++) {
    for (int e = 0; e < 3; e++) {
     if (h != q) {
      if (mat[h][e] == 1) {
       if (mat[e][q] == 1) {
        if (mat[h][q] == 1)
         continue;
        else aka.add(h + "-" + q);
       } else {
        aka.add(e + "-" + q);
        if (mat[h][q] == 1)
         continue;
        else aka.add(h + "-" + q);
       }
      } else {
       aka.add(h + "-" + e);
       if (mat[e][q] == 1) {
        if (mat[h][q] == 1)
         continue;
        else aka.add(h + "-" + q);
       } else {
        aka.add(e + "-" + q);
        if (mat[h][q] == 1)
         continue;
        else aka.add(h + "-" + q);

       }
      }
     }

    }
   }
  }
  ArrayList < String > a = new ArrayList < String > ();
  for (int t = 0; t < aka.size(); t++)
   if (!a.contains(aka.get(t)) == true)
    a.add(aka.get(t));

  return a;
 }

}
       
 

Find out minimum cost between two nodes in a weighted graph using greedy approach using java.....

Input :- 1.cost matrix for the graph is given via text file ,just write the matrix in the text file simply like we write normally and save it ,change the path of the file in the program too.

2.For those nodes which don't have direct paths between them corresponding entries in the input adjacency matrix via file should be "-1".
here is the code  ........

       
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ShortestPath {
 public static int count = 0;
 public static int[][] matrix;

 public static void main(String[] args) throws NumberFormatException, IOException {
  // TODO Auto-generated method stub
  File file = new File("C:/Users/gauravy/Desktop/matrix.txt");
  BufferedReader be = new BufferedReader(new FileReader(file));
  while ((be.readLine()) != null)
   count++;
  matrix = new int[count][count];
  String fileName = "C:/Users/gauravy/Desktop/matrix.txt";

  FileInputStream inputStream = new FileInputStream(fileName);
  BufferedReader bf = new BufferedReader(new InputStreamReader(inputStream));

  int lineCount = 0;
  String[] numbers;
  String line = null;
  while ((line = bf.readLine()) != null) {
   numbers = line.split(" ");
   for (int i = 0; i < count; i++) {
    matrix[lineCount][i] = Integer.parseInt(numbers[i]);
   }

   lineCount++;
  }
  bf.close();
  for (int l = 0; l < count; l++)
   for (int s = 0; s < count; s++)
    if (matrix[l][s] == -1) matrix[l][s] = Integer.MAX_VALUE;

  System.out.println("Minimum cost which we evaluated is " + minPath(matrix, 3, count - 1));
 }
 public static int minPath(int[][] mat, int i, int j) {
  int cost;
  if (i == j) return 0;
  else {
   int y = getNodeWithMinDistance(i);
   cost = matrix[i][y] + minPath(mat, y, j);
   if (cost < mat[i][j]) return cost;
   else return mat[i][j];
  }
 }

 public static int getNodeWithMinDistance(int source) {
  int min = matrix[source][source + 1];
  int minNeighbourNode = source + 1;
  for (int k = source + 1; k < count; k++) {
   if (matrix[source][k] < min) {
    min = matrix[source][k];
    minNeighbourNode = k;
   }
  }
  return minNeighbourNode;
 }
}