Introduction
Given a graph, find all the articulation
nodes or Cut-Vertices or separating vertices .
In a graph, all
nodes are reachable to each other, either directly connected or via other
nodes. When an articulation
node is removed from a graph, the graph will be fragmented into 2 or
more isolated islands. Inside the isolated island, there can be 1 node or
multiple linked nodes.
Usage of
articulation nodes: Find Articulation Nodes to identify chock points in a
network, when any Articulation Nodes is out of service, connections of the
whole network is fragmented.
I use shortest path
algorithm to check if the graph is fragmented after a node is removed from
a graph. Set any node as a starting node. The starting node supposing able
to get shortest path to all remaining nodes in the graph. If some nodes are
unreachable to starting node, these nodes are fragmented away from starting
node. Hence the removed node is an articulation
node.
Methods:
Check every node one-by-one to identify
if it is an articulation node. In each iteration, set current node s isMaskedOff to true. In next iteration, reset this node
s isMaskedOff to false, set following node s isMaskedOff to true. When a node s isMaskedOff
is set to true, the node is temporarily removed from the graph. Shortest
Path Search will ignore this node and no connections to this node.
Set a node as starting node. I set
node 0 as starting node. Our chosen starting node is possibly an articulation
node. Therefore, when node 0 is being masked-off, choose another node
(node 1 ) as starting node.
Perform Shortest Path Search . The
starting node supposing has shortest paths to all remaining nodes in the
graph. If some nodes are unreachable to starting node, these nodes are
fragmented away from starting node. Hence the removed node is an articulation
node.
End of the iteration, reset Shortest
Path Search results. Set shortestDistance to
infinity, prevPath to -1, isMaskedOff to false.
Finding articulation node do not
require travel weight. However, Shortest Path Search need to have travel
weight between connected nodes. Therefore, we can simply set travel weight
as 1 between connected nodes.
Visual c# Console App
In graph1.txt file,
1st line is the node 0; 2nd line is the node 1; and
so on. Each pair in the line is the neighbouring node ID and the weight,
separated by a space. If a graph doesn t have weights stated, set all edges
weight to 1.
main_v0.cs
graph4.txt:
Node 1 & 4 are the articulation nodes
graph5.txt:
Node 1 , 6 , 7 , 9 are the articulation nodes
Graph4
Graph 5
Reference
Code challenges
website: https://www.geeksforgeeks.org/problems/articulation-point-1/1?page=2&difficulty=Hard&sortBy=submissions
Wikipedia: https://en.wikipedia.org/wiki/Biconnected_component
|