Generated on for Gecode by doxygen 1.18.0
frontier.hh
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34
35#ifndef GECODE_SEARCH_PAR_FRONTIER_HH
36#define GECODE_SEARCH_PAR_FRONTIER_HH
37
38#include <gecode/search.hh>
41#include <exception>
42
43#if defined(GECODE_HAS_EXPERIMENTAL) && defined(GECODE_HAS_THREADS)
44namespace Gecode { namespace Search { namespace Par {
45
53 class Frontier : public Search::Engine {
54 protected:
56 class Task {
57 public:
61 unsigned long int depth;
63 unsigned long long int revision;
65 bool counted;
67 Task(void) : depth(0), revision(0), counted(false) {}
68 };
69
72 Frontier& engine;
74 unsigned int id;
75 public:
79 Runner(Frontier& e, unsigned int i);
81 void run(void) override;
83 Support::Terminator* terminator(void) const override;
85 void terminated(void) override;
86 };
87
94 std::unique_ptr<Space> solution;
96 unsigned long long int order;
100 unsigned int n_pending;
110 unsigned int active;
114 std::exception_ptr error;
115
117
118
119 virtual bool open(void) const = 0;
121 virtual Entry select(void) = 0;
123 virtual void submit(const Entry& e, bool leased) = 0;
125 virtual bool advance(void) = 0;
127 virtual void clear(void) = 0;
129 virtual void started(const Space& r);
131
132 static const unsigned int max_batch = 8;
134 unsigned int batch;
136 bool keyed;
137
139 Frontier(const Options& o);
141 void initialize(Space* s, bool clone);
143 void push(Task* t);
145 void terminate(void);
147 void publish(Space* s, std::int64_t b);
149 void launch(void);
151 void wake(void);
153 bool enabled(unsigned int id);
155 void work(unsigned int id);
156 public:
158 ~Frontier(void) override;
160 Space* next(void) override;
162 Search::Statistics statistics(void) const override;
164 bool stopped(void) const override;
166 bool limited(void) const override;
168 void constrain(const Space& s) override;
170 void reset(Space* s) override;
171 };
172
173}}}
174#endif
175#endif
176
177// STATISTICS: search-par
Search engine implementation interface
Definition search.hh:1063
Open node of a heuristic search engine.
Definition heuristic.hh:53
Guidance for heuristic search engines (experimental).
Definition search.hh:1259
Best solution found so far.
Definition heuristic.hh:87
Search engine options
Definition search.hh:848
Thread running a worker.
Definition frontier.hh:70
Support::Terminator * terminator(void) const override
Return terminator.
void terminated(void) override
Signal termination.
void run(void) override
Run worker.
Support::Event wake
Events for waking up and for termination.
Definition frontier.hh:77
Runner(Frontier &e, unsigned int i)
Initialize.
Node leased by a worker, or partially expanded node.
Definition frontier.hh:56
unsigned long int depth
Depth of the node.
Definition frontier.hh:61
unsigned long long int revision
Incumbent revision the node is constrained with.
Definition frontier.hh:63
bool counted
Whether the node has been counted.
Definition frontier.hh:65
Seq::ChoiceExpansion expansion
The node with its remaining alternatives.
Definition frontier.hh:59
bool stopped(void) const override
Whether search has been stopped.
~Frontier(void) override
Destructor.
std::exception_ptr error
First exception thrown by a worker.
Definition frontier.hh:114
void reset(Space *s) override
Reset engine to restart at space s.
void wake(void)
Wake up all workers.
virtual Entry select(void)=0
Remove and return the next open node.
void work(unsigned int id)
Run worker id.
Support::Event changed
Signalled when search is idle.
Definition frontier.hh:106
unsigned long long int order
Number of created entries.
Definition frontier.hh:96
Space * next(void) override
Return next better solution (nullptr if none or stopped).
void constrain(const Space &s) override
Constrain future solutions to be better than s.
void publish(Space *s, std::int64_t b)
Make s with bound b the incumbent, if it improves.
Search::Statistics stat
Statistics.
Definition frontier.hh:108
Options opt
Search options.
Definition frontier.hh:88
std::unique_ptr< Space > solution
Solution to be returned by next().
Definition frontier.hh:94
Support::Mutex mutex
Mutex protecting all data.
Definition frontier.hh:104
void terminate(void)
Stop all workers (must be called by subclass destructors).
bool enabled(unsigned int id)
Whether worker id is currently enabled.
bool keyed
Whether to compute dominance keys.
Definition frontier.hh:136
Runner ** runners
The threads (allocated on first next()).
Definition frontier.hh:102
HeuristicGuidance guidance
Guidance.
Definition frontier.hh:90
virtual bool open(void) const =0
Whether there are open nodes.
void initialize(Space *s, bool clone)
Start search from root s.
Support::DynamicQueue< Task *, Heap > pending
Partially expanded nodes.
Definition frontier.hh:98
virtual void clear(void)=0
Delete all open nodes.
unsigned int batch
Number of children a worker collects before submitting.
Definition frontier.hh:134
void push(Task *t)
Add pending task t.
void launch(void)
Start the threads.
virtual bool advance(void)=0
Called when all work is done, return whether there is new work.
Search::Statistics statistics(void) const override
Return statistics.
virtual void submit(const Entry &e, bool leased)=0
Add child e, or delete it; leased tells whether its parent is still leased.
bool limited(void) const override
Whether search stopped at the width or frontier limit.
bool running
Whether search is running, being shut down, stopped, or limited.
Definition frontier.hh:112
unsigned int n_pending
Number of partially expanded nodes.
Definition frontier.hh:100
unsigned int active
Number of workers holding a task.
Definition frontier.hh:110
Incumbent best
Best solution so far.
Definition frontier.hh:92
static const unsigned int max_batch
Maximal number of children a worker collects before submitting.
Definition frontier.hh:132
virtual void started(const Space &r)
Called with the root r when search starts.
Frontier(const Options &o)
Initialize with options o.
Node whose alternatives are expanded one at a time.
Search engine statistics
Definition search.hh:155
Computation spaces.
Definition core.hpp:1787
Queue with arbitrary number of elements.
An event for synchronization.
Definition thread.hpp:138
A mutex for mutual exclausion among several threads.
Definition thread.hpp:78
An interface for objects that can be run by a thread.
Definition thread.hpp:181
An interface for objects that can be called after a thread has terminated (after running the thread's...
Definition thread.hpp:168
Search engines
Gecode toplevel namespace