Java Program to Find the Edge Connectivity of a Graph

This is a java program find the edge connectivity of the given graph. The edge connectivity simply means, number of bridges in a graph, bridges are edges when removed makes the graph disconnected.

Here is the source code of the Java Program to Find the Edge 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 bridges 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 ECBag<Item> implements Iterable<Item>
  11. {
  12.     private int        N;    // number of elements in ECBag
  13.     private Node<Item> first; // beginning of ECBag
  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 ECBag()
  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 BridgeGraph
  85. {
  86.     private final int        V;
  87.     private int              E;
  88.     private ECBag<Integer>[] adj;
  89.  
  90.     @SuppressWarnings("unchecked")
  91.     public BridgeGraph(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 = (ECBag<Integer>[]) new ECBag[V];
  99.         for (int v = 0; v < V; v++)
  100.         {
  101.             adj[v] = new ECBag<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.         for (int i = 0; i < E; i++)
  113.         {
  114.             int v = sc.nextInt();
  115.             int w = sc.nextInt();
  116.             addEdge(v, w);
  117.         }
  118.         sc.close();
  119.     }
  120.  
  121.     public BridgeGraph(BridgeGraph G)
  122.     {
  123.         this(G.V());
  124.         this.E = G.E();
  125.         for (int v = 0; v < G.V(); v++)
  126.         {
  127.             // reverse so that adjacency list is in same order as original
  128.             Stack<Integer> reverse = new Stack<Integer>();
  129.             for (int w : G.adj[v])
  130.             {
  131.                 reverse.push(w);
  132.             }
  133.             for (int w : reverse)
  134.             {
  135.                 adj[v].add(w);
  136.             }
  137.         }
  138.     }
  139.  
  140.     public int V()
  141.     {
  142.         return V;
  143.     }
  144.  
  145.     public int E()
  146.     {
  147.         return E;
  148.     }
  149.  
  150.     public void addEdge(int v, int w)
  151.     {
  152.         if (v < 0 || v >= V)
  153.             throw new IndexOutOfBoundsException();
  154.         if (w < 0 || w >= V)
  155.             throw new IndexOutOfBoundsException();
  156.         E++;
  157.         adj[v].add(w);
  158.         adj[w].add(v);
  159.     }
  160.  
  161.     public Iterable<Integer> adj(int v)
  162.     {
  163.         if (v < 0 || v >= V)
  164.             throw new IndexOutOfBoundsException();
  165.         return adj[v];
  166.     }
  167.  
  168.     public String toString()
  169.     {
  170.         StringBuilder s = new StringBuilder();
  171.         String NEWLINE = System.getProperty("line.separator");
  172.         s.append(V + " vertices, " + E + " edges " + NEWLINE);
  173.         for (int v = 0; v < V; v++)
  174.         {
  175.             s.append(v + ": ");
  176.             for (int w : adj[v])
  177.             {
  178.                 s.append(w + " ");
  179.             }
  180.             s.append(NEWLINE);
  181.         }
  182.         return s.toString();
  183.     }
  184. }
  185.  
  186. public class EdgeConnectivity
  187. {
  188.     private int   bridges; // number of bridges
  189.     private int   cnt;    // counter
  190.     private int[] pre;    // pre[v] = order in which dfs examines v
  191.     private int[] low;    // low[v] = lowest preorder of any vertex connected
  192.                            // to v
  193.  
  194.     public EdgeConnectivity(BridgeGraph G)
  195.     {
  196.         low = new int[G.V()];
  197.         pre = new int[G.V()];
  198.         for (int v = 0; v < G.V(); v++)
  199.             low[v] = -1;
  200.         for (int v = 0; v < G.V(); v++)
  201.             pre[v] = -1;
  202.         for (int v = 0; v < G.V(); v++)
  203.             if (pre[v] == -1)
  204.                 dfs(G, v, v);
  205.     }
  206.  
  207.     public int components()
  208.     {
  209.         return bridges + 1;
  210.     }
  211.  
  212.     private void dfs(BridgeGraph G, int u, int v)
  213.     {
  214.         pre[v] = cnt++;
  215.         low[v] = pre[v];
  216.         for (int w : G.adj(v))
  217.         {
  218.             if (pre[w] == -1)
  219.             {
  220.                 dfs(G, v, w);
  221.                 low[v] = Math.min(low[v], low[w]);
  222.                 if (low[w] == pre[w])
  223.                 {
  224.                     // System.out.println(v + "-" + w + " is a bridge");
  225.                     bridges++;
  226.                 }
  227.             }
  228.             // update low number - ignore reverse of edge leading to v
  229.             else if (w != u)
  230.                 low[v] = Math.min(low[v], pre[w]);
  231.         }
  232.     }
  233.  
  234.     public static void main(String[] args)
  235.     {
  236.         Scanner sc = new Scanner(System.in);
  237.         System.out.println("Enter the number of vertices: ");
  238.         BridgeGraph G = new BridgeGraph(sc.nextInt());
  239.         System.out.println(G);
  240.         EdgeConnectivity bridge = new EdgeConnectivity(G);
  241.         System.out.println("Edge Connectivity: " + bridge.bridges);
  242.         sc.close();
  243.     }
  244. }

Output:

$ javac EdgeConnectivity.java
$ java EdgeConnectivity
 
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 
 
Edge Connectivity: 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.

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.