Java Program to Check Check Cut Vertices (Articulation Vertex) Exists in a Graph

This is a java program check if the graph contains any weak link (articulation point). 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. They are useful for designing reliable networks.

Here is the source code of the Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph or Check Whether G is Biconnected or Not. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

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

Output:

$ javac ArticulationPoints.java
$ java ArticulationPoints
 
Enter the number of vertices: 
6
Enter the number of edges: 
7
 
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 
 
Atriculation points: 
1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

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

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.