Lee's Algorithm for Routing

This project provides a C++ implementation of Lee's algorithm (also known as Breadth-First Search or BFS on a grid) to find the shortest, non-overlapping paths for multiple nets on a 2D grid, simulating a routing problem.

Features

• Lee's Algorithm: Utilizes BFS to guarantee the shortest path for a single net.
• Multi-Net Routing: Capable of routing multiple source-destination pairs (nets).
• Obstacle Avoidance: Recognizes pre-defined obstacle areas on the grid and routes around them.
• Backtracking for Non-Overlapping Paths: If a path for a net cannot be found, the algorithm backtracks, removes a previously routed path, and attempts to find a new configuration.
• Custom File I/O: Parses a specific input format for grid dimensions, obstacles, and nets, and generates a corresponding output file with the routing solution.

Project Structure

.
├── case1/              # Example test case 1
├── case2/              # Example test case 2
├── src/                # Source code
│   ├── graph.cpp
│   ├── graph.h
│   ├── lee_algorithm.cpp
│   ├── lee_algorithm.h
│   ├── main.cpp
│   └── pair_point_hash.h
├── Makefile.mk         # Makefile for building the project
└── Readme.md           # This readme file

Usage

Prerequisites

• A C++17 compatible compiler (e.g., g++)
• make build automation tool

Building the Project

1. Clone the repository.

2. Navigate to the project's root directory.

3. Compile the source code by running make:

   make

   This will create an executable named main in the root directory.

4. To clean up build artifacts (object files and the executable), run:

   make clean

Running the Application

Execute the program from the command line, providing the input and output file paths as arguments.

./main <input_file_path> <output_file_path>

Example:

./main case1/case1.in case1/my_output.out

This command will read the grid configuration from case1/case1.in, perform the routing, and write the results to case1/my_output.out.

File Formats

Input File Format

The input file defines the grid, obstacles, and nets to be routed.

• .row <number>: Specifies the number of rows in the grid.
• .col <number>: Specifies the number of columns in the grid.
• .blk <count>: Defines the number of obstacle blocks. The following <count> lines each contain four integers x1 y1 x2 y2 representing the top-left and bottom-right corners of a rectangular obstacle.
• .net <count>: Defines the number of nets. The following <count> lines each contain a net name and four integers sx sy dx dy representing the source (start) and destination (end) coordinates of the net.

Output File Format

The output file describes the path for each successfully routed net.

• Net<ID>: The name of the net.
• begin: Start of the path description.
• <cost>: The total length of the path (number of segments).
• A series of lines with x1 y1 x2 y2, where each line represents a straight horizontal or vertical segment of the path.
• end: End of the path description.