graph 相关问题

我按照 https://ricardomatins.cc/2016/06/08/interior-mutability 中提到的方法使用 Rc 和 RefCell 在 Rust 中创建图形。类型 NodeRef = Rc 我遵循 https://ricardomatins.cc/2016/06/08/interior-mutability 中提到的方法，使用 Rc 和 RefCell 在 Rust 中创建图形。 type NodeRef<i32> = Rc<RefCell<_Node<i32>>>; #[derive(Clone)] // The private representation of a node. struct _Node<i32> { inner_value: i32, adjacent: Vec<NodeRef<i32>>, } #[derive(Clone)] // The public representation of a node, with some syntactic sugar. struct Node<i32>(NodeRef<i32>); impl<i32> Node<i32> { // Creates a new node with no edges. fn new(inner: i32) -> Node<i32> { let node = _Node { inner_value: inner, adjacent: vec![] }; Node(Rc::new(RefCell::new(node))) } // Adds a directed edge from this node to other node. fn add_adjacent(&self, other: &Node<i32>) { (self.0.borrow_mut()).adjacent.push(other.0.clone()); } } #[derive(Clone)] struct Graph<i32> { nodes: Vec<Node<i32>>, } impl<i32> Graph<i32> { fn with_nodes(nodes: Vec<Node<i32>>) -> Self { Graph { nodes: nodes } } } 我认为这种方法在循环图的情况下会导致内存泄漏。我该如何解决这个问题？您不必阅读博客文章即可找到答案，只需阅读文档： Rc指针之间的循环永远不会被释放。因此，Weak 用于打破循环。例如，一棵树可以具有从父节点到子节点的强 Rc 指针，以及从子节点返回到其父节点的 Weak 指针。另请参阅：有没有一种方法可以在没有运行时开销的情况下构建具有循环链接的结构？在 Rust 中实现类图数据结构 Rust 中的递归数据结构 Rust 并不是为具有任意反向链接的编程结构（例如图形）而设计的。您可能会寻求自己进行释放，以便可以保留任意边缘。幸运的是，Rust 足够灵活，可以几乎无缝地满足您的场景。这是一种可能的解决方案。首先，定义两个宏用于将原始指针转换回借用指针： // Given a class or array pointer, transforms it to a mutable reference #[macro_export] macro_rules! modify { ($ptr:expr) => { (unsafe { &mut *$ptr }) } } // Given a class or array pointer, transforms it to a read-only reference #[macro_export] macro_rules! read { ($ptr:expr) => { (unsafe { &*$ptr }) } } 然后，修改引用，使其成为真正的指针。我在下面添加方法来检查它是否为空，但如果您愿意，也可以使用选项类型。请注意，我将您的类型参数从 i32 更改为 I，因为类型参数大写更符合习惯。 type NodeRef = *mut _Node; pub fn NullNodeRef() -> NodeRef { std::ptr::null_mut() } pub fn IsNullNodeRef(node: NodeRef) -> bool { node.is_null() } 现在您可以使用相同的布局重写节点结构： #[derive(Clone)] // The private representation of a node. struct _Node { inner_value: I, adjacent: Vec<NodeRef>, } #[derive(Clone)] // The public representation of a node, with some syntactic sugar. struct Node(NodeRef); 要创建节点，您需要在堆上分配它，这样您就可以检索到稳定的地址，并且 Rust 不会释放它。 impl Node { // Creates a new node with no edges. pub fn new(inner: I) -> Node { let node_ref = Box::into_raw(Box::new(_Node { inner_value: inner, adjacent: vec![] })); Node(node_ref) } 作为奖励，我添加了一个函数来检查一个节点是否是另一个节点的邻居，以演示宏的使用read!(): pub fn is_pointing_to(self, other: &Node) -> bool { let this_node = self.0; let other_node = other.0; read!(this_node).adjacent.contains(&other_node) } 您可以使用 add_adjacent 宏方便地重写原始函数 modify!()。请注意，不再需要克隆引用，因为引用具有复制语义。 // Adds a directed edge from this node to other node. pub fn add_adjacent(&mut self, other: &Node) { modify!(self.0).adjacent.push(other.0); } } 现在您可以定义图表，但到目前为止它只拥有地址，而不拥有对象本身。因此，您需要实现 Drop 特征，以便您可以手动释放内存： #[derive(Clone)] struct Graph { nodes: Vec<Node>, } impl Graph { fn with_nodes(nodes: Vec<Node>) -> Self { Graph { nodes: nodes } } impl Drop for Graph { fn drop(&mut self) { for node in &self.nodes { unsafe { drop(Box::from_raw(node.0)); } } } } } 免责声明：手动管理内存很容易出错，除非必要，否则我不建议这样做。我发明这些宏是因为我负责将代码生成器从 Dafny 编写到 Rust，而 Dafny 是一种安全的语言，没有所有权的概念，但可以安全地释放。因此，我生成的代码将使用所有这些宏，但以可证明安全的方式。手动使用它们的风险和收益由您自行承担。但是，通过这种方法，您可以避免任何内存泄漏。

memory-management graph memory-leaks rust

回答 2 投票 0

创建dijkstras算法并在C语言中遇到问题

在我的程序中，我的任务是获取第一个输入，节点名称，然后根据节点名称的数量，为用于显示

c algorithm graph dijkstra

回答 1 投票 0

将 .mat ECG 绘制为 50mm ECG 可视化

我正在尝试绘制此数据库 https://data.mendeley.com/datasets/7dybx7wyfn/3 中的 .mat 文件，并使用 ecg-plot 0.2.8 将它们保存为 .svg 或 .png （https： //pypi.org/project/ecg-plot/)。我是...

python graph model.matrix

回答 1 投票 0

Boykov-Kolmogorov 最大流算法中图的反向弧上的负流是什么意思？

尝试解决Boost网站上提供的示例问题：https://www.boost.org/doc/libs/1_54_0/libs/graph/example/boykov_kolmogorov-eg.cpp （代码必须运行为 &...

c++ algorithm graph boost max-flow

回答 1 投票 0

不用递归来编写迭代深化的DFS

所以目前我有一个带有以下伪代码的DFS 程序DFS（图，源）：创建堆栈S 将源推送到 S 标记来源当 S 不为空时：弹出...

graph stack graph-theory depth-first-search iterative-deepening

回答 2 投票 0

所选站点的 Graph API 权限有什么问题

即使 API 声明值也不包含请求访问所有网站内容的任何权限级别：在授予权限期间，它会要求对所有共享点站点进行读写：可以