0
\$\begingroup\$

I have made an algorithm that simplifies the "temperature" aspect of simulated annealing in an attempt (for fun) to solve Conway's 99 Conjecture. A brief explanation of Conway's 99 conjecture and of simulated annealing can be found in the top comment of my src/main.rs. Any guidance on how to optimize this code would be greatly appreciated.

(From my previous question on Brocard's conjecture, I don't believe the advice applies to here except for maybe the bitfield advice. I was, however, unable to see a way to make the bitfield work for the data structures I used.)

src/main.rs

/// A Simulated Annealing variant for solving Conway's 99 Problem.
/// Conway's 99 Problem: Is there a graph with 99 vertices such that each 
/// neighboring pair of vertices is contained in a unique triangle and each 
/// non-neighboring pair is contained in a unique square? 
/// For more information, see: 
/// https://en.wikipedia.org/wiki/Conway's_99-graph_problem
/// Simulated Annealing Variant outline:
/// 1. Start with a random graph.
/// 2. Randomly add/remove edges to improve the "fitness".
/// 3. If the new graph does not improve the fitness (+ a small slowly
///    increasing penalty factor) reject the candidate, otherwise accept the
///    candidate.
/// 4. Repeat until a candidate with "perfect" fitness is found.
/// The fitness of the graph is explained in the score function.
/// The "temperature" in the standard simulated annealing is simplified in this
/// variant. To see more about simulated annealing see:
/// https://en.wikipedia.org/wiki/Simulated_annealing

use std::collections::hash_set::Intersection;
use array_init::array_init;
use rayon::prelude::*;
// OsRng seemed to be the fastest rng generator on my computer.
use rand_core::{RngCore, OsRng};
use rustc_data_structures::fx::{FxHashSet, FxHasher};
use std::hash::BuildHasherDefault;

#[global_allocator]
static GLOBAL: mimalloc::MiMalloc = mimalloc::MiMalloc;

/// Datastructure used to represent the graph.
struct Graph<const N: usize> {
    adj: [FxHashSet<usize>; N]
}


impl<const N: usize> Graph<N> {

    /// Initializes a graph with no edges and vertices.
    fn new() -> Self {
        let mut g: [FxHashSet<usize>; N] = 
            array_init(|_| FxHashSet::<usize>::default());
        for entry in g.iter_mut() {
            *entry = FxHashSet::<usize>::default();
        }
        Self {
            adj: g
        }
    }
    
    /// Adds the edge {i, j}.
    #[inline(always)]
    fn add_edge(&mut self, i: usize, j: usize) {
        let to_add = &mut self.adj;
        to_add[i].insert(j);
        to_add[j].insert(i);
    }
    
    /// Removes the edge {i, j}.
    #[inline(always)]
    fn remove_edge(&mut self, i: usize, j: usize) {
        let to_del = &mut self.adj;
        to_del[i].remove(&j);
        to_del[j].remove(&i);
    }
    
    /// Checks if {i, j} is an edge in the graph.
    #[inline(always)]
    fn contains_edge(&self, i: usize, j: usize) -> bool {
        let to_check = &self.adj;
        to_check[i].contains(&j)
    }
    
    /// Retrieves the common neighbors that two vertices have.
    #[inline(always)]
    fn common_neighbors(&self, i: usize, j: usize) 
        -> Intersection<usize, BuildHasherDefault<FxHasher>> {
        let adj = &self.adj;
        adj[i].intersection(&adj[j])
    }
}

/// Computes the score/fitness of the graph.
/// The ideal fitness is a value of 0, and the way it is scored is as follows:
/// If {i,j} is an edge, then i and j are neighbors, so they should be contained
/// in a unique triangle. Thus, they should have 1 neighbor in common.
/// Thus, 
/// If {i,j} is not an edge, then i and j are not neighbors, so they should be
/// contained in a unique square. Thus, they should have 2 neighbors in common.
///
/// Thus, the penalty is either (neighbors in common - 1)^2 or 
/// (neighbors in common - 2)^2 to see how far away from the correct number of
/// neighbors in common the two vertices really are.
#[inline(always)]
fn score<const N: usize>(g: &Graph<N>) -> usize {
    // Check all pairs of vertices in parallel.
    (0..N).into_par_iter()
        .map(|i| {
            (i+1..N).into_par_iter()
                .map(|j| {
                    let count = g.common_neighbors(i, j).count();
                    // Should have one neighbor in common.
                    if g.contains_edge(i, j) {
                        ((count as i32 - 1) * (count as i32 - 1)) as usize
                    // Should have two neighbors in common.
                    } else {
                        ((count as i32 - 2) * (count as i32 - 2)) as usize
                    }
                }).sum::<usize>()
        }).sum()
}

/// Randomly add/remove edge.
#[inline(always)]
fn improve_pair<const N: usize>(g: &mut Graph<N>) -> ((usize, usize), bool) {
    let choice0 = (OsRng.next_u32() % (N as u32)) as usize;
    let choice1 = (OsRng.next_u32() % (N as u32)) as usize;
    if OsRng.next_u32() % 2 == 1 {
        g.add_edge(choice0,
                   choice1);
        ((choice0, choice1), true)
    } else {
        g.remove_edge(choice0,
                      choice1);
        ((choice0, choice1), false)
    }
}

/// Create an G(n, p) graph, that is a graph that has n vertices and edges are
/// added to the graph with probability p.
fn gnp<const N: usize>(p: f32) -> Graph<N> {
    // Although there may be room for parallelization, this function is only
    // called once and takes a negligible time in the long run.
    let mut g = Graph::<N>::new();
    for i in 0..N {
        for j in i+1..N {
            if rand::random::<f32>() < p {
                g.add_edge(i, j);
            }
        }
    }
    g
}

/// Called when the edge added/removed from improve_pair was bad, revert it by
/// removing/adding the edge.
#[inline(always)]
fn revert<const N:usize>(g: &mut Graph<N>, 
                         pair: (usize, usize),
                         add_or_del: bool) {
    // False indicates add, true indicates delete the edge.
    let (fst, snd) = pair;
    if add_or_del {
        g.remove_edge(fst, snd);
    } else {
        g.add_edge(fst, snd);
    }
}

fn main() {
    // Number of vertices in the graph.
    const N: usize = 99;
    let mut g = gnp::<N>(14.0/99.0);
    // Higher fitness is worse, make a trivial upperbound that is essentially
    // infinity.
    let mut best_fitness: usize = 10000000;
    let mut prev_fitness: usize = 0;
    let mut fitness = 1;
    let mut penalty_factor = 0.5;
    const COOLING_FACTOR: f32 = 1.5;
    const HEATING_FACTOR: f32 = 0.005;
    const PENALTY_UPPER: f32 = 3.0;
    // While the perfect graph has not been found.
    while fitness > 0 {
        fitness = score(&g);
        // Randomly add/remove edges in hopes of improving the graph.
        let (choice, add_or_del) = improve_pair(&mut g);
        let new_score = score(&g);
        // Keep track of the best fitness found so far.
        if best_fitness > fitness {
            best_fitness = fitness;
            println!("Fit {fitness:?} Penalty {penalty_factor:?}");
            // A great solution has been found! Reset the penalty factor.
            penalty_factor = 0.0;
        }
        // Add a slowly increasing penalty factor that "heats up" when no
        // improvement has been found and "cools down" when a better solution
        // has been found.
        // Make sure penalty never goes negative, and keep it small (i.e. <= 3)
        if prev_fitness == fitness  {
            penalty_factor = f32::min(penalty_factor 
                                      + HEATING_FACTOR, PENALTY_UPPER);
        } else {
            penalty_factor = f32::max(penalty_factor 
                                      - COOLING_FACTOR, 0.0);
        }
        // Check if the improvement was actually bad, and if so, revert the 
        // graph
        prev_fitness = fitness;
        if new_score > fitness + (penalty_factor as usize) {
            revert(&mut g, choice, add_or_del);
        }
    }
    println!("serialized = {:?}", g.adj);
}

Cargo.toml

[package]
name = "ga99"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[build]
rustflags = ["-C", "target-cpu=native"]

[profile.release]
codegen-units = 1
lto = false
#debug = true

[dependencies]
rustc-hash = "1.1.0"
rayon = "1.10.0"
array-init = "2.1.0"
rand = "0.8.5"
rustc_data_structures = "0.1.2"
rand_core = "0.6.4"
mimalloc = "0.1.41"
\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.