Improve test coverage to match Julia UnitDiskMapping

[GiggleLiu]

Summary

Analysis of test coverage comparing Rust implementation with Julia's UnitDiskMapping reveals several gaps and failing tests that need attention.

Missing Tests (from Julia)

High Priority

1. Logic Gates (logicgates.jl)

   • NOT, XOR, AND, OR, NOR, NXOR gate gadgets
   • Truth table verification for each gate

2. Multiplier/Factoring (multiplier.jl)

   • Multiplier gadget construction
   • Factoring (2×2, 2×3 bits)
   • Completeness verification (all inputs reachable)
   • Soundness verification (correct arithmetic)

3. Boundary Config Extraction (extracting_results.jl)

   • mapped_entry_to_compact
   • source_entry_to_configs
   • mapped_boundary_config
   • source_boundary_config

Low Priority (Visualization)

• Drag and drop tests
• Visualization tests

Failing Tests (Need Investigation)

Triangular map_config_back

These tests verify solution extraction from the grid graph:

• test_triangular_map_config_back_path_graph
• test_triangular_map_config_back_bull
• test_triangular_map_config_back_diamond
• test_triangular_map_config_back_house
• test_triangular_map_config_back_petersen

Gadget MIS Equivalence

These test individual gadget correctness via MIS solving:

• test_triturn_mis_equivalence
• test_tricross_connected_weighted_mis_equivalence
• test_tricross_disconnected_weighted_mis_equivalence
• test_tribranch_mis_equivalence

Interface Tests

• test_triangular_interface_full - MIS overhead formula with random weights

Current Status

Category	Rust	Julia	Notes
Total tests	160	~50	Rust has more basic coverage
Alpha tensor	✅ 11/11	N/A	Gadget verification
MIS overhead	✅ 9/9	✅	Formula: overhead == mapped_MIS
map_config_back	❌ 5 failing	✅	Triangular mode broken
Logic gates	❌ Missing	✅	Not implemented
Multiplier	❌ Missing	✅	Not implemented

Reference

Julia test files: ~/.julia/dev/UnitDiskMapping/test/

• triangular.jl - Triangular lattice tests
• weighted.jl - Weighted mode tests
• logicgates.jl - Logic gate tests
• multiplier.jl - Multiplier/factoring tests
• extracting_results.jl - Boundary config tests

[GiggleLiu]

Test Coverage Update

The test file has been reorganized into a modular structure mirroring src/rules/mapping/:

tests/rules/mapping/
├── common.rs      # Shared MIS solvers and helpers
├── copyline.rs    # CopyLine functionality tests
├── gadgets.rs     # Square and triangular gadget tests
├── map_graph.rs   # Square lattice mapping tests
├── triangular.rs  # Triangular lattice mapping tests
├── weighted.rs    # Weighted mode tests
└── mod.rs

Test Results (as of commit e9a5cbd)

Category	Passed	Failed	Ignored
Total	75	7	1

Failing Tests (Pre-existing Issues)

1. Triangular gadget MIS equivalence (5 tests):

   • test_triturn_mis_equivalence
   • test_tribranch_mis_equivalence
   • test_tricross_connected_weighted_mis_equivalence
   • test_tricross_disconnected_weighted_mis_equivalence
   • test_all_triangular_weighted_gadgets_mis_equivalence

   These fail because the triangular gadgets report mis_overhead = -2 but the actual measured overhead differs. This suggests the triangular gadget implementations or their MIS overhead calculations need verification.

2. Weighted mode test (1 test):

   • test_map_weights_one - Total weight calculation doesn't match expected overhead

3. MIS overhead test (1 test):

   • test_triangular_mis_overhead_path_graph - Mapped MIS doesn't equal original + overhead

Next Steps

• Verify triangular gadget mis_overhead() values against Julia reference
• Debug weight calculation in map_weights function
• Fix or mark tests as #[ignore] if they require incomplete features

[GiggleLiu]

Progress Update (PR #13)

Fixed in this PR

Triangular Gadgets Rewrite:

• All 13 triangular gadgets now match Julia's UnitDiskMapping exactly
• Fixed connected_nodes() to use 1-indexed values (was 0-indexed)
• Fixed TRIANGULAR_UNIT_RADIUS from 1.5 to 1.1
• Fixed GridType from Square to Triangular { offset_even_cols: false }
• Alpha tensor verification now uses correct triangular unit disk edges

Test Status Update:

Category	Status	Notes
Alpha tensor	✅ 11/11	All gadgets verified
MIS overhead (triangular)	✅ All pass	bull, diamond, house, cubical, petersen
MIS overhead (square)	✅ All pass	path, triangle graphs
Weighted gadgets	✅ All pass	Weight conservation verified
map_config_back	✅ Working	Both region-based and center-based methods
Clippy	✅ Clean	All warnings addressed
CI	✅ All pass	Tests, Clippy, Coverage

Remaining from issue:

• Logic gates (NOT, XOR, AND, OR, NOR, NXOR) - not implemented
• Multiplier/Factoring gadgets - not implemented
• Boundary config extraction functions - partially implemented

These are lower priority features that can be addressed in future PRs.

[GiggleLiu]

Archived Julia Code from PR #13

This code was used to generate test trace files for comparison with the Rust implementation. Archiving here before cleanup.

tests/julia/dump_bull_mapping.jl

"""
Dump graph mapping information for comparison with Rust implementation.
Follows the testing pattern from UnitDiskMapping/test/mapping.jl.

Supports modes: UnWeighted(), Weighted(), TriangularWeighted()
"""

using Pkg
Pkg.activate(@__DIR__)
Pkg.develop(path="/Users/liujinguo/.julia/dev/UnitDiskMapping")
Pkg.instantiate()

using UnitDiskMapping
using Graphs
using GenericTensorNetworks
using UnitDiskMapping: is_independent_set

# Manual JSON serialization (no external deps)
function to_json(obj, indent=0)
    ind = "  " ^ indent
    ind1 = "  " ^ (indent + 1)

    if obj isa Dict
        isempty(obj) && return "{}"
        parts = ["$(ind1)\"$k\": $(to_json(v, indent + 1))" for (k, v) in pairs(obj)]
        return "{\n$(join(parts, ",\n"))\n$ind}"
    elseif obj isa Vector
        isempty(obj) && return "[]"
        all(x -> x isa Number, obj) && return "[" * join(obj, ", ") * "]"
        parts = [to_json(x, indent + 1) for x in obj]
        return "[\n$(ind1)" * join(parts, ",\n$(ind1)") * "\n$ind]"
    elseif obj isa String
        return "\"$(escape_string(obj))\""
    elseif obj isa Number
        return string(obj)
    elseif obj isa Bool
        return obj ? "true" : "false"
    elseif obj === nothing
        return "null"
    else
        return "\"$(escape_string(string(obj)))\""
    end
end

function dump_mapping_info(mode, g, name)
    # Get mapping result using the specified mode
    res = map_graph(mode, g)
    mode_name = string(typeof(mode))

    # Capture grid state at different stages for comparison
    # Stage 1: After embed_graph (copylines only, includes Connected cells at crossings)
    ug_copylines_only = UnitDiskMapping.embed_graph(mode, g)

    # Stage 2: After crossing gadgets (before simplifiers)
    ug_before_simplify = UnitDiskMapping.embed_graph(mode, g)
    ug_before_simplify, crossing_tape = UnitDiskMapping.apply_crossing_gadgets!(mode, ug_before_simplify)

    info = Dict{String, Any}()
    info["graph_name"] = name
    info["mode"] = mode_name
    info["num_vertices"] = nv(g)
    info["num_edges"] = ne(g)
    info["edges"] = [[src(e), dst(e)] for e in edges(g)]

    # Grid graph info
    m, n = size(res.grid_graph)
    info["grid_size"] = [m, n]
    info["padding"] = res.padding
    info["mis_overhead"] = res.mis_overhead
    info["num_grid_nodes"] = length(res.grid_graph.nodes)

    # Grid nodes with positions and weights (AFTER simplifiers - final result)
    nodes_info = [Dict(
        "index" => i,
        "row" => node.loc[1],
        "col" => node.loc[2],
        "weight" => node.weight isa Number ? node.weight : 1
    ) for (i, node) in enumerate(res.grid_graph.nodes)]
    info["grid_nodes"] = nodes_info

    # Grid nodes BEFORE simplifiers (after copylines + crossing gadgets)
    # Extract from ug_before_simplify.content which is a matrix of cells
    # Include cell state: O=Occupied, D=Doubled, C=Connected
    nodes_before_simplifiers = []
    for i in 1:size(ug_before_simplify.content, 1)
        for j in 1:size(ug_before_simplify.content, 2)
            cell = ug_before_simplify.content[i, j]
            if !isempty(cell)
                state = if cell.doubled
                    "D"
                elseif cell.connected
                    "C"
                else
                    "O"
                end
                push!(nodes_before_simplifiers, Dict("row" => i, "col" => j, "state" => state))
            end
        end
    end
    info["grid_nodes_before_simplifiers"] = nodes_before_simplifiers
    info["num_grid_nodes_before_simplifiers"] = length(nodes_before_simplifiers)

    # Grid nodes AFTER copylines only (before crossing gadgets)
    # Include cell state: O=Occupied, D=Doubled, C=Connected
    nodes_copylines_only = []
    for i in 1:size(ug_copylines_only.content, 1)
        for j in 1:size(ug_copylines_only.content, 2)
            cell = ug_copylines_only.content[i, j]
            if !isempty(cell)
                state = if cell.doubled
                    "D"
                elseif cell.connected
                    "C"
                else
                    "O"
                end
                push!(nodes_copylines_only, Dict("row" => i, "col" => j, "state" => state))
            end
        end
    end
    info["grid_nodes_copylines_only"] = nodes_copylines_only
    info["num_grid_nodes_copylines_only"] = length(nodes_copylines_only)

    # Tape entries (mapping_history)
    tape_info = [Dict(
        "index" => i,
        "type" => string(typeof(entry[1])),
        "row" => entry[2],
        "col" => entry[3]
    ) for (i, entry) in enumerate(res.mapping_history)]
    info["tape"] = tape_info
    info["num_tape_entries"] = length(tape_info)

    # Copy lines info with locations
    spacing = res.spacing
    lines_info = []
    for (i, line) in enumerate(res.lines)
        # Get copyline_locations for this line
        locs = UnitDiskMapping.copyline_locations(UnitDiskMapping.nodetype(mode), line, res.padding, spacing)
        locs_info = [Dict("row" => loc.loc[1], "col" => loc.loc[2]) for loc in locs]

        push!(lines_info, Dict(
            "index" => i,
            "vertex" => line.vertex,
            "vslot" => line.vslot,
            "hslot" => line.hslot,
            "vstart" => line.vstart,
            "vstop" => line.vstop,
            "hstop" => line.hstop,
            "locations" => locs_info
        ))
    end
    info["copy_lines"] = lines_info

    # Solve optimal MIS/WMIS using GenericTensorNetworks
    missize_original = solve(GenericTensorNetwork(IndependentSet(g)), SizeMax())[].n
    info["original_mis_size"] = missize_original

    # For weighted modes (Weighted, TriangularWeighted), solve weighted MIS
    # For unweighted mode, solve standard MIS
    if mode isa UnitDiskMapping.UnWeighted
        # Unweighted: use SimpleGraph directly
        gp = GenericTensorNetwork(IndependentSet(SimpleGraph(res.grid_graph));
                                  optimizer=TreeSA(ntrials=1, niters=10))
        missize_map = solve(gp, SizeMax())[].n
        info["mapped_mis_size"] = missize_map
        info["overhead_check"] = res.mis_overhead + missize_original == missize_map

        # Get optimal MIS configuration
        misconfig = solve(gp, SingleConfigMax())[].c
        selected_positions = [Dict(
            "node_index" => i,
            "row" => res.grid_graph.nodes[i].loc[1],
            "col" => res.grid_graph.nodes[i].loc[2]
        ) for i in 1:length(misconfig.data) if misconfig.data[i] > 0]
        info["mis_selected_positions"] = selected_positions
        info["mis_selected_count"] = length(selected_positions)

        # Map config back
        original_configs = map_config_back(res, collect(misconfig.data))
        info["original_config"] = collect(original_configs)
        info["mapped_back_size"] = count(isone, original_configs)
        info["is_valid_is"] = is_independent_set(g, original_configs)
        info["size_matches"] = count(isone, original_configs) == missize_original
    else
        # Weighted modes: use unitdisk_graph to construct edges, then solve weighted MIS
        try
            # Get unit disk graph edges from grid positions
            grid_graph = res.grid_graph
            nodes = grid_graph.nodes
            n_nodes = length(nodes)

            # Construct SimpleGraph for topology
            sg = SimpleGraph(n_nodes)
            unit = mode isa UnitDiskMapping.TriangularWeighted ? 1.1 : 1.5
            grid_type = mode isa UnitDiskMapping.TriangularWeighted ? TriangularGrid() : SquareGrid()

            # Compute physical positions and add edges
            physical_locs = [UnitDiskMapping.physical_position(node, grid_type) for node in nodes]
            for i in 1:n_nodes
                for j in i+1:n_nodes
                    dist_sq = sum(abs2, physical_locs[i] .- physical_locs[j])
                    if dist_sq < unit^2
                        add_edge!(sg, i, j)
                    end
                end
            end

            # Get weights
            weights = [node.weight for node in nodes]

            # Solve weighted MIS
            gp = GenericTensorNetwork(IndependentSet(sg, weights);
                                      optimizer=TreeSA(ntrials=1, niters=10))
            wmis_result = solve(gp, SizeMax())[]
            missize_map = wmis_result.n

            info["mapped_mis_size"] = missize_map
            info["num_grid_edges"] = ne(sg)
            info["overhead_check"] = res.mis_overhead + missize_original == missize_map

            # Get optimal configuration
            misconfig = solve(gp, SingleConfigMax())[].c
            selected_positions = [Dict(
                "node_index" => i,
                "row" => nodes[i].loc[1],
                "col" => nodes[i].loc[2],
                "weight" => weights[i]
            ) for i in 1:length(misconfig.data) if misconfig.data[i] > 0]
            info["mis_selected_positions"] = selected_positions
            info["mis_selected_count"] = length(selected_positions)
            info["mis_selected_weight"] = sum(weights[i] for i in 1:length(misconfig.data) if misconfig.data[i] > 0; init=0)

            # Map config back
            original_configs = map_config_back(res, collect(misconfig.data))
            info["original_config"] = collect(original_configs)
            info["mapped_back_size"] = count(isone, original_configs)
            info["is_valid_is"] = is_independent_set(g, original_configs)
            info["size_matches"] = count(isone, original_configs) == missize_original
        catch e
            println("  Note: Error solving weighted MIS: $e")
            info["mapped_mis_size"] = nothing
            info["overhead_check"] = nothing
            info["mis_selected_positions"] = []
            info["mis_selected_count"] = 0
            info["original_config"] = []
            info["mapped_back_size"] = 0
            info["is_valid_is"] = nothing
            info["size_matches"] = nothing
        end
    end

    return info
end

# Test multiple graphs with different modes
function main()
    modes = [
        ("unweighted", UnitDiskMapping.UnWeighted()),
        ("weighted", UnitDiskMapping.Weighted()),
        ("triangular", UnitDiskMapping.TriangularWeighted()),
    ]

    graphs = [
        ("diamond", smallgraph(:diamond)),
        ("bull", smallgraph(:bull)),
        ("house", smallgraph(:house)),
        ("petersen", smallgraph(:petersen)),
    ]

    for (mode_name, mode) in modes
        println("\n" * "="^60)
        println("MODE: $mode_name")
        println("="^60)

        for (graph_name, g) in graphs
            println("\n--- $graph_name graph ($mode_name) ---")

            try
                info = dump_mapping_info(mode, g, graph_name)

                # Save to JSON
                output_path = joinpath(@__DIR__, "$(graph_name)_$(mode_name)_trace.json")
                open(output_path, "w") do f
                    write(f, to_json(info))
                end
                println("Saved to: $output_path")

                # Print summary
                println("  Vertices: $(info["num_vertices"])")
                println("  Grid size: $(info["grid_size"][1]) x $(info["grid_size"][2])")
                println("  Grid nodes: $(info["num_grid_nodes"])")
                println("  Tape entries: $(info["num_tape_entries"])")
                println("  Original MIS: $(info["original_mis_size"])")
                println("  Mapped MIS: $(info["mapped_mis_size"])")
                println("  MIS overhead: $(info["mis_overhead"])")
                println("  Overhead check: $(info["overhead_check"])")
                println("  Original config: $(info["original_config"])")
                println("  Is valid IS: $(info["is_valid_is"])")
                println("  Size matches: $(info["size_matches"])")
            catch e
                println("  ERROR: $e")
            end
        end
    end
end

main()

tests/julia/Project.toml

[deps]
GenericTensorNetworks = "3521c873-ad32-4bb4-b63d-f4f178f42b49"
Graphs = "86223c79-3864-5bf0-83f7-82e725a168b6"
UnitDiskMapping = "1b61a8d9-79ed-4491-8266-ef37f39e1727"

examples/debug_map_config_back.jl

using Pkg
Pkg.activate("/Users/liujinguo/.julia/dev/UnitDiskMapping")
using UnitDiskMapping
using Graphs

g = smallgraph(:diamond)
result = map_graph(g)

# Use the same MIS positions as Rust
mis_positions = Set([
    (4, 6), (4, 8), (4, 10), (6, 7), (6, 11), (7, 15), (8, 9), (8, 11), 
    (8, 13), (9, 15), (10, 11), (11, 15), (12, 13)
])

# Build config matrix
m, n = size(result.grid_graph)
config = zeros(Int, m, n)
for node in result.grid_graph.nodes
    if (node.loc[1], node.loc[2]) in mis_positions
        config[node.loc...] = 1
    end
end

println("=== JULIA DEBUG ===")
println("Config total before: $(sum(config))")
println("Grid size: $m x $n")

# Map config back
original = map_config_back(result, config)
println("\nMAP CONFIG BACK RESULT: $original")
println("Sum: $(sum(original))")

[GiggleLiu]

Closed by #13