在Rust中是否可以使用Rc自动化约束传播

x1c 0d1x的数据
考虑上图表示一个常见的约束满足问题：

六边形是一个六边形网格上的单元格，它向六个方向中的任何一个方向延伸。为了简单起见，我只包括了其中的三个，A，B和C。
每个六边形包含一组N值，通常称为六边形的“域”。在本例中，domain = {red, blue}和|domain| = N = 2。
一个约束被定义为从一个六边形的特定域值到另一个六边形的域值的一条边，所以这里的一个例子是A_blue -> B_red。
六边形的内部不会出现边，所以A_red -> A_blue是不可能的。
循环可以直接或间接（通过另一个六边形）出现。
*从技术上讲，边缘可以出现在整个网格中（在非邻居之间），但该细节与此问题无关。

现在，考虑一个从六边形中删除域值的操作。这样做会影响其他六边形的域，并导致域值从其他六边形中删除。例如，从A中删除blue将导致A_blue -> C_red -> B_blue -> A_red全部删除。然而，它将不会导致C_blue被删除，因为C_blue有2的边指向它（另一个来自B_red）。
问题是，如何传播这种“涟漪”变化。也就是说，当一个域值被删除时，如何将变化传播到所有其他六边形。有很多算法可以优化这种操作的效率，但我更感兴趣的是如何在Rust中自动传播这种变化（如果可能的话）。请允许我解释一下。
通常情况下，你会为每个六边形的每个域值保留一个计数器，当一个域值被删除时，相邻（受影响）的六边形会递减这个计数器。如果这个计数器达到0，那么你就知道是时候进一步传播变化了，如果你愿意的话，这是一个花哨的BFS/DFS。
但是我很好奇使用std::rc::Rc是否允许我自动递减这个计数器，因为std::rc::Rc无论如何都是一个计数器。
到目前为止，我已经考虑过将std::rc::Rc和std::rc::Weak结合起来，在六边形中存储其他std::rc::Rc域值的Weak引用。然后我以某种方式删除这个Weak引用的内容，这样存储在里面的Rc就被删除了，这种变化就会传播出去，但我不认为我正朝着正确的方向前进。我可能需要内部可变性。或者这根本不可能。
对Rust来说很新，有人有什么想法吗？

简而言之，没有。
考虑一个简单的例子，两个域值由一条边连接：

A -> B

字符串
A包含一个指向B的Weak指针，它表示它们之间的边。我们希望删除A会导致删除B。然而，当我们将A的Weak指针升级为Rc时，现在有 * 两个 * 对B的强引用。丢弃新获取的Rc只会使计数器减回1。
你描述的级联效果只有在Rc递归嵌套时才有效，就像在链表中一样。

struct Node {
    next: Rc<Node>,
}

型
这是因为你得到了一个调用堆栈，如：

- Node::drop()          // Head of list dropped, which contained...
  - Rc::<Node>::drop()   // the only Rc pointing to...
   - Node::drop()        // the second element, which contained...
    - Rc::<Node>::drop() // the only Rc pointing to...
     - Node::drop()      // the third element, which...
      - etc.

型
对于任意图结构，节点通常位于平面存储中，如Vec<Rc<Node>>。在这种情况下，Node的drop实现需要“向上”所有权层次结构以删除Vec的另一个元素。如果没有不安全的代码，这是不可能的，并且在Rust中是一个反模式。
请注意，其他一些语言（例如Java，C#）能够实现你想要的，因为它们有垃圾收集，循环检测，最重要的是 * 没有所有权的概念 *。在这些语言中，如果你有一个指向对象的指针，你可以修改它，就像你拥有它一样，细节（比如它存储在哪里，什么时候被销毁）在幕后处理。
在Rust中，图通常使用索引或ID而不是指针来实现。一个 * 非常 * 简单的有向图可能看起来像：

struct Node {
    num_incoming: usize,
    outgoing: Vec<usize>,
}

struct Graph {
    // Increment every time a node is added.
    next_id: usize,
    nodes: HashMap<usize, Node>,
}

型
删除节点需要DFS/BFS，在本例中为BFS：

impl Graph {
    fn remove(&mut self, id: usize) {
        let removed = self.nodes.remove(&id).unwrap();
        
        // For simplicity, assume no incoming edges.
        assert_eq!(removed.num_incoming, 0);

        let mut queue = VecDeque::from_iter(removed.outgoing);

        while let Some(other) = queue.pop_front() {
            let Entry::Occupied(entry) = self.nodes.entry(other) else {
                panic!("missing node with id {id}");
            };

            // Decrement the refcount.
            entry.get_mut().num_incoming -= 1;

            // If the refcount hits zero, add all adjacent nodes to the queue
            // and remove the node.
            if entry.get().num_incoming == 0 {
                let node = entry.remove();
                queue.extend(node.outgoing);
            }
        }
    }
}

型
基于ID的图的更好的例子可以在petgraph crate中找到，它被广泛使用。

在Rust中是否可以使用Rc自动化约束传播

1条答案

相关问题

热门标签

最新问答