Return 哈希表中的所有 petgraph 连接组件

Question

我正在使用 petgraph，我想提取连通分量。

我想要一个HashMap<u32, Vec<&petgraph::graph::NodeIndex>> u32 作为连接组件的标识符，Vec 作为容器，引用连接组件中的所有节点。

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

我试过这样的事情：

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

这段小得多的代码出现了同样的问题 (playground)：

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
}

"But,"你说，"I don't want to copy an entire NodeIndex! I just want to have a pointer to it! NodeIndex is a big fat hairy struct, right?"

好吧，如果那个（拥有指针）确实是您所需要的，那么 Box 几乎总是您想要的。但是先看看NodeIndex and check out the source code的定义，如果你想知道这些指数到底有多大重量：

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

A NodeIndex 只是一个 Ix，它（如果您查找 DefaultIx）只是 u32 的别名。在 64 位 PC 上，它实际上 比你试图存储的指针小 ，并且在 Rust 中，你不需要为使用它支付任何额外费用——在运行时，它确实只是一个u32.

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

Return 哈希表中的所有 petgraph 连接组件

Return all petgraph connected components in a hashtable

graph

rust

connected-components

petgraph