FINDING ALL ARTICULATION POINT IN A GRAPH
A vertex in a graph is considered an articulation point if removing it and all the edges connected with it raises the number of linked components in the graph.
Hence it might be considered as an ATM problem since many of the vertices in the above picture are ATM machines, and several of the vertex (ATM’s) are essential for the operation of all of the ATM’s in the graph. As a result, if any of those essential vertices (ATM) is withdrawn, the whole network is disconnected, and they will operate independently.
How can I locate the Articulation points on this graph? To do this, we are use the DFS Algorithm. Therefore, as an example, consider the DFS algorithm.
DFS Spanning Tree
The following steps must be taken:
[1] Traverse from the initial node (A) to the finishing node (I),
[2] When a path in our first traverse is missing, we must add a Back edge (dotted lines) as explained in the diagram below.
[3] Determine the depth value (d) and smallest index (I) that each vertex can reach.
[4] To find the articulation point, use the formula below and check 2 vertex’s.
[5] If this condition is met, the “u” will be an articulation point. Let’s look at two examples to see what the articulation points are
[6] So that’s how you identify the articulation points in a huge number of complex graphs.
Let’s look at the java algorithm for determining the articulation point.
// A Java program to find articulation points in an undirected graph
import java.io.*;
import java.util.*;
import java.util.LinkedList;
// This class represents an undirected graph using adjacency list
// representation
class Graph
{
private int V; // No. of vertices
// Array of lists for Adjacency List Representation
private LinkedList<Integer> adj[];
int time = 0;
static final int NIL = -1;
// Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v, int w)
{
adj[v].add(w); // Add w to v’s list.
adj[w].add(v); //Add v to w’s list
}
// A recursive function that find articulation points using DFS
// u → The vertex to be visited next
// visited[] → keeps tract of visited vertices
// disc[] → Stores discovery times of visited vertices
// parent[] → Stores parent vertices in DFS tree
// ap[] → Store articulation points
void APUtil(int u, boolean visited[], int disc[],
int low[], int parent[], boolean ap[])
{
// Count of children in DFS Tree
int children = 0;
// Mark the current node as visited
visited[u] = true;
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
// Go through all vertices aadjacent to this
Iterator<Integer> i = adj[u].iterator();
while (i.hasNext())
{
int v = i.next(); // v is current adjacent of u
// If v is not visited yet, then make it a child of u
// in DFS tree and recur for it
if (!visited[v])
{
children++;
parent[v] = u;
APUtil(v, visited, disc, low, parent, ap);
// Check if the subtree rooted with v has a connection to
// one of the ancestors of u
low[u] = Math.min(low[u], low[v]);
// u is an articulation point in following cases
// (1) u is root of DFS tree and has two or more chilren.
if (parent[u] == NIL && children > 1)
ap[u] = true;
// (2) If u is not root and low value of one of its child
// is more than discovery value of u.
if (parent[u] != NIL && low[v] >= disc[u])
ap[u] = true;
}
// Update low value of u for parent function calls.
else if (v != parent[u])
low[u] = Math.min(low[u], disc[v]);
}
}
// The function to do DFS traversal. It uses recursive function APUtil()
void AP()
{
// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
int disc[] = new int[V];
int low[] = new int[V];
int parent[] = new int[V];
boolean ap[] = new boolean[V]; // To store articulation points
// Initialize parent and visited, and ap(articulation point)
// arrays
for (int i = 0; i < V; i++)
{
parent[i] = NIL;
visited[i] = false;
ap[i] = false;
}
// Call the recursive helper function to find articulation
// points in DFS tree rooted with vertex ‘i’
for (int i = 0; i < V; i++)
if (visited[i] == false)
APUtil(i, visited, disc, low, parent, ap);
// Now ap[] contains articulation points, print them
for (int i = 0; i < V; i++)
if (ap[i] == true)
System.out.print(i+” “);
}
// Driver method
public static void main(String args[])
{
// Create graphs given in above diagrams
System.out.println(“Articulation points in first graph “);
Graph g1 = new Graph(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
g1.AP();
System.out.println();
System.out.println(“Articulation points in Second graph”);
Graph g2 = new Graph(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.AP();
System.out.println();
System.out.println(“Articulation points in Third graph “);
Graph g3 = new Graph(7);
g3.addEdge(0, 1);
g3.addEdge(1, 2);
g3.addEdge(2, 0);
g3.addEdge(1, 3);
g3.addEdge(1, 4);
g3.addEdge(1, 6);
g3.addEdge(3, 5);
g3.addEdge(4, 5);
g3.AP();
}
}