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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371 | // IAInterface.hpp MeshKit version
#ifndef MESHKIT_IA_INTERFACE_HP
#define MESHKIT_IA_INTERFACE_HP
#include "meshkit/IAVariable.hpp"
#include "meshkit/Types.hpp"
#include "meshkit/Error.hpp"
#include "meshkit/MeshScheme.hpp"
#include "meshkit/ModelEnt.hpp"
#include "moab/Interface.hpp"
#include <set>
#include <vector>
namespace MeshKit {
class IAData;
class IASolution;
/** \class IAInterface IAInterface.hpp "meshkit/IAInterface.hpp"
* \brief The class used in MeshKit for Interval Assignment.
*
* Instances of this class are tools. The problem is to set up and solving the number of mesh edges
* to place on model entities and entity features. When solved, each curve can be meshed
* independently, and treated as fixed when meshing each surface or volume containing it.
* Different mesh schemes have different requirements (constraints), such as a mapped surface
* needs opposite sides to have equal numbers of mesh edges (intervals).
* The number of mesh edges on one curve is a variable; there may be additional variables.
* The goal (objective function) is to have mesh edges close to the user-desired sizes.
*
* Construction of IAInterface does not cause the construction of variables.
* Destruction of IAInterface does destroy the underlying variables.
* IAInterface owns an IAVariable, for creation and deletion.
* But the ModelEnt can request a variable for itself, and lets the interface know when
* it is no longer wanted.
* ModelEnt keeps handles (pointers) to the variables it cares about.
* \nosubgrouping
*/
class IAInterface : public MeshScheme // register it with SchemeFactory
{
public:
/** \name Constructor/destructor
*/
/**@{*/
/** \brief Constructor; model entity can be missing, in which case it's retrieved or created
*
* \param MKCore instance
* \param MEntVector
*/
IAInterface(MKCore *mkcore, const MEntVector &me_vec = MEntVector()) : MeshScheme(mkcore, me_vec){}
/** \brief Destructor, destroys IAVariables
*/
virtual ~IAInterface();
/**@}*/
/** \name Set Up
*/
/**@{*/
/** \name Variables
*/
/**@{*/
/** \brief Create a variable.
* Variables are created before constraints.
* It is OK if a variable is not in any constraint, but constraints are defined by their variables.
* \param ModelEnt* model entity: this variable corresponds to the number of intervals
* on that model entity. If NULL, the variable corresponds to anything else that has
* meaning to the caller, and the caller will have to keep track of the variable
* in order to access its solution value later.
*/
IAVariable *get_variable( ModelEnt* model_entity = NULL, bool create_if_missing = true );
/** \brief Create a variable and assign it a firmness and goal
* \param IAVariable::Firmness The required fidelity of the solution to the goal.
* If HARD, then it is required that the solution equals the goal; goal should be integer.
* If SOFT, usual case, try to get close to the goal.
* If LIMP, we don't care how far the solution is from the goal.
* \param double goal The desired number of intervals for this variable.
* The goal may be non-integer, but we assume the solution must be a natural number,
* i.e. an integer >= 1.
*/
// there is a reason we don't provide default parameters here, don't combine with above version.
IAVariable *create_variable( ModelEnt* model_entity, IAVariable::Firmness set_firmness, double goal_value);
/** \brief Get const_iterators over the variables.
*/
typedef std::vector< IAVariable* > VariableVec;
VariableVec::const_iterator variables_begin() const {return variables.begin();}
VariableVec::const_iterator variables_end() const {return variables.end();}
/** \brief Destroy a variable. If a variable is not explicitly destroyed, it will be
* destroyed on IAInterface tool destruction.
*/
void destroy_variable( IAVariable* ia_variable );
/**@}*/
/** \name Constraints
*/
/**@{*/
/** \brief Containers for variables for specifying constraints.
*/
//typedef std::vector<ModelEnt*> MEVec;
// Types.hpp defines std::vector<ModelEnt*> MeshKit::MEntVector
typedef std::vector<IAVariable*> IAVariableVec;
/** \brief Convert container of ModelEnts to a container of IAVariables.
* MEVec is an indirect way of specifying the model entities's variables.
*/
// convert vector of ModelEntities into vector of IAVariables
IAVariableVec make_constraint_group( const MEntVector &model_entity_vec );
/** \brief Constrain that the sum of the number of intervals
* on one side is equal to the number on the other side. E.g. when mapping a surface,
* the opposite sides require equal intervals.
*/
void constrain_sum_equal( const IAVariableVec &side_one, const IAVariableVec &side_two );
/** \brief Constrain that the sum of the number of intervals is an even number,
* i.e. 2k for some integer k. E.g. for the curves bounding an unstructured quad mesh.
*/
void constrain_sum_even( const IAVariableVec &sum_even_vars );
/** \brief More constraint types may be implemented here.
*/
//... additional constraint types...
/**@}*/
/**@}*/
/** \brief Main function that graph calls. Inherited from MeshScheme.
*/
virtual void setup_this();
/** \name Solve the problem
*/
/**@{*/
/** \brief Main function that graph calls. Inherited from MeshScheme.
* find solution satisfying all the constraints
* assign the solution to the variables
* May be unsuccessful if the problem is over-specified.
* (how can callers detect failure? exception throw? no valid solution value in variables?)
*/
virtual void execute_this();
/**@}*/
/**\brief Get class name */
static const char* name()
{ return "IntervalAssignment"; }
/**\brief Function returning whether this scheme can mesh entities of
* the specified dimension.
*\param dim entity dimension
*/
static bool can_mesh(iBase_EntityType dim)
{ return iBase_VERTEX <= dim && iBase_REGION >= dim; }
/** \brief Function returning whether this scheme can mesh the specified entity
*
* Used by MeshOpFactory to find scheme for an entity.
* \param model_ent ModelEnt being queried
* \return If true, this scheme can mesh the specified ModelEnt
*/
static bool can_mesh(ModelEnt *model_ent)
{ return can_mesh((iBase_EntityType)model_ent->dimension()); }
/**\brief Get list of mesh entity types that can be generated.
*\return array terminated with \c moab::MBMAXTYPE
*/
static const moab::EntityType* output_types();
/** \brief Return the mesh entity types operated on by this scheme
* \return array terminated with \c moab::MBMAXTYPE
*/
virtual const moab::EntityType* mesh_types_arr() const
{ return output_types(); }
/** \brief Print the problem that was defined
*/
void print_problem() const;
/** \brief Destroy all the variables and constraints
*/
void destroy_data();
private:
/** \brief Internal representation of the data specifying the Interval Assignment problem.
*/
// data
VariableVec variables;
typedef std::vector< VariableVec > VariableVecVec;
VariableVecVec sumEqualConstraints1, sumEqualConstraints2; // one for each side
VariableVecVec sumEvenConstraints;
// ... additional types of constraints ...
/** \brief Find the global interface index of the given variable
*/
int variable_to_index(const IAVariable* var) const;
/** \brief Find the ind'th variable.
*/
IAVariable *index_to_variable(int ind) const;
/** \name Subdivide into independent sub-problems
*/
/**@{*/
/** \brief Subdivide the problem into independent subproblems, in the sense that the
* solution to one subproblem is not affected in any way by the solution to another.
* I.e. independent if have no constraints or variables in common.
* A given subproblem is complete, in that it contains all the variables for each of
* its constraints, and also all the constraints for each of its variables.
*/
/** \name Represent a sub-set for a sub-problem
*/
typedef std::set<int> IndexSet;
/** \name Represent a sub-set for a sub-problem, vector for variable or constraint
*/
typedef std::vector< IndexSet > IndexSetVec;
typedef std::vector< int > IndexVec;
typedef std::vector< IndexVec > IndexVecVec;
/** \brief Set = [0,1,...k-1]
*/
void make_set_0_to_nm1( IndexSet &index_set, const size_t k);
/** \brief Vector = [0,1,...k-1]
*/
void make_vec_0_to_nm1( IndexVec &index_vec, const size_t k);
/** \brief Vector = [-1,-1,...-1] of length k
*/
void make_vec_unset( IndexVec &index_vec, const size_t k );
/** \brief Represent the dependency of the problem using indicator sets.
*/
struct VariableConstraintDependencies
{
/** brief
* IndexVecVec constraint_variables the ith constraint_variables are the indices of the variables in the ith constraints.
* IndexVecVec variable_constraints the ith variable_constraints are the indices of the constraints containing the ith variable.
*/
IndexVecVec constraintVariables, variableConstraints;
void print() const; // debug
};
/** \brief Build a representation of the dependency of the problem using indicator sets.
* \param constraintVariables (member) Output.
* \param variableConstraints (member) Output.
*/
void set_variable_constraint_indices(VariableConstraintDependencies &var_con_dep);
/** \brief Underlying workhorse to build a representation of the dependency of the
* problem using indicator sets, for one constraint.
* \param constraintVariables (member) Output.
* \param variableConstraints (member) Output.
* \param int i_start: Input. The following vector of constraints is indexed starting at i_start.
* \param VariableVecVec: Input. Constraints, each entry is a vector specifying one constraint.
*/
void set_variable_constraint_indices( VariableConstraintDependencies &var_con_dep,
const int i_start,
const VariableVecVec &variable_vec_vec );
/** \brief Collections of indicator sets of variables and constraints that
* define a subproblem, or define the global problem, or define the remaining part of
* the global problem
*/
class ProblemSets
{
public:
IndexSet constraintSet, variableSet, hardVariableSet;
IndexVec varMap; // map from local indices to indices in other set, i.e sub->global or global->sub
bool empty() const {return constraintSet.empty() && variableSet.empty();}
// default constructor makes empty sets, with an empty map, suitable for sub_problem initialization
/** \brief Create a subset by chasing variables or constraints. Top of recursion - call this version.
* "this" is the global set.
*/
void find_dependent_set( const VariableConstraintDependencies &var_con_dep, ProblemSets &subsets );
/** \brief
* This is the recursive implementation; call "find_dependent_set" instead.
* Add the variable (index) to the sub-problem, mark it as removed from the larger
* problem, and recursively build the sub-problem by chasing its dependent constraints.
* "this" is the global set.
*/
void find_variable_dependent_set( const int variable_j,
const VariableConstraintDependencies &var_con_dep,
ProblemSets &subsets );
/** \brief
* This is the recursive implementation; call "find_dependent_set" instead.
* Add the constraint (index) to the sub-problem, mark it as removed from the larger
* problem, and recursively build the sub-problem by chasing its variables.
* "this" is the global set.
*/
void find_constraint_dependent_set( const int constraint_i,
const VariableConstraintDependencies &var_con_dep,
ProblemSets &subsets );
void print() const; // debug
};
/** \brief Initialize the global set defining the global problem.
*/
void make_global_set(ProblemSets &problem_sets);
/** \brief Convert a globally-indexed constraint into a locally-indexed constraint
*/
void global_to_sub_side( const VariableVec &global_constraint, IndexVec &global_var_map,
IndexVec &local_constraint, int &rhs ) const;
/** \brief Represent a subproblem, its IAData and its mapping back to the global problem
*/
struct SubProblem<--- 'struct SubProblem' does not have a copy constructor which is recommended since the class contains a pointer to allocated memory.
{
static int max_id;
int id;
IAData *data;
ProblemSets problemSets;
IASolution *solution;
void print() const; // debug
SubProblem();
virtual ~SubProblem();
};
typedef std::vector<SubProblem*> SubProblemVec;
/** \brief Convert set-based definition of problem into an IAData based representation.
*/
void fill_problem( ProblemSets &sub_sets, SubProblem *sub_problem, IndexVec &global_var_map ) const;
/** \brief Build independent subproblems
*/
void subdivide_problem(SubProblemVec &subproblems);
void subdivide_problem_one(std::vector<IAData*> &subproblems); // just make one problem
/**@}*/
/** \brief For a subproblem, find a solution for the number of intervals for each variable.
*/
bool solve_subproblem( SubProblem *subproblem );
/** \brief Assign the found solution to the IAVariables.
*/
void assign_solution( SubProblem *subproblem );
static const bool debugging;
};
} // namespace MeshKit
#endif
/*
todo:
It shouldn't be a singleton, since there are cases I can envision where you'd want a local one.
Since IAInterface is a GraphNode, it will get destructed when the graph goes away.
- tim
On 10/26/2012 05:38 PM, Mitchell, Scott A wrote:
I'm a little confused about mkCore constructing an IAInterface.
How, if at all, is it destructed?
Should there be just one IAInterface, or many?
- Scott
*/
|