Skip to main content

ShortestPathBuilder

competitive::graph::shortest_path

Struct ShortestPathBuilder 

Source 
pub struct ShortestPathBuilder<'a, G, S, P = NoParent>
where
    G: Graph,
    S: ShortestPathSemiRing,
    P: ParentPolicy<G>,
{
    graph: &'a G,
    _marker: PhantomData<fn() -> (S, P)>,
}

Fields§

§graph: &'a G§_marker: PhantomData<fn() -> (S, P)>

Implementations§

Source§

impl<'a, G, S, P> ShortestPathBuilder<'a, G, S, P>
where G: Graph, S: ShortestPathSemiRing, P: ParentPolicy<G>,

Source

fn bfs_distance_core<M, I>( &self, sources: I, weight: &M, ) -> ShortestPathWithParent<G, S, P>
where G: VertexMap<S::T>, M: Fn(G::Label) -> S::T + ?Sized, I: IntoIterator<Item = G::Vertex>,

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 426)
420    pub fn bfs_distance<M, I>(&self, sources: I, weight: M) -> <G as VertexMap<S::T>>::Vmap
421    where
422        G: VertexMap<S::T>,
423        M: Fn(G::Label) -> S::T,
424        I: IntoIterator<Item = G::Vertex>,
425    {
426        self.bfs_distance_core(sources, &weight).dist
427    }
428
429    pub fn dijkstra<M, I>(&self, sources: I, weight: M) -> <G as VertexMap<S::T>>::Vmap
430    where
431        G: VertexMap<S::T>,
432        M: Fn(G::Label) -> S::T,
433        I: IntoIterator<Item = G::Vertex>,
434    {
435        self.dijkstra_core(sources, &weight, |_| false).dist
436    }
437
438    pub fn bellman_ford<M, I>(
439        &self,
440        sources: I,
441        weight: M,
442        check: bool,
443    ) -> Option<<G as VertexMap<S::T>>::Vmap>
444    where
445        G: VertexMap<S::T>,
446        M: Fn(G::Label) -> S::T,
447        I: IntoIterator<Item = G::Vertex>,
448    {
449        self.bellman_ford_core(sources, &weight, check)
450            .map(|sp| sp.dist)
451    }
452
453    pub fn warshall_floyd_ap<M>(
454        &self,
455        weight: M,
456    ) -> <G as VertexMap<<G as VertexMap<S::T>>::Vmap>>::Vmap
457    where
458        G: VertexMap<S::T, Vmap: Clone> + VertexMap<<G as VertexMap<S::T>>::Vmap>,
459        M: Fn(G::Label) -> S::T,
460    {
461        let graph = self.graph;
462        let mut dist = graph.construct_vmap(|| graph.construct_vmap(S::inf));
463        for u in graph.vertices() {
464            *graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), u) = S::source();
465        }
466        for u in graph.vertices() {
467            for neighbor in graph.neighbors(u) {
468                let weight = weight(neighbor.label);
469                S::add_assign(
470                    graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), neighbor.to),
471                    &weight,
472                );
473            }
474        }
475        for k in graph.vertices() {
476            for i in graph.vertices() {
477                for j in graph.vertices() {
478                    let d1 = graph.vmap_get(graph.vmap_get(&dist, i), k);
479                    let d2 = graph.vmap_get(graph.vmap_get(&dist, k), j);
480                    let nd = S::mul(d1, d2);
481                    S::add_assign(graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, i), j), &nd);
482                }
483            }
484        }
485        dist
486    }
487}
488
489impl<'a, G, S> ShortestPathBuilder<'a, G, S, RecordParent>
490where
491    G: Graph + VertexMap<Option<<G as Graph>::Vertex>>,
492    S: ShortestPathSemiRing,
493{
494    pub fn bfs_distance<M, I>(&self, sources: I, weight: M) -> ShortestPathWithParent<G, S>
495    where
496        G: VertexMap<S::T>,
497        M: Fn(G::Label) -> S::T,
498        I: IntoIterator<Item = G::Vertex>,
499    {
500        self.bfs_distance_core(sources, &weight)
501    }
Source

fn dijkstra_core<M, I>( &self, sources: I, weight: &M, stop: impl FnMut(G::Vertex) -> bool, ) -> ShortestPathWithParent<G, S, P>
where G: VertexMap<S::T>, M: Fn(G::Label) -> S::T + ?Sized, I: IntoIterator<Item = G::Vertex>,

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 435)
429    pub fn dijkstra<M, I>(&self, sources: I, weight: M) -> <G as VertexMap<S::T>>::Vmap
430    where
431        G: VertexMap<S::T>,
432        M: Fn(G::Label) -> S::T,
433        I: IntoIterator<Item = G::Vertex>,
434    {
435        self.dijkstra_core(sources, &weight, |_| false).dist
436    }
437
438    pub fn bellman_ford<M, I>(
439        &self,
440        sources: I,
441        weight: M,
442        check: bool,
443    ) -> Option<<G as VertexMap<S::T>>::Vmap>
444    where
445        G: VertexMap<S::T>,
446        M: Fn(G::Label) -> S::T,
447        I: IntoIterator<Item = G::Vertex>,
448    {
449        self.bellman_ford_core(sources, &weight, check)
450            .map(|sp| sp.dist)
451    }
452
453    pub fn warshall_floyd_ap<M>(
454        &self,
455        weight: M,
456    ) -> <G as VertexMap<<G as VertexMap<S::T>>::Vmap>>::Vmap
457    where
458        G: VertexMap<S::T, Vmap: Clone> + VertexMap<<G as VertexMap<S::T>>::Vmap>,
459        M: Fn(G::Label) -> S::T,
460    {
461        let graph = self.graph;
462        let mut dist = graph.construct_vmap(|| graph.construct_vmap(S::inf));
463        for u in graph.vertices() {
464            *graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), u) = S::source();
465        }
466        for u in graph.vertices() {
467            for neighbor in graph.neighbors(u) {
468                let weight = weight(neighbor.label);
469                S::add_assign(
470                    graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), neighbor.to),
471                    &weight,
472                );
473            }
474        }
475        for k in graph.vertices() {
476            for i in graph.vertices() {
477                for j in graph.vertices() {
478                    let d1 = graph.vmap_get(graph.vmap_get(&dist, i), k);
479                    let d2 = graph.vmap_get(graph.vmap_get(&dist, k), j);
480                    let nd = S::mul(d1, d2);
481                    S::add_assign(graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, i), j), &nd);
482                }
483            }
484        }
485        dist
486    }
487}
488
489impl<'a, G, S> ShortestPathBuilder<'a, G, S, RecordParent>
490where
491    G: Graph + VertexMap<Option<<G as Graph>::Vertex>>,
492    S: ShortestPathSemiRing,
493{
494    pub fn bfs_distance<M, I>(&self, sources: I, weight: M) -> ShortestPathWithParent<G, S>
495    where
496        G: VertexMap<S::T>,
497        M: Fn(G::Label) -> S::T,
498        I: IntoIterator<Item = G::Vertex>,
499    {
500        self.bfs_distance_core(sources, &weight)
501    }
502
503    pub fn dijkstra<M, I>(&self, sources: I, weight: M) -> ShortestPathWithParent<G, S>
504    where
505        G: VertexMap<S::T>,
506        M: Fn(G::Label) -> S::T,
507        I: IntoIterator<Item = G::Vertex>,
508    {
509        self.dijkstra_core(sources, &weight, |_| false)
510    }
511
512    pub fn bellman_ford<M, I>(
513        &self,
514        sources: I,
515        weight: M,
516        check: bool,
517    ) -> Option<ShortestPathWithParent<G, S>>
518    where
519        G: VertexMap<S::T>,
520        M: Fn(G::Label) -> S::T,
521        I: IntoIterator<Item = G::Vertex>,
522    {
523        self.bellman_ford_core(sources, &weight, check)
524    }
525}
526
527impl<'a, G, M, P> ShortestPathBuilder<'a, G, StandardSp<M>, P>
528where
529    G: Graph,
530    M: Monoid<T: Bounded + Ord>,
531    P: ParentPolicy<G>,
532{
533    /// Distances other than the target may remain tentative.
534    pub fn dijkstra_to<W, I>(
535        &self,
536        sources: I,
537        target: G::Vertex,
538        weight: W,
539    ) -> ShortestPathWithParent<G, StandardSp<M>, P>
540    where
541        G: VertexMap<M::T>,
542        W: Fn(G::Label) -> M::T,
543        I: IntoIterator<Item = G::Vertex>,
544    {
545        self.dijkstra_core(sources, &weight, |u| u == target)
546    }
Source

fn bellman_ford_core<M, I>( &self, sources: I, weight: &M, check: bool, ) -> Option<ShortestPathWithParent<G, S, P>>
where G: VertexMap<S::T>, M: Fn(G::Label) -> S::T + ?Sized, I: IntoIterator<Item = G::Vertex>, P: ParentPolicy<G>,

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 449)
438    pub fn bellman_ford<M, I>(
439        &self,
440        sources: I,
441        weight: M,
442        check: bool,
443    ) -> Option<<G as VertexMap<S::T>>::Vmap>
444    where
445        G: VertexMap<S::T>,
446        M: Fn(G::Label) -> S::T,
447        I: IntoIterator<Item = G::Vertex>,
448    {
449        self.bellman_ford_core(sources, &weight, check)
450            .map(|sp| sp.dist)
451    }
452
453    pub fn warshall_floyd_ap<M>(
454        &self,
455        weight: M,
456    ) -> <G as VertexMap<<G as VertexMap<S::T>>::Vmap>>::Vmap
457    where
458        G: VertexMap<S::T, Vmap: Clone> + VertexMap<<G as VertexMap<S::T>>::Vmap>,
459        M: Fn(G::Label) -> S::T,
460    {
461        let graph = self.graph;
462        let mut dist = graph.construct_vmap(|| graph.construct_vmap(S::inf));
463        for u in graph.vertices() {
464            *graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), u) = S::source();
465        }
466        for u in graph.vertices() {
467            for neighbor in graph.neighbors(u) {
468                let weight = weight(neighbor.label);
469                S::add_assign(
470                    graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), neighbor.to),
471                    &weight,
472                );
473            }
474        }
475        for k in graph.vertices() {
476            for i in graph.vertices() {
477                for j in graph.vertices() {
478                    let d1 = graph.vmap_get(graph.vmap_get(&dist, i), k);
479                    let d2 = graph.vmap_get(graph.vmap_get(&dist, k), j);
480                    let nd = S::mul(d1, d2);
481                    S::add_assign(graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, i), j), &nd);
482                }
483            }
484        }
485        dist
486    }
487}
488
489impl<'a, G, S> ShortestPathBuilder<'a, G, S, RecordParent>
490where
491    G: Graph + VertexMap<Option<<G as Graph>::Vertex>>,
492    S: ShortestPathSemiRing,
493{
494    pub fn bfs_distance<M, I>(&self, sources: I, weight: M) -> ShortestPathWithParent<G, S>
495    where
496        G: VertexMap<S::T>,
497        M: Fn(G::Label) -> S::T,
498        I: IntoIterator<Item = G::Vertex>,
499    {
500        self.bfs_distance_core(sources, &weight)
501    }
502
503    pub fn dijkstra<M, I>(&self, sources: I, weight: M) -> ShortestPathWithParent<G, S>
504    where
505        G: VertexMap<S::T>,
506        M: Fn(G::Label) -> S::T,
507        I: IntoIterator<Item = G::Vertex>,
508    {
509        self.dijkstra_core(sources, &weight, |_| false)
510    }
511
512    pub fn bellman_ford<M, I>(
513        &self,
514        sources: I,
515        weight: M,
516        check: bool,
517    ) -> Option<ShortestPathWithParent<G, S>>
518    where
519        G: VertexMap<S::T>,
520        M: Fn(G::Label) -> S::T,
521        I: IntoIterator<Item = G::Vertex>,
522    {
523        self.bellman_ford_core(sources, &weight, check)
524    }
Source§

impl<'a, G, S> ShortestPathBuilder<'a, G, S, NoParent>
where G: Graph, S: ShortestPathSemiRing,

Source

pub fn with_parent(self) -> ShortestPathBuilder<'a, G, S, RecordParent>
where G: VertexMap<Option<<G as Graph>::Vertex>>,

Examples found in repository?
crates/library_checker/src/graph/shortest_path.rs (line 10)
5pub fn shortest_path(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, s, t, (g, c): @DirectedGraphScanner::<usize, u64>::new(n, m));
8    let sp = g
9        .standard_sp_additive()
10        .with_parent()
11        .dijkstra_to([s], t, |eid| c[eid]);
12    if let Some(path) = sp.path_to(&g, t) {
13        pp!(sp.dist[t], path.len() - 1; @it2d path.windows(2));
14    } else {
15        pp!(-1);
16    }
17}
Source

pub fn bfs_distance<M, I>( &self, sources: I, weight: M, ) -> <G as VertexMap<S::T>>::Vmap
where G: VertexMap<S::T>, M: Fn(G::Label) -> S::T, I: IntoIterator<Item = G::Vertex>,

Source

pub fn dijkstra<M, I>( &self, sources: I, weight: M, ) -> <G as VertexMap<S::T>>::Vmap
where G: VertexMap<S::T>, M: Fn(G::Label) -> S::T, I: IntoIterator<Item = G::Vertex>,

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_1_a.rs (line 11)
8pub fn grl_1_a(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
11    let cost = graph.standard_sp_additive().dijkstra([r], |eid| d[eid]);
12    for u in graph.vertices() {
13        if cost[u].is_maximum() {
14            pp!("INF");
15        } else {
16            pp!(cost[u]);
17        }
18    }
19}
20
21#[verify::aizu_online_judge("GRL_1_A")]
22pub fn grl_1_a_option(reader: impl Read, writer: impl Write) {
23    prepare_io!(reader, writer);
24    sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
25    let cost = graph.option_sp_additive().dijkstra([r], |eid| Some(d[eid]));
26    for u in graph.vertices() {
27        match cost[u] {
28            Some(d) => pp!(d),
29            None => pp!("INF"),
30        };
31    }
32}
Source

pub fn bellman_ford<M, I>( &self, sources: I, weight: M, check: bool, ) -> Option<<G as VertexMap<S::T>>::Vmap>
where G: VertexMap<S::T>, M: Fn(G::Label) -> S::T, I: IntoIterator<Item = G::Vertex>,

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_1_b.rs (line 10)
5pub fn grl_1_b(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
8    let cost = graph
9        .option_sp_additive()
10        .bellman_ford([r], |eid| Some(d[eid]), true);
11    if let Some(cost) = cost {
12        for u in graph.vertices() {
13            match cost[u] {
14                Some(d) => pp!(d),
15                None => pp!("INF"),
16            };
17        }
18    } else {
19        pp!("NEGATIVE CYCLE");
20    }
21}
Source

pub fn warshall_floyd_ap<M>( &self, weight: M, ) -> <G as VertexMap<<G as VertexMap<S::T>>::Vmap>>::Vmap
where G: VertexMap<S::T, Vmap: Clone> + VertexMap<<G as VertexMap<S::T>>::Vmap>, M: Fn(G::Label) -> S::T,

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_1_c.rs (line 13)
8pub fn grl_1_c(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(vs, es, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
11    let cost = graph
12        .option_sp_additive()
13        .warshall_floyd_ap(|eid| Some(Saturating(d[eid])));
14    if graph.vertices().any(|u| cost[u][u].unwrap().0 < 0) {
15        pp!("NEGATIVE CYCLE");
16    } else {
17        for u in graph.vertices() {
18            for v in graph.vertices() {
19                match cost[u][v] {
20                    Some(d) => pp!(d.0, !),
21                    None => pp!("INF", !),
22                };
23                pp!(if v + 1 == vs { '\n' } else { ' ' }, !);
24            }
25        }
26    }
27}
Source§

impl<'a, G, S> ShortestPathBuilder<'a, G, S, RecordParent>
where G: Graph + VertexMap<Option<<G as Graph>::Vertex>>, S: ShortestPathSemiRing,

Source

pub fn bfs_distance<M, I>( &self, sources: I, weight: M, ) -> ShortestPathWithParent<G, S>
where G: VertexMap<S::T>, M: Fn(G::Label) -> S::T, I: IntoIterator<Item = G::Vertex>,

Source

pub fn dijkstra<M, I>( &self, sources: I, weight: M, ) -> ShortestPathWithParent<G, S>
where G: VertexMap<S::T>, M: Fn(G::Label) -> S::T, I: IntoIterator<Item = G::Vertex>,

Source

pub fn bellman_ford<M, I>( &self, sources: I, weight: M, check: bool, ) -> Option<ShortestPathWithParent<G, S>>
where G: VertexMap<S::T>, M: Fn(G::Label) -> S::T, I: IntoIterator<Item = G::Vertex>,

Source§

impl<'a, G, M, P> ShortestPathBuilder<'a, G, StandardSp<M>, P>
where G: Graph, M: Monoid<T: Bounded + Ord>, P: ParentPolicy<G>,

Source

pub fn dijkstra_to<W, I>( &self, sources: I, target: G::Vertex, weight: W, ) -> ShortestPathWithParent<G, StandardSp<M>, P>
where G: VertexMap<M::T>, W: Fn(G::Label) -> M::T, I: IntoIterator<Item = G::Vertex>,

Distances other than the target may remain tentative.

Examples found in repository?
crates/library_checker/src/graph/shortest_path.rs (line 11)
5pub fn shortest_path(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, s, t, (g, c): @DirectedGraphScanner::<usize, u64>::new(n, m));
8    let sp = g
9        .standard_sp_additive()
10        .with_parent()
11        .dijkstra_to([s], t, |eid| c[eid]);
12    if let Some(path) = sp.path_to(&g, t) {
13        pp!(sp.dist[t], path.len() - 1; @it2d path.windows(2));
14    } else {
15        pp!(-1);
16    }
17}

Auto Trait Implementations§

§

impl<'a, G, S, P> Freeze for ShortestPathBuilder<'a, G, S, P>
where &'a G: Freeze, PhantomData<fn() -> (S, P)>: Freeze,

§

impl<'a, G, S, P> RefUnwindSafe for ShortestPathBuilder<'a, G, S, P>
where &'a G: RefUnwindSafe, PhantomData<fn() -> (S, P)>: RefUnwindSafe,

§

impl<'a, G, S, P> Send for ShortestPathBuilder<'a, G, S, P>
where &'a G: Send, PhantomData<fn() -> (S, P)>: Send,

§

impl<'a, G, S, P> Sync for ShortestPathBuilder<'a, G, S, P>
where &'a G: Sync, PhantomData<fn() -> (S, P)>: Sync,

§

impl<'a, G, S, P> Unpin for ShortestPathBuilder<'a, G, S, P>
where &'a G: Unpin, PhantomData<fn() -> (S, P)>: Unpin,

§

impl<'a, G, S, P> UnsafeUnpin for ShortestPathBuilder<'a, G, S, P>
where &'a G: UnsafeUnpin, PhantomData<fn() -> (S, P)>: UnsafeUnpin,

§

impl<'a, G, S, P> UnwindSafe for ShortestPathBuilder<'a, G, S, P>
where &'a G: UnwindSafe, PhantomData<fn() -> (S, P)>: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.