-
Notifications
You must be signed in to change notification settings - Fork 297
/
NBMatching.mo
408 lines (377 loc) · 16.2 KB
/
NBMatching.mo
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
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
/*
* This file is part of OpenModelica.
*
* Copyright (c) 1998-2020, Open Source Modelica Consortium (OSMC),
* c/o Linköpings universitet, Department of Computer and Information Science,
* SE-58183 Linköping, Sweden.
*
* All rights reserved.
*
* THIS PROGRAM IS PROVIDED UNDER THE TERMS OF GPL VERSION 3 LICENSE OR
* THIS OSMC PUBLIC LICENSE (OSMC-PL) VERSION 1.2.
* ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS PROGRAM CONSTITUTES
* RECIPIENT'S ACCEPTANCE OF THE OSMC PUBLIC LICENSE OR THE GPL VERSION 3,
* ACCORDING TO RECIPIENTS CHOICE.
*
* The OpenModelica software and the Open Source Modelica
* Consortium (OSMC) Public License (OSMC-PL) are obtained
* from OSMC, either from the above address,
* from the URLs: http://www.ida.liu.se/projects/OpenModelica or
* http://www.openmodelica.org, and in the OpenModelica distribution.
* GNU version 3 is obtained from: http://www.gnu.org/copyleft/gpl.html.
*
* This program is distributed WITHOUT ANY WARRANTY; without
* even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE, EXCEPT AS EXPRESSLY SET FORTH
* IN THE BY RECIPIENT SELECTED SUBSIDIARY LICENSE CONDITIONS OF OSMC-PL.
*
* See the full OSMC Public License conditions for more details.
*
*/
encapsulated uniontype NBMatching
"file: NBMatching.mo
package: NBMatching
description: This file contains the functions which perform the matching process;
"
// self import
import Matching = NBMatching;
import GCExt;
protected
// NF import
import NFFlatten.FunctionTree;
import Variable = NFVariable;
// NB import
import Adjacency = NBAdjacency;
import NBEquation.{Equation, EqData, EquationPointer, EquationPointers};
import Module = NBModule;
import ResolveSingularities = NBResolveSingularities;
import System = NBSystem;
import BVariable = NBVariable;
import NBVariable.{VarData, VariablePointer, VariablePointers};
// OB import
import BackendDAEEXT;
// Util import
import BackendUtil = NBBackendUtil;
import Slice = NBSlice;
import NBSlice.IntLst;
import StringUtil;
public
// =======================================
// MATCHING
// =======================================
record MATCHING
array<Integer> var_to_eqn;
array<Integer> eqn_to_var;
end MATCHING;
constant Matching EMPTY_MATCHING = MATCHING(listArray({}), listArray({}));
function toString
input Matching matching;
input output String str = "";
algorithm
str := StringUtil.headline_2(str + "Scalar Matching") + "\n";
str := str + toStringSingle(matching.var_to_eqn, false) + "\n";
str := str + toStringSingle(matching.eqn_to_var, true) + "\n";
end toString;
function regular
"author: kabdelhak
Regular matching algorithm for bipartite graphs by Constantinos C. Pantelides.
First published in doi:10.1137/0909014"
input output Matching matching;
input Adjacency.Matrix adj;
input Boolean transposed = false "transpose matching if true";
input Boolean partially = false "do not fail on singular systems and return partial matching if true";
input Boolean clear = true "start from scratch if true";
protected
list<list<Integer>> marked_eqns;
algorithm
(matching, marked_eqns, _, _) := continue_(matching, adj, transposed, clear);
if not partially and not listEmpty(List.flatten(marked_eqns)) then
Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed because the system is structurally singular."});
fail();
end if;
end regular;
function singular
"author: kabdelhak
Matching algorithm for bipartite graphs by Constantinos C. Pantelides.
First published in doi:10.1137/0909014
In the case of singular systems in tries to resolve it by applying index reduction
using the dummy derivative method by Sven E. Mattsson and Gustaf Söderlind
First published in doi:10.1137/0914043
algorithm:
1. apply pantelides but carry list of singular markings (eqs)
whenever singular - add all current marks to singular markings
2. if done and not everything is matched -> index reduction / balance initialization
3. restart matching if step 2. changed the system
"
input output Matching matching;
input output Adjacency.Matrix adj;
input output VariablePointers vars;
input output EquationPointers eqns;
input output FunctionTree funcTree;
input output VarData varData;
input output EqData eqData;
input System.SystemType systemType;
input Boolean transposed = false "transpose matching if true";
input Boolean partially = false "do not resolve singular systems and return partial matching if true";
input Boolean clear = true "start from scratch if true";
protected
list<list<Integer>> marked_eqns;
Option<Adjacency.Mapping> mapping;
Adjacency.MatrixStrictness matrixStrictness;
Boolean changed;
algorithm
// 1. match the system
try
(matching, marked_eqns, mapping, matrixStrictness) := continue_(matching, adj, transposed, clear);
else
Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed to match system:\n"
+ VariablePointers.toString(vars, "system vars") + "\n"
+ EquationPointers.toString(eqns, "system eqns") + "\n"
+ Adjacency.Matrix.toString(adj)});
fail();
end try;
// 2. Resolve singular systems if necessary
changed := match systemType
case NBSystem.SystemType.INI algorithm
// ####### BALANCE INITIALIZATION #######
(vars, eqns, varData, eqData, funcTree, changed) := ResolveSingularities.balanceInitialization(vars, eqns, varData, eqData, funcTree, adj, matching, mapping);
then changed;
else algorithm
// ####### INDEX REDUCTION ######
// for now no index reduction
(vars, eqns, varData, eqData, funcTree, changed) := ResolveSingularities.noIndexReduction(vars, eqns, varData, eqData, funcTree, adj, matching, mapping);
then changed;
end match;
// 3. Recompute adjacency and restart matching if something changed in step 2.
if changed then
// ToDo: keep more of old information by only updating changed stuff
adj := Adjacency.Matrix.create(vars, eqns, matrixStrictness);
(matching, adj, vars, eqns, funcTree, varData, eqData) := singular(EMPTY_MATCHING, adj, vars, eqns, funcTree, varData, eqData, systemType, false, true);
end if;
end singular;
function continue_
input output Matching matching;
input Adjacency.Matrix adj;
input Boolean transposed;
input Boolean clear;
output list<list<Integer>> marked_eqns;
output Option<Adjacency.Mapping> mapping;
output Adjacency.MatrixStrictness matrixStrictness;
protected
array<Integer> var_to_eqn, eqn_to_var;
algorithm
// 1. Match the system
(matching, marked_eqns, mapping, matrixStrictness) := match adj
// PSEUDO ARRAY
case Adjacency.Matrix.PSEUDO_ARRAY_ADJACENCY_MATRIX() algorithm
(var_to_eqn, eqn_to_var) := getAssignments(matching, adj.m, adj.mT);
(var_to_eqn, eqn_to_var, marked_eqns) := PFPlusExternal(adj.m, var_to_eqn, eqn_to_var, clear);
matching := MATCHING(var_to_eqn, eqn_to_var);
then (matching, marked_eqns, SOME(adj.mapping), adj.st);
// EMPTY
case Adjacency.Matrix.EMPTY_ADJACENCY_MATRIX()
then (EMPTY_MATCHING, {}, NONE(), NBAdjacency.MatrixStrictness.FULL);
// FAIL
else algorithm
Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed."});
then fail();
end match;
end continue_;
function getAssignments
"expands the assignments with -1 if needed"
input Matching matching;
input array<list<Integer>> m;
input array<list<Integer>> mT;
output array<Integer> var_to_eqn;
output array<Integer> eqn_to_var;
protected
Integer nVars = arrayLength(mT);
Integer nEqns = arrayLength(m);
algorithm
var_to_eqn := Array.expandToSize(nVars, matching.var_to_eqn, -1);
eqn_to_var := Array.expandToSize(nEqns, matching.eqn_to_var, -1);
end getAssignments;
function getMatches
input Matching matching;
input Option<Adjacency.Mapping> mapping_opt;
input VariablePointers variables;
input EquationPointers equations;
output list<Slice<VariablePointer>> matched_vars = {}, unmatched_vars = {};
output list<Slice<EquationPointer>> matched_eqns = {}, unmatched_eqns = {};
protected
Adjacency.Mapping mapping;
UnorderedMap<VariablePointer, IntLst> var_map_matched, var_map_unmatched;
UnorderedMap<EquationPointer, IntLst> eqn_map_matched, eqn_map_unmatched;
Pointer<Variable> arr_var;
Pointer<Equation> arr_eqn;
Integer start_idx;
algorithm
// pseudo array case
if isSome(mapping_opt) then
mapping := Util.getOption(mapping_opt);
var_map_matched := UnorderedMap.new<IntLst>(BVariable.hash, BVariable.equalName);
var_map_unmatched := UnorderedMap.new<IntLst>(BVariable.hash, BVariable.equalName);
eqn_map_matched := UnorderedMap.new<IntLst>(Equation.hash, Equation.equalName);
eqn_map_unmatched := UnorderedMap.new<IntLst>(Equation.hash, Equation.equalName);
// check if variables are matched and sort them accordingly
for var in 1:arrayLength(matching.var_to_eqn) loop
arr_var := ExpandableArray.get(mapping.var_StA[var], variables.varArr);
(start_idx, _) := mapping.var_AtS[mapping.var_StA[var]];
if matching.var_to_eqn[var] > 0 then
Slice.addToSliceMap(arr_var, (var - start_idx), var_map_matched);
else
Slice.addToSliceMap(arr_var, (var - start_idx), var_map_unmatched);
end if;
end for;
// check if equations are matched and sort them accordingly
for eqn in 1:arrayLength(matching.eqn_to_var) loop
arr_eqn := ExpandableArray.get(mapping.eqn_StA[eqn], equations.eqArr);
(start_idx, _) := mapping.eqn_AtS[mapping.eqn_StA[eqn]];
if matching.eqn_to_var[eqn] > 0 then
Slice.addToSliceMap(arr_eqn, (eqn - start_idx), eqn_map_matched);
else
Slice.addToSliceMap(arr_eqn, (eqn - start_idx), eqn_map_unmatched);
end if;
end for;
// get the slice lists while sorting indices and simplifying whole slices to {}
matched_vars := list(Slice.simplify(slice, BVariable.size) for slice in Slice.fromMap(var_map_matched));
unmatched_vars := list(Slice.simplify(slice, BVariable.size) for slice in Slice.fromMap(var_map_unmatched));
matched_eqns := list(Slice.simplify(slice, Equation.size) for slice in Slice.fromMap(eqn_map_matched));
unmatched_eqns := list(Slice.simplify(slice, Equation.size) for slice in Slice.fromMap(eqn_map_unmatched));
else
// check if variables are matched and sort them accordingly
for var in 1:arrayLength(matching.var_to_eqn) loop
if matching.var_to_eqn[var] > 0 then
matched_vars := Slice.SLICE(ExpandableArray.get(var, variables.varArr),{}) :: matched_vars;
else
unmatched_vars := Slice.SLICE(ExpandableArray.get(var, variables.varArr),{}) :: unmatched_vars;
end if;
end for;
// check if equations are matched and sort them accordingly
for eqn in 1:arrayLength(matching.eqn_to_var) loop
if matching.eqn_to_var[eqn] > 0 then
matched_eqns := Slice.SLICE(ExpandableArray.get(eqn, equations.eqArr),{}) :: matched_eqns;
else
unmatched_eqns := Slice.SLICE(ExpandableArray.get(eqn, equations.eqArr),{}) :: unmatched_eqns;
end if;
end for;
end if;
end getMatches;
protected
function toStringSingle
input array<Integer> mapping;
input Boolean inverse;
output String str;
protected
String head = if inverse then "equation to variable" else "variable to equation";
String from = if inverse then "eqn" else "var";
String to = if inverse then "var" else "eqn";
algorithm
str := StringUtil.headline_4(head);
for i in 1:arrayLength(mapping) loop
str := str + "\t" + from + " " + intString(i) + " --> " + to + " " + intString(mapping[i]) + "\n";
end for;
end toStringSingle;
// ######################################
// SCALAR MATCHING
// ######################################
function scalarMatching
input array<list<Integer>> m;
input array<list<Integer>> mT;
input Boolean transposed = false "transpose matching if true";
input Boolean partially = false "do not fail on singular systems and return partial matching if true";
output Matching matching;
// this needs partially = true to get computed. Otherwise it fails on singular systems
output list<list<Integer>> marked_eqns = {} "marked equations for index reduction in the case of a singular system";
protected
Integer nVars = arrayLength(mT), nEqns = arrayLength(m);
array<Integer> var_to_eqn;
array<Integer> eqn_to_var;
array<Boolean> var_marks;
array<Boolean> eqn_marks;
Boolean pathFound;
algorithm
var_to_eqn := arrayCreate(nVars, -1);
// loop over all equations and try to find an augmenting path
// to match each uniquely to a variable
for eqn in 1:nEqns loop
var_marks := arrayCreate(nVars, false);
eqn_marks := arrayCreate(nEqns, false);
(var_to_eqn, var_marks, eqn_marks, pathFound) := augmentPath(eqn, m, mT, var_to_eqn, var_marks, eqn_marks);
// if it is not possible index reduction needs to be applied
if not pathFound then
if not partially then
Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed because the system is structurally singular. Index Reduction is not yet supported"});
elseif transposed then
// if transposed the variable marks represent equations
marked_eqns := BackendUtil.findTrueIndices(var_marks) :: marked_eqns;
else
marked_eqns := BackendUtil.findTrueIndices(eqn_marks) :: marked_eqns;
end if;
end if;
end for;
// create inverse matching
eqn_to_var := arrayCreate(nEqns, -1);
for var in 1:nVars loop
if var_to_eqn[var] > 0 then
eqn_to_var[var_to_eqn[var]] := var;
end if;
end for;
// free auxiliary arrays
if nEqns > 0 then
GCExt.free(var_marks);
GCExt.free(eqn_marks);
end if;
// create the matching structure
matching := if transposed then MATCHING(eqn_to_var, var_to_eqn) else MATCHING(var_to_eqn, eqn_to_var);
end scalarMatching;
function augmentPath
input Integer eqn;
input array<list<Integer>> m;
input array<list<Integer>> mT;
input output array<Integer> var_to_eqn;
input output array<Boolean> var_marks;
input output array<Boolean> eqn_marks;
output Boolean pathFound = false;
algorithm
eqn_marks[eqn] := true;
// loop over each edge and try to find an unmatched variable
for var in m[eqn] loop
if var_to_eqn[var] <= 0 then
pathFound := true;
var_to_eqn[var] := eqn;
return;
end if;
end for;
// if no umatched variable can be found, loop over all edges again
// and try to recursively revoke an old matching decision
for var in m[eqn] loop
if not var_marks[var] then
var_marks[var] := true;
// recursive call
(var_to_eqn, var_marks, eqn_marks, pathFound) := augmentPath(var_to_eqn[var], m, mT, var_to_eqn, var_marks, eqn_marks);
if pathFound then
var_to_eqn[var] := eqn;
return;
end if;
end if;
end for;
end augmentPath;
function PFPlusExternal
input array<list<Integer>> m;
input output array<Integer> ass1;
input output array<Integer> ass2;
input Boolean clear;
// this needs partially = true to get computed. Otherwise it fails on singular systems
output list<list<Integer>> marked_eqns = {} "marked equations for index reduction in the case of a singular system";
protected
Integer n1 = arrayLength(ass1), n2 = arrayLength(ass2), nonZero = BackendUtil.countElem(m);
Integer cheap = 0, algIndx = 5 "PFPlusExternal index";
algorithm
BackendDAEEXT.setAssignment(n2, n1, ass2, ass1);
BackendDAEEXT.setAdjacencyMatrix(n1, n2, nonZero, m);
BackendDAEEXT.matching(n1, n2, algIndx, cheap, 1.0, if clear then 1 else 0);
BackendDAEEXT.getAssignment(ass2, ass1);
end PFPlusExternal;
annotation(__OpenModelica_Interface="backend");
end NBMatching;