Skip to content
/ Redux Public
forked from ReduxISU/Redux

The official backend repository for the Redux project

0 stars 12 forks Branches Tags Activity
Star
Notifications You must be signed in to change notification settings

Diyapandey0/Redux

BranchesTags
 
 

Repository files navigation

Redux Backend

An interactive, dynamic knowledgebase of canonical Computer Science problems, solutions, and reductions

Idaho State University

Live Demo

Table of Contents

About Redux

Redux is a web-based platform that makes computational complexity theory accessible and interactive. It provides:

  • Interactive Problem Visualization: See canonical NP-Complete problems in action
  • Reduction Framework: Understand how problems reduce to one another
  • Solver & Verifier Tools: Execute and verify solutions to computational problems
  • Educational Resource: Built on Karp's 21 NP-Complete problems and beyond

The backend is designed to be adaptable and can work with different frontends. The default frontend can be found at Redux_GUI.

Features

NP-Complete Problem Library: Comprehensive collection of canonical CS problems
RESTful API: Full API access with Swagger documentation
Solver Algorithms: Multiple solving strategies for each problem
Certificate Verification: Verify solutions efficiently
Reduction Mappings: Visualize and understand problem reductions
Graph & SAT Visualizations: Interactive problem representations

Quick Start

Prerequisites

Installation

  1. Clone the repositories

    # Backend
git clone https://github.com/ReduxISU/Redux.git

# Frontend (optional, for full local setup)
git clone https://github.com/ReduxISU/Redux_GUI.git

  2. Run the Backend

    Navigate to the Redux directory and run:

    dotnet run

    The API will be available at http://127.0.0.1:27000/

  3. Access Swagger API Documentation

    Open your browser to: http://127.0.0.1:27000/swagger/index.html

Development Mode

For automatic reloading during development:

dotnet watch --project API.csproj run -- --project API.csproj

Docker Deployment

docker build -t reduxapi .
docker run -it --rm -p 27000:80 --name reduxapi reduxapi

Documentation

Core Concepts

Problems

All problems are located in Problems/NPComplete/. Each problem follows a standardized structure:

NPC_PROBLEMNAME/
├── PROBLEMNAME_class.cs      # Implements IProblem interface
├── Solvers/                  # Solver implementations
├── Verifiers/                # Verifier implementations
└── PROBLEMNAME_controller.cs # API endpoints

Interfaces

Redux uses five main interfaces that problems must implement:

  1. IProblem - Main problem interface with solver, verifier, and visualization
  2. ISolver - Solves problem instances
  3. IVerifier - Verifies solution certificates
  4. IVisualization - Creates visual representations
  5. IReduction - Maps one problem to another

For detailed interface documentation, see the Interfaces section below.

API Usage

The Redux API is documented using SwaggerUI. All endpoints can be tested directly from the Swagger interface at:

  • Production: https://api.redux.portneuf.cose.isu.edu/swagger/index.html
  • Local: http://127.0.0.1:27000/swagger/index.html

Adding API Endpoints

When adding an API endpoint, the current practice is to add a controller into the problem reduction controller class, which corresponds to a specific class for that problem reduction. Each reduction has its own controller. The current naming convention is NameOfRelatedClassController.

Important: If not named correctly, the GUI will not function properly.

Controller Attributes:

API Attributes

Each controller should include:

  • [Route("controller")]
  • [Tag("Problem Name")]

XML Documentation Comments

API calls must include proper XML comments to appear in SwaggerUI documentation. Add these comments above each HTTP call:

  • <summary> - Brief description of API call
  • <param name="parameterName" example="example value"> - Description of parameter
  • <response code="200"> - What call returns

Example:

/// <summary>Brief description of API call</summary>
/// <param name="parameterName" example="example value">Description of parameter</param>
/// <response code="200">What call returns</response>

SPADE Parser

SPADE is used for parsing instance strings into usable data structures. It should be used in problem class constructors.

Documentation: SPADE GitHub

Example usage can be found in the Knapsack problem class.

Architecture

Backend Structure

Redux/
├── Problems/
│   └── NPComplete/          # NP-Complete problem implementations
├── Interfaces/              # Core interfaces and graph utilities
├── AdditionalControllers/
│   └── Navigation/          # API controllers for problem retrieval
└── API.csproj              # Main project file

Key Components

Graph Utilities

For graph-based problems, use UtilCollectionGraph from the Interfaces folder. It includes:

  • Automatic handling of directed/undirected graphs
  • Weight management
  • ToAPIGraph() conversion for API responses

Navigation Controllers

Located in AdditionalControllers/Navigation/, these controllers handle:

  • Retrieving available problems
  • Listing algorithms
  • Problem metadata

** Caution**: The frontend heavily relies on these controllers. Changes should be made carefully.

Contributing

We welcome contributions! Join our community:

Branching Strategy

  • Production Branch: CSharpAPI
  • Development Branch: develop

Workflow:

  1. Make changes on the develop branch (or create a feature branch)
  2. Create a pull request to develop
  3. Assign a reviewer
  4. After code review, merge into develop
  5. Periodically merge develop into CSharpAPI for production

** Important**: DO NOT complete pull requests before they are reviewed.

Definition of Done

New Problems

  • Correctly implements all interfaces
  • Includes at least one solver
  • Includes at least one verifier
  • Tests created and passing

New Reductions

  • Correctly implements all interfaces
  • Includes working solution mapping function
  • Located in correct folder
  • Has API endpoint for reduction info, reduced string, and mapped solution

API Additions

  • Controller named properly
  • Controller in proper controller class
  • Proper XML comments for all HTTP calls

Adding New Problems

  1. Create folder: Problems/NPComplete/NPC_PROBLEMNAME/

  2. Implement required files:

Folder Structure:

Problem Folder Structure

Each problem folder should include 4 files/folders:

  • PROBLEMNAME_class.cs (implements IProblem)
  • Solvers/ folder with at least one solver
  • Verifiers/ folder with at least one verifier
  • PROBLEMNAME_controller.cs with API endpoints
  1. Write tests
  2. Submit pull request

Testing

Testing uses Xunit. All new problems should include tests for:

  • Verifier correctness
  • Solver correctness
  • Reduction algorithms

Run tests with:

dotnet test

Interfaces Detail

IProblem

Main interface with generic types for ISolver, IVerifier, and IVisualization.

Required Fields:

  • problemName - Human-readable name
  • formalDefinition - Mathematical definition
  • problemDefinition - Readable description
  • source - Citation
  • defaultInstance - Example instance
  • contributors - Developer names
  • defaultSolver - Default solver object
  • defaultVerifier - Default verifier object

Required Constructors:

  • Constructor taking a string instance
  • Constructor using default instance

ISolver

Implements solving algorithms.

Required Methods:

  • Solve(problem) → Returns solution string
  • GetSteps() → (Optional) Returns first 99 solution steps

IVerifier

Verifies solution certificates.

Required Methods:

  • Verify(problem, certificate) → Returns boolean

IVisualization

Creates visual representations.

Visualization Types:

  • Boolean Satisfiability - Uses API_SAT
  • Graph D3 - Uses API_graph

Required Methods:

  • Visualize(problem) → Returns API_JSON
  • SolvedVisualization(problem, solution) → (Optional) Highlights solution
  • StepsVisualization(steps) → (Optional) Visualizes steps

IReduction

Maps one problem to another.

Required Fields:

  • reductionFrom - Starting problem
  • reductionTo - Resulting problem
  • gadgets - UI element relationships for highlighting

Required Methods:

  • Reduce() - Performs the reduction
  • MapSolutions(certificate) - Maps solution from one problem to another

Production Deployment

SystemD Service (Linux)

  1. Install service file to /etc/systemd/system/redux.service
  2. Configure paths for your environment
  3. Enable and start:
systemctl daemon-reload
systemctl enable redux.service
systemctl start redux.service

Updating Production

cd [working directory]
git pull origin
sudo systemctl restart redux.service

Viewing Logs

journalctl -xeu redux

For complete production setup instructions, see the production documentation in the repository.

Contributors

This project is developed by students and faculty at Idaho State University's Computer Science Department.

For a complete list of contributors, visit our About Us page.

Additional Resources

Documentation Links

Related Repositories

License

This project is developed at Idaho State University's Computer Science Department.

Contact & Support

  • Issues: Please use GitHub Issues for bug reports and feature requests
  • Discord: Join our community
  • Email: Contact the CS department at Idaho State University

About

The official backend repository for the Redux project

Resources

Readme
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages

  • C# 99.9%
  • Other 0.1%