Graph Processing (Java)

Overview

This project implements a command-line utility that processes a directed graph from a CSV file and computes key structural and algorithmic properties.

The program:

• Parses a graph from an edge list
• Determines whether the graph is a DAG (Directed Acyclic Graph)
• Computes maximum in-degree and out-degree
• Runs the PageRank algorithm and outputs min/max scores

---

Features

• DAG detection using topological sorting (Kahn’s Algorithm)
• Degree calculations (in-degree and out-degree)
• PageRank implementation (no external libraries)
• Handles dangling nodes correctly
• Fully executable with a single command

---

Project Structure

graph-project/
├── graph_solution        # Executable shell script
├── src/
│   └── Main.java         # Main Java implementation
├── bin/                  # Compiled classes (generated automatically)
├── test_cases/           # Sample input/output files
│   ├── graph1.csv
│   ├── graph1_output.txt
│   ├── graph2.csv
│   ├── graph2_output.txt
│   ├── graph3.csv
│   └── graph3_output.txt
├── README.md
└── .gitignore

---

Requirements

• Java JDK 8 or higher
• Unix-like environment (Linux / macOS / WSL)

---

How to Run

Step 1: Make the script executable

chmod +x graph_solution

Step 2: Run the program

./graph_solution test_cases/graph1.csv

---

Input Format

• CSV file
• Each line represents a directed edge:

source_node,target_node

Example:

0,1
0,2
1,3
2,3

---

Output Format

The program prints exactly 5 lines:

is_dag: true
max_in_degree: 2
max_out_degree: 2
pr_max: 0.372381
pr_min: 0.135169

Notes

• Boolean values are lowercase (true / false)
• PageRank values are rounded to 6 decimal places

---

PageRank Details

• Damping factor: 0.85
• Iterations: 20
• Initial distribution: uniform
• Dangling nodes: distributed equally to all nodes

---

Build Behavior

• No manual compilation needed

• The graph_solution script:

  • Compiles Java code automatically
  • Runs the program

---

Testing

Sample test cases are included in the test_cases/ directory.

You can verify correctness by comparing your output with:

graph1_output.txt
graph2_output.txt
graph3_output.txt

---

Notes for Evaluators

• The program is designed to run with a single command
• No external dependencies are required
• All algorithms are implemented manually as required
• The repository can be cloned and executed directly

---

Author

Sumughan Divina

---