Retourne tous les composants connectés dans une table de hachage

Question

J'utilise petgraph et je voudrais extraire les composants connectés.

Je veux avoir un HashMap<u32, Vec<&petgraph::graph::NodeIndex>> avec un u32 que l'identificateur de la composante connexe et un Vec comme un récipient avec des références à tous les noeuds du composant connecté.

Si c'est un mauvais design, n'hésitez pas à en signaler un meilleur; Je suis un débutant rouillé.

J'ai essayé quelque chose comme ceci:

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="*" 

Avec l'erreur du compilateur:

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 

Je cloné l'index de noeud dans mon vecteur et que travaillé:

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

Je crois (peut-être à tort) que travailler avec des références sera plus efficace que la copie.

Answer 1

Ce bien plus petit morceau de code présente le même problème (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); 
} 

-à-dire, vous créez une courte durée NodeIndex dans une boucle et d'essayer de stocker une référence dans une plus longue -livré Vec.

Dans ce cas, la solution est très simple: il suffit de déplacer le NodeIndex au lieu de prendre une référence.

v.push(nx) 

Dans votre code d'origine le correctif est pas différent.

// 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 
} 

« Mais, » vous dites: « Je ne veux pas copier un NodeIndex entier! Je veux juste avoir un pointeur vers elle! NodeIndex est un gros poilu struct, non? »

Eh bien, si cela (un pointeur propriétaire) est vraiment ce dont vous avez besoin, Box est ce que vous voulez presque toujours. Mais d'abord regarder la définition de NodeIndex et de vérifier la source code, si vous voulez savoir comment des poids lourds de ces indices sont vraiment:

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

A NodeIndex est juste un Ix, qui est (si vous regardez DefaultIx) juste un alias pour u32. Sur un PC 64 bits, c'est plus petit que le pointeur que vous essayiez de stocker, et dans Rust, vous ne payez aucun coût supplémentaire pour l'utiliser - au moment de l'exécution, il est vraiment un u32.

Idéalement, NodeIndex is Copy (quand Ix est Copy), de sorte que vous ne même pas besoin de jeter ce .clone() supplémentaire dans; vous pouvez simplement faire current_vec.push(nx) suivi par already_visited.insert(nx) comme je l'ai fait ci-dessus. (Mais même si vous écrivez .clone(), vous ne payez aucun coût d'exécution pour le faire, c'est inutile.)