pub fn execute<E, Ty, G>(
        mut self,
        graph: &G,
        src_id: usize,
    ) -> Result<ShortestPathSubgraph<W, E, Ty, G>>
    where
        E: Edge<W>,
        Ty: EdgeDir,
        G: Vertices + Edges<W, E> + Neighbors + Graph<W, E, Ty>,
    {
        let mut sp_edges = vec![];

        let vertex_count = graph.vertex_count();

        let id_map = graph.continuos_id_map();

        let src_virt_id = id_map.virt_id_of(src_id);

        self.distance[src_virt_id] = W::zero().into();

        let edges = graph.as_directed_edges();

        for _ in 0..vertex_count - 1 {
            for (u_real_id, v_real_id, edge) in &edges {
                let u_virt_id = id_map.virt_id_of(*u_real_id);
                let v_virt_id = id_map.virt_id_of(*v_real_id);

                let alt = self.distance[u_virt_id] + *edge.get_weight();
                if alt < self.distance[v_virt_id] {
                    self.distance[v_virt_id] = alt;
                    self.prev[v_virt_id] = u_virt_id.into();

                    sp_edges.retain(|(_, dst_id, _)| dst_id != v_real_id); // remove edge to neighbor
                    sp_edges.push((*u_real_id, *v_real_id, *edge)); // add new edge
                }
            }
        }

        for (u_real_id, v_real_id, edge) in &edges {
            let u_virt_id = id_map.real_id_of(*u_real_id);
            let v_virt_id = id_map.real_id_of(*v_real_id);

            let alt = self.distance[u_virt_id] + *edge.get_weight();
            if alt < self.distance[v_virt_id] {
                Err(Error::new_ncd())?
            }
        }

        let mut distance_map = HashMap::new();
        for virt_id in 0..graph.vertex_count() {
            let real_id = id_map.real_id_of(virt_id);
            distance_map.insert(real_id, self.distance[virt_id]);
        }

        let vertices = edges
            .iter()
            .flat_map(|(src_id, dst_id, _)| vec![*src_id, *dst_id])
            .chain(std::iter::once(src_id))
            .collect::<HashSet<usize>>();

        Ok(ShortestPathSubgraph::init(
            graph,
            sp_edges,
            vertices,
            distance_map,
        ))
    }
/// Finds shortest path from a single source to all other vertices.
///
/// # Arguments
/// * `graph`: Graph to search for the shortest paths in.
/// * `src_id`: Id of the source vertex(Shortest path will be calculated from this vertex to all other vertices)
///
/// # Returns
/// * `Ok`: The shortest path as a subgraph of the original graph.
/// You can query shortest path from source to each destination using api provided by `ShortestPathSubgraph`.
/// * `Err`: If graph contains negative cycle.
Finds shortest path from a single source to all other vertices.
Finds shortest path from a single source to all other vertices .
pub fn execute<E, Ty, G>(
        mut self,
        graph: &G,
        src_id: usize,
    ) -> Result<ShortestPathSubgraph<W, E, Ty, G>>
    where
        E: Edge<W>,
        Ty: EdgeDir,
        G: Vertices + Edges<W, E> + Neighbors + Graph<W, E, Ty>,
    {
        let mut sp_edges = vec![];
        let vertex_count = graph.vertex_count();
        let id_map = graph.continuos_id_map();
        let src_virt_id = id_map.virt_id_of(src_id);
        self.distance[src_virt_id] = W::zero().into();
        let edges = graph.as_directed_edges();
        for _ in 0..vertex_count - 1 {
            for (u_real_id, v_real_id, edge) in &edges {
                let u_virt_id = id_map.virt_id_of(*u_real_id);
                let v_virt_id = id_map.virt_id_of(*v_real_id);
                let alt = self.distance[u_virt_id] + *edge.get_weight();
                if alt < self.distance[v_virt_id] {
                    self.distance[v_virt_id] = alt;
                    self.prev[v_virt_id] = u_virt_id.into();
                    sp_edges.retain(|(_, dst_id, _)| dst_id != v_real_id); // remove edge to neighbor
                    sp_edges.push((*u_real_id, *v_real_id, *edge)); // add new edge
                }
            }
        }
        for (u_real_id, v_real_id, edge) in &edges {
            let u_virt_id = id_map.real_id_of(*u_real_id);
            let v_virt_id = id_map.real_id_of(*v_real_id);
            let alt = self.distance[u_virt_id] + *edge.get_weight();
            if alt < self.distance[v_virt_id] {
                Err(Error::new_ncd())?
            }
        }
        let mut distance_map = HashMap::new();
        for virt_id in 0..graph.vertex_count() {
            let real_id = id_map.real_id_of(virt_id);
            distance_map.insert(real_id, self.distance[virt_id]);
        }
        let vertices = edges
            .iter()
            .flat_map(|(src_id, dst_id, _)| vec![*src_id, *dst_id])
            .chain(std::iter::once(src_id))
            .collect::<HashSet<usize>>();
        Ok(ShortestPathSubgraph::init(
            graph,
            sp_edges,
            vertices,
            distance_map,
        ))
    }
pub fn execute < E , Ty , G > ( mut self , graph : & G , src_id : usize , ) -> Result < ShortestPathSubgraph < W , E , Ty , G > > where E : Edge < W > , Ty : EdgeDir , G : Vertices + Edges < W , E > + Neighbors + Graph < W , E , Ty > , { let mut sp_edges = vec ! [ ] ; let vertex_count = graph . vertex_count ( ) ; let id_map = graph . continuos_id_map ( ) ; let src_virt_id = id_map . virt_id_of ( src_id ) ; self . distance [ src_virt_id ] = W :: zero ( ) . into ( ) ; let edges = graph . as_directed_edges ( ) ; for _ in 0 .. vertex_count - 1 { for ( u_real_id , v_real_id , edge ) in & edges { let u_virt_id = id_map . virt_id_of ( * u_real_id ) ; let v_virt_id = id_map . virt_id_of ( * v_real_id ) ; let alt = self . distance [ u_virt_id ] + * edge . get_weight ( ) ; if alt < self . distance [ v_virt_id ] { self . distance [ v_virt_id ] = alt ; self . prev [ v_virt_id ] = u_virt_id . into ( ) ; sp_edges . retain ( | ( _ , dst_id , _ ) | dst_id != v_real_id ) ; // remove edge to neighbor sp_edges . push ( ( * u_real_id , * v_real_id , * edge ) ) ; // add new edge } } } for ( u_real_id , v_real_id , edge ) in & edges { let u_virt_id = id_map . real_id_of ( * u_real_id ) ; let v_virt_id = id_map . real_id_of ( * v_real_id ) ; let alt = self . distance [ u_virt_id ] + * edge . get_weight ( ) ; if alt < self . distance [ v_virt_id ] { Err ( Error :: new_ncd ( ) ) ? } } let mut distance_map = HashMap :: new ( ) ; for virt_id in 0 .. graph . vertex_count ( ) { let real_id = id_map . real_id_of ( virt_id ) ; distance_map . insert ( real_id , self . distance [ virt_id ] ) ; } let vertices = edges . iter ( ) . flat_map ( | ( src_id , dst_id , _ ) | vec ! [ src_id dst_id ] ) . chain ( std :: iter :: once ( src_id ) ) . collect :: < HashSet < usize > > ( ) ; Ok ( ShortestPathSubgraph :: init ( graph , sp_edges , vertices , distance_map , ) ) }
Finds shortest path from a single source to all other vertices.
Finds shortest path from a single source to all other vertices .
mut self
graph
&G
src_id
usize
`Ok`: The shortest path as a subgraph of the original graph.
You can query shortest path from source to each destination using api provided by `ShortestPathSubgraph`.
`Err`: If graph contains negative cycle.
` Ok ` : The shortest path as a subgraph of the original graph . You can query shortest path from source to each destination using api provided by ` ShortestPathSubgraph ` . ` Err ` : If graph contains negative cycle .
mut self
graph
&G
src_id
usize