ShortestPathBuilder

competitive::graph::shortest_path

Struct ShortestPathBuilder 

Source 
pub struct ShortestPathBuilder<'a, G, S, P = NoParent>
where
    G: GraphBase,
    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: GraphBase, S: ShortestPathSemiRing, P: ParentPolicy<G>,

Source

fn bfs_distance_core<M, I>( &self, sources: I, weight: &'a M, ) -> ShortestPathWithParent<G, S, P>
where G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>, I: IntoIterator<Item = G::VIndex>,

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 398)
393    pub fn bfs_distance<M, I>(&self, sources: I, weight: &'a M) -> <G as VertexMap<S::T>>::Vmap
394    where
395        G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
396        I: IntoIterator<Item = G::VIndex>,
397    {
398        self.bfs_distance_core::<M, I>(sources, weight).dist
399    }
400
401    pub fn dijkstra<M, I>(&self, sources: I, weight: &'a M) -> <G as VertexMap<S::T>>::Vmap
402    where
403        G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
404        I: IntoIterator<Item = G::VIndex>,
405    {
406        self.dijkstra_core::<M, I>(sources, weight).dist
407    }
408
409    pub fn bellman_ford<M, I>(
410        &self,
411        sources: I,
412        weight: &'a M,
413        check: bool,
414    ) -> Option<<G as VertexMap<S::T>>::Vmap>
415    where
416        G: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize,
417        I: IntoIterator<Item = G::VIndex>,
418    {
419        self.bellman_ford_core::<M, I>(sources, weight, check)
420            .map(|sp| sp.dist)
421    }
422
423    pub fn warshall_floyd_ap<M>(
424        &self,
425        weight: &'a M,
426    ) -> <G as VertexMap<<G as VertexMap<S::T>>::Vmap>>::Vmap
427    where
428        G: Vertices
429            + VertexMap<S::T, Vmap: Clone>
430            + VertexMap<<G as VertexMap<S::T>>::Vmap>
431            + AdjacencyView<'a, M, S::T>,
432    {
433        let graph = self.graph;
434        let mut dist = graph.construct_vmap(|| graph.construct_vmap(S::inf));
435        for u in graph.vertices() {
436            *graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), u) = S::source();
437        }
438        for u in graph.vertices() {
439            for a in graph.aviews(weight, u) {
440                S::add_assign(
441                    graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), a.vindex()),
442                    &a.avalue(),
443                );
444            }
445        }
446        for k in graph.vertices() {
447            for i in graph.vertices() {
448                for j in graph.vertices() {
449                    let d1 = graph.vmap_get(graph.vmap_get(&dist, i), k);
450                    let d2 = graph.vmap_get(graph.vmap_get(&dist, k), j);
451                    let nd = S::mul(d1, d2);
452                    S::add_assign(graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, i), j), &nd);
453                }
454            }
455        }
456        dist
457    }
458}
459
460impl<'a, G, S> ShortestPathBuilder<'a, G, S, RecordParent>
461where
462    G: GraphBase + VertexMap<Option<<G as GraphBase>::VIndex>>,
463    S: ShortestPathSemiRing,
464{
465    pub fn bfs_distance<M, I>(&self, sources: I, weight: &'a M) -> ShortestPathWithParent<G, S>
466    where
467        G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
468        I: IntoIterator<Item = G::VIndex>,
469    {
470        self.bfs_distance_core::<M, I>(sources, weight)
471    }
Source

fn dijkstra_core<M, I>( &self, sources: I, weight: &'a M, ) -> ShortestPathWithParent<G, S, P>
where G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>, I: IntoIterator<Item = G::VIndex>,

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 406)
401    pub fn dijkstra<M, I>(&self, sources: I, weight: &'a M) -> <G as VertexMap<S::T>>::Vmap
402    where
403        G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
404        I: IntoIterator<Item = G::VIndex>,
405    {
406        self.dijkstra_core::<M, I>(sources, weight).dist
407    }
408
409    pub fn bellman_ford<M, I>(
410        &self,
411        sources: I,
412        weight: &'a M,
413        check: bool,
414    ) -> Option<<G as VertexMap<S::T>>::Vmap>
415    where
416        G: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize,
417        I: IntoIterator<Item = G::VIndex>,
418    {
419        self.bellman_ford_core::<M, I>(sources, weight, check)
420            .map(|sp| sp.dist)
421    }
422
423    pub fn warshall_floyd_ap<M>(
424        &self,
425        weight: &'a M,
426    ) -> <G as VertexMap<<G as VertexMap<S::T>>::Vmap>>::Vmap
427    where
428        G: Vertices
429            + VertexMap<S::T, Vmap: Clone>
430            + VertexMap<<G as VertexMap<S::T>>::Vmap>
431            + AdjacencyView<'a, M, S::T>,
432    {
433        let graph = self.graph;
434        let mut dist = graph.construct_vmap(|| graph.construct_vmap(S::inf));
435        for u in graph.vertices() {
436            *graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), u) = S::source();
437        }
438        for u in graph.vertices() {
439            for a in graph.aviews(weight, u) {
440                S::add_assign(
441                    graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, u), a.vindex()),
442                    &a.avalue(),
443                );
444            }
445        }
446        for k in graph.vertices() {
447            for i in graph.vertices() {
448                for j in graph.vertices() {
449                    let d1 = graph.vmap_get(graph.vmap_get(&dist, i), k);
450                    let d2 = graph.vmap_get(graph.vmap_get(&dist, k), j);
451                    let nd = S::mul(d1, d2);
452                    S::add_assign(graph.vmap_get_mut(graph.vmap_get_mut(&mut dist, i), j), &nd);
453                }
454            }
455        }
456        dist
457    }
458}
459
460impl<'a, G, S> ShortestPathBuilder<'a, G, S, RecordParent>
461where
462    G: GraphBase + VertexMap<Option<<G as GraphBase>::VIndex>>,
463    S: ShortestPathSemiRing,
464{
465    pub fn bfs_distance<M, I>(&self, sources: I, weight: &'a M) -> ShortestPathWithParent<G, S>
466    where
467        G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
468        I: IntoIterator<Item = G::VIndex>,
469    {
470        self.bfs_distance_core::<M, I>(sources, weight)
471    }
472
473    pub fn dijkstra<M, I>(&self, sources: I, weight: &'a M) -> ShortestPathWithParent<G, S>
474    where
475        G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
476        I: IntoIterator<Item = G::VIndex>,
477    {
478        self.dijkstra_core::<M, I>(sources, weight)
479    }
Source

fn bellman_ford_core<M, I>( &self, sources: I, weight: &'a M, check: bool, ) -> Option<ShortestPathWithParent<G, S, P>>
where G: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize, I: IntoIterator<Item = G::VIndex>, P: ParentPolicy<G>,

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

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

Source

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

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

pub fn bfs_distance<M, I>( &self, sources: I, weight: &'a M, ) -> <G as VertexMap<S::T>>::Vmap
where G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>, I: IntoIterator<Item = G::VIndex>,

Source

pub fn dijkstra<M, I>( &self, sources: I, weight: &'a M, ) -> <G as VertexMap<S::T>>::Vmap
where G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>, I: IntoIterator<Item = G::VIndex>,

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

pub fn bellman_ford<M, I>( &self, sources: I, weight: &'a M, check: bool, ) -> Option<<G as VertexMap<S::T>>::Vmap>
where G: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize, I: IntoIterator<Item = G::VIndex>,

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

pub fn warshall_floyd_ap<M>( &self, weight: &'a M, ) -> <G as VertexMap<<G as VertexMap<S::T>>::Vmap>>::Vmap
where G: Vertices + VertexMap<S::T, Vmap: Clone> + VertexMap<<G as VertexMap<S::T>>::Vmap> + AdjacencyView<'a, M, S::T>,

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

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

Source

pub fn bfs_distance<M, I>( &self, sources: I, weight: &'a M, ) -> ShortestPathWithParent<G, S>
where G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>, I: IntoIterator<Item = G::VIndex>,

Source

pub fn dijkstra<M, I>( &self, sources: I, weight: &'a M, ) -> ShortestPathWithParent<G, S>
where G: VertexMap<S::T> + AdjacencyView<'a, M, S::T>, I: IntoIterator<Item = G::VIndex>,

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

pub fn bellman_ford<M, I>( &self, sources: I, weight: &'a M, check: bool, ) -> Option<ShortestPathWithParent<G, S>>
where G: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize, I: IntoIterator<Item = G::VIndex>,

Auto Trait Implementations§

§

impl<'a, G, S, P> Freeze for ShortestPathBuilder<'a, G, S, P>

§

impl<'a, G, S, P> RefUnwindSafe for ShortestPathBuilder<'a, G, S, P>
where G: RefUnwindSafe,

§

impl<'a, G, S, P> Send for ShortestPathBuilder<'a, G, S, P>
where G: Sync,

§

impl<'a, G, S, P> Sync for ShortestPathBuilder<'a, G, S, P>
where G: Sync,

§

impl<'a, G, S, P> Unpin for ShortestPathBuilder<'a, G, S, P>

§

impl<'a, G, S, P> UnwindSafe for ShortestPathBuilder<'a, G, S, P>
where G: RefUnwindSafe,

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, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

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

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

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.