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

Question

我一直在尝试实现 Bron-Kerbosch algorithm我的硕士论文是用 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);
}

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

顺序并不重要，无论使用 HashSet 还是 BTreeSet，程序都应该可以工作。

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
}