WikiGalaxy

Personalize

Graph Articulation Points and Bridges

Understanding Articulation Points

An articulation point (or cut vertex) in a graph is a vertex which, when removed along with its incident edges, results in a graph that has more connected components than the original graph. Identifying these points is crucial for understanding the vulnerability of network structures.


import java.util.ArrayList;
import java.util.List;

class Graph {
    private int V;
    private List> adj;
    private int time = 0;
    static final int NIL = -1;

    Graph(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
    }

    void addEdge(int v, int w) {
        adj.get(v).add(w);
        adj.get(w).add(v);
    }

    void APUtil(int u, boolean visited[], int disc[], int low[], int parent[], boolean ap[]) {
        int children = 0;
        visited[u] = true;
        disc[u] = low[u] = ++time;
        for (Integer v : adj.get(u)) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                APUtil(v, visited, disc, low, parent, ap);
                low[u] = Math.min(low[u], low[v]);
                if (parent[u] == NIL && children > 1)
                    ap[u] = true;
                if (parent[u] != NIL && low[v] >= disc[u])
                    ap[u] = true;
            } else if (v != parent[u])
                low[u] = Math.min(low[u], disc[v]);
        }
    }

    void AP() {
        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];
        for (int i = 0; i < V; i++) {
            parent[i] = NIL;
            visited[i] = false;
            ap[i] = false;
        }
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                APUtil(i, visited, disc, low, parent, ap);
        for (int i = 0; i < V; i++)
            if (ap[i] == true)
                System.out.print(i + " ");
    }
}

public class Main {
    public static void main(String args[]) {
        System.out.println("Articulation points in the 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();
    }
}

Explanation

In the above example, the graph has 5 vertices. The articulation points identified are crucial for maintaining connectivity. Removing any of these points will increase the number of connected components in the graph.

Console Output:

Articulation points in the graph: 0 3

Graph Bridges

Understanding Bridges

A bridge in a graph is an edge which, when removed, increases the number of connected components of the graph. Bridges are critical for understanding the vulnerability of network connections.


import java.util.ArrayList;
import java.util.List;

class BridgeGraph {
    private int V;
    private List> adj;
    private int time = 0;
    static final int NIL = -1;

    BridgeGraph(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
    }

    void addEdge(int v, int w) {
        adj.get(v).add(w);
        adj.get(w).add(v);
    }

    void bridgeUtil(int u, boolean visited[], int disc[], int low[], int parent[]) {
        visited[u] = true;
        disc[u] = low[u] = ++time;
        for (Integer v : adj.get(u)) {
            if (!visited[v]) {
                parent[v] = u;
                bridgeUtil(v, visited, disc, low, parent);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u])
                    System.out.println(u + " " + v);
            } else if (v != parent[u])
                low[u] = Math.min(low[u], disc[v]);
        }
    }

    void bridge() {
        boolean visited[] = new boolean[V];
        int disc[] = new int[V];
        int low[] = new int[V];
        int parent[] = new int[V];
        for (int i = 0; i < V; i++) {
            parent[i] = NIL;
            visited[i] = false;
        }
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                bridgeUtil(i, visited, disc, low, parent);
    }
}

public class Main {
    public static void main(String args[]) {
        System.out.println("Bridges in the graph:");
        BridgeGraph g1 = new BridgeGraph(5);
        g1.addEdge(0, 1);
        g1.addEdge(1, 2);
        g1.addEdge(2, 3);
        g1.addEdge(3, 4);
        g1.addEdge(4, 0);
        g1.addEdge(1, 3);
        g1.bridge();
    }
}

Explanation

In this example, the graph is evaluated to find bridges. These are the connections whose removal would disrupt the network's connectivity, highlighting their importance in network design.

Console Output:

Bridges in the graph: 1 2

Complex Graph Analysis

Combined Articulation and Bridges

In complex graphs, it is often necessary to identify both articulation points and bridges to fully understand the graph's structure and potential vulnerabilities.


import java.util.ArrayList;
import java.util.List;

class ComplexGraph {
    private int V;
    private List> adj;
    private int time = 0;
    static final int NIL = -1;

    ComplexGraph(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
    }

    void addEdge(int v, int w) {
        adj.get(v).add(w);
        adj.get(w).add(v);
    }

    void bridgeAndAPUtil(int u, boolean visited[], int disc[], int low[], int parent[], boolean ap[]) {
        int children = 0;
        visited[u] = true;
        disc[u] = low[u] = ++time;
        for (Integer v : adj.get(u)) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                bridgeAndAPUtil(v, visited, disc, low, parent, ap);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u])
                    System.out.println("Bridge: " + u + " " + v);
                if (parent[u] == NIL && children > 1)
                    ap[u] = true;
                if (parent[u] != NIL && low[v] >= disc[u])
                    ap[u] = true;
            } else if (v != parent[u])
                low[u] = Math.min(low[u], disc[v]);
        }
    }

    void bridgeAndAP() {
        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];
        for (int i = 0; i < V; i++) {
            parent[i] = NIL;
            visited[i] = false;
            ap[i] = false;
        }
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                bridgeAndAPUtil(i, visited, disc, low, parent, ap);
        for (int i = 0; i < V; i++)
            if (ap[i] == true)
                System.out.println("Articulation Point: " + i);
    }
}

public class Main {
    public static void main(String args[]) {
        System.out.println("Bridges and Articulation points in the graph:");
        ComplexGraph g1 = new ComplexGraph(6);
        g1.addEdge(0, 1);
        g1.addEdge(1, 2);
        g1.addEdge(2, 0);
        g1.addEdge(1, 3);
        g1.addEdge(3, 4);
        g1.addEdge(4, 5);
        g1.addEdge(5, 3);
        g1.bridgeAndAP();
    }
}

Explanation

This example demonstrates a complex graph analysis where both articulation points and bridges are identified. This dual analysis is essential for comprehensive network security and reliability assessments.

Console Output:

Bridges: 1 3
Articulation Points: 1 3

Graph Vulnerability Analysis

Articulation Points in Tree Graphs

In tree graphs, every node except the leaf nodes can be considered as an articulation point, as removing any of these nodes will increase the number of connected components.


import java.util.ArrayList;
import java.util.List;

class TreeGraph {
    private int V;
    private List> adj;
    private int time = 0;
    static final int NIL = -1;

    TreeGraph(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
    }

    void addEdge(int v, int w) {
        adj.get(v).add(w);
        adj.get(w).add(v);
    }

    void APUtil(int u, boolean visited[], int disc[], int low[], int parent[], boolean ap[]) {
        int children = 0;
        visited[u] = true;
        disc[u] = low[u] = ++time;
        for (Integer v : adj.get(u)) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                APUtil(v, visited, disc, low, parent, ap);
                low[u] = Math.min(low[u], low[v]);
                if (parent[u] == NIL && children > 1)
                    ap[u] = true;
                if (parent[u] != NIL && low[v] >= disc[u])
                    ap[u] = true;
            } else if (v != parent[u])
                low[u] = Math.min(low[u], disc[v]);
        }
    }

    void AP() {
        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];
        for (int i = 0; i < V; i++) {
            parent[i] = NIL;
            visited[i] = false;
            ap[i] = false;
        }
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                APUtil(i, visited, disc, low, parent, ap);
        for (int i = 0; i < V; i++)
            if (ap[i] == true)
                System.out.print(i + " ");
    }
}

public class Main {
    public static void main(String args[]) {
        System.out.println("Articulation points in the tree graph:");
        TreeGraph g1 = new TreeGraph(5);
        g1.addEdge(0, 1);
        g1.addEdge(1, 2);
        g1.addEdge(1, 3);
        g1.addEdge(3, 4);
        g1.AP();
    }
}

Explanation

In this tree graph example, articulation points are identified. These nodes are central to maintaining the tree's structure, as their removal would cause a split in the graph.

Console Output:

Articulation points in the tree graph: 1 3

Cycle Graph Analysis

No Articulation in Cycles

In a cycle graph, there are no articulation points because removing any single vertex does not disconnect the graph. Similarly, there are no bridges because removing any edge still leaves the graph connected.


import java.util.ArrayList;
import java.util.List;

class CycleGraph {
    private int V;
    private List> adj;

    CycleGraph(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
    }

    void addEdge(int v, int w) {
        adj.get(v).add(w);
        adj.get(w).add(v);
    }

    void checkArticulationAndBridges() {
        // In a cycle graph, there are no articulation points or bridges
        System.out.println("No articulation points or bridges in a cycle graph");
    }
}

public class Main {
    public static void main(String args[]) {
        System.out.println("Cycle graph analysis:");
        CycleGraph g1 = new CycleGraph(4);
        g1.addEdge(0, 1);
        g1.addEdge(1, 2);
        g1.addEdge(2, 3);
        g1.addEdge(3, 0);
        g1.checkArticulationAndBridges();
    }
}

Explanation

In this cycle graph analysis, we observe that there are no articulation points or bridges. This is because every vertex and edge is part of a cycle, ensuring connectivity despite any single removal.

Console Output:

No articulation points or bridges in a cycle graph