OMCompiler/Compiler/NBackEnd/Modules/1_Main/NBMatching.mo
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * This file is part of OpenModelica. | ||
| 3 | * | ||
| 4 | * Copyright (c) 1998-2026, Open Source Modelica Consortium (OSMC), | ||
| 5 | * c/o Linköpings universitet, Department of Computer and Information Science, | ||
| 6 | * SE-58183 Linköping, Sweden. | ||
| 7 | * | ||
| 8 | * All rights reserved. | ||
| 9 | * | ||
| 10 | * THIS PROGRAM IS PROVIDED UNDER THE TERMS OF AGPL VERSION 3 LICENSE OR | ||
| 11 | * THIS OSMC PUBLIC LICENSE (OSMC-PL) VERSION 1.8. | ||
| 12 | * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS PROGRAM CONSTITUTES | ||
| 13 | * RECIPIENT'S ACCEPTANCE OF THE OSMC PUBLIC LICENSE OR THE GNU AGPL | ||
| 14 | * VERSION 3, ACCORDING TO RECIPIENTS CHOICE. | ||
| 15 | * | ||
| 16 | * The OpenModelica software and the OSMC (Open Source Modelica Consortium) | ||
| 17 | * Public License (OSMC-PL) are obtained from OSMC, either from the above | ||
| 18 | * address, from the URLs: | ||
| 19 | * http://www.openmodelica.org or | ||
| 20 | * https://github.com/OpenModelica/ or | ||
| 21 | * http://www.ida.liu.se/projects/OpenModelica, | ||
| 22 | * and in the OpenModelica distribution. | ||
| 23 | * | ||
| 24 | * GNU AGPL version 3 is obtained from: | ||
| 25 | * https://www.gnu.org/licenses/licenses.html#GPL | ||
| 26 | * | ||
| 27 | * This program is distributed WITHOUT ANY WARRANTY; without | ||
| 28 | * even the implied warranty of MERCHANTABILITY or FITNESS | ||
| 29 | * FOR A PARTICULAR PURPOSE, EXCEPT AS EXPRESSLY SET FORTH | ||
| 30 | * IN THE BY RECIPIENT SELECTED SUBSIDIARY LICENSE CONDITIONS OF OSMC-PL. | ||
| 31 | * | ||
| 32 | * See the full OSMC Public License conditions for more details. | ||
| 33 | * | ||
| 34 | */ | ||
| 35 | |||
| 36 | encapsulated uniontype NBMatching | ||
| 37 | "file: NBMatching.mo | ||
| 38 | package: NBMatching | ||
| 39 | description: This file contains the functions which perform the matching process; | ||
| 40 | " | ||
| 41 | // self import | ||
| 42 | import Matching = NBMatching; | ||
| 43 | import GCExt; | ||
| 44 | |||
| 45 | protected | ||
| 46 | // OF imports | ||
| 47 | import Absyn.Path; | ||
| 48 | |||
| 49 | // NF import | ||
| 50 | import NFFunction.Function; | ||
| 51 | import Variable = NFVariable; | ||
| 52 | import ComponentRef = NFComponentRef; | ||
| 53 | |||
| 54 | // NB import | ||
| 55 | import Adjacency = NBAdjacency; | ||
| 56 | import NBEquation.{Equation, EqData, EquationPointer, EquationPointers}; | ||
| 57 | import Module = NBModule; | ||
| 58 | import ResolveSingularities = NBResolveSingularities; | ||
| 59 | import Partition = NBPartition; | ||
| 60 | import BVariable = NBVariable; | ||
| 61 | import NBVariable.{VarData, VariablePointer, VariablePointers}; | ||
| 62 | |||
| 63 | // OB import | ||
| 64 | import BackendDAEEXT; | ||
| 65 | |||
| 66 | // Util import | ||
| 67 | import BackendUtil = NBBackendUtil; | ||
| 68 | import Slice = NBSlice; | ||
| 69 | import Vector; | ||
| 70 | import NBSlice.IntLst; | ||
| 71 | import StringUtil; | ||
| 72 | public | ||
| 73 | // ======================================= | ||
| 74 | // MATCHING | ||
| 75 | // ======================================= | ||
| 76 | record MATCHING | ||
| 77 | array<Integer> var_to_eqn "eqn := var_to_eqn[var]"; | ||
| 78 | array<Integer> eqn_to_var "var := eqn_to_var[eqn]"; | ||
| 79 | end MATCHING; | ||
| 80 | |||
| 81 | constant Matching EMPTY_MATCHING = MATCHING(listArray({}), listArray({})); | ||
| 82 | |||
| 83 | function toString | ||
| 84 | input Matching matching; | ||
| 85 | input output String str = ""; | ||
| 86 | algorithm | ||
| 87 | ✗ | str := StringUtil.headline_2(str + "Scalar Matching") + "\n"; | |
| 88 | ✗ | str := str + toStringSingle(matching.var_to_eqn, false) + "\n"; | |
| 89 | ✗ | str := str + toStringSingle(matching.eqn_to_var, true) + "\n"; | |
| 90 | end toString; | ||
| 91 | |||
| 92 | function trivial | ||
| 93 | "produces a trivial soluation where e1 matches v1 etc." | ||
| 94 | input Integer n; | ||
| 95 | output Matching matching; | ||
| 96 | protected | ||
| 97 | array<Integer> arr = Array.createIntRange(n); | ||
| 98 | algorithm | ||
| 99 | 12 | matching := MATCHING(arr, arr); | |
| 100 | end trivial; | ||
| 101 | |||
| 102 | function regular | ||
| 103 | "author: kabdelhak | ||
| 104 | Regular matching algorithm for bipartite graphs by Constantinos C. Pantelides. | ||
| 105 | First published in doi:10.1137/0909014" | ||
| 106 | input output Matching matching; | ||
| 107 | input Adjacency.Matrix adj; | ||
| 108 | input Boolean transposed = false "transpose matching if true"; | ||
| 109 | input Boolean partially = false "do not fail on singular partitions and return partial matching if true"; | ||
| 110 | input Boolean clear = true "start from scratch if true"; | ||
| 111 | protected | ||
| 112 | list<list<Integer>> marked_eqns; | ||
| 113 | algorithm | ||
| 114 | 1552 | (matching, marked_eqns, _, _) := continue_(matching, adj, transposed, clear); | |
| 115 |
3/4✓ Branch 0 taken 1140 times.
✓ Branch 1 taken 412 times.
✓ Branch 3 taken 1140 times.
✗ Branch 4 not taken.
|
1552 | if not partially and not listEmpty(List.flatten(marked_eqns)) then |
| 116 | ✗ | Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed because the partition is structurally singular."}); | |
| 117 | ✗ | fail(); | |
| 118 | end if; | ||
| 119 | end regular; | ||
| 120 | |||
| 121 | constant Integer MAX_INDEX_REDUCTION_RESTARTS = 20 "index reduction restarts after which the system is considered unresolvable"; | ||
| 122 | |||
| 123 | function singular | ||
| 124 | "author: kabdelhak | ||
| 125 | Matching algorithm for bipartite graphs by Constantinos C. Pantelides. | ||
| 126 | First published in doi:10.1137/0909014 | ||
| 127 | In the case of singular partitions in tries to resolve it by applying index reduction | ||
| 128 | using the dummy derivative method by Sven E. Mattsson and Gustaf Söderlind | ||
| 129 | First published in doi:10.1137/0914043 | ||
| 130 | |||
| 131 | algorithm: | ||
| 132 | 1. apply pantelides but carry list of singular markings (eqs) | ||
| 133 | whenever singular - add all current marks to singular markings | ||
| 134 | 2. if done and not everything is matched -> index reduction / balance initialization | ||
| 135 | 3. restart matching if step 2. changed the partition | ||
| 136 | " | ||
| 137 | input output Matching matching; | ||
| 138 | input output Adjacency.Matrix adj; | ||
| 139 | input output Adjacency.Matrix full; | ||
| 140 | input output VariablePointers vars; | ||
| 141 | input output EquationPointers eqns; | ||
| 142 | input UnorderedMap<Path, Function> funcMap; | ||
| 143 | input output VarData varData; | ||
| 144 | input output EqData eqData; | ||
| 145 | input Partition.Kind kind; | ||
| 146 | input Boolean transposed = false "transpose matching if true"; | ||
| 147 | input Boolean clear = true "start from scratch if true"; | ||
| 148 | input Integer restarts = 0 "number of index reduction restarts so far"; | ||
| 149 | protected | ||
| 150 | list<list<Integer>> marked_eqns; | ||
| 151 | Option<Adjacency.Mapping> mapping; | ||
| 152 | Adjacency.MatrixStrictness matrixStrictness; | ||
| 153 | Boolean changed; | ||
| 154 | algorithm | ||
| 155 | // 1. match the partition | ||
| 156 | try | ||
| 157 | 552 | (matching, marked_eqns, mapping, matrixStrictness) := continue_(matching, adj, transposed, clear); | |
| 158 | else | ||
| 159 | ✗ | Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed to match partition:\n" | |
| 160 | + VariablePointers.toString(vars, "partition vars") + "\n" | ||
| 161 | + EquationPointers.toString(eqns, "partition eqns") + "\n" | ||
| 162 | + Adjacency.Matrix.toString(adj)}); | ||
| 163 | ✗ | fail(); | |
| 164 | end try; | ||
| 165 | |||
| 166 | // 2. Resolve singular partitions if necessary | ||
| 167 |
2/2✓ Branch 1 taken 181 times.
✓ Branch 2 taken 371 times.
|
552 | if Partition.kindIsInitial(kind) then |
| 168 | // ####### BALANCE INITIALIZATION ####### | ||
| 169 | 181 | (adj, full, vars, eqns, varData, eqData, changed) := ResolveSingularities.balanceInitialization(adj, full, vars, eqns, varData, eqData, kind, funcMap, matching, mapping); | |
| 170 | else | ||
| 171 | // ####### INDEX REDUCTION ####### | ||
| 172 | 371 | (adj, full, vars, eqns, varData, eqData, changed) := ResolveSingularities.indexReduction(adj, full, vars, eqns, varData, eqData, kind, funcMap, matching, mapping); | |
| 173 | end if; | ||
| 174 | |||
| 175 | // 3. Recompute adjacency and restart matching if something changed in step 2. | ||
| 176 |
2/2✓ Branch 0 taken 71 times.
✓ Branch 1 taken 481 times.
|
552 | if changed then |
| 177 | // ToDo: keep more of old information by only updating changed stuff | ||
| 178 | 71 | full := Adjacency.Matrix.createFull(vars, eqns, kind); | |
| 179 | 71 | adj := Adjacency.Matrix.fullToFinal(full, vars.map, eqns.map, eqns, matrixStrictness); | |
| 180 |
2/2✓ Branch 1 taken 28 times.
✓ Branch 2 taken 43 times.
|
71 | if Partition.kindIsInitial(kind) then |
| 181 | // ####### DO NOT REDO BALANCING INITIALIZATION ####### | ||
| 182 | 28 | matching := regular(EMPTY_MATCHING, adj); | |
| 183 | else | ||
| 184 | // ####### REDO INDEX REDUCTION IF NECESSARY ####### | ||
| 185 | // a structurally singular system (e.g. over-determined) never becomes regular by differentiation | ||
| 186 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 42 times.
|
43 | if restarts >= MAX_INDEX_REDUCTION_RESTARTS then |
| 187 | 2 | Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " could not resolve the structural singularity after " | |
| 188 | + intString(restarts) + " index reduction steps. The system is probably over-determined or has a too high index."}); | ||
| 189 | 1 | fail(); | |
| 190 | end if; | ||
| 191 | 42 | (matching, adj, full, vars, eqns, varData, eqData) := singular(EMPTY_MATCHING, adj, full, vars, eqns, funcMap, varData, eqData, kind, transposed, restarts = restarts + 1); | |
| 192 | end if; | ||
| 193 | end if; | ||
| 194 | end singular; | ||
| 195 | |||
| 196 | function fromSeed | ||
| 197 | "the matching of a causalized partition with nearly the same equations and | ||
| 198 | variables, transferred by name. A pair is kept when the variable is still a | ||
| 199 | solvable occurrence of the equation, the rest is left for the matching | ||
| 200 | algorithm to repair." | ||
| 201 | input Partition.Partition seed; | ||
| 202 | input Adjacency.Matrix adj; | ||
| 203 | input VariablePointers vars; | ||
| 204 | input EquationPointers eqns; | ||
| 205 | output Matching matching = EMPTY_MATCHING; | ||
| 206 | protected | ||
| 207 | Matching seed_matching; | ||
| 208 | Adjacency.Mapping seed_map, map; | ||
| 209 | array<Integer> var_to_eqn, eqn_to_var, data, var_index; | ||
| 210 | Integer e, v, eqn, var, eqn_start, eqn_len, seed_start, seed_len, seed_var_start, var_start, var_len, offset, first; | ||
| 211 | algorithm | ||
| 212 |
4/12✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 6 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 6 times.
|
6 | if isNone(seed.matching) or isNone(seed.adjacencyMatrix) then return; end if; |
| 213 | 6 | seed_matching := Util.getOption(seed.matching); | |
| 214 | () := match (Adjacency.Matrix.getMappingOpt(Util.getOption(seed.adjacencyMatrix)), adj) | ||
| 215 | case (SOME(seed_map), Adjacency.Matrix.FINAL(mapping = map)) algorithm | ||
| 216 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
12 | var_index := arrayCreate(arrayLength(seed_map.var_AtS), -1); |
| 217 |
1/2✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
|
428 | for i in 1:arrayLength(var_index) loop |
| 218 | 422 | var_index[i] := VariablePointers.getVarIndex(vars, BVariable.getVarName(VariablePointers.getVarAt(seed.unknowns, i))); | |
| 219 | end for; | ||
| 220 | 6 | data := Adjacency.IntMatrix.entries(adj.m); | |
| 221 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
12 | var_to_eqn := arrayCreate(arrayLength(map.var_StA), -1); |
| 222 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
12 | eqn_to_var := arrayCreate(arrayLength(map.eqn_StA), -1); |
| 223 |
2/4✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
|
553 | for i in 1:arrayLength(seed_map.eqn_AtS) loop |
| 224 | 541 | e := EquationPointers.getEqnIndex(eqns, Equation.getEqnName(EquationPointers.getEqnAt(seed.equations, i))); | |
| 225 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 539 times.
|
541 | if e < 1 then continue; end if; |
| 226 | 539 | (seed_start, seed_len) := seed_map.eqn_AtS[i]; | |
| 227 |
2/2✓ Branch 1 taken 498 times.
✓ Branch 2 taken 41 times.
|
539 | (eqn_start, eqn_len) := map.eqn_AtS[e]; |
| 228 |
2/2✓ Branch 0 taken 498 times.
✓ Branch 1 taken 41 times.
|
1189 | for k in 0:min(seed_len, eqn_len) - 1 loop |
| 229 | 650 | v := seed_matching.eqn_to_var[seed_start + k]; | |
| 230 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 650 times.
|
650 | if v < 1 then continue; end if; |
| 231 | 650 | (seed_var_start, _) := seed_map.var_AtS[seed_map.var_StA[v]]; | |
| 232 | 650 | offset := v - seed_var_start; | |
| 233 | 650 | v := var_index[seed_map.var_StA[v]]; | |
| 234 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 650 times.
|
650 | if v < 1 then continue; end if; |
| 235 | 650 | (var_start, var_len) := map.var_AtS[v]; | |
| 236 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 650 times.
|
650 | if offset >= var_len then continue; end if; |
| 237 | 650 | var := var_start + offset; | |
| 238 | 650 | eqn := eqn_start + k; | |
| 239 | 650 | first := adj.m.start[eqn]; | |
| 240 |
1/2✓ Branch 1 taken 650 times.
✗ Branch 2 not taken.
|
1226 | for p in first:first + adj.m.len[eqn] - 1 loop |
| 241 |
2/2✓ Branch 1 taken 648 times.
✓ Branch 2 taken 576 times.
|
1224 | if data[p] == var then |
| 242 | 648 | eqn_to_var[eqn] := var; | |
| 243 | 648 | var_to_eqn[var] := eqn; | |
| 244 | 648 | break; | |
| 245 | end if; | ||
| 246 | end for; | ||
| 247 | end for; | ||
| 248 | end for; | ||
| 249 | 6 | matching := MATCHING(var_to_eqn, eqn_to_var); | |
| 250 | then (); | ||
| 251 | else (); | ||
| 252 | end match; | ||
| 253 | end fromSeed; | ||
| 254 | |||
| 255 | function continue_ | ||
| 256 | input output Matching matching; | ||
| 257 | input Adjacency.Matrix adj; | ||
| 258 | input Boolean transposed; | ||
| 259 | input Boolean clear; | ||
| 260 | output list<list<Integer>> marked_eqns; | ||
| 261 | output Option<Adjacency.Mapping> mapping; | ||
| 262 | output Adjacency.MatrixStrictness matrixStrictness; | ||
| 263 | protected | ||
| 264 | array<Integer> var_to_eqn, eqn_to_var; | ||
| 265 | algorithm | ||
| 266 | // 1. Match the partition | ||
| 267 | (matching, marked_eqns, mapping, matrixStrictness) := match adj | ||
| 268 | // PSEUDO ARRAY | ||
| 269 | case Adjacency.Matrix.FINAL() algorithm | ||
| 270 | 2101 | (var_to_eqn, eqn_to_var) := getAssignments(matching, adj.m, adj.mT); | |
| 271 | 2101 | (var_to_eqn, eqn_to_var, marked_eqns) := PFPlusExternal(adj.m, var_to_eqn, eqn_to_var, clear); | |
| 272 | 2101 | matching := MATCHING(var_to_eqn, eqn_to_var); | |
| 273 | 2101 | then (matching, marked_eqns, SOME(adj.mapping), adj.st); | |
| 274 | |||
| 275 | // EMPTY | ||
| 276 | case Adjacency.Matrix.EMPTY() | ||
| 277 | 3 | then (EMPTY_MATCHING, {}, NONE(), NBAdjacency.MatrixStrictness.FULL); | |
| 278 | |||
| 279 | // FAIL | ||
| 280 | else algorithm | ||
| 281 | ✗ | Error.addMessage(Error.INTERNAL_ERROR, {getInstanceName() + " failed."}); | |
| 282 | ✗ | then fail(); | |
| 283 | end match; | ||
| 284 | end continue_; | ||
| 285 | |||
| 286 | function isEmpty | ||
| 287 | input Matching matching; | ||
| 288 | output Boolean b = arrayEmpty(matching.eqn_to_var) and arrayEmpty(matching.var_to_eqn); | ||
| 289 | end isEmpty; | ||
| 290 | |||
| 291 | function isPerfect | ||
| 292 | "returns true if all variables OR equations have been matched | ||
| 293 | Note: if it's not a square problem, it returns true if one of the two is fully matched" | ||
| 294 | input Matching matching; | ||
| 295 | output Boolean b; | ||
| 296 | algorithm | ||
| 297 | ✗ | if arrayLength(matching.var_to_eqn) > arrayLength(matching.eqn_to_var) then | |
| 298 | ✗ | b := Array.all(matching.eqn_to_var, function intGt(i2 = 0)); | |
| 299 | else | ||
| 300 | ✗ | b := Array.all(matching.var_to_eqn, function intGt(i2 = 0)); | |
| 301 | end if; | ||
| 302 | end isPerfect; | ||
| 303 | |||
| 304 | function getAssignments | ||
| 305 | "expands the assignments with -1 if needed" | ||
| 306 | input Matching matching; | ||
| 307 | input Adjacency.IntMatrix m; | ||
| 308 | input Adjacency.IntMatrix mT; | ||
| 309 | output array<Integer> var_to_eqn; | ||
| 310 | output array<Integer> eqn_to_var; | ||
| 311 | protected | ||
| 312 | Integer nVars = Adjacency.IntMatrix.rows(mT); | ||
| 313 | Integer nEqns = Adjacency.IntMatrix.rows(m); | ||
| 314 | algorithm | ||
| 315 | 2101 | var_to_eqn := Array.expandToSize(nVars, matching.var_to_eqn, -1); | |
| 316 | 2101 | eqn_to_var := Array.expandToSize(nEqns, matching.eqn_to_var, -1); | |
| 317 | end getAssignments; | ||
| 318 | |||
| 319 | function getMatches | ||
| 320 | input Matching matching; | ||
| 321 | input Option<Adjacency.Mapping> mapping_opt; | ||
| 322 | input VariablePointers variables; | ||
| 323 | input EquationPointers equations; | ||
| 324 | output list<Slice<VariablePointer>> matched_vars = {}, unmatched_vars = {}; | ||
| 325 | output list<Slice<EquationPointer>> matched_eqns = {}, unmatched_eqns = {}; | ||
| 326 | protected | ||
| 327 | Adjacency.Mapping mapping; | ||
| 328 | UnorderedMap<VariablePointer, IntLst> var_map_matched, var_map_unmatched; | ||
| 329 | UnorderedMap<EquationPointer, IntLst> eqn_map_matched, eqn_map_unmatched; | ||
| 330 | Pointer<Variable> arr_var; | ||
| 331 | Pointer<Equation> arr_eqn; | ||
| 332 | Integer start_idx; | ||
| 333 | algorithm | ||
| 334 | // pseudo array case | ||
| 335 |
3/4✗ Branch 0 not taken.
✓ Branch 1 taken 222 times.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 221 times.
|
222 | if isSome(mapping_opt) then |
| 336 | 221 | mapping := Util.getOption(mapping_opt); | |
| 337 | |||
| 338 | 221 | var_map_matched := UnorderedMap.new<IntLst>(BVariable.hash, BVariable.equalName); | |
| 339 | 221 | var_map_unmatched := UnorderedMap.new<IntLst>(BVariable.hash, BVariable.equalName); | |
| 340 | 221 | eqn_map_matched := UnorderedMap.new<IntLst>(Equation.hash, Equation.equalName); | |
| 341 | 221 | eqn_map_unmatched := UnorderedMap.new<IntLst>(Equation.hash, Equation.equalName); | |
| 342 | |||
| 343 | // check if variables are matched and sort them accordingly | ||
| 344 |
2/4✗ Branch 0 not taken.
✓ Branch 1 taken 221 times.
✓ Branch 2 taken 221 times.
✗ Branch 3 not taken.
|
9913 | for var in 1:arrayLength(matching.var_to_eqn) loop |
| 345 | 9471 | arr_var := ExpandableArray.get(mapping.var_StA[var], variables.varArr); | |
| 346 | 9471 | (start_idx, _) := mapping.var_AtS[mapping.var_StA[var]]; | |
| 347 |
2/2✓ Branch 1 taken 9276 times.
✓ Branch 2 taken 195 times.
|
9471 | if matching.var_to_eqn[var] > 0 then |
| 348 | 9276 | Slice.addToSliceMap(arr_var, (var - start_idx), var_map_matched); | |
| 349 | else | ||
| 350 | 195 | Slice.addToSliceMap(arr_var, (var - start_idx), var_map_unmatched); | |
| 351 | end if; | ||
| 352 | end for; | ||
| 353 | |||
| 354 | // check if equations are matched and sort them accordingly | ||
| 355 |
2/4✗ Branch 0 not taken.
✓ Branch 1 taken 221 times.
✓ Branch 2 taken 221 times.
✗ Branch 3 not taken.
|
9759 | for eqn in 1:arrayLength(matching.eqn_to_var) loop |
| 356 | 9317 | arr_eqn := ExpandableArray.get(mapping.eqn_StA[eqn], equations.eqArr); | |
| 357 | 9317 | (start_idx, _) := mapping.eqn_AtS[mapping.eqn_StA[eqn]]; | |
| 358 |
2/2✓ Branch 1 taken 9276 times.
✓ Branch 2 taken 41 times.
|
9317 | if matching.eqn_to_var[eqn] > 0 then |
| 359 | 9276 | Slice.addToSliceMap(arr_eqn, (eqn - start_idx), eqn_map_matched); | |
| 360 | else | ||
| 361 | 41 | Slice.addToSliceMap(arr_eqn, (eqn - start_idx), eqn_map_unmatched); | |
| 362 | end if; | ||
| 363 | end for; | ||
| 364 | |||
| 365 | // get the slice lists while sorting indices and simplifying whole slices to {} | ||
| 366 |
4/4✓ Branch 1 taken 3656 times.
✓ Branch 2 taken 221 times.
✓ Branch 3 taken 3656 times.
✓ Branch 4 taken 221 times.
|
3877 | matched_vars := list(Slice.simplify(slice, function BVariable.size(resize = true)) for slice in Slice.fromMap(var_map_matched)); |
| 367 |
4/4✓ Branch 1 taken 82 times.
✓ Branch 2 taken 221 times.
✓ Branch 3 taken 82 times.
✓ Branch 4 taken 221 times.
|
303 | unmatched_vars := list(Slice.simplify(slice, function BVariable.size(resize = true)) for slice in Slice.fromMap(var_map_unmatched)); |
| 368 |
4/4✓ Branch 1 taken 4455 times.
✓ Branch 2 taken 221 times.
✓ Branch 3 taken 4455 times.
✓ Branch 4 taken 221 times.
|
4676 | matched_eqns := list(Slice.simplify(slice, function Equation.size(resize = true)) for slice in Slice.fromMap(eqn_map_matched)); |
| 369 |
4/4✓ Branch 1 taken 41 times.
✓ Branch 2 taken 221 times.
✓ Branch 3 taken 41 times.
✓ Branch 4 taken 221 times.
|
262 | unmatched_eqns := list(Slice.simplify(slice, function Equation.size(resize = true)) for slice in Slice.fromMap(eqn_map_unmatched)); |
| 370 | else | ||
| 371 | // check if variables are matched and sort them accordingly | ||
| 372 |
2/4✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 time.
|
2 | for var in 1:arrayLength(matching.var_to_eqn) loop |
| 373 | ✗ | if matching.var_to_eqn[var] > 0 then | |
| 374 | ✗ | matched_vars := Slice.SLICE(ExpandableArray.get(var, variables.varArr),{}) :: matched_vars; | |
| 375 | else | ||
| 376 | ✗ | unmatched_vars := Slice.SLICE(ExpandableArray.get(var, variables.varArr),{}) :: unmatched_vars; | |
| 377 | end if; | ||
| 378 | end for; | ||
| 379 | |||
| 380 | // check if equations are matched and sort them accordingly | ||
| 381 |
2/4✗ Branch 0 not taken.
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 1 time.
✗ Branch 3 not taken.
|
2 | for eqn in 1:arrayLength(matching.eqn_to_var) loop |
| 382 | ✗ | if matching.eqn_to_var[eqn] > 0 then | |
| 383 | ✗ | matched_eqns := Slice.SLICE(ExpandableArray.get(eqn, equations.eqArr),{}) :: matched_eqns; | |
| 384 | else | ||
| 385 | ✗ | unmatched_eqns := Slice.SLICE(ExpandableArray.get(eqn, equations.eqArr),{}) :: unmatched_eqns; | |
| 386 | end if; | ||
| 387 | end for; | ||
| 388 | end if; | ||
| 389 | end getMatches; | ||
| 390 | |||
| 391 | function getMatchedVars | ||
| 392 | "returns the variables from the map that have at least one matched scalar element" | ||
| 393 | input Matching matching; | ||
| 394 | input Option<Adjacency.Mapping> mapping_opt; | ||
| 395 | input UnorderedMap<ComponentRef, Integer> vars_map; | ||
| 396 | input VariablePointers variables; | ||
| 397 | output list<VariablePointer> matched = {}; | ||
| 398 | protected | ||
| 399 | Integer start, size; | ||
| 400 | algorithm | ||
| 401 |
2/2✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
|
6 | for arr_idx in UnorderedMap.valueList(vars_map) loop |
| 402 | (start, size) := match mapping_opt | ||
| 403 | local | ||
| 404 | Adjacency.Mapping mapping; | ||
| 405 | 4 | case SOME(mapping) then mapping.var_AtS[arr_idx]; | |
| 406 | ✗ | else (arr_idx, 1); | |
| 407 | end match; | ||
| 408 |
1/2✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
|
4 | for scal_idx in start:start+size-1 loop |
| 409 |
3/6✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 4 times.
✗ Branch 6 not taken.
|
8 | if scal_idx <= arrayLength(matching.var_to_eqn) and matching.var_to_eqn[scal_idx] > 0 then |
| 410 | 4 | matched := ExpandableArray.get(arr_idx, variables.varArr) :: matched; | |
| 411 | 4 | break; | |
| 412 | end if; | ||
| 413 | end for; | ||
| 414 | end for; | ||
| 415 | end getMatchedVars; | ||
| 416 | |||
| 417 | protected | ||
| 418 | function toStringSingle | ||
| 419 | input array<Integer> mapping; | ||
| 420 | input Boolean inverse; | ||
| 421 | output String str; | ||
| 422 | protected | ||
| 423 | String head = if inverse then "equation to variable" else "variable to equation"; | ||
| 424 | String from = if inverse then "eqn" else "var"; | ||
| 425 | String to = if inverse then "var" else "eqn"; | ||
| 426 | algorithm | ||
| 427 | ✗ | str := StringUtil.headline_4(head); | |
| 428 | ✗ | for i in 1:arrayLength(mapping) loop | |
| 429 | ✗ | str := str + "\t" + from + " " + intString(i) + " --> " + to + " " + intString(mapping[i]) + "\n"; | |
| 430 | end for; | ||
| 431 | end toStringSingle; | ||
| 432 | |||
| 433 | // ###################################### | ||
| 434 | // SCALAR MATCHING | ||
| 435 | // ###################################### | ||
| 436 | function scalarMatching | ||
| 437 | input array<list<Integer>> m; | ||
| 438 | input array<list<Integer>> mT; | ||
| 439 | input Boolean transposed = false "transpose matching if true"; | ||
| 440 | input Boolean partially = false "do not fail on singular partitions and return partial matching if true"; | ||
| 441 | output Matching matching; | ||
| 442 | // this needs partially = true to get computed. Otherwise it fails on singular partitions | ||
| 443 | output list<list<Integer>> marked_eqns = {} "marked equations for index reduction in the case of a singular partition"; | ||
| 444 | protected | ||
| 445 | Integer nVars = arrayLength(mT), nEqns = arrayLength(m); | ||
| 446 | array<Integer> var_to_eqn; | ||
| 447 | array<Integer> eqn_to_var; | ||
| 448 | array<Boolean> var_marks = arrayCreate(0, false); | ||
| 449 | array<Boolean> eqn_marks = arrayCreate(0, false); | ||
| 450 | Boolean pathFound; | ||
| 451 | algorithm | ||
| 452 | ✗ | var_to_eqn := arrayCreate(nVars, -1); | |
| 453 | // loop over all equations and try to find an augmenting path | ||
| 454 | // to match each uniquely to a variable | ||
| 455 | ✗ | for eqn in 1:nEqns loop | |
| 456 | ✗ | var_marks := arrayCreate(nVars, false); | |
| 457 | ✗ | eqn_marks := arrayCreate(nEqns, false); | |
| 458 | ✗ | (var_to_eqn, var_marks, eqn_marks, pathFound) := augmentPath(eqn, m, mT, var_to_eqn, var_marks, eqn_marks); | |
| 459 | // if it is not possible index reduction needs to be applied | ||
| 460 | ✗ | if not pathFound then | |
| 461 | ✗ | if not partially then | |
| 462 | ✗ | Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed because the partition is structurally singular. Index Reduction is not yet supported"}); | |
| 463 | elseif transposed then | ||
| 464 | // if transposed the variable marks represent equations | ||
| 465 | ✗ | marked_eqns := BackendUtil.findTrueIndices(var_marks) :: marked_eqns; | |
| 466 | else | ||
| 467 | ✗ | marked_eqns := BackendUtil.findTrueIndices(eqn_marks) :: marked_eqns; | |
| 468 | end if; | ||
| 469 | end if; | ||
| 470 | end for; | ||
| 471 | |||
| 472 | // create inverse matching | ||
| 473 | ✗ | eqn_to_var := arrayCreate(nEqns, -1); | |
| 474 | ✗ | for var in 1:nVars loop | |
| 475 | ✗ | if var_to_eqn[var] > 0 then | |
| 476 | ✗ | eqn_to_var[var_to_eqn[var]] := var; | |
| 477 | end if; | ||
| 478 | end for; | ||
| 479 | |||
| 480 | // free auxiliary arrays | ||
| 481 | ✗ | if nEqns > 0 then | |
| 482 | ✗ | GCExt.free(var_marks); | |
| 483 | ✗ | GCExt.free(eqn_marks); | |
| 484 | end if; | ||
| 485 | |||
| 486 | // create the matching structure | ||
| 487 | ✗ | matching := if transposed then MATCHING(eqn_to_var, var_to_eqn) else MATCHING(var_to_eqn, eqn_to_var); | |
| 488 | end scalarMatching; | ||
| 489 | |||
| 490 | function augmentPath | ||
| 491 | input Integer eqn; | ||
| 492 | input array<list<Integer>> m; | ||
| 493 | input array<list<Integer>> mT; | ||
| 494 | input output array<Integer> var_to_eqn; | ||
| 495 | input output array<Boolean> var_marks; | ||
| 496 | input output array<Boolean> eqn_marks; | ||
| 497 | output Boolean pathFound = false; | ||
| 498 | algorithm | ||
| 499 | ✗ | eqn_marks[eqn] := true; | |
| 500 | // loop over each edge and try to find an unmatched variable | ||
| 501 | ✗ | for var in m[eqn] loop | |
| 502 | ✗ | if var_to_eqn[var] <= 0 then | |
| 503 | ✗ | pathFound := true; | |
| 504 | ✗ | var_to_eqn[var] := eqn; | |
| 505 | ✗ | return; | |
| 506 | end if; | ||
| 507 | end for; | ||
| 508 | |||
| 509 | // if no umatched variable can be found, loop over all edges again | ||
| 510 | // and try to recursively revoke an old matching decision | ||
| 511 | ✗ | for var in m[eqn] loop | |
| 512 | ✗ | if not var_marks[var] then | |
| 513 | ✗ | var_marks[var] := true; | |
| 514 | // recursive call | ||
| 515 | ✗ | (var_to_eqn, var_marks, eqn_marks, pathFound) := augmentPath(var_to_eqn[var], m, mT, var_to_eqn, var_marks, eqn_marks); | |
| 516 | ✗ | if pathFound then | |
| 517 | ✗ | var_to_eqn[var] := eqn; | |
| 518 | ✗ | return; | |
| 519 | end if; | ||
| 520 | end if; | ||
| 521 | end for; | ||
| 522 | end augmentPath; | ||
| 523 | |||
| 524 | function PFPlusExternal | ||
| 525 | input Adjacency.IntMatrix m; | ||
| 526 | input output array<Integer> ass1; | ||
| 527 | input output array<Integer> ass2; | ||
| 528 | input Boolean clear; | ||
| 529 | // this needs partially = true to get computed. Otherwise it fails on singular partitions | ||
| 530 | output list<list<Integer>> marked_eqns = {} "marked equations for index reduction in the case of a singular partition"; | ||
| 531 | protected | ||
| 532 | Integer n1 = arrayLength(ass1), n2 = arrayLength(ass2), nonZero = Adjacency.IntMatrix.nonZeroCount(m); | ||
| 533 | Integer cheap = 0, algIndx = 5 "PFPlusExternal index"; | ||
| 534 | algorithm | ||
| 535 | 2101 | BackendDAEEXT.setAssignment(n2, n1, ass2, ass1); | |
| 536 | 2101 | BackendDAEEXT.setAdjacencyMatrixFlat(n1, n2, nonZero, m.start, m.len, Vector.rawArray(m.data)); | |
| 537 |
2/2✓ Branch 0 taken 240 times.
✓ Branch 1 taken 1861 times.
|
2341 | BackendDAEEXT.matching(n1, n2, algIndx, cheap, 1.0, if clear then 1 else 0); |
| 538 | 2101 | BackendDAEEXT.getAssignment(ass2, ass1); | |
| 539 | end PFPlusExternal; | ||
| 540 | |||
| 541 | annotation(__OpenModelica_Interface="nbackend"); | ||
| 542 | end NBMatching; | ||
| 543 |