in Graph

Understanding Articulation Points in a graph

Graphs can be directed or undirected in nature. Articulation points are quite important in a graph as they signal possible vulnerabilities in a given network. Removing a node from a connected undirected graph is likely to split the network into different components of an undirected graph. 

A simple illustration of articulation points 

The undirected graph below contains seven nodes and there are two articulation or critical points. Node B is very important to the network as it directly connects with five nodes. Removing node B will break this graph into three disconnected components. The three disconnected graphs after removing node B will be (A) , (C and D) and (E, F and G). The second articulation point on this graph is node C. A decision to remove node C will lead to two disconnected components which are nodes (A, B, E, F, G) and (D). This clearly shows that node B and C are the two articulation points with B being slightly more critical. Node B is the most critical because if removed it renders the remaining graphs into three disconnected components. On the other hand, removing vertex C splits the graph into two disconnected components.

Some steps in discovering articulation points 

A standard way of finding the articulation point in a given graph is by removing each node one after the other. The goal is to determine if the elimination of a specific node will lead to the disconnection of the graph. Two common techniques utilised for finding articulation points  and checking the connectivity of a graph is the DFS (Depth First Search) and BFS (Breadth First Search) approaches. 

Step 1: Remove node v from the graph

Step 2: Determine the connectivity of the graph using BFS or DFS

Step 3: Restore node v back to the disconnected or connected graph.  

DFS and BFS in articulation points

I’ve written an article on DFS and BFS but in this section will briefly look at how these two techniques are relevant to discovering articulation points. DFS uses an edge-based technique to traverse through a graph via a LIFO(Last in, First Out) approach. The visited nodes are added to a stack and the most recent vertex in the graph is removed for the continuation of the traversal. On the contrary, BFS adopts a node-based technique in finding the shortest path. When a vertex is visited, it is marked and added to the queue. Usually, nodes at the same horizontal level are first visited before progressing to the next tier. When a node is visited, it is added to a queue which is known for its FIFO (First in, First Out) strategy. BFS are considered to be slower than DFS in implementation.

DFS as a better option for Articulation points:

DFS can be viewed as a better traversal to prevent the disconnection of a graph. Compared to BFS, DFS pays better recognition to parent nodes which are sometimes the articulation points in a given graph. 

The output of a BFS traversal for the above graph will be : R, A, B, C, D, E. With a queue based system, the source node of R will be removed from the node lists and that will result in the disconnection of the graph as node R is an articulation point.

On the other hand, with DFS, the source or origin node remains in the stack due to the LIFO method. The outcome in this case is R, A, E, B, C, D. The connected network will remain as the source node R is maintained. Unlike in BFS, a queue-based system implies the removal of an articulation node R. In the above example, there are two articulation vertices R and E. 

From a business perspective, articulation points could be applicable to a telephone network where a critical connection between other units is disconnected. Or, a group of friends who are usually brought together by the same person in the group. Assuming the link between these friends goes travelling or is out of town, the social connection between these folks will go cold.

// A Java program to find articulation points in an undirected graph 
import java.io.*; 
import java.util.*; 
import java.util.LinkedList; 

// Class represents an undirected graph using adjacency list 
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[]) 
	{ 

		// Actual count of children in DFS Tree 
		int children = 0; 

		// indeicate the current node as visited 
		visited[u] = true; 

		// commencing discovery time and low value 
		disc[u] = low[u] = ++time; 

		// Run through all nodes adjacent to this 
		Iterator<Integer> i = adj[u].iterator(); 
		while (i.hasNext()) 
		{ 
			int v = i.next(); // v is current adjacent of u 

			// when v is not visited yet,  make it a child of u 
			// in DFS tree and recur for it as appropriate
			if (!visited[v]) 
			{ 
				children++; 
				parent[v] = u; 
				APUtil(v, visited, disc, low, parent, ap); 


				low[u] = Math.min(low[u], low[v]); 

				// the u is an articulation point in following cases 

	 
				if (parent[u] == NIL && children > 1) 
					ap[u] = true; 

 
				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; 
		} 

		// Using 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+" "); 
	} 

	// Using the driver method 
	public static void main(String args[]) 
	{ 
		// Alphabetical graph labels are replaced by number. i.e A is 0.
		System.out.println("Articulation points in graph "); 
		Graph g1 = new Graph(7); 
        g1.addEdge(0,1); 
        g1.addEdge(1,6); 
        g1.addEdge(0,2); 
        g1.addEdge(0,3); 
        g1.addEdge(0,4);
        g1.addEdge(4,6); 
		g1.AP(); 
		System.out.println(); 
       
        
        
        
	} 
}

Articulation points in graph 
0


		
									

Write a Comment

Comment