Undirected Vertex Geography Solver

This repository contains a standalone undirected vertex geography solver.

The solver:

• parses a versioned UVG1 graph format,
• reproduces the same game-state transition rules,
• solves positions with a matching-based exact criterion for undirected vertex geography.

Quick start

cmake -S . -B build-root -DCMAKE_BUILD_TYPE=Release -DUVG_WARNINGS_AS_ERRORS=ON && cmake --build build-root -j
./build-root/uvg_solver evaluate data/graphs/iau_constellations/iau_constellations_88_point.uvg --initial And --final Cas
./build-root/uvg_solver analyze data/graphs/iau_constellations/iau_constellations_88_point.uvg --random --with-final --min-dist 2 --seed 42

Build

Prerequisites:

• CMake 3.22+ (project minimum in CMakeLists.txt)
• C++23-capable compiler — CI-tested with GCC 13+ and Clang 17+ on Linux; MSVC may work but is not CI-verified

cmake -S . -B build-root -DCMAKE_BUILD_TYPE=Release -DUVG_WARNINGS_AS_ERRORS=ON
cmake --build build-root -j

Binary:

• build-root/uvg_solver

Tests

cmake -S . -B build-root -DCMAKE_BUILD_TYPE=Release -DUVG_WARNINGS_AS_ERRORS=ON
cmake --build build-root -j
ctest --test-dir build-root --output-on-failure

Test executables:

• cross_check_random_graphs — random small-graph cross-checks (matching vs minimax) for verification. Uses multiple families (degree-controlled Erdos-Renyi, tree+extra edges, cycle+chords, grid+deletions) up to n=14. Default deterministic profile: seeds 183517,271828,314159, 100 graphs per seed, 20 positions per graph (6000 checked positions). Cross-check profile can be overridden with environment variables: UVG_CROSS_CHECK_SEEDS (CSV), UVG_CROSS_CHECK_GRAPHS, UVG_CROSS_CHECK_POSITIONS, UVG_CROSS_CHECK_MAX_VERTICES.
• graph_parser_validation — deterministic unit tests for UVG1 graph parsing and error handling.
• game_state_transitions — deterministic unit tests for GameState transitions and terminal cases.
• matching_unit — deterministic unit tests for the maximum matching algorithm.
• solver_unit — deterministic unit tests for solver depth computation, node-budget abort, depth limits, and vertex-count rejection.
• random_game_initializer_unit — deterministic unit tests for random state construction, distance constraints, and reproducibility.

Additionally, CTest includes smoke tests for CLI commands (evaluate, analyze, duel, state), option validation, help output, and UVGSTATE notation handling.

Optional stricter warning profile:

cmake -S . -B build-root -DCMAKE_BUILD_TYPE=Release -DUVG_WARNINGS_AS_ERRORS=ON -DUVG_ENABLE_SIGN_CONVERSION=ON
cmake --build build-root -j

Clean rebuild (removes previous build artifacts):

rm -rf build-root && cmake -S . -B build-root -DCMAKE_BUILD_TYPE=Release -DUVG_WARNINGS_AS_ERRORS=ON
cmake --build build-root -j

Clang-tidy check (requires clang-tidy and run-clang-tidy):

cmake -S . -B build-root -DCMAKE_BUILD_TYPE=Release -DUVG_WARNINGS_AS_ERRORS=ON
run-clang-tidy -p build-root -header-filter="(include|src|tests)/" "/(src|tests)/.*\.cpp$"

Usage

For exact command syntax and options:

./build-root/uvg_solver --help

help, -h, and --help are accepted aliases. For release/build identification:

./build-root/uvg_solver --version

Documentation

• Architecture and solver model: docs/architecture.md
• CLI reference and examples: docs/cli.md
• UVGSTATE format and validation: docs/uvgstate.md
• Graph format and bundled datasets: docs/graph-format.md
• Sample data notes: docs/sample-data.md

License

This project is licensed under the Apache License 2.0. See LICENSE.