Point Set Embedder

A high-performance CUDA-accelerated solver for the point set embedding problem, featuring GPU-optimized algorithms for embedding graphs onto predefined point sets without edge crossings.

Overview

The point set embedding problem asks for an injective mapping from graph vertices to a given set of points such that no edges cross when the graph is drawn. Given:

• A topology graph G = (V, E) with n vertices and m edges
• A set P ⊂ ℝ² of points where |P| ≥ n

Find an injective function f: V → P such that edges don't cross vertices in the resulting drawing.

This is a more restrictive variant of Crossing-Minimal Point-Set Embedding.

Features

• GPU-Accelerated: CUDA implementation for high-performance solving
• Multiple Algorithms: Random search and nearest neighbor solvers
• Scalable: Handles graphs up to ~20,000 vertices (RTX 2080Ti w/ 12GB RAM)
• ILP Support: Integer Linear Programming solver for smaller instances (~20 vertices)
• Visualization Tools: Built-in problem and solution visualization

Quick Start

Prerequisites

• NVIDIA GPU with CUDA capability
• Ubuntu 20.04/22.04
• CUDA 12.0+

Installation

1. Install dependencies:

   # C++ compiler
   sudo apt install gcc-10 g++-10 -y
   
   # CMake
   sudo snap install cmake --channel=3.25.2/stable --classic
   
   # CUDA 12
   wget https://developer.download.nvidia.com/compute/cuda/12.0.0/local_installers/cuda_12.0.0_525.60.13_linux.run
   sudo sh cuda_12.0.0_525.60.13_linux.run --toolkit --toolkitpath=/opt/cuda
   
   # Python dependencies (for visualization)
   pip install -r requirements.txt

2. Build the project:

   cmake -DCMAKE_BUILD_TYPE=Release -B build-release
   cmake --build build-release -j $(nproc)

Usage

Solve a problem instance:

./build-release/honeybadger random -i problems/g1_t1.json

Use nearest neighbor solver with hints:

./build-release/honeybadger nearest -i problems/g1_t1.json -f 0 99

Visualize problems and solutions:

./tools/visualize_problem.py   # Output: out/problems/
./tools/visualize_solution.py  # Output: out/solutions/

Advanced Configuration

Optional Dependencies

ccache (faster compilation):

sudo apt install ccache -y
sudo /usr/sbin/update-ccache-symlinks
ccache -F 0 && ccache -M 0

Gurobi (ILP solver for small instances):

wget https://packages.gurobi.com/9.5/gurobi9.5.2_linux64.tar.gz
tar -xf gurobi9.5.2_linux64.tar.gz
cp -r gurobi952 /opt/gurobi
# Get academic license at https://www.gurobi.com/downloads/free-academic-license
/opt/gurobi/linux64/bin/grbgetkey <your-license-key>

Command Line Options

honeybadger <algorithm> [options]

Algorithms:
  random    GPU-accelerated random search (recommended)
  nearest   Nearest neighbor solver (best with hints)

Options:
  -i, --input <file>     Input JSON problem file
  -o, --output <file>    Output JSON solution file
  -f, --fix <v> <p>      Fix vertex v to point p (hint)
  -m, --mode <mode>      init | improve | init_and_improve
  -n, --neighbor <size>  Neighborhood size for local search

---

Built with CUDA • Optimized for NVIDIA GPUs • Academic Research Tool