// codesnip-guard: ClosureGraph
#[cfg_attr(any(),rustfmt::skip)]pub use self::closure::{ClosureGraph,UsizeGraph};#[cfg_attr(any(),rustfmt::skip)]mod closure{use super::{DirectedGraph,Graph,Neighbor,VertexMap};use std::{collections::HashMap,hash::Hash,iter::Map,marker::PhantomData,ops::Range};pub struct UsizeGraph<Fa>{vsize:usize,adj:Fa}impl<Fa>UsizeGraph<Fa>{pub fn new(vsize:usize,adj:Fa)->Self{Self{vsize,adj}}}impl<Fa,I,T>Graph for UsizeGraph<Fa>where I:Iterator<Item=(usize,T)>,Fa:Fn(usize)->I{type Vertex=usize;type Label=T;type Vertices<'g>=Range<usize>where Fa:'g;type Neighbors<'g>=Map<I,fn((usize,T))->Neighbor<usize,T>>where Fa:'g;#[inline]fn vsize(&self)->usize{self.vsize}#[inline]fn vertices(&self)->Self::Vertices<'_>{0..self.vsize}#[inline]fn neighbors(&self,vertex:Self::Vertex)->Self::Neighbors<'_>{(self.adj)(vertex).map(Into::into)}}impl<Fa>DirectedGraph for UsizeGraph<Fa>where UsizeGraph<Fa>:Graph{}impl<Fa,T>VertexMap<T>for UsizeGraph<Fa>where Self:Graph<Vertex=usize>{type Vmap=Vec<T>;#[inline]fn construct_vmap<F>(&self,f:F)->Self::Vmap where F:FnMut()->T{let mut v=Vec::with_capacity(self.vsize);v.resize_with(self.vsize,f);v}#[inline]fn vmap_get<'a>(&self,map:&'a Self::Vmap,vid:Self::Vertex)->&'a T{&map[vid]}#[inline]fn vmap_get_mut<'a>(&self,map:&'a mut Self::Vmap,vid:Self::Vertex)->&'a mut T{&mut map[vid]}}pub struct ClosureGraph<V,Fv,Fa>{vs:Fv,adj:Fa,_marker:PhantomData<fn()->V>}impl<V,Fv,Fa>ClosureGraph<V,Fv,Fa>{pub fn new(vs:Fv,adj:Fa)->Self{Self{vs,adj,_marker:PhantomData}}}impl<V,Fv,Fa,Iv,Ia,T>Graph for ClosureGraph<V,Fv,Fa>where V:Eq+Copy,Iv:Iterator<Item=V>,Fv:Fn()->Iv,Ia:Iterator<Item=(V,T)>,Fa:Fn(V)->Ia{type Vertex=V;type Label=T;type Vertices<'g>=Iv where V:'g,Fv:'g,Fa:'g;type Neighbors<'g>=Map<Ia,fn((V,T))->Neighbor<V,T>>where V:'g,Fv:'g,Fa:'g;#[inline]fn vsize(&self)->usize{(self.vs)().count()}#[inline]fn vertices(&self)->Self::Vertices<'_>{(self.vs)()}#[inline]fn neighbors(&self,vertex:Self::Vertex)->Self::Neighbors<'_>{(self.adj)(vertex).map(Into::into)}}impl<V,Fv,Fa>DirectedGraph for ClosureGraph<V,Fv,Fa>where Self:Graph{}impl<V,Fv,Fa,T>VertexMap<T>for ClosureGraph<V,Fv,Fa>where V:Eq+Copy+Hash,T:Clone,Self:Graph<Vertex=V>{type Vmap=(HashMap<V,T>,T);#[inline]fn construct_vmap<F>(&self,mut f:F)->Self::Vmap where F:FnMut()->T{(HashMap::new(),f())}#[inline]fn vmap_get<'a>(&self,(map,val):&'a Self::Vmap,vid:Self::Vertex)->&'a T{map.get(&vid).unwrap_or(val)}#[inline]fn vmap_get_mut<'a>(&self,(map,val):&'a mut Self::Vmap,vid:Self::Vertex)->&'a mut T{map.entry(vid).or_insert_with(| |val.clone())}}}
// codesnip-guard: Graph
#[cfg_attr(any(),rustfmt::skip)]pub use self::graph_base::*;#[cfg_attr(any(),rustfmt::skip)]mod graph_base{#[doc=" A neighboring vertex and the label of the arc used to reach it."]#[derive(Debug,Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Hash)]pub struct Neighbor<V,L>{pub to:V,pub label:L}impl<V,L>Neighbor<V,L>{#[inline]pub fn new(to:V,label:L)->Self{Self{to,label}}}impl<V,L>From<(V,L)>for Neighbor<V,L>{#[inline]fn from((to,label):(V,L))->Self{Self::new(to,label)}}#[doc=" A finite graph whose outgoing arcs can be iterated without allocation."]pub trait Graph{type Vertex:Copy+Eq;type Label;type Vertices<'g>:Iterator<Item=Self::Vertex>where Self:'g;type Neighbors<'g>:Iterator<Item=Neighbor<Self::Vertex,Self::Label>>where Self:'g;fn vsize(&self)->usize;fn vertices(&self)->Self::Vertices<'_>;fn neighbors(&self,vertex:Self::Vertex)->Self::Neighbors<'_>;}#[doc=" A graph whose adjacency relation represents directed arcs."]pub trait DirectedGraph:Graph{}pub trait VertexMap<T>:Graph{type Vmap;fn construct_vmap<F>(&self,f:F)->Self::Vmap where F:FnMut()->T;fn vmap_get<'a>(&self,map:&'a Self::Vmap,vertex:Self::Vertex)->&'a T;fn vmap_get_mut<'a>(&self,map:&'a mut Self::Vmap,vertex:Self::Vertex)->&'a mut T;#[inline]fn vmap_set(&self,map:&mut Self::Vmap,vertex:Self::Vertex,value:T){*self.vmap_get_mut(map,vertex)=value;}}pub trait EdgeMap<T>:Graph{type Emap;fn construct_emap<F>(&self,f:F)->Self::Emap where F:FnMut()->T;fn emap_get<'a>(&self,map:&'a Self::Emap,eid:Self::Label)->&'a T;fn emap_get_mut<'a>(&self,map:&'a mut Self::Emap,eid:Self::Label)->&'a mut T;#[inline]fn emap_set(&self,map:&mut Self::Emap,eid:Self::Label,value:T){*self.emap_get_mut(map,eid)=value;}}}