/*
* Titile : Implementation of the algorithm to find the bi-connected
* components in a graph G ( V, E ) in O ( |V| + |E| ) time and space.
*
* Requirements : Java 1.5.0_01 (or higher)
*
* Author : Saket Soni, mtc0420, ISI Kolkata.
*
* Subject : Design and Analysis of Algorithms
*
* Submitted To : Shri K. Mukhopadhyay
*
*/
// The Imports ...
import java.util.*; // for ArrayList and Stack Class
import java.io.*; // for BufferedReader and InputStreamReader Class
/*
* Class to model a vertex of a graph, each vertex has a list of vertices to
* which it is connected to.
*/
class GraphVertex
{
// Instance variables ...
// Vertex id ...
int id = -1;
// fields used during finding connected components ...
int dfsNo = -1;
int highValue = -1;
boolean root = false;
boolean isArtVer = false;
GraphVertex parent = null;
ArrayList listOfChilds = new ArrayList(); // list of GraphVertex Objects
// adjancency list ...
ArrayList connectedTo = new ArrayList(); // list of GraphVertex Objects
// Method Definitions ...
// function to check for equivalence ...
public boolean equals(Object obj)
{
if ( this == obj )
return true;
if ( obj == null )
return false;
if ( getClass() != obj.getClass() )
return false;
GraphVertex other = (GraphVertex)obj;
return ( id == other.id ) ;
}
// returns the readable string representation of the vertex ...
public String toString()
{
StringBuffer str = new StringBuffer (
"Vertex id : " + id + "\n" +
" dfsNo : " + dfsNo + "\n" +
" highValue : " + highValue + "\n" +
" isArtVer : " +
( ( isArtVer ) ? "yes" : "" ) + "\n" +
" root : " +
( ( root ) ? "yes" : "" ) + "\n" +
" parent : " +
( ( parent != null ) ? parent.id : "" ) + "\n" +
" connected to : "
);
int count = connectedTo.size();
GraphVertex temp = null;
for ( int i = 0 ; i < count ; i++ )
{
temp = (GraphVertex) connectedTo.get(i);
str.append( temp.id + ", " );
}
if ( count > 0 )
str.setCharAt( str.length()-2, ' ' );
count = listOfChilds.size();
str.append( "\n dfs childrens : " );
for ( int i = 0 ; i < count ; i++ )
{
temp = (GraphVertex) listOfChilds.get(i);
str.append( temp.id + ", " );
}
if ( count > 0 )
str.setCharAt( str.length()-2, ' ' );
return new String ( str + "\n\n" );
}
}
/*
* Class to model an edge of an undirected simple graph.
*/
class GraphEdge
{
// Instance variables ...
// Start and End vertices
GraphVertex start = null; // though names are start and end,
GraphVertex end = null; // there is no direction as such.
// Method Definitons ...
// constructor to create Edge objects ...
GraphEdge( GraphVertex aStart, GraphVertex aEnd ) throws Exception
{
if ( aStart == null )
throw new Exception ( "aStart is null, cannot create edge " );
if ( aEnd == null )
throw new Exception ( "aEnd is null, cannot create edge " );
if ( aStart == aEnd )
throw new Exception ( "Self loops are not allowed, cannot create edge " );
if ( aStart.id == aEnd.id )
throw new Exception ( "Both the vertices have same id, cannot create edge " );
if ( aStart.id < aEnd.id ) { // since, ab and ba are both equal
start = aStart;
end = aEnd;
}
else {
start = aEnd;
end = aStart;
}
}
// function to check for equivalence ...
public boolean equals(Object obj)
{
if ( this == obj )
return true;
if ( obj == null )
return false;
if ( getClass() != obj.getClass() )
return false;
GraphEdge other = (GraphEdge)obj;
if ( start == other.start && end == other.end )
return true;
return ( start.id == other.start.id && end.id == other.end.id );
}
// returns the readable string representation of the edge ...
public String toString()
{
return "Edge : (" + start.id + "-" + end.id + ") \n";
}
}
/*
* Class to model and store the information of a bi-connected component, it is
* basically a set of edges.
*/
class BiConComponent
{
// Instance variables ...
// list of edges in the component ...
ArrayList listOfEdges = new ArrayList(); // list of GraphEdge Objects
// Method Definitions ...
// function to add an edge into the list of edges ...
boolean addEdge ( GraphEdge edge ) throws Exception
{
if ( edge == null )
throw new Exception ( "edge is null, cannot add edge in BiConComponent ");
if ( listOfEdges.contains( edge ) )
return false;
listOfEdges.add ( edge );
return true;
}
// returns the readable string representation of the bi-con-component ...
public String toString()
{
int count = listOfEdges.size();
StringBuffer str = new StringBuffer ( "BiConComponent : (" + count + " edges)\n" );
GraphEdge edge = null;
for ( int i = 0 ; i < count ; i++ )
{
edge = (GraphEdge)listOfEdges.get(i);
str.append ( " " + (i+1) + " : " + edge.toString() );
}
str.append("\n");
return new String ( str );
}
}
/*
* Class to model a simple undirected graph, no self loops or multi-edges are
* allowed, it also has a method to find and identify all the bi-connected
* components present in the graph.
*/
class Graph
{
// Instance variables ...
// list of vertices ...
ArrayList arrVertex = new ArrayList(); // list of GraphVertex Objects
// list of edges ...
ArrayList arrEdge = new ArrayList(); // list of GraphEdge Objects
// list of bi-connected-components ...
ArrayList listBiComp = new ArrayList(); // list of BiConComponent Objects
// list of articulation points ...
ArrayList artiList = new ArrayList(); // list of GraphVertex Objects
// stack, used to store vertices and edges in the method to find
// bi-connected-components ...
Stack stk = new Stack();
// gdfs_no variable, used to give dfs nos to vertices in the method
// to find bi-connected-components ...
int gdfs_no = -1;
// Method Definitions ...
// function to display the articulation points, before using this function
// ensure that the bi-connected-components have been re-computed on the
// updated graph ...
void displayArticulationPoints()
{
GraphVertex temp = null;
int count = artiList.size();
Utl.p ( "Articulation Points (" + count + " vertices) : " );
for ( int i = 0 ; i < count ; i++ )
{
temp = (GraphVertex) artiList.get(i);
Utl.p ( temp.id + ", " );
}
Utl.pln();
Utl.pln();
}
// function to display the bi-connected components, before using this function
// ensure that the bi-connected-components have been re-computed on the
// updated graph ...
void displayBiComponents()
{
BiConComponent biComp = null;
int count = listBiComp.size();
Utl.pln ( "Bi-connected components are (" + count + " components) :\n" );
for ( int i = 0 ; i < count ; i++ )
{
biComp = (BiConComponent) listBiComp.get(i);
Utl.pln ( " " + (i+1) + " :: " + biComp.toString() );
}
}
// function to set the graph value to a default, used for testing of the
// algorithm ...
void setDefault() throws Exception
{
GraphVertex start = null;
GraphVertex end = null;
GraphVertex temp = null;
GraphEdge edge = null;
if ( arrVertex.size() > 0 )
arrVertex.clear();
if ( arrEdge.size() > 0 )
arrEdge.clear();
for ( int i = 0 ; i < 16 ; i++ )
{
temp = new GraphVertex();
temp.id = i;
arrVertex.add(temp);
}
start = (GraphVertex)arrVertex.get(0);
end = (GraphVertex)arrVertex.get(1);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(0);
end = (GraphVertex)arrVertex.get(4);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(0);
end = (GraphVertex)arrVertex.get(2);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(0);
end = (GraphVertex)arrVertex.get(5);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(0);
end = (GraphVertex)arrVertex.get(10);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(1);
end = (GraphVertex)arrVertex.get(3);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(1);
end = (GraphVertex)arrVertex.get(11);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(1);
end = (GraphVertex)arrVertex.get(7);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(1);
end = (GraphVertex)arrVertex.get(4);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(3);
end = (GraphVertex)arrVertex.get(6);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(3);
end = (GraphVertex)arrVertex.get(12);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(3);
end = (GraphVertex)arrVertex.get(7);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(6);
end = (GraphVertex)arrVertex.get(11);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(6);
end = (GraphVertex)arrVertex.get(12);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(4);
end = (GraphVertex)arrVertex.get(8);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(8);
end = (GraphVertex)arrVertex.get(14);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(8);
end = (GraphVertex)arrVertex.get(13);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(8);
end = (GraphVertex)arrVertex.get(15);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(14);
end = (GraphVertex)arrVertex.get(13);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(14);
end = (GraphVertex)arrVertex.get(15);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(2);
end = (GraphVertex)arrVertex.get(5);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(5);
end = (GraphVertex)arrVertex.get(9);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
start = (GraphVertex)arrVertex.get(5);
end = (GraphVertex)arrVertex.get(10);
start.connectedTo.add(end);
end.connectedTo.add(start);
edge = new GraphEdge(start,end);
arrEdge.add(edge);
}
// function to read the new graph details from the user, old values in the
// graph is lost ...
void readInput()
{
// local variables ...
BufferedReader in = new BufferedReader
( new InputStreamReader(System.in) );
int numOfVertices = -1;
int numOfEdges = -1;
int st = -1;
int en = -1;
GraphVertex start = null;
GraphVertex end = null;
GraphEdge edge = null;
// deleting old values of the graph ...
if ( arrVertex.size() > 0 ) // delete old vertices
arrVertex.clear();
if ( arrEdge.size() > 0 ) // delete old edges
arrEdge.clear();
// read input from the user, do while input not read completely ...
while ( true )
{
try
{
Utl.p( "Enter the number of vertices : ");
numOfVertices = Integer.parseInt(in.readLine());
GraphVertex temp = null;
for ( int i = 0 ; i < numOfVertices ; i++ )
{
temp = new GraphVertex(); // create new vertices
temp.id = i;
arrVertex.add(temp);
}
Utl.p( "Enter the number of edges : ");
numOfEdges = Integer.parseInt(in.readLine());
for ( int i = 0 ; i < numOfEdges ; i++ )
{
Utl.p("Enter for Edge " + i + "\n Start Vertex No : ");
st = Integer.parseInt(in.readLine());
start = (GraphVertex) arrVertex.get(st);
Utl.p(" End Vertex No : ");
en = Integer.parseInt(in.readLine());
end = (GraphVertex) arrVertex.get(en);
if ( st != en )
{
if ( start.connectedTo.contains(end) )
{
Utl.pln( "Error : edge already exists !! ");
i--;
}
else
{
start.connectedTo.add(end); // update adjacency list
end.connectedTo.add(start);
edge = new GraphEdge(start,end); // create edge
arrEdge.add(edge);
}
}
else
{
Utl.pln( "Error : cannot create self loops !!" );
i--;
}
}
break; // no exception thrown so break quitely
}
catch ( Exception e ) // if an input error, catch exception
{ // and show message
Utl.pln ( "" + e );
}
}
}
// returns the readable string representation of the graph ...
public String toString()
{
StringBuffer str = new StringBuffer ("V E R T I C E S :\n~~~~~~~~~~~~~~~~~~\n\n");
int count = arrVertex.size();
GraphVertex vertex = null;
for ( int i = 0 ; i < count ; i++ )
{
vertex = (GraphVertex) arrVertex.get(i);
str.append( vertex.toString() );
}
str.append ( "E D G E S :\n~~~~~~~~~~~~\n\n");
count = arrEdge.size();
GraphEdge edge = null;
for ( int i = 0 ; i < count ; i++ )
{
edge = (GraphEdge) arrEdge.get(i);
str.append( edge.toString() );
}
return new String ( str );
}
// function to find the bi-connected components of the graph ...
void computeBiConnectedComponents( int vertexId ) throws Exception
{
int count = arrVertex.size(); // find no of vertices
// check for error conditions ...
if ( count == 0 )
throw new Exception ( "Graph empty, cannot compute " +
"bi connected components " );
if ( vertexId >= count || vertexId < 0 )
throw new Exception ( "Vertex (id:" + vertexId +
") not in graph, cannot compute bi-connected components " );
GraphVertex temp = null; // temporary variable
// initialize the vertices ...
for ( int i = 0 ; i < count ; i++ )
{
temp = (GraphVertex) arrVertex.get(i);
temp.root = false;
temp.dfsNo = 0 ;
}
// initialize the variables before entering into the dfsBC algorithm ...
gdfs_no = count; // set gdfs to num of vertices
stk.clear(); // clear stack
// get the vertex with the specified id ...
temp = (GraphVertex) arrVertex.get(vertexId);
// set the vertex as root ...
temp.root = true;
// call dfsBC algorithm with the vertex ...
dfsBC ( temp );
// to find other left out bi-connected components if any in other
// disjoint components of the graph ...
for ( int i = 0 ; i < count ; i++ )
{
temp = (GraphVertex) arrVertex.get(i);
if ( temp.dfsNo == 0 )
{
stk.clear();
gdfs_no = count;
temp.root = true;
dfsBC ( temp );
}
}
}
// function to find max of 'a' and 'b' ...
int max ( int a, int b )
{
return ( ( a > b ) ? a : b );
}
// recursive algorithm to find the bi-connected components of a graph,
// starting from vertex v, it traverses the graph in DFS and computes the
// the dfs_no(s) and high_values of each vertex, this information is then
// used to find the articulation points and the bi-connected components.
void dfsBC ( GraphVertex v ) throws Exception
{
// local variables ...
GraphEdge edge = null;
GraphVertex w = null;
Object obj = null;
// initialize the vertex v's dfsno and highvalue ...
v.dfsNo = gdfs_no;
v.highValue = v.dfsNo;
// decrement the gdfs_no ...
gdfs_no--;
// put the vertex into the stack ...
stk.push ( v );
// find the num of edges going out from v ...
int numOfEdges = v.connectedTo.size();
// do for all edges going out from v ...
for ( int i = 0 ; i < numOfEdges ; i++ )
{
// get the i'th neighbour w of v ...
w = (GraphVertex) v.connectedTo.get(i);
// create an edge v-w ...
edge = new GraphEdge ( v, w );
// put the edge into the stack ( each edge is inserted twice into
// the stack, one for each direction ) ...
stk.push ( edge );
if ( ! w.equals(v.parent) ) // if w is not parent of v
{
if ( w.dfsNo == 0 ) // if w has not been visited yet
{
w.parent = v; // set v as parent of w
v.listOfChilds.add ( w ); // add w as a child of v
dfsBC ( w ); // since w has not been visited,
// visit w (DFS)
// w has been visited now, and its dfsno and highvalues has
// been computed.
if ( w.highValue <= v.dfsNo )// if highvalue of w is less
{ // of equal to v's
dfsno, then
// v is the only w
by which
// w is connected
to the rest
// of the graph,
and hence v
// is an
articulation point
v.isArtVer = true; // set v as articulation point
if ( ! artiList.contains(v) )
artiList.add(v); // add into the list of articulation
// points
// w and the sub-tree of w (dfs tree) is a separate
// bi-connected component, hence create a new
// BiConComponent object to store this information.
BiConComponent biComp = new BiConComponent();
while ( true ) // pop all vertices and edges from the
{ // the stack until v is found
obj = stk.pop();
if ( v.equals(obj) )
break;
// if the poped object is an edge, then insert it
// into the newly created biComp object.
if ( obj.getClass().equals(GraphEdge.class) )
biComp.addEdge((GraphEdge)obj);
}
// add the newly created biComp object into the list
// of bi-connected components ...
listBiComp.add(biComp);
// push v back into the stack, as it may also be
// a part of other components ...
stk.push(v);
}
// set the highvalue of v to the max of that of v and w ...
v.highValue = max ( v.highValue, w.highValue );
}
// v-w is a back-edge or a forward-edge, and hence set the
// highvalue of v to the max of v's highvalue and w's dfsno ...
v.highValue = max ( v.highValue, w.dfsNo );
}
}
}
}
/*
* Container class for application entry point.
*/
public class bic2
{
// Application Entry point.
public static void main( String [] args)
{
try
{
// create new Graph object ...
Graph gph1 = new Graph();
// read input from the user ...
// gph1.readInput();
// or set a default for testing ...
gph1.setDefault();
// print the read graph ...
Utl.pln ( "I N I T I A L G R A P H :" );
Utl.pln ( "~~~~~~~~~~~~~~~~~~~~~~~~~~~" );
Utl.pln ( gph1.toString() );
// find the bi-connected-conponents ...
gph1.computeBiConnectedComponents(0);
// print the graph again to check the dfs tree created ...
Utl.pln ( "\n\n\n\n\n" );
Utl.pln ( "G R A P H A F T E R C O M P U T A T I O N :" );
Utl.pln ( "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" );
Utl.pln ( gph1.toString() );
Utl.pln();
// print the articulation points found ...
gph1.displayArticulationPoints();
Utl.pln();
// print the bi-connected-components found ...
gph1.displayBiComponents();
}
catch ( Exception e )
{
Utl.pln( "" + e ); // show error message
e.printStackTrace(); // print the stack trace
}
}
}
/*
*
* Contains general purpose utility functions for printing on screen, etc.
*
*/
class Utl
{
// Printing Functions ...
/*
* For printing text followed by a newline.
*/
public static void pln ( String str )
{
System.out.println ( str );
}
/*
* For printing text.
*/
public static void p ( String str )
{
System.out.print ( str );
}
/*
* For printing a newline.
*/
public static void pln()
{
System.out.println();
}
}