GridLab v2.1
GridLab is an interactive 3D visualization and editing tool for exploring Hamiltonian paths and cycles on grid graphs. Built with Three.js, it provides an environment for studying graph theory, particularly the properties of paths and cycles on rectangular lattice structures.
Overview
GridLab enables researchers and enthusiasts to:
- Generate and visualize Hamiltonian paths and cycles on 2D and 3D grid graphs
- Perform backbite moves (both automated and manual) to explore the space of Hamiltonian paths
- Apply switch moves to modify cycles and paths
- Color edges with gradients and add directional arrows
- Work with multiple grids simultaneously
- Add vertex and edge decorations for marking special structures
- Display all grid vertices for structural visualization
- Save and load complete project states
Core Concepts
Grid Graphs
A grid graph is a rectangular lattice of vertices connected by edges. GridLab supports grids of arbitrary dimensions (width × height × depth), allowing exploration of everything from 2D planar grids to complex 3D structures.
Hamiltonian Paths and Cycles
- Hamiltonian Path: A path that visits every vertex in the graph exactly once
- Hamiltonian Cycle: A path that visits every vertex exactly once and returns to the starting vertex
Backbite Moves
A backbite move is a local transformation that reconfigures a Hamiltonian path into a new one. This is a key operation for exploring the space of all Hamiltonian paths on a given grid.
Switch Moves
switch move operates on a "switchable box" - a 2×2 square where exactly two parallel edges are in the path/cycle/subgraph. The move swaps which pair is included. If we start with a Hamiltonian cycle in 3D, the move either produces a new Hamiltonian cycle or it produce a cover of the grid with two cycles. Switching any boundary box between those two cycles produces a new Hamiltonian cycle.
Getting Started
Creating Your First Grid
- Set dimensions using the Grid Dimensions controls (top right)
- Click Add Grid to create a new grid
- The grid appears in the 3D viewport with a button in the grid list at the bottom
Navigation
- Rotate: Left-click and drag (disabled for 2D grids)
- Pan: Right-click and drag (or Shift + left-click and drag)
- Zoom: Scroll wheel
- 2D Grids: Grids with one dimension = 1 use special camera mode (pan/zoom only, no rotation) for easier navigation. This can be toggled in Preferences.
Performance & Complexity
Path generation uses a backbite algorithm optimized with treap data structures. Computational complexity:
Running time ≈ c·N·log(N)
Where N = x × y × z (total vertices), c ≥ 10 is the backbite iteration multiplier, and log(N) is the cost per backbite move using treap-optimized path reversals. Enable Progressive LOD in Preferences for 1.5-2× additional speedup on large grids.
Note: Press ESC during generation to stop the process at any time.
Performance Note: For very large grids (30×30×30 and above), GPU rendering capabilities become the bottleneck, not the cost of backbite moves themselves. The treap optimization reduces backbite computational cost to near-instant O(log N) operations. To maximize performance on large grids, enable Progressive LOD in Preferences, enable Unified Edge Size to reduce draw calls by rendering all edges with the same thickness, and use Toggle Grid to hide uncolored edges, which dramatically improves rendering performance and interactivity.
Key Features
Path Generation
- Generate Path: Creates a random Hamiltonian path with colored endpoints (green = start, red = end)
- Generate Cycle: Creates a random Hamiltonian cycle
- Check Hamiltonian: Verifies if the current structure is Hamiltonian
Interactive Modes
- Backbite Mode: Manual or automated backbite transformations. Use arrow keys, PgUp, and PgDn for manual control, T key to reverse path direction
- Switch Mode: Click on 2×2 switchable boxes to perform switch moves
- Add Edge: Click edges to toggle their colors
- Arrows: Show directional arrows along an edge or generated Hamiltonian path or cycle
- Gradient Mode: Apply smooth color gradients along generated Hamiltonian paths or cycles
Decorations
- Decorate Edge: Add small cubes to mark specific edges
- Add Vertex: Place colored spheres at vertices
- Decorate Vertex: Add three orthogonal great circles as a secondary vertex marker
- BB Distance Coloring: Color all vertices at a specific backbite distance from a reference vertex
Grid Management
- Multiple Grids: Work with multiple grids simultaneously using the grid list at the bottom of the screen
- Drag to Reorder: Click and drag grid tabs to rearrange their order
- Duplicate: Create copies of grids to preserve configurations before modifications
- Per-Grid Notes: Attach rich-text notes to individual grids (draggable window)
- Sync View: Align camera position across all grids for easy comparison
Preferences
Access via Preferences button (or Shift+P) to customize:
- Switch Mode: Enable/disable box highlighting and component coloring
- Coordinate Hover: Toggle vertex/edge coordinate display on hover
- Vertex Settings: Show all grid vertices as gray spheres for structure visualization
- Edge Settings: Adjust edge click radius for easier selection
- Display: Choose from 6 themes (Paper White, Dark, Sandstone, Mist Blue, Warm Light, Contrast) and custom backgrounds
- Camera: Adjust mouse sensitivity, toggle 2D camera mode for grids with one dimension = 1, show/hide sensitivity slider
Keyboard Shortcuts
File Operations
- Ctrl+S: Save all grids
- Ctrl+L: Load grids from file
- Ctrl+M: Toggle notes window
- Esc: Stop path/cycle generation in progress
Undo/Redo
- Ctrl+Z: Undo
- Ctrl+Y: Redo
Mode Toggles
- E: Toggle edge coloring mode
- Shift+E: Toggle edge decoration mode
- Shift+A: Toggle arrows
- V: Toggle vertex mode
- Shift+V: Toggle vertex decoration mode
Backbite Mode
- Arrow Keys: Move in X-Y plane
- Page Up/Down: Move in Z direction
- T: Reverse path direction
Use Cases
- Research: Hamiltonian path/cycle reconfiguration, grid graph structure analysis.
- Education: Graph theory teaching, algorithm visualization, 3D spatial reasoning
- Art: Generative patterns, color studies, aesthetic exploration
Tips
- Use Toggle Grid to hide uncolored edges on large grids
- Enable Plane Controls to highlight cross-sections of 3D grids
- Use gradient mode to visualize position along long paths
- Add vertex markers at key positions for reference
- In Preferences, enable "Show all grid vertices" to visualize the complete grid structure with gray spheres
- For 2D grids, the camera defaults to 2D mode (pan/zoom only). This can be changed in Preferences → Camera
- Duplicate grids before major changes to preserve configurations
GridLab - Explore the space of Hamiltonian paths