Java Program to Find Number of Articulation Points in a Graph

«
»
This Java program is to find number of articulation points in graph. A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components.

Here is the source code of the Java program to find number of articulation points in graph. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.HashSet;
  2. import java.util.InputMismatchException;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6. import java.util.Set;
  7. import java.util.Stack;
  8.  
  9. public class NumberOfArticulationPoints
  10. {
  11.     private Stack<Integer> stack;
  12.     private int numberOfNodes;
  13.     private Set<Integer> articulationPoints;
  14.     private int[] parent;
  15.     private int[] visited;
  16.     private int[][] adjacencyMatrix;
  17.  
  18.     public NumberOfArticulationPoints(int numberOfNodes)
  19.     {
  20.         this.numberOfNodes = numberOfNodes;
  21.         this.stack = new Stack<Integer>();
  22.         this.articulationPoints = new HashSet<Integer>();
  23.         this.parent = new int[numberOfNodes + 1];
  24.         this.visited = new int[numberOfNodes + 1];
  25.         this.adjacencyMatrix = new int[numberOfNodes + 1][numberOfNodes + 1];
  26.     }
  27.  
  28.     public int numberOfArticulationPoint(int adjacencyMatrix[][], int source)
  29.     {
  30.         int children = 0;
  31.         int element, destination;
  32.         stack.push(source);
  33.         visited[source] = 1;
  34.  
  35.         for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)
  36.         {
  37.             for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)
  38.             {
  39.                 this.adjacencyMatrix[sourceVertex][destinationVertex]
  40.                      = adjacencyMatrix[sourceVertex][destinationVertex];
  41.             }
  42.         }
  43.  
  44.         while (!stack.isEmpty())
  45.         {
  46.             element = stack.peek();
  47.             destination = element;
  48.             while (destination <= numberOfNodes)
  49.             {
  50.                 if (this.adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)
  51.                 {
  52.                     stack.push(destination);
  53.                     visited[destination] = 1;
  54.                     parent[destination] = element;
  55.                     if (element == source)
  56.                     {
  57.                         children++;
  58.                     }
  59.                     if (!isLeaf(this.adjacencyMatrix, destination))
  60.                     {
  61.                         if (children > 1)
  62.                         {
  63.                             articulationPoints.add(source);
  64.                         }
  65.                         if (isArticulationPoint(this.adjacencyMatrix, destination))
  66.                         {
  67.                             articulationPoints.add(destination);
  68.                         }
  69.                     }
  70.                     element = destination;
  71.                     destination = 1;
  72.                     continue;
  73.                 }
  74.                 destination++;
  75.             }
  76.             stack.pop();
  77.         }
  78.         return articulationPoints.size();
  79.     }
  80.  
  81.     private boolean isArticulationPoint(int adjacencyMatrix[][], int root)
  82.     {
  83.         int explored[] = new int[numberOfNodes + 1];
  84.         Stack<Integer> stack = new Stack<Integer>();
  85.         stack.push(root);
  86.         int element = 0, destination = 0;
  87.  
  88.         while (!stack.isEmpty())
  89.         {
  90.             element = stack.peek();
  91.             destination = 1;
  92.             while (destination <= numberOfNodes)
  93.             {
  94.                 if ( element != root)
  95.                 {
  96.                     if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1)
  97.                     {
  98.                         if (this.stack.contains(destination))
  99.                         {
  100.                             if (destination <= parent[root])
  101.                             {
  102.                                 return false;
  103.                             }
  104.                             return true;
  105.                         }
  106.                     } 
  107.                 }
  108.                 if ((adjacencyMatrix[element][destination] == 1 && explored[destination] == 0 )
  109.                             && visited[destination] == 0)
  110.                 {
  111.                     stack.push(destination);
  112.                     explored[destination] = 1;
  113.                     adjacencyMatrix[destination][element] = 0;
  114.                     element = destination;
  115.                     destination = 1;
  116.                     continue;
  117.                 }
  118.                 destination++;
  119.             }
  120.             stack.pop();
  121.         }	
  122.         return true;
  123.     }
  124.  
  125.     private boolean isLeaf(int adjacencyMatrix[][], int node)
  126.     {
  127.         boolean isLeaf = true;
  128.         for (int vertex = 1; vertex <= numberOfNodes; vertex++)
  129.         {
  130.             if (adjacencyMatrix[node][vertex] == 1 && visited[vertex] == 1)
  131.             {
  132.                  isLeaf = true;
  133.             }else if (adjacencyMatrix[node][vertex] == 1 && visited[vertex] == 0)
  134.             {
  135.                  isLeaf = false;
  136.                  break;
  137.             }
  138.         }
  139.         return isLeaf;
  140.     }
  141.  
  142.     public static void main(String... arg)
  143.     {
  144.         int number_of_nodes, source;
  145.         Scanner scanner = null;
  146.         try
  147.         {
  148.  
  149.             System.out.println("Enter the number of nodes in the graph");
  150.             scanner = new Scanner(System.in);
  151.             number_of_nodes = scanner.nextInt();
  152.  
  153.             int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  154.             System.out.println("Enter the adjacency matrix");
  155.             for (int i = 1; i <= number_of_nodes; i++)
  156.                 for (int j = 1; j <= number_of_nodes; j++)
  157.                     adjacency_matrix[i][j] = scanner.nextInt();
  158.  
  159.             System.out.println("Enter the source for the graph");
  160.             source = scanner.nextInt();
  161.  
  162.             NumberOfArticulationPoints articulationPoints = new NumberOfArticulationPoints(number_of_nodes);		  
  163.             int num = articulationPoints.numberOfArticulationPoint(adjacency_matrix, source);
  164.             System.out.println("The number is " + num);
  165.  
  166.         } catch (InputMismatchException inputMismatch)
  167.         {
  168.             System.out.println("Wrong Input format");
  169.         }
  170.         scanner.close();
  171.     }	
  172. }


$javac NumberOfArticulationPoints.java
$java NumberOfArticulationPoints
Enter the number of nodes in the graph
5
Enter the adjacency matrix
0 1 1 1 0
1 0 1 0 0
1 1 0 0 1
1 0 0 0 1
0 0 1 1 0
Enter the source for the graph
1
The Given Graph is BiConnected

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.