Почему я получаю разные результаты для алгоритма Брон-Кербоша при переключении между BTreeSet и HashSet?

Question

Я пытался реализовать алгоритм Брон-Кербоша в Rust для моей магистерской работы. Пока все работало, но когда я попытался изменить значение с BTreeSet на HashSet для сравнения производительности, поведение стало совершенно случайным (по крайней мере, результаты).

Я не могу найти никакой информации о порядке узлов, оказывающих какое-либо влияние на результат, но переход к неупорядоченной коллекции нарушает результаты, так как алгоритм, похоже, пропускает некоторые ветви во время обратного отслеживания.

use std::collections::hash_map::Entry::{Occupied, Vacant};
use std::collections::{BTreeSet, HashMap};

type Nodes = BTreeSet<u32>;
type Graph = HashMap<u32, Nodes>;
type Record = (u32, u32);

fn init_nodes(records: &[Record]) -> Graph {
    let mut nodes: Graph = Graph::with_capacity(records.len());
    for record in records.iter() {
        let n: &mut Nodes = match nodes.entry(record.0) {
            Vacant(entry) => entry.insert(Nodes::new()),
            Occupied(entry) => entry.into_mut(),
        };
        n.insert(record.1);
        nodes.entry(record.1).or_insert_with(Nodes::new);
    }
    nodes.shrink_to_fit();
    nodes
}

fn bron1(graph: &Graph, r: Nodes, mut p: Nodes, mut x: Nodes, cliques: &mut Vec<Nodes>) {
    if p.is_empty() && x.is_empty() {
        cliques.push(r);
    } else if !p.is_empty() {
        let nodes = p.iter().cloned().collect::<Nodes>();
        nodes.iter().for_each(|node| {
            let neighbours: &Nodes = graph.get(node).unwrap();
            let mut to_add: Nodes = Nodes::new();
            to_add.insert(*node);
            bron1(
                graph,
                r.union(&to_add).cloned().collect(),
                p.intersection(&neighbours).cloned().collect(),
                x.intersection(&neighbours).cloned().collect(),
                cliques,
            );
            p.remove(node);
            x.insert(*node);
        });
    }
}

fn display_cliques(cliques: &[Nodes]) {
    let max = (&cliques[0]).len();
    let mut count = 0;
    for (idx, cl) in cliques.iter().enumerate() {
        if cl.len() != max {
            count = idx;
            break;
        }
    }
    println!(
        "Found {} cliques of {} nodes on a total of {} cliques",
        count,
        max,
        cliques.len()
    )
}

fn main() {
    let records: Vec<Record> = vec![
        (1, 88160),
        (1, 118_052),
        (1, 161_555),
        (1, 244_916),
        (1, 346_495),
        (1, 444_232),
        (1, 447_165),
        (1, 500_600),
        (2, 27133),
        (2, 62291),
        (2, 170_507),
        (2, 299_250),
        (2, 326_776),
        (2, 331_042),
        (2, 411_179),
        (2, 451_149),
        (2, 454_888),
        (4, 16050),
        (4, 286_286),
        (4, 310_803),
        (4, 320_519),
        (4, 408_108),
        (4, 448_284),
        (5, 173_362),
    ];

    let nodes = init_nodes(&records);
    let r: Nodes = nodes.keys().copied().collect();
    let mut cliques: Vec<Nodes> = Vec::new();
    bron1(&nodes, Nodes::new(), r, Nodes::new(), &mut cliques);
    cliques.sort_unstable_by(|a, b| a.len().cmp(&b.len()).reverse());
    display_cliques(&cliques);
}

Детская площадка

Запуск кода с использованием BTreeSet дает правильные результаты.

Found 24 cliques of 2 nodes on a total of 48 cliques

Изменение типа Nodes на HashSet дает совершенно разные результаты.

Found 5 cliques of 2 nodes on a total of 29 cliques

Answer 1

Порядок не имеет значения, и программа должна работать независимо от того, использует она HashSet s или BTreeSet s.

Функция init_nodes неверна, поскольку Bron-Kerbosch Алгоритм работает с неориентированными графами, но функция init_nodes не регистрирует ребра в обоих направлениях, что направляет граф и приводит к тому, что порядок имеет значение.

Вот правильная реализация функции:

fn init_nodes(records: &[Record]) -> Graph {
    let mut nodes: Graph = Graph::with_capacity(records.len());
    for r in records.iter() {
        let n: &mut Nodes = match nodes.entry(r.0) {
            Vacant(entry) => entry.insert(Nodes::new()),
            Occupied(entry) => entry.into_mut(),
        };
        n.insert(r.1);
        let n: &mut Nodes = match nodes.entry(r.1) {
            Vacant(entry) => entry.insert(Nodes::new()),
            Occupied(entry) => entry.into_mut(),
        };
        n.insert(r.0);
    }
    nodes.shrink_to_fit();
    nodes
}