// codesnip-guard: graph_order
#[cfg_attr(any(),rustfmt::skip)]pub use self::order::GraphOrderExt;#[cfg_attr(any(),rustfmt::skip)]mod order{use super::{EdgeMap,Graph,VertexMap};use std::collections::VecDeque;pub trait GraphOrderExt:Graph{fn bfs_order(&self,root:Self::Vertex)->Vec<Self::Vertex>where Self:VertexMap<bool>{let mut visited=self.construct_vmap(| |false);let mut order=Vec::with_capacity(self.vsize());*self.vmap_get_mut(&mut visited,root)=true;let mut queue=VecDeque::from([root]);while let Some(u)=queue.pop_front(){order.push(u);for neighbor in self.neighbors(u){if!self.vmap_get(&visited,neighbor.to){*self.vmap_get_mut(&mut visited,neighbor.to)=true;queue.push_back(neighbor.to);}}}order}fn dfs_order(&self,root:Self::Vertex)->Vec<Self::Vertex>where Self:VertexMap<bool>{let mut visited=self.construct_vmap(| |false);let mut order=Vec::with_capacity(self.vsize());*self.vmap_get_mut(&mut visited,root)=true;let mut stack=vec![root];while let Some(u)=stack.pop(){order.push(u);for neighbor in self.neighbors(u){if!self.vmap_get(&visited,neighbor.to){*self.vmap_get_mut(&mut visited,neighbor.to)=true;stack.push(neighbor.to);}}}order}fn dfs_tree(&self,root:Self::Vertex)-><Self as EdgeMap<bool>>::Emap where Self:EdgeMap<bool>+VertexMap<bool>{let mut visited=self.construct_vmap(| |false);let mut used=self.construct_emap(| |false);*self.vmap_get_mut(&mut visited,root)=true;let mut stack=vec![root];while let Some(u)=stack.pop(){for neighbor in self.neighbors(u){if!self.vmap_get(&visited,neighbor.to){*self.vmap_get_mut(&mut visited,neighbor.to)=true;self.emap_set(&mut used,neighbor.label,true);stack.push(neighbor.to);}}}used}#[doc=" f: |g, root, ord: [vertex, parent]| {}"]fn for_each_connected_components<F>(&self,mut f:F)where Self:VertexMap<bool>,F:FnMut(&Self,Self::Vertex,&[(Self::Vertex,Option<Self::Vertex>)]){let mut visited=self.construct_vmap(| |false);let mut order=Vec::with_capacity(self.vsize());for root in self.vertices(){if!self.vmap_get(&visited,root){*self.vmap_get_mut(&mut visited,root)=true;order.push((root,None));let mut i=0;while i<order.len(){let u=order[i].0;for neighbor in self.neighbors(u){if!self.vmap_get(&visited,neighbor.to){*self.vmap_get_mut(&mut visited,neighbor.to)=true;order.push((neighbor.to,Some(u)));}}i+=1;}f(self,root,&order);order.clear();}}}}impl<G>GraphOrderExt for G where G:Graph+?Sized{}}
// 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;}}}