#graph #graph-algorithms #cyclic #comparison #equivalence

no-std graph_safe_compare

可以处理循环、共享和深度非常深的图的等价谓词

4 个版本

0.2.1 2022年6月19日
0.2.0 2022年3月27日
0.1.1 2022年1月29日
0.1.0 2022年1月28日

算法 中排名 852

通用许可证

115KB
2K SLoC

graph_safe_compare

可以处理循环、共享和深度非常深的图的等价谓词。实现了论文《Efficient Nondestructive Equality Checking for Trees and Graphs》中描述的算法。增加了支持递归而不使用调用栈以支持深度很大的图,并支持多路比较以支持对图进行排序的功能。

动机

使用 Rust 时,常见的是 #[derive(PartialEq)] 为类型,以便比较值。然而,这样的派生实现无法处理循环或深度非常深的输入,并且在给它们时会导致栈溢出,并且在给具有大量共享结构的输入时执行效率低下。

此 crate 提供了适用于通用图形形状的函数,这些函数是安全和高效的,可以用作 PartialEq 实现。

示例

退化的有向无环图形状

一个链,其中每个 My::Branch 的左右边都引用相同的下一个 Rc<My> 节点。如果没有共享结构的检测,它将像完美二叉树一样遍历,有 2^(depth+1)-2 次递归,但使用此 crate 的共享结构检测,它只使用 2*depth 次递归。

use graph_safe_compare::{robust, utils::RefId, Node};
use std::rc::Rc;
use My::*;

#[derive(Eq)]
enum My {
    Leaf { val: i32 },
    Branch { left: Rc<Self>, right: Rc<Self> },
}

impl My {
    fn new_degenerate_shared_structure(depth: usize) -> Self {
        let next = Leaf { val: 1 };
        (0..depth).fold(next, |next, _| {
            let next = Rc::new(next);
            Branch { left: Rc::clone(&next), right: next }
        })
    }
}

impl PartialEq for My {
    fn eq(&self, other: &Self) -> bool { robust::equiv(self, other) }
}

impl Node for &My {
    type Cmp = bool;
    type Id = RefId<Self>;
    type Index = usize;

    fn id(&self) -> Self::Id { RefId(*self) }

    fn get_edge(&self, index: &Self::Index) -> Option<Self> {
        match (self, index) {
            (Branch { left, .. }, 0) => Some(left),
            (Branch { right, .. }, 1) => Some(right),
            _ => None,
        }
    }

    fn equiv_modulo_edges(&self, other: &Self) -> Self::Cmp {
        match (self, other) {
            (Leaf { val: v1 }, Leaf { val: v2 }) => v1 == v2,
            (Branch { .. }, Branch { .. }) => true,
            _ => false,
        }
    }
}

fn main() {
    // A depth that is fast with the `robust` variant of this crate, but that
    // would be infeasible and either take forever, due to the great degree of
    // shared structure, or cause stack overflow, due to the great depth, if
    // another variant were used.
    let depth = 1_000_000;
    let a = My::new_degenerate_shared_structure(depth);
    let b = My::new_degenerate_shared_structure(depth);
    assert!(a == b);

    // Prevent running the drop destructor, to avoid the stack overflow it would
    // cause due to the great depth.  (A real implementation would need a `Drop`
    // designed to properly avoid that.)
    std::mem::forget((a, b));
}
循环形状

一个非常简单的循环。如果没有共享结构的检测,它将无限递归并溢出栈,但使用此 crate 的共享结构检测,它不会这样做,并且它高效地完成。

涉及的类型更为复杂,以便能够构建循环。

use graph_safe_compare::{cycle_safe, utils::RefId, Node};
use std::{cell::{Ref, RefCell}, rc::Rc};
use Inner::*;

#[derive(Clone)]
struct My(Rc<RefCell<Inner>>);

enum Inner {
    Leaf { val: i32 },
    Branch { left: My, right: My },
}

impl My {
    fn leaf(val: i32) -> Self { My(Rc::new(RefCell::new(Leaf { val }))) }

    fn set_branch(&self, left: My, right: My) {
        *self.0.borrow_mut() = Branch { left, right };
    }

    fn new_cyclic_structure() -> Self {
        let cyc = My::leaf(0);
        cyc.set_branch(My::leaf(1), cyc.clone());
        cyc
    }

    fn inner(&self) -> Ref<'_, Inner> { self.0.borrow() }
}

impl PartialEq for My {
    fn eq(&self, other: &Self) -> bool {
        cycle_safe::equiv(self.clone(), other.clone())
    }
}
impl Eq for My {}

impl Node for My {
    type Cmp = bool;
    type Id = RefId<Rc<RefCell<Inner>>>;
    type Index = u32;

    fn id(&self) -> Self::Id { RefId(Rc::clone(&self.0)) }

    fn get_edge(&self, index: &Self::Index) -> Option<Self> {
        match (index, &*self.inner()) {
            (0, Branch { left, .. }) => Some(left.clone()),
            (1, Branch { right, .. }) => Some(right.clone()),
            _ => None,
        }
    }

    fn equiv_modulo_edges(&self, other: &Self) -> Self::Cmp {
        match (&*self.inner(), &*other.inner()) {
            (Leaf { val: v1 }, Leaf { val: v2 }) => v1 == v2,
            (Branch { .. }, Branch { .. }) => true,
            _ => false,
        }
    }
}

fn main() {
    let a = My::new_cyclic_structure();
    let b = My::new_cyclic_structure();
    assert!(a == b);

    // (A real implementation would need to break the cycles, to allow them to
    // be dropped.)
}
多方式比较以排序
use graph_safe_compare::{basic, utils::RefId, Node};
use std::cmp::Ordering;

#[derive(Eq)]
struct My(Vec<i32>);

impl Ord for My {
    fn cmp(&self, other: &Self) -> Ordering { basic::equiv(self, other) }
}
impl PartialOrd for My {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl PartialEq for My {
    fn eq(&self, other: &Self) -> bool { self.cmp(other).is_eq() }
}

impl Node for &My {
    type Cmp = Ordering;
    type Id = RefId<Self>;
    type Index = u8;

    fn id(&self) -> Self::Id { RefId(*self) }

    fn get_edge(&self, _: &Self::Index) -> Option<Self> { None }

    fn equiv_modulo_edges(&self, other: &Self) -> Self::Cmp {
        self.0.iter().cmp(other.0.iter())
    }
}

fn main() {
    let mut array = [My(vec![1, 2, 3]), My(vec![3]), My(vec![1, 2])];
    array.sort();
    assert!(array == [My(vec![1, 2]), My(vec![1, 2, 3]), My(vec![3])])
}

设计

  • unsafe 代码。

  • 无恐慌。

  • 非常少的依赖。

  • 组织成模块,为不同可能的图形状提供算法变体。形状有限的程序可以从使用仅支持所需内容的变体中受益,从而避免其他变体涉及的开销。例如,当只有浅循环形状时,cycle_safe 模块提供的函数就足够了;例如,当只有无环的深度形状时,deep_safe 模块就足够了;例如,当可能的深度循环形状时,可以使用 robust 模块。

  • 一个 generic 模块公开了通用的 API(其他模块基于此构建),这使得可以自定义算法的参数(类型和常量)以创建自定义变体。

  • 通用的 API 支持可失败的结果 Result,具有自定义的错误类型,可用于实现自定义限制,例如内存使用量或执行时间的限制。

no_std 支持

虽然对循环和深度图的支持需要内部动态内存分配,但这可以在没有 stdalloc crate 的情况下提供。这个 crate 的通用 API 被设计为自定义提供所需动态数据结构。当不带其 "std" 功能构建时,此 crate 是 no_std

文档

源代码有许多文档注释,这些注释被渲染为 API 文档。

在线查看:[http://docs.rs/graph_safe_compare](http://docs.rs/graph_safe_compare)

或者,您可以通过执行以下操作自行生成并本地查看:

cargo doc --open

测试

有单元测试和集成测试,可以通过执行以下操作运行:

cargo test --workspace

可以运行 ignored 测试来演示不支持某些形状的变体的局限性,并预期它们将导致堆栈溢出崩溃或花费很长时间。

有一个包测试使用 crate 作为 no_std,可以通过执行以下操作运行:

cd test_no_std
cargo build --features graph_safe_compare/wyrng

基准测试

有变体的基准测试,使用具有非常少开销的节点类型,可以通过执行以下操作运行:

cargo +nightly bench --profile bench-max-optim

依赖关系