dogs 1.3.0

Discrete Optimization Global Search framework. Implements various search algorithms that can be found in combinatorial optimization or heuristic search.
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
132
133
134
135
136
137
138
139
140
141

use std::marker::PhantomData;

use crate::search_space::{SearchSpace, GuidedSpace, TotalNeighborGeneration, PartialNeighborGeneration, Identifiable, ParetoDominanceSpace, ToSolution};
use crate::tree_search::decorators::helper::discrepancy::{DiscrepancyNode, DiscrepancyType};
use crate::search_decorator::SearchSpaceDecorator;

/**
 * Restrics the search tree by the children having positive remaining discrepancies.
 */
#[derive(Debug)]
pub struct LDSDecorator<Tree, D, G, B> {
    s: Tree,
    allowed_discrepancies: f64,
    discrepancy_type: D,
    phantom_g: PhantomData<G>,
    phantom_b: PhantomData<B>
}

impl<N,G,Tree,D,B> GuidedSpace<DiscrepancyNode<N>,G> for LDSDecorator<Tree, D, G, B>
where 
    Tree:GuidedSpace<N,G>
{
    fn guide(&mut self, n: &DiscrepancyNode<N>) -> G { self.s.guide(&n.node) }
}

impl<N, Space, D, G, B> TotalNeighborGeneration<DiscrepancyNode<N>> for LDSDecorator<Space, D, G, B>
where 
    Space: TotalNeighborGeneration<N>+GuidedSpace<N,G>+SearchSpace<N,B>,
    D: DiscrepancyType,
    G: Ord+Into<f64>+From<f64>
{
    fn neighbors(&mut self, n: &mut DiscrepancyNode<N>) -> Vec<DiscrepancyNode<N>> {
        if n.discrepancies > self.allowed_discrepancies {
            return Vec::new();
        }
        let mut tmp:Vec<DiscrepancyNode<N>> = self.discrepancy_type.compute_discrepancies(&mut self.s, n);
        // extracts and filters by discrepancies <= allowed
        let mut res = Vec::new();
        while !tmp.is_empty() {
            let n = tmp.pop().unwrap();
            if n.discrepancies <= self.allowed_discrepancies {
                res.push(n);
            }
        }
        res
    }
}


impl <Space, D, G, B, N, Sol> ToSolution<DiscrepancyNode<N>,Sol> for LDSDecorator<Space, D, G, B>
where
    Space: SearchSpace<N,B>+ToSolution<N,Sol>
{
    fn solution(&mut self, n: &mut DiscrepancyNode<N>) -> Sol { self.s.solution(&mut n.node) }
}


impl<N,Space,D,G,B> SearchSpace<DiscrepancyNode<N>,B> for LDSDecorator<Space, D, G, B>
where Space:SearchSpace<N,B>
{

    fn initial(&mut self) -> DiscrepancyNode<N> {
        DiscrepancyNode {
            node: self.s.initial(),
            discrepancies: 0.
        }
    }

    fn bound(&mut self, n: &DiscrepancyNode<N>) -> B { self.s.bound(&n.node) }

    fn g_cost(&mut self, n: &DiscrepancyNode<N>) -> B { self.s.g_cost(&n.node) }

    fn goal(&mut self, n: &DiscrepancyNode<N>) -> bool { self.s.goal(&n.node) }

    fn restart(&mut self, msg: String) {
        self.s.restart(msg);
    }

    fn handle_new_best(&mut self, n: DiscrepancyNode<N>) -> DiscrepancyNode<N> {
        DiscrepancyNode {
            node: self.s.handle_new_best(n.node),
            discrepancies: n.discrepancies
        }
    }

    fn stop_search(&mut self, _msg: String) {
        self.s.stop_search(_msg);
    }

    fn display_statistics(&self) {
        self.s.display_statistics();
    }

    fn json_statistics(&self, json:&mut serde_json::Value) {
        self.s.json_statistics(json);
    }
}

impl<Space, D, G, B> SearchSpaceDecorator<Space> for LDSDecorator<Space, D, G, B> {
    fn unwrap(&self) -> &Space { &self.s }
}

impl<Space, D, G, B> LDSDecorator<Space, D, G, B> {

    /** builds the decorator around a search space, the number of allowed discrepancies and
    a discrepancy policy */
    pub fn new(s: Space, allowed_discrepancies: f64, d:D) -> Self {
        Self {
            s,
            allowed_discrepancies,
            discrepancy_type: d,
            phantom_g: PhantomData,
            phantom_b: PhantomData
        }
    }
}

impl<N, B, Id, Space, D, G> Identifiable<DiscrepancyNode<N>, Id> for LDSDecorator<Space, D, G, B>
where
    Space: Identifiable<N, Id>,
{
    fn id(&self, n: &mut DiscrepancyNode<N>) -> Id { self.s.id(&mut n.node) }
}

impl<N,Space,D,G,B> ParetoDominanceSpace<DiscrepancyNode<N>> for LDSDecorator<Space, D, G, B>
where Space: ParetoDominanceSpace<N>
{
    fn dominates(&self, a:&DiscrepancyNode<N>, b:&DiscrepancyNode<N>) -> bool {
        self.s.dominates(&a.node,&b.node)
    }
}


impl<N,Tree,D,G,B> PartialNeighborGeneration<DiscrepancyNode<N>> for LDSDecorator<Tree, D, G, B>
where
    Tree: PartialNeighborGeneration<N>
{
    fn next_neighbor(&mut self, _node: &mut DiscrepancyNode<N>) -> Option<DiscrepancyNode<N>> {
        panic!("not implemented");
    }
}