Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
101 lines (90 sloc) 3.25 KB
use std::collections::{BTreeSet, BinaryHeap};
use std::iter::FromIterator;
use std::cmp::Ordering;
use bit_set::BitSet;
use slog::Logger;
use objective::*;
use serde_json::to_string as json_string;
pub struct WeightedNode<O: Objective> {
pub weight: f32,
pub node: O::Element,
}
impl<O: Objective> PartialEq for WeightedNode<O> {
fn eq(&self, other: &Self) -> bool {
self.weight == other.weight
}
}
impl<O: Objective> Eq for WeightedNode<O> {}
impl<O: Objective> PartialOrd for WeightedNode<O> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
self.weight.partial_cmp(&other.weight)
}
}
impl<O: Objective> Ord for WeightedNode<O> {
fn cmp(&self, other: &Self) -> Ordering {
self.weight.partial_cmp(&other.weight).unwrap()
}
}
pub fn greedy<O: Objective + Sync>(obj: &O,
k: usize,
log: &Logger)
-> Result<(f32, Vec<O::Element>, O::State), CurvError<O>>
where O::Element: Send + Sync,
O::State: Sync
{
let mut state = O::State::default();
let mut solset = BitSet::new();
fn reheap<O: Objective>(sol: &BitSet,
obj: &O,
state: &O::State,
prior: BinaryHeap<WeightedNode<O>>,
elements: BTreeSet<O::Element>)
-> Result<BinaryHeap<WeightedNode<O>>, CurvError<O>> {
prior.into_iter()
.filter(|ref we| !elements.contains(&we.node))
.map(|we| Ok(we))
.chain(elements.iter().cloned().map(|e| {
let w = obj.delta(e, &sol, &state)?;
Ok(WeightedNode {
node: e,
weight: w,
})
}))
.collect()
}
let elements = BTreeSet::from_iter(obj.elements().into_iter());
debug!(log, "initializing heap");
let mut heap = reheap(&solset,
obj,
&state,
BinaryHeap::with_capacity(elements.len()),
elements)?;
debug!(log, "done initializing heap");
let mut f = 0f32;
let mut sol = Vec::with_capacity(k);
let mut i = 0;
while let Some(top) = heap.pop() {
sol.push(top.node);
solset.insert(top.node.into());
f += top.weight;
debug!(log, "selected element"; "node" => top.node.into(), "objective value" => f);
obj.insert_mut(top.node, &mut state)?;
// NOTE: this assumes a symmetric dependency relationship,
// i.e. v ∈ D(u) ⇐⇒ u ∈ D(v) ∀ u,v ∈ E
heap = reheap(&solset,
obj,
&state,
heap,
obj.depends(top.node, &state)?
.into_iter()
.filter(|&u| !solset.contains(u.into()))
.collect())?;
// can't && i < k in a while let, unfortunately
i += 1;
if i >= k {
break;
}
}
info!(log, "greedy solution"; "f" => f, "sol" => json_string(&sol.iter().map(|x| x.clone().into()).collect::<Vec<usize>>()).unwrap());
Ok((f, sol, state))
}