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

        let id_map = graph.continuos_id_map();

        let src_virt_id = id_map.virt_id_of(src_id);

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

        while let Some(virt_id) = self.next_id() {
            self.visited[virt_id] = true;

            let real_id = id_map.real_id_of(virt_id);

            for (n_id, edge) in graph.edges_from(real_id).unwrap() {
                let n_virt_id = id_map.virt_id_of(n_id);

                let alt = self.dist[virt_id] + *edge.get_weight();
                if alt < self.dist[n_virt_id] {
                    self.dist[n_virt_id] = alt;
                    self.prev[n_virt_id] = virt_id.into();

                    edges.retain(|(_, dst_id, _)| *dst_id != n_id); // remove edge to neighbor
                    edges.push((real_id, n_id, edge)); // add new edge
                }
            }
        }

        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.dist[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>>();

        ShortestPathSubgraph::init(graph, 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
/// 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`.
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,
    ) -> ShortestPathSubgraph<W, E, Ty, G>
    where
        E: Edge<W>,
        Ty: EdgeDir,
        G: Edges<W, E> + Neighbors + Vertices + Graph<W, E, Ty>,
    {
        let mut edges = vec![];
        let id_map = graph.continuos_id_map();
        let src_virt_id = id_map.virt_id_of(src_id);
        self.dist[src_virt_id] = W::zero().into();
        while let Some(virt_id) = self.next_id() {
            self.visited[virt_id] = true;
            let real_id = id_map.real_id_of(virt_id);
            for (n_id, edge) in graph.edges_from(real_id).unwrap() {
                let n_virt_id = id_map.virt_id_of(n_id);
                let alt = self.dist[virt_id] + *edge.get_weight();
                if alt < self.dist[n_virt_id] {
                    self.dist[n_virt_id] = alt;
                    self.prev[n_virt_id] = virt_id.into();
                    edges.retain(|(_, dst_id, _)| *dst_id != n_id); // remove edge to neighbor
                    edges.push((real_id, n_id, edge)); // add new edge
                }
            }
        }
        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.dist[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>>();
        ShortestPathSubgraph::init(graph, edges, vertices, distance_map)
    }
pub fn execute < E , Ty , G > ( mut self , graph : & G , src_id : usize , ) -> ShortestPathSubgraph < W , E , Ty , G > where E : Edge < W > , Ty : EdgeDir , G : Edges < W , E > + Neighbors + Vertices + Graph < W , E , Ty > , { let mut edges = vec ! [ ] ; let id_map = graph . continuos_id_map ( ) ; let src_virt_id = id_map . virt_id_of ( src_id ) ; self . dist [ src_virt_id ] = W :: zero ( ) . into ( ) ; while let Some ( virt_id ) = self . next_id ( ) { self . visited [ virt_id ] = true ; let real_id = id_map . real_id_of ( virt_id ) ; for ( n_id , edge ) in graph . edges_from ( real_id ) . unwrap ( ) { let n_virt_id = id_map . virt_id_of ( n_id ) ; let alt = self . dist [ virt_id ] + * edge . get_weight ( ) ; if alt < self . dist [ n_virt_id ] { self . dist [ n_virt_id ] = alt ; self . prev [ n_virt_id ] = virt_id . into ( ) ; edges . retain ( | ( _ , dst_id , _ ) | * dst_id != n_id ) ; // remove edge to neighbor edges . push ( ( real_id , n_id , edge ) ) ; // add new edge } } } 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 . dist [ 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 > > ( ) ; ShortestPathSubgraph :: init ( graph , 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
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`.
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 ` .
mut self
graph
&G
src_id
usize