In rust; what types are included in a type's Namespace?

Question

I'm studying the source to the petgraph library, and I cannot find out where the type Graph::NodeId comes from.

I can see that the function astar accepts a type G (which can be a Graph). astar expects there to be a type NodeId in G's namespace.

pub fn astar<G, F, H, K, IsGoal>(
    graph: G, 
    start: G::NodeId, 
    is_goal: IsGoal, 
    edge_cost: F, 
    estimate_cost: H
) -> Option<(K, Vec<G::NodeId>)> where
    G: IntoEdges + Visitable,
    IsGoal: FnMut(G::NodeId) -> bool,
    G::NodeId: Eq + Hash,
    F: FnMut(G::EdgeRef) -> K,
    H: FnMut(G::NodeId) -> K,
    K: Measure + Copy, 

I can see that Graph is defined as

pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx> {
    nodes: Vec<Node<N, Ix>>,
    edges: Vec<Edge<E, Ix>>,
    ty: PhantomData<Ty>,
}

I don't however, see where the type NodeId comes from. The only place I see it defined in the source code is in the trait implementation EdgeRef for EdgeReference

impl<'a, Ix, E> EdgeRef for EdgeReference<'a, E, Ix>
    where Ix: IndexType,
{
    type NodeId = NodeIndex<Ix>;
    type EdgeId = EdgeIndex<Ix>;
    type Weight = E;

    fn source(&self) -> Self::NodeId { self.node[0] }
    fn target(&self) -> Self::NodeId { self.node[1] }
    fn weight(&self) -> &E { self.weight }
    fn id(&self) -> Self::EdgeId { self.index }
}

But I don't understand how that type would get into scope under Graph.

Answer 1

astar has a bound G: IntoEdges + Visitable where Visitable is defined as

pub trait Visitable: GraphBase { … }

and GraphBase is defined as

pub trait GraphBase {
    type EdgeId: Copy + PartialEq;
    type NodeId: Copy + PartialEq;
}

This is what allows astar to use G::NodeId. Essentially you have this:

struct Graph;

trait GraphBase {
    type Type;
}

trait Visitable: GraphBase {}

impl GraphBase for Graph {
    type Type = u8;
}

impl Visitable for Graph {}

fn foo<G: Visitable>(_: G, _: G::Type) {}

fn main() {
    foo(Graph, 42);
}

(Permalink to the playground)