CC-6 : Check if the input graph follows star structure.

Description:

A star graph has a central vertex and all other vertices are connected only to the central vertex. Check if the input graph follows the star structure.

Test cases and expected outputs:

Input Parameters	Expected outputs
Adjacency Matrix : 0,1,1,1, 1,0,0,0, 1,0,0,0, 1,0,0,0,	Check Star graph: true
Adjacency Matrix : 0,1,1,1, 1,0,0,0, 1,0,0,0, 0,0,0,0,	Check Star graph: false

Pseudocode:

The adjacencyMatrix of the graph is received as an input parameter.

Using the adjacencyMatrix iterate through all the vertices of the graph and count the number of other vertices it is connected to.

If the following conditions are fulfilled, the graph is a star graph:

Only one node (central node) should be connected to (vertices-1) nodes.

All other nodes should be connected to one node.

Code:

public class GraphCheckStar {
int vertices=0;

public GraphCheckStar(int vertices) {
	 this.vertices=vertices;
}

public boolean checkStarGraph(int[][] matrix){
	int vertexWithDegree1=0;
	int vertexWithDegreeN1=0;
	if (vertices==1)  {return true;}
	if ((vertices==2) && (matrix[0][1]==1) && (matrix[1][0]==1)) {
		return true;
	}
	for (int iIdx=0;iIdx < vertices; iIdx++) {
		int currDegree=0;
		for (int jIdx=0;jIdx < vertices; jIdx++) {
			if (matrix[iIdx][jIdx]==1) {
				currDegree++;
			}
		}
		if (currDegree==1) {vertexWithDegree1++;}
		if (currDegree==vertices-1) {vertexWithDegreeN1++;}
	}
	if ((vertexWithDegree1== vertices-1) && (vertexWithDegreeN1==1)) {
		return true;
	}else {	
		return false;	
	}
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class GraphCheckStar {
int vertices=0;

public GraphCheckStar(int vertices) {
	 this.vertices=vertices;
}

public boolean checkStarGraph(int[][] matrix){
	int vertexWithDegree1=0;
	int vertexWithDegreeN1=0;
	if (vertices==1)  {return true;}
	if ((vertices==2) && (matrix[0][1]==1) && (matrix[1][0]==1)) {
		return true;
	}
	for (int iIdx=0;iIdx < vertices; iIdx++) {
		int currDegree=0;
		for (int jIdx=0;jIdx < vertices; jIdx++) {
			if (matrix[iIdx][jIdx]==1) {
				currDegree++;
			}
		}
		if (currDegree==1) {vertexWithDegree1++;}
		if (currDegree==vertices-1) {vertexWithDegreeN1++;}
	}
	if ((vertexWithDegree1== vertices-1) && (vertexWithDegreeN1==1)) {
		return true;
	}else {	
		return false;	
	}
}

public static void print2dArray(int[][] intArray, String label) throws Exception {
	// Case 1: The input Array is null !!
    if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
    // Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	System.out.println();
	System.out.println("************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	boolean retVal;
	try {
	GraphCheckStar gph=new GraphCheckStar(4);
	int[][] matrix = {	{0,1,1,1},
						{1,0,0,0},	
						{1,0,0,0},
						{1,0,0,0}};
	print2dArray(matrix, "Edge Matrix" );
	retVal=gph.checkStarGraph(matrix);
	System.out.print("Check Star graph: "+ retVal);
	
	gph=new GraphCheckStar(4);
	int[][] matrix1 = {	{0,1,1,1},
						{1,0,0,0},	
						{1,0,0,0},
						{0,0,0,0}};
	print2dArray(matrix1, "Edge Matrix" );
	retVal=gph.checkStarGraph(matrix1);
	System.out.print("Check Star graph: "+ retVal);
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}