001package algs41;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac Biconnected.java
005 *  Dependencies: Graph.java
006 *
007 *  Identify articulation points and print them out.
008 *  This can be used to decompose a graph into biconnected components.
009 *  Runs in O(E + V) time.
010 *
011 *  http://www.cs.brown.edu/courses/cs016/book/slides/Connectivity2x2.pdf
012 *
013 *************************************************************************/
014
015public class XBiconnected {
016        private final int[] low;
017        private final int[] pre;
018        private int cnt;
019        // private int bridges;
020        private final boolean[] articulation;
021
022        public XBiconnected(Graph G) {
023                low = new int[G.V()];
024                pre = new int[G.V()];
025                articulation = new boolean[G.V()];
026                for (int v = 0; v < G.V(); v++) low[v] = -1;
027                for (int v = 0; v < G.V(); v++) pre[v] = -1;
028
029                for (int v = 0; v < G.V(); v++)
030                        if (pre[v] == -1)
031                                dfs(G, v, v);
032        }
033
034        private void dfs(Graph G, int u, int v) {
035                int children = 0;
036                pre[v] = cnt++;
037                low[v] = pre[v];
038                for (int w : G.adj(v)) {
039                        if (pre[w] == -1) {
040                                children++;
041                                dfs(G, v, w);
042
043                                // update low number
044                                low[v] = Math.min(low[v], low[w]);
045
046                                // non-root of DFS is an articulation point if low[w] >= pre[v]
047                                if (low[w] >= pre[v] && u != v)
048                                        articulation[v] = true;
049                        }
050
051                        // update low number - ignore reverse of edge leading to v
052                        else if (w != u)
053                                low[v] = Math.min(low[v], pre[w]);
054                }
055
056                // root of DFS is an articulation point if it has more than 1 child
057                if (u == v && children > 1)
058                        articulation[v] = true;
059        }
060
061        // is vertex v an articulation point?
062        public boolean isArticulation(int v) { return articulation[v]; }
063
064        // test client
065        public static void main(String[] args) {
066                args = new String [] { "6", "6" };
067                int V = Integer.parseInt(args[0]);
068                int E = Integer.parseInt(args[1]);
069                Graph G = GraphGenerator.simple(V, E);
070                G.toGraphviz ("g");
071                StdOut.println(G);
072
073                XBiconnected bic = new XBiconnected(G);
074
075                // print out articulation points
076                StdOut.println();
077                StdOut.println("Articulation points");
078                StdOut.println("-------------------");
079                for (int v = 0; v < G.V(); v++)
080                        if (bic.isArticulation(v)) StdOut.println(v);
081        }
082
083
084}
085