Skip to content

New model for the graph iterator / visit traits #469

@bluss

Description

@bluss

The graph iterator and visit traits have a very long history, they use some “interesting” (in all senses of the word) macros to generate implementations. They use IntoIterator style, and only support (shared) references.

Here's a potential new model for how it could be done.
However, this is only a step on the way towards the GAT feature - which is probably how it really should be done (rust-lang/rust#44265)

This uses code from @steffahn https://users.rust-lang.org/t/lifetime-conflicting-requirements/64070/4

I haven't really fleshed out the PoC more, but I think it could work, here's an example graph trait with this:

pub trait HasNeighbors<'a, _Outlives = &'a Self> {
    // FIXME: Name should probably be Neighbors
    type NeighborIterType;
}

// FIXME: Name should probably be Neighbors
pub type NeighborIterType<'a, This> = <This as HasNeighbors<'a>>::NeighborIterType;

// FIXME: Name should probably be Neighbors, like the visit trait this is replacing.
pub trait NeighborsIter: visit::GraphBase + for<'a> HasNeighbors<'a> {
    fn neighbors(&self, a: Self::NodeId) -> NeighborIterType<'_, Self>;
}

impl<'a, N, E, Ty, Ix> HasNeighbors<'a> for Graph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    type NeighborIterType = Neighbors<'a, E, Ix>;
}

impl<N, E, Ty, Ix> NeighborsIter for Graph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<'_, E, Ix> {
        self.neighbors(a)
    }
}

2023 Edit: if GAT is ready, it could be even better than whatever is sketched here (?!)

Metadata

Metadata

Assignees

No one assigned

    Labels

    S-needs-triageStatus: Needs to be labelled

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions