1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

use fun::max_prop;
use prelude::*;
use props::{Color, FnProp};
use traverse::*;

pub trait Distances: Incidence {
    fn diameter(&self) -> usize
    where
        Self: VertexList + WithVertexProp<usize> + WithVertexProp<Color>,
    {
        let mut dist = self.default_vertex_prop(0);
        self.vertices()
            .map(|v| {
                dist.set_values(self.vertices(), usize::max_value());
                self.dfs(RecordDistance(&mut dist)).root(v).run();
                max_prop(FnProp(|x| dist[x]), self.vertices()).unwrap()
            })
            .max()
            .unwrap_or(0)
    }
}

impl<G: Incidence> Distances for G {}