ff_k_center 1.2.2

A linear-time k-center algorithm with fairness conditions and worst-case guarantees that is very fast in practice. Includes python bindings.
Documentation 
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

use crate::types::PointCount;
use crate::{ClusteringProblem, ColoredMetric, OptionalParameters};

/// Asserts a clustering problem.
/// Checks whether the clustering problem is feasible. If this assertion runs through, the main
/// algorithm will return a feasible clustering.
///
/// # Inputs
/// * a metric space implementing the [ColoredMetric] trait,
/// * a [ClusteringProblem].
///
/// # Panics
/// Panics if one of the following asserts fails:
/// * k must be bigger than 1.
/// * n must be bigger than k.
/// * n must be bigger or equal to k * `privacy_bound`.
/// * for each representative interval the lower limit must be smaller or equal to the upper limit.
/// * the sum of the lower limits must be smaller or equal to k.
/// * the number of points of a specific color must be greater or equal to the lower limit of that
/// color.
/// * k must be smaller or equal to the sum of the upper limits of the representative intervals.
pub fn assert_clustering_problem<M: ColoredMetric>(
    space: &M,
    prob: &ClusteringProblem,
) -> Result<(), String> {
    assert_problem_parameters(prob)?; // first check, whether prob-parameter are consistent within itself (without the space)

    if space.n() < prob.k {
        return Err(format!(
            "We have n < k ({} < {})! We need more points than centers.",
            space.n(),
            prob.k
        ));
    }; // the number of points should not be less than the number of centers

    if space.n() < prob.k * prob.privacy_bound {
        return Err(format!("We have n < k * L ({} < {} * {})! We need enough points so that k center can satisfy the privacy condition.", space.n(), prob.k, prob.privacy_bound));
    };

    let mut number_of_points_of_color: Vec<PointCount> = vec![0; space.gamma()];
    for p in space.point_iter() {
        number_of_points_of_color[space.color(p)] += 1;
    }

    let restricted_colors = if space.gamma() < prob.rep_intervals.len() {
        space.gamma()
    } else {
        prob.rep_intervals.len()
    }; // min{gamma, rep_intervals.len()}

    // check if lower bound can be satisfied
    for (c, color) in number_of_points_of_color
        .iter()
        .enumerate()
        .take(restricted_colors)
    {
        if *color < prob.rep_intervals[c].0 {
            return Err(format!("There are {} points of color {}, but we require a = {} of the centers to be of this color.", number_of_points_of_color[c], c, prob.rep_intervals[c].0));
        };
    }
    for c in restricted_colors..prob.rep_intervals.len() {
        if prob.rep_intervals[c].0 != 0 {
            return Err(format!("We want {} centers of color {}, but there is not a single point of that color. We have gamma = {}.", prob.rep_intervals[c].0, c, space.gamma()));
        };
    }

    // check sum of the upper bounds (min{ left side of interval, number of points }) is not
    // smaller than k
    let mut sum_of_b = 0;
    (0..restricted_colors).for_each(|c| {
        let upper_bound = if prob.rep_intervals[c].1 < number_of_points_of_color[c] {
            prob.rep_intervals[c].1
        } else {
            number_of_points_of_color[c]
        };
        sum_of_b += upper_bound;
    });
    (restricted_colors..space.gamma()).for_each(|c| {
        sum_of_b += number_of_points_of_color[c];
    });
    if sum_of_b < prob.k {
        return Err(format!("The sum of the upper bounds of the representative intervals (or the number of points of that color) is {}, which is smaller than k = {}.", sum_of_b, prob.k));
    };

    Ok(())
}

/// Assertions that does not need the metric space.
pub(crate) fn assert_problem_parameters(prob: &ClusteringProblem) -> Result<(), String> {
    if prob.k < 1 {
        return Err(format!(
            "We have k = {}! There should be at least one center.",
            prob.k
        ));
    }; // we want to allow at least 1 center

    for (c, interval) in prob.rep_intervals.iter().enumerate() {
        if interval.0 > interval.1 {
            return Err(format!("The interval of color {} is ({}, {}). Lower bound cannot be bigger than the upper bound.", c, interval.0, interval.1));
        };
    }

    let mut sum_of_a = 0;

    // check whether the sum of the lower bounds is not bigger than k
    for (a, _) in prob.rep_intervals.iter() {
        sum_of_a += a;
    }
    if sum_of_a > prob.k {
        return Err(format!("The sum of the lower bounds of the representative intervals is {}, which is larger than k = {}.", sum_of_a, prob.k));
    };

    Ok(())
}

/// Assertion for the optional program parameters.
pub(crate) fn assert_optional_parameters(para: &OptionalParameters) -> Result<(), String> {
    if let Some(i) = para.verbose {
        if i > 2 {
            return Err(String::from(
                "The verbose parameter must be 0 (silent), 1 (brief) or 2 (verbose).",
            ));
        }
    };
    if let Some(i) = para.thread_count {
        if i <= 1 {
            return Err(String::from("There need to be at least two threads."));
        }
    };
    Ok(())
}