HyperEdge trait

[ratmice]

I'm wondering if you would consider accepting an addition to add a HyperEdge trait, which would allow the library to encode Hypergraphs.

Presumably it could be an edge with a I: Iterator<Item = &K> in place of the left/right/pair, With an invariant that the iterator is non-empty. You would have to convert a HyperEdge into multiple Edge's to actually store them in the existing AdjacencyList, (I guess what i'm trying to say is I'm not sure at the moment the best way to formulate its incidence structure at the moment).

If that sounds okay, I would gladly take a stab at implementing it, I imagine something like:

pub trait HyperEdge<'a, K: 'a, W, C, I>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Add + Sub + Eq + Ord + Copy,
           I: Iterator<Item=&'a K>,
{
    fn get_weight(&self) -> W;
    fn set_weight(&mut self, weight: W);
    fn iter(&self) -> I;
    fn key(&self) -> C;
 }

[KayJay7]

First of all, I like that. But I think it leads to add a lot more things than just that trait, that being said, I think we should do it. But it's not something that we can build on what we currently have (or at least we shouldn't); we should, instead build an higher level of abstraction, on the line of what I already did with Graph and DirectedGraph, but instead this new level should define HyperGraph and HyperEdge (I don't think we need a new abstraction for Vertex). This means we shouldn't implement a way to store hyper edges in the existing adjacency list, but instead make a new implementation for hyper graphs.

Now, I'll be honest with you, this was meant to be a small subproject for an implementation of Dijkstra's, but as you can see it's not finished and it has already become bigger than what I initially expected. And I do actually want to expand it, BUT I'm also a student and I have exams to take. Of course it's not like I won't accept collaboration, if you feel like doing it yourself I'm willing to accept your code; otherwise you will have to wait until I can make it instead, I will do it if you don't, I just need time.

[ratmice]

Indeed, I agree with all those points, Lacking any existing incidence structure there isn't much point in taking it as it. I'll keep working at it and push something once I've got it more fleshed out to look at.

[ratmice]

Well, I'm not sure if it's my trait-fu or rust's trait-fu isn't strong enough, but I haven't managed to get a working definition of HyperGraph, the Iterator Trait being a trait/doing trait object things I'm not sure how to get around that in a way that Graph and friends never encounter.

For adjacency though, I believe now that the right thing for HyperGraph is actually going to be having a function incidence_graph which returns a Graph,

This incidence_graph then has a Vertex for each HyperEdge, as well as a Vertex for each Vertex in the HyperGraph, and Edge's between those. So essentially it's just a structure from which we derive a bipartite graph. Anyhow I'll keep at it, but it seems difficult to maintain the same style/level of generality as was done with Graph and friends, for HyperGraph

[KayJay7]

What you are trying to do is not easy at all, I would suggest a different approach.

First of all, iterators are cool, but maybe it's easier to implement your structure with a vector first, also remember that vectors can be easily turned into iterator.

Now it depends on what is more important to you, what you need first, the traits definition thing or an actual working implementation of HyperGraph.

If you want to start with the traits, try first to think of what primitives from Edge can still be used on an HyperEdge and move them from the first trait to the latter (Edge will implement HyperEdge), then add to the trait those primitives that weren't present in Edge but keep in mind while defining them that those functions must be implementable on a normal edge. Then do the same with DirectedGraph and HyperGraph but remember that the primitives in HyperGraph work with HyperEdges while those in DirectedGraph work with Edges which implement HyperEdge.

During the process, don't forget that the hierarchy we want is Graph: DirectedGraph: HyperGraph and Edge: HyperEdge

If, instead, you really need a working HyperGraph first, I would suggest not to have incidence_graph() function returning an adjacency list, but, instead, to build a wrapper around that graph, the traits will come later. Please, if you choose this path, I said the traits will come later, but if you keep the hierarchy we want in mind the traits will come much easier

Now, I know that you have some good implementation ideas in mind, and you want to start building your hyper graph without thinking at all that trait-fu thingies before you forget those ideas (trust me, I know how it is); but unless you really, really need that working implementation immediately, I think that starting from the traits will pay off more in the long run.