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.
// Number of articulation points in a graph package com.maixuanviet.graph; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Scanner; import java.util.Stack; class VCBag<Item> implements Iterable<Item> { private int N; // number of elements in VCBag private Node<Item> first; // beginning of VCBag // helper linked list class private static class Node<Item> { private Item item; private Node<Item> next; } public VCBag() { first = null; N = 0; } public boolean isEmpty() { return first == null; } public int size() { return N; } public void add(Item item) { Node<Item> oldfirst = first; first = new Node<Item>(); first.item = item; first.next = oldfirst; N++; } public Iterator<Item> iterator() { return new ListIterator<Item>(first); } // an iterator, doesn't implement remove() since it's optional @SuppressWarnings("hiding") private class ListIterator<Item> implements Iterator<Item> { private Node<Item> current; public ListIterator(Node<Item> first) { current = first; } public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.item; current = current.next; return item; } } } class VCGraph { private final int V; private int E; private VCBag<Integer>[] adj; @SuppressWarnings("unchecked") public VCGraph(int V) { if (V < 0) throw new IllegalArgumentException( "Number of vertices must be nonnegative"); this.V = V; this.E = 0; adj = (VCBag<Integer>[]) new VCBag[V]; for (int v = 0; v < V; v++) { adj[v] = new VCBag<Integer>(); } System.out.println("Enter the number of edges: "); Scanner sc = new Scanner(System.in); int E = sc.nextInt(); if (E < 0) { sc.close(); throw new IllegalArgumentException( "Number of edges must be nonnegative"); } System.out.println("Enter the edges: <from> <to>"); for (int i = 0; i < E; i++) { int v = sc.nextInt(); int w = sc.nextInt(); addEdge(v, w); } sc.close(); } public VCGraph(VCGraph G) { this(G.V()); this.E = G.E(); for (int v = 0; v < G.V(); v++) { // reverse so that adjacency list is in same order as original Stack<Integer> reverse = new Stack<Integer>(); for (int w : G.adj[v]) { reverse.push(w); } for (int w : reverse) { adj[v].add(w); } } } public int V() { return V; } public int E() { return E; } public void addEdge(int v, int w) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); if (w < 0 || w >= V) throw new IndexOutOfBoundsException(); E++; adj[v].add(w); adj[w].add(v); } public Iterable<Integer> adj(int v) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); return adj[v]; } public String toString() { StringBuilder s = new StringBuilder(); String NEWLINE = System.getProperty("line.separator"); s.append(V + " vertices, " + E + " edges " + NEWLINE); for (int v = 0; v < V; v++) { s.append(v + ": "); for (int w : adj[v]) { s.append(w + " "); } s.append(NEWLINE); } return s.toString(); } } public class VertexConnectivity { private int[] low; private int[] pre; private int cnt; private boolean[] articulation; public VertexConnectivity(VCGraph G) { low = new int[G.V()]; pre = new int[G.V()]; articulation = new boolean[G.V()]; for (int v = 0; v < G.V(); v++) low[v] = -1; for (int v = 0; v < G.V(); v++) pre[v] = -1; for (int v = 0; v < G.V(); v++) if (pre[v] == -1) dfs(G, v, v); } private void dfs(VCGraph G, int u, int v) { int children = 0; pre[v] = cnt++; low[v] = pre[v]; for (int w : G.adj(v)) { if (pre[w] == -1) { children++; dfs(G, v, w); // update low number low[v] = Math.min(low[v], low[w]); // non-root of DFS is an articulation point if low[w] >= pre[v] if (low[w] >= pre[v] && u != v) articulation[v] = true; } // update low number - ignore reverse of edge leading to v else if (w != u) low[v] = Math.min(low[v], pre[w]); } // root of DFS is an articulation point if it has more than 1 child if (u == v && children > 1) articulation[v] = true; } // is vertex v an articulation point? public boolean isArticulation(int v) { return articulation[v]; } // test client public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter the number of vertices: "); VCGraph G = new VCGraph(sc.nextInt()); System.out.println(G); VertexConnectivity bic = new VertexConnectivity(G); int count = 0; for (int v = 0; v < G.V(); v++) if (bic.isArticulation(v)) count++; System.out.println("Vertex Connectivity: " + count); sc.close(); } }
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
Related posts:
The “final” Keyword in Java
Introduction to Spring Security Expressions
ThreadPoolTaskExecutor corePoolSize vs. maxPoolSize
Spring Security – Reset Your Password
A Guide to the finalize Method in Java
So sánh HashMap và HashSet trong Java
Java Program to Implement Quick Sort Using Randomization
Most commonly used String methods in Java
Giới thiệu Java 8
Java Program to Compare Binary and Sequential Search
A Guide to JUnit 5 Extensions
Changing Annotation Parameters At Runtime
Tạo ứng dụng Java RESTful Client với thư viện OkHttp
Spring Boot - Batch Service
Hướng dẫn Java Design Pattern – Intercepting Filter
ArrayList trong java
Spring Boot - Bootstrapping
Java Program to Check for balanced parenthesis by using Stacks
Function trong Java 8
Error Handling for REST with Spring
Java Program to Implement Direct Addressing Tables
Jackson JSON Views
Use Liquibase to Safely Evolve Your Database Schema
Circular Dependencies in Spring
Runnable vs. Callable in Java
Java 8 Stream findFirst() vs. findAny()
Guide to System.gc()
Java Program to Find a Good Feedback Edge Set in a Graph
Jackson Ignore Properties on Marshalling
Java Program to implement Array Deque
How to Read a File in Java
Netflix Archaius with Various Database Configurations