A graph is specified as follows First ask the user to input

A graph is specified as follows. First ask the user to input a number n. This is the number of vertices - the vertices are numbered 1, 2, ..., n. Now, ask the user the enter the number m - this is the number of edges. Now ask the user to enter the edge data, m times. For example you can ask the user to enter one endpoint, followed by the question to enter the second endpoint. For example the user could enter n = 4, m = 3 and the edges as between (1, 3), (2.3), (4, 3). Once this is done, output the following: Output the adjacency list representation of the graph in the format, v: v_1v_2... v_k one per line for each vertex v. For example from the graph above the output will be: 1: 3 2: 3 3:124 4: 3 Output the adjacency matrix representation of the graph as a matrix of 0\'s and 1\'s where row i corresponds to vertex i and column i also corresponds to vertex i. For example, for the graph above your code should output: 0 0 10 0 0 10 110 1 0 0 10 Count the number of triangles in G. A triangle is a set of 3 vertices which are all adjacent to each other. For example, for the graph above the answer should be 0. Make your algorithm as fast as possible - give an estimate of its running time as a function of n, m (or other parameters of the graph): you may output this sis a final sentence after your answer. For example you could answer: The graph has 0 triangles The running time is 0(n * n)

Solution

For the given set of problems, we will represent the Graph in adjacency matrix format. And will storee the data in it by taking input from user (described in comments section of code below).

Once the graph is in adjacency Matrix fromat, we can simply get the adjacency list format by using loops for each row of adjacency matrix.

In order to find the number of triangles, we can take the cube of the asjacency Matrix, then find the trace of the cube of adjacency matrix(which is sum of diagonal elements), and divide it by 6.

The code for the given set of problems is as follows. The code is written in java -

import java.io.BufferedReader;
import java.io.InputStreamReader;

class TestClass {
static int[][] arr,arr1,buf;
  
  
private static void edgeData(int edge) //Taking input for Edge Data
{
int a=0,b=0;
  
for(int i=1;i<=edge;i++)
{
System.out.println(\"Enter First Endpoint\");
a=Integer.parseInt(br.readLine());
  
System.out.println(\"Enter Second Endpoint\");
b=Integer.parseInt(br.readLine());
  
arr[a-1][b-1]=1; // Saving data in Adjacency Matrix Format for faster application of algorithms
}
}
  
private static void adjacencyList() // Printing the Adjacency list Representation
{
for(int i=0;i<n;i++)
{
System.out.print((i+1)+\" :\");
for(int j=0;j<n;j++)
{
if(arr[i][j]==1)
System.out.print(\" \"+(j+1));
}
System.out.println(\"\"); // changing lines
}
}
  
private static void adjacencyMatrix() // Printing the Adjacency Matrix Representation
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
System.out.print(arr[i][j]+\" \");
}
System.out.println(\"\");
}
}
  
private void matMul(int[][] X, int[][] Y, int[][] Z) // Matrix Multipication
{
int aa=X.length;
for (int i = 0; i < aa; i++)
{
for (int j = 0; j < aa; j++)
{
Z[i][j] = 0;
for (int k = 0; k < aa; k++)
Z[i][j] += X[i][k]*Y[k][j];
}
}
}
  
private int trace(int[][] X)
{
int ret=0;
  
for(int i=0;i<X.length;i++)
{
ret=ret+X[i][i];
}
  
return ret;
}
  
  
public static void main(String args[] ) throws Exception {
  
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
int n=0,m=0,tr=0;
  
System.out.println(\"Enter Number of Vertices\");
n=Integer.parseInt(br.readLine());
  
System.out.println(\"Enter Number of Edges\");
m=Integer.parseInt(br.readLine());
  
arr=new int[n][n]; // will use array from index 1.
  
arr1=new int[n][n]; // will store cube of matrix
  
buf=new int[n][n];
  
edgeData(m); // takig edgedata for m edges
  
adjacencyList(); //Printing Adjacency list
  
adjacencyMatrix(); //Printing Adjacency Matrix
  
matMul(arr,arr,buf);
  
matMul(arr,buf,arr1); // arr1 will store cube of adjacency matrix matrix
  
tr=trace(arr1);
  
System.out.println(\"The Graph has\"+(tr/6)+\"triangles\"); // Number of triangles is (1/6)th of the trace of the cube of adjacency matrix
System.out.println(\"Running Time is O(n*n)\");
}
}