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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

/**
Defines a search space. A search space is a graph structure (directed or not).
It contains nodes. The initial state is the entry point of the search procedure. 
*/
pub trait SearchSpace<N,B> {
    /**
        returns the initial (or root) node
    */
    fn initial(&mut self) -> N;

    /**
        returns the bound value of the node (i.e. f-cost)
     */
    fn bound(&mut self, node: &N) -> B;
 
    /**
        returns true if and only if the node is goal
     */
    fn goal(&mut self, node: &N) -> bool;
 
    /**
        returns the g-cost of the node
        the h-cost can be computed by substracting the f-cost (SearchSpace.bound) by the g-cost
    */
    fn g_cost(&mut self, n: &N) -> B;

    /**
     called when the algorithm finds a new-best-known solution
     */
    fn handle_new_best(&mut self, node: N) -> N { node }



    // RESTARTING INFORMATION

    /**
     called when the algorithm starts
     */
    fn start_search(&mut self, _msg: String) {}

    /**
     called when the algorithm restarts
     */
    fn restart(&mut self, _msg: String) {}

    /**
     called when the algorithm finishes
     */
    fn stop_search(&mut self, _msg: String) {}


    // GETTING SEARCH INFORMATION

    /**
     displays various statistics about the search (nb nodes, etc.)
     TODO: use export_statistics to get the statistics in the JSON format, and display them
     */
    fn display_statistics(&self) {}

    /**
     registers information about the search statistics in a json file
     */
    fn json_statistics(&self, _json:&mut serde_json::Value) {}

    /**
     * requests log headers (does nothing if there is no logging decorator within the algorithm)
     */
    fn request_log_header(&self, _res:Vec<String>) {}

    /**
     * requests a logging to appear (does nothing if there is no logging decorator within the algorithm)
     */
    fn request_logging(&self, _res:Vec<String>) {}
}

/**
exports a node to a problem solution Sol.
*/
pub trait ToSolution<N,Sol> {
    /**
     constructs a solution from a goal node
     panics if the node is not a goal
    */
    fn solution(&mut self, node: &mut N) -> Sol;
}

/**
Defines a guidance function
*/
pub trait GuidedSpace<N,G> {
    /**
     * returns the guide value of the node
     */
    fn guide(&mut self, node: &N) -> G;
}


/**
    implements a total neighbor expansion (neighbors)
 */
pub trait TotalNeighborGeneration<N> {
    /**
        returns all neighbors of a given node
     */
    fn neighbors(&mut self, node: &mut N) -> Vec<N>;
}


/**
    implements a partial neighbor expansion (next_neighbor)
 */
pub trait PartialNeighborGeneration<N> {
    /**
        returns the next neighbor if it exists, or None
     */
    fn next_neighbor(&mut self, node: &mut N) -> Option<N>;
}


/**
    Allows to identify a node. Useful to implement g-cost-dominance / bucket-lists
    or tabu-search
 */
pub trait Identifiable<N, Id> {
    /**
        returns the ID of the node
     */
    fn id(&self, n: &mut N) -> Id;
}


/**
    Represents a search space where nodes can pareto-dominate some other.
    *i.e.* a node dominantes another if all of its features are better
 */
pub trait ParetoDominanceSpace<N> {
    /**
        returns true if a dominates b
     */
    fn dominates(&self, a:&N, b:&N) -> bool;
}


/**
    Represents a search space which there exists a bound on the distance between the root node and
    any node. This kind of property is frequent in combinatorial branch-and-bounds.
*/
pub trait BoundedDistanceSpace<N> {
    /** maximum distance between the root node and a state */
    fn maximum_root_distance(&self) -> usize;

    /** returns the distance from the root of a given node */
    fn distance_from_root(&self, n:&N) -> usize;

    /** returns the distance from root ratio (distance/distance_max) */
    fn root_distance_ratio(&self, n:&N) -> f64 {
        self.distance_from_root(n) as f64 / self.maximum_root_distance() as f64
    }
}