为什么在 BTreeSet 和 HashSet 之间切换时，Bron-Kerbosch 算法会得到不同的结果？

Question

我一直在尝试用 Rust 实现 Bron-Kerbosch algorithm 作为我的硕士论文。到目前为止一切正常，但是当我出于性能比较目的尝试从 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);
}

Playground

运行使用 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

顺序无关紧要，无论使用 HashSets 还是 BTreeSets，程序都应该可以运行。

init_nodes函数不正确，因为Bron-Kerbosch algorithm作用于无向图，然而，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
}

为什么在 BTreeSet 和 HashSet 之间切换时，Bron-Kerbosch 算法会得到不同的结果？

Why do I obtain different results for the Bron-Kerbosch algorithm when switching between a BTreeSet and a HashSet?

clique

hashset

clique-problem

graph-algorithm

rust