Lost Robots Retrieval - Graph Generator & Analyzer

This repository contains a modular, object-oriented Graph Generator and Validator tool developed for the final project of the Advanced Algorithms course at the Iran University of Science and Technology (IUST).

The project models a city as a connected, weighted, undirected graph where robots are scattered across random vertices. It generates customized test scenarios (instances) incorporating time costs for movements (Remote) and simulated student scout reports (Scout) with configurable error rates.

---

Software Engineering Architecture

The codebase is designed with a strict adherence to core software engineering methodologies:

• SOLID Principles: Each module has a single, well-defined responsibility (e.g., generation logic is isolated from file storage and analytics).
• DRY (Don't Repeat Yourself): Reusable data models and utility services prevent code duplication.
• Layered Architecture: Clear separation between data representation (models.py), configuration management (config_loader.py), core algorithm mechanics (generator.py), and persistence (storage.py).

---

Project Structure

graph_generator/
├── config.example.json  # Template configuration file
├── main.py              # Entry point for graph generation
├── analyzer.py          # Independent CLI tool for graph validation and analysis
├── config_loader.py     # Configuration loading and validation service
├── models.py            # Object-oriented data structures for graphs and instances
├── generator.py         # Core algorithms for spanning trees and instance creation
├── storage.py           # Output file management and collision handling
└── .gitignore           # Ignores local config.json and generated outputs

---

Setup & Configuration

To prevent accidental commits of local settings, the primary configuration file (config.json) is included in .gitignore. A template file named config.example.json is provided in the root directory.

1. Initialize Configuration

Before running the project, create your local configuration file by copying the example template:

cp config.example.json config.json

2. Configuration Parameters

Open config.json and adjust the parameters according to your desired test scenarios. Below is the description of each key:

Parameter	Type	Default	Description
default_city	String	"NewYork"	The base name for the generated city. Used for naming output JSON files.
vertices	Integer	100	Total number of vertices (nodes) in the city graph.
scout_time	Integer	1	Time unit cost incurred per student when executing a Scout operation.
students	Integer	40	Total number of student scouts available for reporting.
robots_count	Integer	5	Number of lost robots placed randomly across the graph vertices.
instances_count	Integer	1	Number of independent test scenarios (instances) to generate per graph.
student_error_min	Integer	0	Minimum number of vertices a student will give false reports about.
student_error_max	Integer	50	Maximum number of vertices a student will give false reports about (capped at half of the vertices).
edge_weight_min	Integer	400	Minimum time cost (weight) for traversing an edge during a Remote operation.
edge_weight_max	Integer	2200	Maximum time cost (weight) for traversing an edge during a Remote operation.
extra_edges_ratio	Float	1.5	Ratio of additional random edges added on top of the base spanning tree to increase graph density while preserving connectivity.

---

Usage

Ensure you have Python 3.x installed. No external dependencies are required for the generator or analyzer, as they utilize Python's standard library.

Generating Graphs

To generate a new graph and its corresponding instances, execute the main entry point:

python main.py

• Output: The program generates a JSON file inside the outputs/ directory (e.g., outputs/NewYork.json).
• Name Collision Handling: If NewYork.json already exists, the storage service automatically appends a numeric suffix (e.g., outputs/NewYork_1.json, outputs/NewYork_2.json) to prevent overwriting existing test data.

---

Analyzing & Validating Graphs

An independent CLI tool (analyzer.py) is provided to inspect generated graph files, verify connectivity constraints, and calculate statistical metrics.

Running the Analyzer

Pass the path of the target JSON file using the --file (or -f) argument:

python analyzer.py --file outputs/NewYork.json

What the Analyzer Reports

The tool parses the generated JSON file and outputs a clean console summary containing:

1. Edge Statistics:

• Total number of edges.
• Minimum, maximum, and average edge weights (checking compliance with the 400-2200 range).

2. Instance Statistics:

• Instance name and assigned Home vertex (H).

• Initial placement vertices of all robots.

• Student Error Metrics: Calculates the minimum, maximum, and average number of false reporting nodes across all students to ensure compliance with problem constraints.

Example Output

==================================================
Graph Analysis Report: NewYork
==================================================
Edge Statistics:
  Total Edges : 249
  Min Weight  : 402
  Max Weight  : 2198
  Avg Weight  : 1295.40
--------------------------------------------------
Instances Statistics:
  Instance Name        : NewYork_0
  Home Vertex          : 42
  Initial Robot Nodes  : [15, 87, 3, 91, 12]
  Student Error Counts:
    Min Errors/Student : 1
    Max Errors/Student : 49
    Avg Errors/Student : 24.85
--------------------------------------------------

---

License

This project is developed for academic purposes at the Iran University of Science and Technology (IUST) with MIT LICENCE.