在一个哈希表中返回所有petgraph连接的组件

Question

我正在使用petgraph，我想提取连接的组件。

我想要一个HashMap<u32, Vec<&petgraph::graph::NodeIndex>>其中CCD_ 2作为所连接组件的标识符并且CCD_。

如果这是一个糟糕的设计，请毫不犹豫地指出一个更好的设计；我是个新手。

我试过这样的东西：

extern crate fnv;
extern crate petgraph;
use petgraph::visit::Dfs;
use fnv::FnvHashMap; // a faster hash for small key
use fnv::FnvHashSet;

// structure definition
pub struct NodeAttr {
pub name_real: String,
}
impl Default for NodeAttr {
fn default() -> Self {
NodeAttr {
name_real: "default_name_for_testing".to_string(),
}
}
}

pub struct EdgesAttr {
pub eval: f64,
pub pid: f32,
pub cov: f32, // minimum coverage
}
impl Default for EdgesAttr {
fn default() -> Self {
EdgesAttr {
eval: 0.0,
pid: 100.0,
cov: 100.0,
}
}
}
pub fn cc_dfs<'a>(
myGraph: &petgraph::Graph<NodeAttr, EdgesAttr, petgraph::Undirected>,
) -> FnvHashMap<u32, Vec<&'a petgraph::graph::NodeIndex>> {
let mut already_visited = FnvHashSet::<&petgraph::graph::NodeIndex>::default();
let mut map_real_index: FnvHashMap<u32, Vec<&petgraph::graph::NodeIndex>> =
FnvHashMap::with_capacity_and_hasher(myGraph.node_count(), Default::default());
let mut cpt = 0;
for current_node_indice in myGraph.node_indices() {
let mut current_vec: Vec<&petgraph::graph::NodeIndex> = Vec::new();
if already_visited.contains(&current_node_indice) {
continue;
}
let mut dfs = Dfs::new(&myGraph, current_node_indice);
while let Some(nx) = dfs.next(&myGraph) {
// the problem is around here
// I believe the just assigned nx live only for the while
//But it should live for the upper for loop. What to do?
current_vec.push(&nx);
already_visited.insert(&nx);
}
map_real_index.insert(cpt, current_vec);
cpt = cpt + 1
}
return map_real_index;
}
fn main() {}

Cargo.toml:

enter[dependencies]
fnv="*"
petgraph="*" 

带有编译器错误：

error[E0597]: `nx` does not live long enough
--> src/main.rs:59:31
|
59 |             current_vec.push(&nx);
|                               ^^ does not live long enough
60 |             already_visited.insert(&nx);
61 |         }
|         - borrowed value only lives until here
|
note: borrowed value must be valid for the lifetime 'a as defined on the function body at 40:1...
--> src/main.rs:40:1
|
40 | / pub fn cc_dfs<'a>(
41 | |     myGraph: &petgraph::Graph<NodeAttr, EdgesAttr, petgraph::Undirected>,
42 | | ) -> FnvHashMap<u32, Vec<&'a petgraph::graph::NodeIndex>> {
43 | |     let mut already_visited = FnvHashSet::<&petgraph::graph::NodeIndex>::default();
...  |
66 | |     return map_real_index;
67 | | }
| |_^
error[E0597]: `nx` does not live long enough
--> src/main.rs:61:9
|
60 |             already_visited.insert(&nx);
|                                     -- borrow occurs here
61 |         }
|         ^ `nx` dropped here while still borrowed
...
67 | }
| - borrowed value needs to live until here

我在我的向量中克隆了节点索引，结果成功了：

current_vec.push(nx.clone()); // instead of (&nx)
already_visited.insert(nx.clone());`

我相信(也许是错误的)使用参考资料会比复制更有效。

Answer 1

这段小得多的代码显示了相同的问题(操场)：

let mut v = Vec::new(); // Vec<&'a NodeIndex> ... but what is 'a?
for n in 0..10 {
let nx: NodeIndex = NodeIndex::new(n);
v.push(&nx);
}

即，您正在循环中创建一个短暂的NodeIndex，并试图将对它的引用存储在一个寿命更长的Vec中。

在这种情况下，解决方案非常简单：只需移动NodeIndex，而不是获取引用。

v.push(nx)

在您的原始代码中，修复也没有什么不同。

// nit: "indices" is the plural of "index"; there is no singular word "indice"
for current_node_index in myGraph.node_indices() {
// actually you don't need to supply a type here, but if you did...
let mut current_vec: Vec<petgraph::graph::NodeIndex> = Vec::new();
if already_visited.contains(&current_node_index) {
continue;
}
let mut dfs = Dfs::new(&myGraph, current_node_index);
while let Some(nx) = dfs.next(&myGraph) {
current_vec.push(nx);
//               ^-----v- Look Ma, no &s!
already_visited.insert(nx);
}
map_real_index.insert(cpt, current_vec);
cpt = cpt + 1
}

"但是，"你说，"我不想复制整个NodeIndex！我只想有一个指向它的指针！NodeIndex是一个巨大的多毛结构，对吧？">

好吧，如果你真的需要(一个拥有的指针)，那么Box就是你几乎一直想要的。但是，如果您想知道这些索引的权重，请首先查看NodeIndex的定义并查看源代码：

pub struct NodeIndex<Ix=DefaultIx>(Ix);

NodeIndex只是Ix，它(如果查找DefaultIx)只是u32的别名。在64位PC上，它实际上比您试图存储的指针小，而在Rust中，您不需要为使用它支付任何额外的成本——在运行时，它实际上只是一个u32。

方便的是，NodeIndex是Copy(当Ix是Copy时)，所以您甚至不需要再加上额外的u320；你可以像我上面做的那样先做current_vec.push(nx)，然后做already_visited.insert(nx)。(但是，即使您确实编写了.clone()，也不需要为此支付运行时成本；这是不必要的。)