competitive::graph

Trait ShortestPathExt

Source 
pub trait ShortestPathExt: GraphBase {
    // Provided methods
    fn bfs_distance_ss<'a, S, M>(
        &self,
        source: Self::VIndex,
        weight: &'a M,
    ) -> <Self as VertexMap<S::T>>::Vmap
       where Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
             S: ShortestPathSemiRing { ... }
    fn bfs_distance_ms<'a, S, M, I>(
        &self,
        sources: I,
        weight: &'a M,
    ) -> <Self as VertexMap<S::T>>::Vmap
       where Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
             S: ShortestPathSemiRing,
             I: IntoIterator<Item = Self::VIndex> { ... }
    fn dijkstra_ss<'a, S, M>(
        &self,
        source: Self::VIndex,
        weight: &'a M,
    ) -> <Self as VertexMap<S::T>>::Vmap
       where Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
             S: ShortestPathSemiRing { ... }
    fn dijkstra_ms<'a, S, M, I>(
        &self,
        sources: I,
        weight: &'a M,
    ) -> <Self as VertexMap<S::T>>::Vmap
       where Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
             S: ShortestPathSemiRing,
             I: IntoIterator<Item = Self::VIndex> { ... }
    fn bellman_ford_ss<'a, S, M>(
        &self,
        source: Self::VIndex,
        weight: &'a M,
        check: bool,
    ) -> Option<<Self as VertexMap<S::T>>::Vmap>
       where Self: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize,
             S: ShortestPathSemiRing { ... }
    fn bellman_ford_ms<'a, S, M, I>(
        &self,
        sources: I,
        weight: &'a M,
        check: bool,
    ) -> Option<<Self as VertexMap<S::T>>::Vmap>
       where Self: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize,
             S: ShortestPathSemiRing,
             I: IntoIterator<Item = Self::VIndex> { ... }
    fn warshall_floyd_ap<'a, S, M>(
        &self,
        weight: &'a M,
    ) -> <Self as VertexMap<<Self as VertexMap<S::T>>::Vmap>>::Vmap
       where Self: Vertices + VertexMap<S::T> + VertexMap<<Self as VertexMap<S::T>>::Vmap> + AdjacencyView<'a, M, S::T>,
             <Self as VertexMap<S::T>>::Vmap: Clone,
             S: ShortestPathSemiRing { ... }
}

Provided Methods§

Source

fn bfs_distance_ss<'a, S, M>( &self, source: Self::VIndex, weight: &'a M, ) -> <Self as VertexMap<S::T>>::Vmap
where Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>, S: ShortestPathSemiRing,

Source

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

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 123)
114    fn bfs_distance_ss<'a, S, M>(
115        &self,
116        source: Self::VIndex,
117        weight: &'a M,
118    ) -> <Self as VertexMap<S::T>>::Vmap
119    where
120        Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
121        S: ShortestPathSemiRing,
122    {
123        self.bfs_distance_ms::<S, M, _>(once(source), weight)
124    }
Source

fn dijkstra_ss<'a, S, M>( &self, source: Self::VIndex, weight: &'a M, ) -> <Self as VertexMap<S::T>>::Vmap
where Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>, S: ShortestPathSemiRing,

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

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

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 167)
158    fn dijkstra_ss<'a, S, M>(
159        &self,
160        source: Self::VIndex,
161        weight: &'a M,
162    ) -> <Self as VertexMap<S::T>>::Vmap
163    where
164        Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
165        S: ShortestPathSemiRing,
166    {
167        self.dijkstra_ms::<S, M, _>(once(source), weight)
168    }
Source

fn bellman_ford_ss<'a, S, M>( &self, source: Self::VIndex, weight: &'a M, check: bool, ) -> Option<<Self as VertexMap<S::T>>::Vmap>
where Self: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize, S: ShortestPathSemiRing,

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_1_b.rs (line 14)
9pub fn grl_1_b(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, i64>::new(vs, es));
13    let cost =
14        graph.bellman_ford_ss::<OptionSp<AdditiveOperation<_>>, _>(r, &|eid| Some(d[eid]), true);
15    if let Some(cost) = cost {
16        for u in graph.vertices() {
17            match cost[u] {
18                Some(d) => writeln!(writer, "{}", d).ok(),
19                None => writeln!(writer, "INF").ok(),
20            };
21        }
22    } else {
23        writeln!(writer, "NEGATIVE CYCLE").ok();
24    }
25}
Source

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

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 206)
196    fn bellman_ford_ss<'a, S, M>(
197        &self,
198        source: Self::VIndex,
199        weight: &'a M,
200        check: bool,
201    ) -> Option<<Self as VertexMap<S::T>>::Vmap>
202    where
203        Self: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize,
204        S: ShortestPathSemiRing,
205    {
206        self.bellman_ford_ms::<S, M, _>(once(source), weight, check)
207    }
Source

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

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_1_c.rs (line 15)
10pub fn grl_1_c(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, vs, es, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
14    let cost = graph
15        .warshall_floyd_ap::<OptionSp<AdditiveOperation<_>>, _>(&|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}

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§

Source§

impl<G> ShortestPathExt for G
where G: GraphBase,