Java Program to Find the Vertex Connectivity of a Graph

«
»
This is a java program to find the vertex connectivity of a graph. Vertex connectivity simply means number of articulations points in a graph, articulation points are vertices of a graph whem removed makes graph disconnected.

Here is the source code of the Java Program to Find the Vertex Connectivity of a Graph. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. // Number of articulation points in a graph
  3. package com.sanfoundry.graph;
  4.  
  5. import java.util.Iterator;
  6. import java.util.NoSuchElementException;
  7. import java.util.Scanner;
  8. import java.util.Stack;
  9.  
  10. class VCBag<Item> implements Iterable<Item>
  11. {
  12.     private int N;    // number of elements in VCBag
  13.     private Node<Item> first;    // beginning of VCBag
  14.  
  15.     // helper linked list class
  16.     private static class Node<Item>
  17.     {
  18.         private Item item;
  19.         private Node<Item> next;
  20.     }
  21.  
  22.     public VCBag()
  23.     {
  24.         first = null;
  25.         N = 0;
  26.     }
  27.  
  28.     public boolean isEmpty()
  29.     {
  30.         return first == null;
  31.     }
  32.  
  33.     public int size()
  34.     {
  35.         return N;
  36.     }
  37.  
  38.     public void add(Item item)
  39.     {
  40.         Node<Item> oldfirst = first;
  41.         first = new Node<Item>();
  42.         first.item = item;
  43.         first.next = oldfirst;
  44.         N++;
  45.     }
  46.  
  47.     public Iterator<Item> iterator()
  48.     {
  49.         return new ListIterator<Item>(first);
  50.     }
  51.  
  52.     // an iterator, doesn't implement remove() since it's optional
  53.     @SuppressWarnings("hiding")
  54.     private class ListIterator<Item> implements Iterator<Item>
  55.     {
  56.         private Node<Item> current;
  57.  
  58.         public ListIterator(Node<Item> first)
  59.         {
  60.             current = first;
  61.         }
  62.  
  63.         public boolean hasNext()
  64.         {
  65.             return current != null;
  66.         }
  67.  
  68.         public void remove()
  69.         {
  70.             throw new UnsupportedOperationException();
  71.         }
  72.  
  73.         public Item next()
  74.         {
  75.             if (!hasNext())
  76.                 throw new NoSuchElementException();
  77.             Item item = current.item;
  78.             current = current.next;
  79.             return item;
  80.         }
  81.     }
  82. }
  83.  
  84. class VCGraph
  85. {
  86.     private final int V;
  87.     private int E;
  88.     private VCBag<Integer>[] adj;
  89.  
  90.     @SuppressWarnings("unchecked")
  91.     public VCGraph(int V)
  92.     {
  93.         if (V < 0)
  94.             throw new IllegalArgumentException(
  95.                     "Number of vertices must be nonnegative");
  96.         this.V = V;
  97.         this.E = 0;
  98.         adj = (VCBag<Integer>[]) new VCBag[V];
  99.         for (int v = 0; v < V; v++)
  100.         {
  101.             adj[v] = new VCBag<Integer>();
  102.         }
  103.         System.out.println("Enter the number of edges: ");
  104.         Scanner sc = new Scanner(System.in);
  105.         int E = sc.nextInt();
  106.         if (E < 0)
  107.         {
  108.             sc.close();
  109.             throw new IllegalArgumentException(
  110.                     "Number of edges must be nonnegative");
  111.         }
  112.         System.out.println("Enter the edges: <from> <to>");
  113.         for (int i = 0; i < E; i++)
  114.         {
  115.             int v = sc.nextInt();
  116.             int w = sc.nextInt();
  117.             addEdge(v, w);
  118.         }
  119.         sc.close();
  120.     }
  121.  
  122.     public VCGraph(VCGraph G)
  123.     {
  124.         this(G.V());
  125.         this.E = G.E();
  126.         for (int v = 0; v < G.V(); v++)
  127.         {
  128.             // reverse so that adjacency list is in same order as original
  129.             Stack<Integer> reverse = new Stack<Integer>();
  130.             for (int w : G.adj[v])
  131.             {
  132.                 reverse.push(w);
  133.             }
  134.             for (int w : reverse)
  135.             {
  136.                 adj[v].add(w);
  137.             }
  138.         }
  139.     }
  140.  
  141.     public int V()
  142.     {
  143.         return V;
  144.     }
  145.  
  146.     public int E()
  147.     {
  148.         return E;
  149.     }
  150.  
  151.     public void addEdge(int v, int w)
  152.     {
  153.         if (v < 0 || v >= V)
  154.             throw new IndexOutOfBoundsException();
  155.         if (w < 0 || w >= V)
  156.             throw new IndexOutOfBoundsException();
  157.         E++;
  158.         adj[v].add(w);
  159.         adj[w].add(v);
  160.     }
  161.  
  162.     public Iterable<Integer> adj(int v)
  163.     {
  164.         if (v < 0 || v >= V)
  165.             throw new IndexOutOfBoundsException();
  166.         return adj[v];
  167.     }
  168.  
  169.     public String toString()
  170.     {
  171.         StringBuilder s = new StringBuilder();
  172.         String NEWLINE = System.getProperty("line.separator");
  173.         s.append(V + " vertices, " + E + " edges " + NEWLINE);
  174.         for (int v = 0; v < V; v++)
  175.         {
  176.             s.append(v + ": ");
  177.             for (int w : adj[v])
  178.             {
  179.                 s.append(w + " ");
  180.             }
  181.             s.append(NEWLINE);
  182.         }
  183.         return s.toString();
  184.     }
  185. }
  186.  
  187. public class VertexConnectivity
  188. {
  189.     private int[] low;
  190.     private int[] pre;
  191.     private int cnt;
  192.     private boolean[] articulation;
  193.  
  194.     public VertexConnectivity(VCGraph G)
  195.     {
  196.         low = new int[G.V()];
  197.         pre = new int[G.V()];
  198.         articulation = new boolean[G.V()];
  199.         for (int v = 0; v < G.V(); v++)
  200.             low[v] = -1;
  201.         for (int v = 0; v < G.V(); v++)
  202.             pre[v] = -1;
  203.         for (int v = 0; v < G.V(); v++)
  204.             if (pre[v] == -1)
  205.                 dfs(G, v, v);
  206.     }
  207.  
  208.     private void dfs(VCGraph G, int u, int v)
  209.     {
  210.         int children = 0;
  211.         pre[v] = cnt++;
  212.         low[v] = pre[v];
  213.         for (int w : G.adj(v))
  214.         {
  215.             if (pre[w] == -1)
  216.             {
  217.                 children++;
  218.                 dfs(G, v, w);
  219.                 // update low number
  220.                 low[v] = Math.min(low[v], low[w]);
  221.                 // non-root of DFS is an articulation point if low[w] >= pre[v]
  222.                 if (low[w] >= pre[v] && u != v)
  223.                     articulation[v] = true;
  224.             }
  225.             // update low number - ignore reverse of edge leading to v
  226.             else if (w != u)
  227.                 low[v] = Math.min(low[v], pre[w]);
  228.         }
  229.         // root of DFS is an articulation point if it has more than 1 child
  230.         if (u == v && children > 1)
  231.             articulation[v] = true;
  232.     }
  233.  
  234.     // is vertex v an articulation point?
  235.     public boolean isArticulation(int v)
  236.     {
  237.         return articulation[v];
  238.     }
  239.  
  240.     // test client
  241.     public static void main(String[] args)
  242.     {
  243.         Scanner sc = new Scanner(System.in);
  244.         System.out.println("Enter the number of vertices: ");
  245.         VCGraph G = new VCGraph(sc.nextInt());
  246.         System.out.println(G);
  247.         VertexConnectivity bic = new VertexConnectivity(G);
  248.         int count = 0;
  249.         for (int v = 0; v < G.V(); v++)
  250.             if (bic.isArticulation(v))
  251.                 count++;
  252.         System.out.println("Vertex Connectivity: " + count);
  253.         sc.close();
  254.     }
  255. }

Output:

$ javac VertexConnectivity.java
$ java VertexConnectivity
 
Enter the number of vertices: 
6
Enter the number of edges: 
7
Enter the edges: <from> <to>
0 1
1 2
1 3
3 4
4 5
5 3
5 2
6 vertices, 7 edges 
0: 1 
1: 3 2 0 
2: 5 1 
3: 5 4 1 
4: 5 3 
5: 2 3 4 
 
Vertex Connectivity: 1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

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.