Generated on for Gecode by doxygen 1.17.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.dev>
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.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#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 unsigned int index;
82 Worker(Space* s, DFS& e, unsigned int index);
84 DFS& engine(void) const;
86 virtual void run(void);
88 bool find(void);
90 void reset(Space* s, unsigned int ngdl);
92 bool owns_work(void) const;
93 };
94
96 public:
98 Worker* worker(unsigned int i) const;
99
101
102
103 void solution(Space* s);
105
107
108
109 DFS(Space* s, const Options& o);
111 virtual Statistics statistics(void) const;
113 virtual void reset(Space* s);
115 virtual NoGoods& nogoods(void);
117 virtual ~DFS(void);
119 };
120
121}}}
122
124
125#endif
126
127// STATISTICS: search-par
No-goods recorded from restarts.
Definition core.hpp:1606
Search engine options
Definition search.hh:848
Parallel depth-first search worker
Definition dfs.hh:66
unsigned int index
Fixed worker index.
Definition dfs.hh:80
Worker(Space *s, DFS &e, unsigned int index)
Initialize for space s with engine e.
Definition dfs.hpp:56
bool owns_work(void) const
Whether this worker currently owns local search.
Definition dfs.hpp:107
bool find(void)
Try to find some work.
Definition dfs.hpp:133
DFS & engine(void) const
Provide access to engine.
Definition dfs.hpp:41
virtual void run(void)
Start execution of worker.
Definition dfs.hpp:175
virtual Statistics statistics(void) const
Return statistics.
Definition dfs.hpp:162
void solution(Space *s)
Report solution s.
Definition dfs.hpp:117
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition dfs.hpp:335
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:95
virtual NoGoods & nogoods(void)
Return no-goods.
Definition dfs.hpp:364
virtual ~DFS(void)
Destructor.
Definition dfs.hpp:387
Support::Mutex m
Mutex for access to worker.
Definition engine.hh:63
Engine & _engine
Reference to engine.
Definition engine.hh:61
Space * cur
Current space being explored.
Definition engine.hh:67
Tracer tracer
Search tracer.
Definition engine.hh:58
unsigned int d
Distance until next clone.
Definition engine.hh:69
bool idle
Whether the worker is idle.
Definition engine.hh:71
Path< Tracer > path
Current path ins search tree.
Definition engine.hh:65
void idle(void)
Report that worker is idle.
Definition engine.hpp:358
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:51
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:220
Support::Event e_search
Event for search (solution found, no more solutions, search stopped).
Definition engine.hh:238
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:240
void block(void)
Block all workers.
Definition engine.hpp:77
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition engine.hh:222
Support::Mutex m_search
Mutex for search.
Definition engine.hh:236
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition engine.hh:218
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:123
void busy(void)
Report that worker is busy.
Definition engine.hpp:369
void release(Cmd c)
Release all workers.
Definition engine.hpp:83
bool signal(void) const
Whether search state changed such that signal is needed.
Definition engine.hpp:352
void stop(unsigned long long int r)
Report that a worker was stopped during call r of next().
Definition engine.hpp:384
void terminate(void)
For engine to perform thread termination.
Definition engine.hpp:443
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:242
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:56
@ C_WORK
Perform work.
Definition engine.hh:163
@ C_RESET
Perform reset operation.
Definition engine.hh:165
@ C_WAIT
Run into wait lock.
Definition engine.hh:164
Search engine statistics
Definition search.hh:155
unsigned long long int fail
Number of failed nodes in search tree.
Definition search.hh:158
unsigned long long int node
Number of nodes expanded.
Definition search.hh:160
void start(void)
Reset stop information.
Definition worker.hh:76
Worker(void)
Initialize.
Definition worker.hh:72
bool stop(const Options &o)
Check whether engine must be stopped.
Definition worker.hh:81
Computation spaces.
Definition core.hpp:1787
Search engines
Gecode toplevel namespace