SCC v1.3 — Double Edge Weight Support

What's New

Double-Precision Edge Weights

SCC now supports floating-point (double) edge weights in addition to the existing integer weights. The weight type is detected automatically from the input file — no flags or configuration needed.

• If any edge weight contains a . or scientific notation (e/E), the double-precision code path is used
• Otherwise, the integer code path is used with identical behavior to previous versions

Auto-Detecting Launchers

Each executable (scc, scc_evolutionary, scc_evaluator, scc_graphchecker) now auto-detects the input weight type and dispatches to the appropriate optimized binary (scc_int/scc_double, etc.). The integer path is compiled separately with zero overhead — no runtime branching, no virtual dispatch.

Bug Fixes

• Fixed std::numeric_limits<int>::max() used for EdgeWeight variables in MPI reduce calls and refinement initialization
• Fixed unqualified abs() call that would silently truncate non-int types
• Fixed std::numeric_limits<EdgeWeight>::min() (wrong for floating-point; replaced with lowest())

Build Changes

• C++ standard bumped from C++11 to C++17
• CMake now builds 12 targets: 4 launchers + 4 int binaries + 4 double binaries

Compatibility

• The integer code path produces bit-exact identical results to v1.2 (verified on 20 instances × 5 seeds)
• Existing graph files work without modification

SCC v1.2

SCC v1.2 -- Scalable Correlation Clustering

Performance: 1.24x faster with identical solution quality.

Systematic performance tuning of the multilevel solver using Algorithm Engineering methodology. 30+ experiments evaluated; 18 optimizations kept. All changes are internal — no API, CLI, or output format changes. Done automatically using
https://github.com/CHSZLab/AgenticAlgorithmEngineering skill and claude.

Highlights:

• 1.24x speedup on geometric mean across 20 benchmark instances (signed social networks and image segmentation graphs)
• Zero quality change: bit-identical solutions for scc; better solutions for scc_evolutionary (more iterations within the same time budget)
• Best-of-50 improvements with scc_evolutionary (100s budget): cityscape7 -268, cityscape52 -96, cityscape34 -50, wikisigned-k2 -20

What changed internally:

• Dense vectors replacing hash maps in hot paths (label remapping, priority queue indexing)
• Counting-sort graph contraction eliminating ~24MB intermediate allocations per level
• Block-ID caching and sweep specialization in label propagation for degree ≤ 32 nodes
• Pointer hoisting with __restrict__ in LP and FM refinement inner loops
• Stack allocation of framework objects; persistent buffers across coarsening levels
• tcmalloc_minimal linking on Linux for reduced allocator overhead

Install: brew install KaHIP/kahip/scc

SCC v1.1

SCC v1.1 -- Scalable Correlation Clustering

Changes:

• Renamed binaries with scc_ prefix to avoid name conflicts (scc, scc_evolutionary, scc_evaluator, scc_graphchecker)
• Simplified CLI: --seed, --time_limit, --output_filename
• --time_limit is now required for scc_evolutionary
• Added NONATIVEOPTIMIZATIONS cmake option for portable builds
• Improved README with badges, logo, full documentation
• Updated citation to ALENEX 2025
• Removed build artifacts from repo

Install: brew install KaHIP/kahip/scc