metamolecular / gamma Goto Github PK

I'm puzzled, because gamma 0.5 defined the Graph trait as generic over node and edge type. StableGraph had similar generic parameters. But now in 0.8, those are all gone, and nodes seem to be hardcoded as usize, even in the Graph trait as well as in DefaultGraph.

I'm wondering what drove this change and what the recommended practice is to use gamma when the nodes are not usize?

Thanks!

Is there an intention to add {iso|mono}-morphism graph matching to this library? I think the beginnings of graph-matching already exist here, but something for subgraph matching (i.e. Ullmann's or VF2) would be a hugely impactful addition.

References:

• NetworkX implementation
• NetworkX documentation
• VF2 paper, Cordella et al 2004

It would be nice if you could explain any advantages you see of your crate over the long-standing petgraph crate. (Or, is it just your own attempt for the sake of learning?)

How do you do this when you do not hard code literals. For my crate blossom I generate random graphs like this:

    fn random_graph<'a>(size: usize, rng: &mut dyn RngCore) -> HashGraph<'a, usize, ()> {
        let nodes: Vec<_> = (0..size).collect();
        let mut edges = vec![];
        
        // Generate some random edges
        for i in 0..size {
            let mut j = i + 1;
            while j < size {
                let interval = size + 1 - j;
                let p = (rng.next_u64() as usize) % interval + j;
                if p < size {
                    edges.push((nodes.index(i), nodes.index(p), ()));
                }
                j = p + 1;
            }
        }

        // error[E0505]: cannot move out of `nodes` because it is borrowed
        HashGraph::build(nodes, edges).unwrap()
    }

which gives the indicated error message. If you do not intend to return the graph, you can change the last line to

        let graph = HashGraph::build(nodes.clone(), edges).unwrap();

However when you want to return graph you get

error[E0515]: cannot return value referencing local variable `nodes`

Using new(), add_node() and add_edge() I run into similar problems. An example of how to do this would be very welcome.

I am implementing a BTreeMap/Set-backed graph. I noticed that the nodes() method returns a slice of usize (&[usize]). This operation doesn't work very nicely for any graph that's not internally stored as a vector -- I imagine I would have to manually assemble a slice by iterating through the entire graph. I wonder if nodes() should instead return an iterator of usize to allow for flexibility in implementations.

Existing code that uses nodes() as a slice can probably be trivially migrated by calling .collect() on the iterator.

Edit: Okay, so it looks like I rediscovered the reason why nodes() & edges() might not be an iterator -- no painless way to return a generic Iterator from trait methods because Generic Associated Types isn't implemented yet. It still isn't very nice to return a slice from a usability perspective so I suppose I will poke around a bit and see if I can get some form of iterator working.