Articulation Point Analysis and Biconnected Components

---

Languages & Tools

This project is a Java command-line application for graph reliability analysis. It can read an undirected graph from CSV or generate a scale-free network, then analyze the graph using an iterative Tarjan-style depth-first search.

The current version reports both:

• articulation points: vertices whose removal disconnects part of the graph
• biconnected components: maximal blocks that stay connected after any single internal vertex failure

Project Analysis

At a high level, the repository has three main layers:

1. Input and graph construction
2. Reliability analysis
3. Reporting and visualization

The flow is:

1. App.java parses CLI arguments.
2. The graph is either loaded from sample_graph.csv or generated by NetworkSimulator.java.
3. ReliabilityAnalyzer.java performs one iterative DFS traversal and computes articulation points, biconnected components, and structural metrics.
4. App.java prints a ranked terminal summary.
5. If requested, GraphVisualizer.java exports an interactive HTML visualization.

---

What It Does

• Loads a graph from CSV, or generates a scale-free graph
• Finds articulation points and ranks their impact
• Prints the top critical nodes in the terminal
• Optionally exports an interactive HTML graph

---

Features

• CSV-based graph input
• synthetic scale-free graph generation
• articulation-point detection
• biconnected-component extraction
• graph classification
• top critical-node ranking
• top BCC summary table
• optional HTML export for smaller graphs
• PowerPoint and Word documentation in docs/

Project Structure

articulation-point-analysis/
├── docs/
│   ├── Articulation_Point_Analysis_and_Biconnected_Components.pptx
│   ├── Articulation_Point_Analysis_DAA_PBL_Report.docx
│   ├── PROJECT_ANALYSIS.md
│   ├── generate_office_documents.ps1
│   └── generate_presentation.py
├── src/
│   └── main/
│       └── java/
│           └── com/
│               └── network/
│                   ├── App.java
│                   ├── Graph.java
│                   ├── GraphVisualizer.java
│                   ├── NetworkSimulator.java
│                   └── ReliabilityAnalyzer.java
├── .gitignore
├── LICENSE
├── README.md
└── sample_graph.csv

---

Requirements

• Java JDK 11 or later
• Windows PowerShell (commands below use PowerShell syntax) To build and run Articulation Point Analysis, ensure the following prerequisites are installed and configured on your system:

1. Java Development Kit (JDK)

• Version: JDK 11 or later (recommended: JDK 17 for long-term support).
• Verify installation:

  java -version
  javac -version

• Both commands should return the installed version.

2. Build Tools

• Maven (optional, if you want dependency management and automated builds).
  • Install from Apache Maven.
  • Verify installation:

    mvn -v

3. Operating System

• Works on Windows, Linux, and macOS.
• Commands in this README use Windows PowerShell syntax; adapt accordingly for other shells (e.g., Bash).

4. IDE / Editor

• Recommended: Visual Studio Code or IntelliJ IDEA.
• Install Java extensions/plugins for syntax highlighting, debugging, and project management.

5. Visualization Tools (Optional)

• GraphViz (if you want advanced graph rendering beyond the built-in Swing/HTML visualizer).
• Install from GraphViz.org.
• Verify installation:

  dot -V

6. Browser

• Any modern browser (Chrome, Edge, Firefox) to open the generated HTML visualizations.

---

Compile

From repository root (D:\ARTICULATION-POINT-ANALYSIS):

javac -d out src/main/java/com/network/*.java

From source folder (D:\ARTICULATION-POINT-ANALYSIS\src\main\java):

javac (Get-ChildItem -Path .\com\network\*.java | ForEach-Object { $_.FullName })

Run

Option A: Run from repository root (recommended)

java -cp out com.network.App --file sample_graph.csv --visualize scale_free_network.html

Generate a graph instead of loading CSV:

java -cp out com.network.App --generate 1000 3 --visualize scale_free_network.html

Option B: Run from src/main/java

java com.network.App --file ..\..\..\sample_graph.csv --visualize ..\..\..\scale_free_network.html

Generate and visualize:

java com.network.App --generate 1000 3 --visualize ..\..\..\scale_free_network.html

Open the Graph Visualization

After running with --visualize, open:

• scale_free_network.html

in your browser.

CSV Input Format

Each non-empty line should contain one undirected edge:

nodeA,nodeB
nodeB,nodeC

Notes:

• Lines starting with # are treated as comments.
• Self-loops and duplicate edges are ignored by the graph builder.

Command Reference

java -cp . com.network.App --file <path_to_csv> [--visualize <output.html>]
java -cp . com.network.App --generate <V> <m> [--visualize <output.html>]

• <V>: number of nodes
• <m>: number of edges from each new node in generation

Important Notes

• Visualization is skipped for graphs with more than 2000 nodes.
• Generated graphs include a small terminal chain to ensure articulation points are present.

Troubleshooting

• Could not find or load main class com.network.App:
  • Use the correct classpath (-cp out from root), or
  • run from src/main/java where compiled package folders exist.
• No HTML output:
  • Ensure --visualize <path>.html is passed.
• Invalid file path:
  • Use relative paths from your current directory, or absolute paths.

---

Source File Responsibilities

src/main/java/com/network/App.java

The CLI entry point.

Responsibilities:

• parses --file, --generate, and --visualize
• validates argument combinations
• loads or generates the graph
• runs the analyzer
• prints timing, memory, and ranked results
• prints a one-line final summary

src/main/java/com/network/Graph.java

The in-memory graph container.

Responsibilities:

• stores the graph as adjacency lists
• maps string node IDs to compact integer indices
• prevents self-loops and duplicate undirected edges
• exposes vertex/edge counts and adjacency access

src/main/java/com/network/NetworkSimulator.java

The graph generator.

Responsibilities:

• generates a Barabasi-Albert style scale-free graph
• uses preferential attachment
• adds a short tail so articulation behavior is visible in demos

src/main/java/com/network/ReliabilityAnalyzer.java

The core algorithm module.

Responsibilities:

• performs iterative Tarjan-style DFS
• computes discovery and low-link arrays
• detects articulation points
• extracts biconnected components from an edge stack
• counts bridge-like blocks
• computes the largest robust block
• classifies whether the full graph is biconnected

src/main/java/com/network/GraphVisualizer.java

The optional reporting/export module.

Responsibilities:

• writes a browser-openable HTML file
• highlights articulation points in red
• color-codes biconnected blocks
• shows BCC membership details in tooltips

Algorithm Explanation

The analyzer uses Tarjan-style DFS in O(V + E) time.

Core idea

For each node u:

• disc[u] = when the node was first discovered
• low[u] = the earliest ancestor reachable from u using tree edges and at most one back edge

Articulation-point rule

If a DFS tree edge goes from parent to child and:

low[child] >= disc[parent]

then the child subtree cannot reconnect to an ancestor of parent. That means parent is separating that subtree and may be an articulation point.

Biconnected-component rule

While DFS runs, traversed edges are pushed onto an edge stack. Whenever:

low[child] >= disc[parent]

all edges from the top of the stack down to (parent, child) form one biconnected component.

So the project gets articulation points and BCCs in the same traversal.

High-Level Pseudocode

analyze(graph):
    initialize disc[], low[], subtreeSize[]
    initialize articulation metrics
    initialize DFS stack
    initialize edge stack for BCC extraction

    for each vertex u:
        if u is unvisited:
            start iterative DFS from u
            while DFS stack not empty:
                process next neighbor
                if neighbor is unvisited:
                    push DFS state
                    push tree edge on edge stack
                else if neighbor is a back edge:
                    update low[u]
                    push back edge on edge stack

                when finishing a child:
                    propagate low[] and subtree sizes upward
                    if low[child] >= disc[parent]:
                        parent separates child subtree
                        pop one biconnected component from edge stack

    derive articulation points from separated-subtree counts
    sort critical nodes by impact
    summarize BCC sizes and block types
    return analysis result

Graph Classification Logic

The project prints one of these labels:

• Biconnected Graph: exactly one connected component and no articulation points
• Connected but not Biconnected: one connected component but at least one articulation point
• Disconnected Graph: more than one connected component

Requirements

• Java JDK 11 or later
• PowerShell or any terminal
• a modern browser if you want HTML visualization
• Microsoft Word and PowerPoint on Windows if you want to regenerate the polished docs in docs/

How To Compile

From the repository root:

New-Item -ItemType Directory -Force -Path out | Out-Null
javac -d out src/main/java/com/network/*.java

How To Run

1. Analyze the provided CSV graph

java -cp out com.network.App --file sample_graph.csv

2. Generate a scale-free graph and analyze it

java -cp out com.network.App --generate 20 2

3. Export HTML visualization for a CSV graph

java -cp out com.network.App --file sample_graph.csv --visualize output.html

4. Export HTML visualization for a generated graph

java -cp out com.network.App --generate 50 2 --visualize output.html

CSV Input Format

Each non-empty line represents one undirected edge:

A,B
B,C
C,D

Supported behavior:

• lines starting with # are treated as comments
• blank lines are ignored
• self-loops are ignored
• duplicate edges are ignored

Example Output Summary

A typical run reports:

• node count
• edge count
• analysis time
• memory used during analysis
• articulation-point count
• biconnected-component count
• connected-component count
• graph classification
• bridge-like component count
• largest biconnected block size
• top critical nodes
• top BCCs
• final brief summary line

Documentation Assets

The docs/ folder contains:

• PROJECT_ANALYSIS.md: short written architectural analysis
• Articulation_Point_Analysis_and_Biconnected_Components.pptx: presentation deck
• Articulation_Point_Analysis_DAA_PBL_Report.docx: Word report
• generate_office_documents.ps1: Windows Office automation script for regenerating the polished documents
• generate_presentation.py: optional fallback presentation generator

To regenerate the Office documents on Windows:

powershell -ExecutionPolicy Bypass -File docs/generate_office_documents.ps1

Repository Cleanup Notes

The repository has been cleaned so that generated/runtime files are not treated as source files.

Ignored artifacts now include:

• out/
• compiled .class files
• generated .html visualizations
• Office temporary files
• IDE metadata

Final Validation Checklist

The project should be checked with these commands after changes:

javac -d out src/main/java/com/network/*.java
java -cp out com.network.App --file sample_graph.csv
java -cp out com.network.App --generate 20 2
java -cp out com.network.App --file sample_graph.csv --visualize output.html

Future Improvements

• add unit tests for small canonical graphs
• add JSON export for analysis results
• add explicit bridge reporting as a first-class metric
• add benchmark scripts for larger generated graphs

Contributors

This project was developed as part of the DAA Project Based Learning (PBL) initiative under Code Crew Nexus.

• M. Sai Krishna
• Rishit Ghosh
• Md. Abdul Rayain

Future contributors welcome! Fork the repo, submit pull requests, and help improve the project.

---