Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
dfs.hh
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2009
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
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#ifndef __GECODE_SEARCH_PAR_DFS_HH__
35#define __GECODE_SEARCH_PAR_DFS_HH__
36
38
39namespace Gecode { namespace Search { namespace Par {
40
42 template<class Tracer>
43 class DFS : public Engine<Tracer> {
44 protected:
45 using Engine<Tracer>::idle;
46 using Engine<Tracer>::busy;
47 using Engine<Tracer>::stop;
48 using Engine<Tracer>::block;
55 using Engine<Tracer>::opt;
66 class Worker : public Engine<Tracer>::Worker {
67 public:
80 Worker(Space* s, DFS& e);
82 DFS& engine(void) const;
84 virtual void run(void);
86 void find(void);
88 void reset(Space* s, unsigned int ngdl);
89 };
90
92 public:
94 Worker* worker(unsigned int i) const;
95
97
98
99 void solution(Space* s);
101
103
104
105 DFS(Space* s, const Options& o);
107 virtual Statistics statistics(void) const;
109 virtual void reset(Space* s);
111 virtual NoGoods& nogoods(void);
113 virtual ~DFS(void);
115 };
116
117}}}
118
120
121#endif
122
123// STATISTICS: search-par
No-goods recorded from restarts.
Definition core.hpp:1590
Search engine options
Definition search.hh:746
Parallel depth-first search worker
Definition dfs.hh:66
Worker(Space *s, DFS &e)
Initialize for space s with engine e.
Definition dfs.hpp:56
void find(void)
Try to find some work.
Definition dfs.hpp:122
DFS & engine(void) const
Provide access to engine.
Definition dfs.hpp:41
virtual void run(void)
Start execution of worker.
Definition dfs.hpp:162
virtual Statistics statistics(void) const
Return statistics.
Definition dfs.hpp:149
void solution(Space *s)
Report solution s.
Definition dfs.hpp:106
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition dfs.hpp:308
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition dfs.hpp:60
Worker * worker(unsigned int i) const
Provide access to worker i.
Definition dfs.hpp:46
Worker ** _worker
Array of worker references.
Definition dfs.hh:91
virtual NoGoods & nogoods(void)
Return no-goods.
Definition dfs.hpp:336
virtual ~DFS(void)
Destructor.
Definition dfs.hpp:359
Support::Mutex m
Mutex for access to worker.
Definition engine.hh:57
Engine & _engine
Reference to engine.
Definition engine.hh:55
Space * cur
Current space being explored.
Definition engine.hh:61
Tracer tracer
Search tracer.
Definition engine.hh:52
unsigned int d
Distance until next clone.
Definition engine.hh:63
bool idle
Whether the worker is idle.
Definition engine.hh:65
Path< Tracer > path
Current path ins search tree.
Definition engine.hh:59
void idle(void)
Report that worker is idle.
Definition engine.hpp:152
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:47
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:151
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Definition engine.hh:169
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:171
void stop(void)
Report that worker has been stopped.
Definition engine.hpp:172
void block(void)
Block all workers.
Definition engine.hpp:73
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition engine.hh:153
Support::Mutex m_search
Mutex for search.
Definition engine.hh:167
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition engine.hh:149
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:116
void busy(void)
Report that worker is busy.
Definition engine.hpp:163
void release(Cmd c)
Release all workers.
Definition engine.hpp:79
bool signal(void) const
Whether search state changed such that signal is needed.
Definition engine.hpp:147
void terminate(void)
For engine to peform thread termination.
Definition engine.hpp:216
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:173
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:52
@ C_WORK
Perform work.
Definition engine.hh:94
@ C_RESET
Perform reset operation.
Definition engine.hh:96
@ C_WAIT
Run into wait lock.
Definition engine.hh:95
Search engine statistics
Definition search.hh:147
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
unsigned long int node
Number of nodes expanded.
Definition search.hh:152
void start(void)
Reset stop information.
Definition worker.hh:74
Worker(void)
Initialize.
Definition worker.hh:70
bool stop(const Options &o)
Check whether engine must be stopped.
Definition worker.hh:79
Computation spaces.
Definition core.hpp:1744
Search engines
Gecode toplevel namespace