Linux GNU 11.4.0 Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 41.4% 63 / 0 / 152
Functions: -% 0 / 1 / 1
Branches: 42.4% 39 / 0 / 92
OMCompiler/Compiler/Util/Graph.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 package Graph
37 " file: Graph.mo
38 package: Graph
39 description: Contains various graph algorithms.
40
41
42 This package contains various graph algorithms such as topological sorting. It
43 should also contain a graph type, but such a type would need polymorphic
44 records that we don't yet support in MetaModelica."
45
46 protected import Error;
47 protected import Array;
48 protected import List;
49
50 public replaceable type NodeType subtypeof Any;
51 public replaceable type ArgType subtypeof Any;
52
53 public function buildGraph
54 "This function will build a graph given a list of nodes, an edge function, and
55 an extra argument to the edge function. The edge function should generate a
56 list of edges for any given node in the list. From this information a graph
57 represented by an adjacency list will be built.
58
59 NOTE: There is no check that there is only unique edges for each node.
60 This module assumes that you do not build a graph with duplicate edges!"
61 input list<NodeType> inNodes;
62 input EdgeFunc inEdgeFunc;
63 input ArgType inEdgeArg;
64 output list<tuple<NodeType, list<NodeType>>> outGraph;
65
66 partial function EdgeFunc
67 input NodeType inNode;
68 input ArgType inArg;
69 output list<NodeType> outEdges;
70 end EdgeFunc;
71 algorithm
72 347781 outGraph := List.zip(inNodes, List.map1(inNodes, inEdgeFunc, inEdgeArg));
73 end buildGraph;
74
75 public function emptyGraph
76 "This function will build an empty graph given a list of nodes."
77 input list<NodeType> inNodes;
78 output list<tuple<NodeType, list<NodeType>>> outGraph;
79 algorithm
80 ✗ outGraph := List.map(inNodes, emptyGraphHelper);
81 end emptyGraph;
82
83 protected function emptyGraphHelper
84 input NodeType nt;
85 output tuple<NodeType,list<NodeType>> out;
86 algorithm
87 ✗ out := (nt,{});
88 end emptyGraphHelper;
89
90 public function topologicalSort
91 "This function will sort a graph topologically. It takes a graph represented
92 by an adjacency list and a node equality function, and returns a list of the
93 nodes ordered by dependencies (a node x is dependent on y if there is an edge
94 from x to y). This function assumes that all edges in the graph are unique.
95
96 It is of course only possible to sort an acyclic graph topologically. If the
97 graph contains cycles this function will return the nodes that it could sort
98 as the first return value, and the remaining graph that contains cycles as the
99 second value."
100 input list<tuple<NodeType, list<NodeType>>> inGraph;
101 input EqualFunc inEqualFunc;
102 output list<NodeType> outNodes;
103 output list<tuple<NodeType, list<NodeType>>> outRemainingGraph;
104
105 partial function EqualFunc
106 "Given two nodes, returns true if they are equal, otherwise false."
107 input NodeType inNode1;
108 input NodeType inNode2;
109 output Boolean isEqual;
110 end EqualFunc;
111 protected
112 list<tuple<NodeType, list<NodeType>>> start_nodes, rest_nodes;
113 algorithm
114 344723 (rest_nodes, start_nodes) := List.splitOnTrue(inGraph, hasOutgoingEdges);
115 344723 (outNodes, outRemainingGraph) :=
116 topologicalSort2(start_nodes, rest_nodes, {}, inEqualFunc);
117 end topologicalSort;
118
119 protected function topologicalSort2
120 "Helper function to topologicalSort, does most of the actual work.
121 inStartNodes is a list of start nodes that have no outgoing edges, i.e. no
122 dependencies. inRestNodes is the rest of the nodes in the graph."
123 input list<tuple<NodeType, list<NodeType>>> inStartNodes;
124 input list<tuple<NodeType, list<NodeType>>> inRestNodes;
125 input list<NodeType> inAccumNodes;
126 input EqualFunc inEqualFunc;
127 output list<NodeType> outNodes;
128 output list<tuple<NodeType, list<NodeType>>> outRemainingGraph;
129
130 partial function EqualFunc
131 "Given two nodes, returns true if they are equal, otherwise false."
132 input NodeType inNode1;
133 input NodeType inNode2;
134 output Boolean isEqual;
135 end EqualFunc;
136 algorithm
137 (outNodes, outRemainingGraph) :=
138 match(inStartNodes, inRestNodes)
139 local
140 NodeType node1;
141 list<tuple<NodeType, list<NodeType>>> rest_start, rest_start_, rest_rest, new_start;
142 list<NodeType> result;
143
144 // No more nodes to sort, reverse the accumulated nodes (because of
145 // accumulation order) and return it with the (hopefully empty) remaining
146 // graph.
147 105661 case ({}, _) then (listReverse(inAccumNodes), inRestNodes);
148
149 // If the remaining graph is empty we don't need to do much more, just
150 // append the rest of the start nodes to the result.
151 case (rest_start, {})
152 algorithm
153 result := inAccumNodes;
154
2/2
✓ Branch 0 taken 1468435 times.
✓ Branch 1 taken 239062 times.
 1707497 for n in rest_start loop
155
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1468435 times.
 1468435 (node1,{}) := n;
156 result := node1 :: result;
157 end for;
158 239062 result := listReverse(result);
159 then (result, {});
160
161 case ((node1, {}) :: rest_start, rest_rest)
162 algorithm
163 // Remove the first start node from the graph.
164 89549 rest_rest := List.map2(rest_rest, removeEdge, node1, inEqualFunc);
165 // Fetch any new nodes that has no dependencies.
166 89549 (rest_rest, new_start) :=
167 List.splitOnTrue(rest_rest, hasOutgoingEdges);
168 // Append those nodes to the list of start nodes.
169 89549 rest_start_ := listAppend(rest_start, new_start);
170 // Add the first node to the list of sorted nodes and continue with the
171 // rest of the nodes.
172 89549 (result, rest_rest) := topologicalSort2(rest_start_, rest_rest,
173 node1 :: inAccumNodes, inEqualFunc);
174 then
175 (result, rest_rest);
176
177 end match;
178 end topologicalSort2;
179
180 protected function hasOutgoingEdges
181 "Returns true if the given node has no outgoing edges, otherwise false."
182 input tuple<NodeType, list<NodeType>> inNode;
183 output Boolean outHasOutEdges;
184 algorithm
185 outHasOutEdges := match inNode
186 case (_, {}) then false;
187 else true;
188 end match;
189 end hasOutgoingEdges;
190
191 protected function removeEdge
192 "Takes a node with it's edges and a node that's been removed from the graph,
193 and removes the edge if it exists in the edge list."
194 input tuple<NodeType, list<NodeType>> inNode;
195 input NodeType inRemovedNode;
196 input EqualFunc inEqualFunc;
197 output tuple<NodeType, list<NodeType>> outNode;
198
199 partial function EqualFunc
200 "Given two nodes, returns true if they are equal, otherwise false."
201 input NodeType inNode1;
202 input NodeType inNode2;
203 output Boolean isEqual;
204 end EqualFunc;
205
206 protected
207 NodeType node;
208 list<NodeType> edges;
209 algorithm
210 705632 (node, edges) := inNode;
211 705632 (edges, _) := List.deleteMemberOnTrue(inRemovedNode, edges, inEqualFunc);
212 705632 outNode := (node, edges);
213 end removeEdge;
214
215 public function findCycles
216 "Returns the cycles in a given graph. It will check each node, and if that
217 node is part of a cycle it will return the cycle. It will also remove the
218 other nodes in the cycle from the list of remaining nodes to check, so the
219 result will be a list of unique cycles.
220
221 This function is not very efficient, so it shouldn't be used for any
222 performance critical tasks. It's meant to be used together with
223 topologicalSort to print an error message if any cycles are detected."
224 input list<tuple<NodeType, list<NodeType>>> inGraph;
225 input EqualFunc inEqualFunc;
226 output list<list<NodeType>> outCycles;
227
228 partial function EqualFunc
229 "Given two nodes, returns true if they are equal, otherwise false."
230 input NodeType inNode1;
231 input NodeType inNode2;
232 output Boolean isEqual;
233 end EqualFunc;
234 algorithm
235 286 outCycles := findCycles2(inGraph, inGraph, inEqualFunc);
236 end findCycles;
237
238 public function findCycles2
239 "Helper function to findCycles."
240 input list<tuple<NodeType, list<NodeType>>> inNodes;
241 input list<tuple<NodeType, list<NodeType>>> inGraph;
242 input EqualFunc inEqualFunc;
243 output list<list<NodeType>> outCycles;
244
245 partial function EqualFunc
246 "Given two nodes, returns true if they are equal, otherwise false."
247 input NodeType inNode1;
248 input NodeType inNode2;
249 output Boolean isEqual;
250 end EqualFunc;
251 algorithm
252 outCycles := matchcontinue inNodes
253 local
254 tuple<NodeType, list<NodeType>> node;
255 list<tuple<NodeType, list<NodeType>>> rest_nodes;
256 list<NodeType> cycle;
257 list<list<NodeType>> rest_cycles;
258
259 case {} then {};
260
261 // Try and find a cycle for the first node.
262 case node :: rest_nodes
263 algorithm
264
2/4
✗ Branch 1 not taken.
✓ Branch 2 taken 284 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 284 times.
 284 SOME(cycle) := findCycleForNode(node, inGraph, {}, inEqualFunc);
265 284 rest_nodes := removeNodesFromGraph(cycle, rest_nodes, inEqualFunc);
266 284 rest_cycles := findCycles2(rest_nodes, inGraph, inEqualFunc);
267 then
268 cycle :: rest_cycles;
269
270 // If previous case failed we couldn't find a cycle for that node, so
271 // continue with the rest of the nodes.
272 case _ :: rest_nodes
273 algorithm
274 ✗ rest_cycles := findCycles2(rest_nodes, inGraph, inEqualFunc);
275 then
276 rest_cycles;
277
278 end matchcontinue;
279 end findCycles2;
280
281 protected function findCycleForNode
282 "Tries to find a cycle in the graph starting from a given node. This function
283 returns an optional cycle, because it's possible that it will encounter a
284 cycle in which the given node is not a part. This makes it possible to
285 continue searching for another cycle. This function will therefore return some
286 cycle if one was found, or fail or return NONE() if no cycle could be found. A
287 given node might be part of several cycles, but this function will stop as
288 soon as it finds one cycle."
289 input tuple<NodeType, list<NodeType>> inNode;
290 input list<tuple<NodeType, list<NodeType>>> inGraph;
291 input list<NodeType> inVisitedNodes;
292 input EqualFunc inEqualFunc;
293 output Option<list<NodeType>> outCycle;
294
295 partial function EqualFunc
296 "Given two nodes, returns true if they are equal, otherwise false."
297 input NodeType inNode1;
298 input NodeType inNode2;
299 output Boolean isEqual;
300 end EqualFunc;
301 algorithm
302 outCycle := matchcontinue(inNode, inVisitedNodes)
303 local
304 NodeType node, start_node;
305 list<NodeType> edges, visited_nodes, cycle;
306 Boolean is_start_node;
307 Option<list<NodeType>> opt_cycle;
308
309 case ((node, _), _ :: _)
310 algorithm
311 // Check if we have already visited this node.
312
2/2
✓ Branch 1 taken 284 times.
✓ Branch 2 taken 284 times.
 568 true := List.isMemberOnTrue(node, inVisitedNodes, inEqualFunc);
313 // Check if the current node is the start node, in that case we're back
314 // where we started and we have a cycle. Otherwise we just encountered a
315 // cycle in the graph that the start node is not part of.
316 284 start_node := List.last(inVisitedNodes);
317
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 284 times.
 284 is_start_node := inEqualFunc(node, start_node);
318
1/2
✓ Branch 0 taken 284 times.
✗ Branch 1 not taken.
 284 opt_cycle := if is_start_node then SOME(inVisitedNodes) else NONE();
319 then
320 opt_cycle;
321
322 case ((node, edges), _)
323 algorithm
324 // If we have not visited the current node yet we add it to the list of
325 // visited nodes, and then call findCycleForNode2 on the edges of the node.
326 visited_nodes := node :: inVisitedNodes;
327 568 cycle := findCycleForNode2(edges, inGraph, visited_nodes, inEqualFunc);
328 then
329 SOME(cycle);
330
331 end matchcontinue;
332 end findCycleForNode;
333
334 protected function findCycleForNode2
335 "Helper function to findCycleForNode. Calls findNodeInGraph on each node in
336 the given list."
337 input list<NodeType> inNodes;
338 input list<tuple<NodeType, list<NodeType>>> inGraph;
339 input list<NodeType> inVisitedNodes;
340 input EqualFunc inEqualFunc;
341 output list<NodeType> outCycle;
342
343 partial function EqualFunc
344 "Given two nodes, returns true if they are equal, otherwise false."
345 input NodeType inNode1;
346 input NodeType inNode2;
347 output Boolean isEqual;
348 end EqualFunc;
349 algorithm
350 outCycle := matchcontinue inNodes
351 local
352 NodeType node;
353 list<NodeType> rest_nodes, cycle;
354 tuple<NodeType, list<NodeType>> graph_node;
355
356 // Try and find a cycle by following this edge.
357 case node :: _
358 algorithm
359 568 graph_node := findNodeInGraph(node, inGraph, inEqualFunc);
360
2/4
✗ Branch 1 not taken.
✓ Branch 2 taken 568 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 568 times.
 568 SOME(cycle) := findCycleForNode(graph_node, inGraph, inVisitedNodes,
361 inEqualFunc);
362 then
363 cycle;
364
365 // No cycle found in previous case, check the rest of the edges.
366 case _ :: rest_nodes
367 algorithm
368 ✗ cycle := findCycleForNode2(rest_nodes, inGraph, inVisitedNodes,
369 inEqualFunc);
370 then
371 cycle;
372
373 end matchcontinue;
374 end findCycleForNode2;
375
376 protected function findNodeInGraph
377 "Returns a node and its edges from a graph given a node to search for, or
378 fails if no such node exists in the graph."
379 input NodeType inNode;
380 input list<tuple<NodeType, list<NodeType>>> inGraph;
381 input EqualFunc inEqualFunc;
382 output tuple<NodeType, list<NodeType>> outNode;
383
384 partial function EqualFunc
385 "Given two nodes, returns true if they are equal, otherwise false."
386 input NodeType inNode1;
387 input NodeType inNode2;
388 output Boolean isEqual;
389 end EqualFunc;
390 algorithm
391 outNode := matchcontinue inGraph
392 local
393 NodeType node;
394 tuple<NodeType, list<NodeType>> graph_node;
395 list<tuple<NodeType, list<NodeType>>> rest_graph;
396
397 case (graph_node as (node, _)) :: _
398 algorithm
399
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 852 times.
✓ Branch 4 taken 284 times.
✓ Branch 5 taken 568 times.
 852 true := inEqualFunc(inNode, node);
400 then
401 graph_node;
402
403 case _ :: rest_graph
404 284 then findNodeInGraph(inNode, rest_graph, inEqualFunc);
405
406 end matchcontinue;
407 end findNodeInGraph;
408
409 protected function findIndexofNodeInGraph
410 "Returns the index in the list of the node from a graph given a node to search for, or
411 fails if no such node exists in the graph."
412 input NodeType inNode;
413 input list<tuple<NodeType, list<NodeType>>> inGraph;
414 input EqualFunc inEqualFunc;
415 input Integer inIndex;
416 output Integer outIndex;
417
418 partial function EqualFunc
419 "Given two nodes, returns true if they are equal, otherwise false."
420 input NodeType inNode1;
421 input NodeType inNode2;
422 output Boolean isEqual;
423 end EqualFunc;
424 algorithm
425 outIndex := matchcontinue inGraph
426 local
427 NodeType node;
428 list<tuple<NodeType, list<NodeType>>> rest_graph;
429
430 case (node, _) :: _
431 algorithm
432 ✗ true := inEqualFunc(inNode, node);
433 then
434 inIndex;
435
436 case _ :: rest_graph
437 ✗ then findIndexofNodeInGraph(inNode, rest_graph, inEqualFunc, inIndex+1);
438
439 end matchcontinue;
440 end findIndexofNodeInGraph;
441
442 protected function removeNodesFromGraph
443 "Removed a list of nodes from the graph. Note that only the nodes are removed
444 and not any edges pointing at the nodes."
445 input list<NodeType> inNodes;
446 input list<tuple<NodeType, list<NodeType>>> inGraph;
447 input EqualFunc inEqualFunc;
448 output list<tuple<NodeType, list<NodeType>>> outGraph;
449
450 partial function EqualFunc
451 "Given two nodes, returns true if they are equal, otherwise false."
452 input NodeType inNode1;
453 input NodeType inNode2;
454 output Boolean isEqual;
455 end EqualFunc;
456 algorithm
457 outGraph := matchcontinue(inNodes, inGraph)
458 local
459 tuple<NodeType, list<NodeType>> graph_node;
460 list<tuple<NodeType, list<NodeType>>> rest_graph;
461 list<NodeType> rest_nodes;
462 NodeType node;
463
464 case ({}, _) then inGraph;
465 case (_, {}) then {};
466
467 case (_, ((node, _)) :: rest_graph)
468 algorithm
469
2/4
✗ Branch 1 not taken.
✓ Branch 2 taken 284 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 284 times.
 284 (rest_nodes, SOME(_)) := List.deleteMemberOnTrue(node, inNodes,
470 inEqualFunc);
471 284 then
472 removeNodesFromGraph(rest_nodes, rest_graph, inEqualFunc);
473
474 case (_, graph_node :: rest_graph)
475 algorithm
476 ✗ rest_graph := removeNodesFromGraph(inNodes, rest_graph, inEqualFunc);
477 then
478 graph_node :: rest_graph;
479
480 end matchcontinue;
481 end removeNodesFromGraph;
482
483 public function transposeGraph
484 "This function transposes a graph by given a graph and vertex list.
485 To call this, use transposeGraph(emptyGraphOnlyNodes,graph,eqFunction).
486 "
487 input list<tuple<NodeType, list<NodeType>>> intmpGraph;
488 input list<tuple<NodeType, list<NodeType>>> inGraph;
489 input EqualFunc inEqualFunc;
490 output list<tuple<NodeType, list<NodeType>>> outGraph;
491
492 partial function EqualFunc
493 "Given two nodes, returns true if they are equal, otherwise false."
494 input NodeType inNode1;
495 input NodeType inNode2;
496 output Boolean isEqual;
497 end EqualFunc;
498
499 algorithm
500 outGraph := matchcontinue inGraph
501 local
502 NodeType node;
503 list<NodeType> nodeList;
504 list<tuple<NodeType, list<NodeType>>> restGraph,tmpGraph;
505 case {} then intmpGraph;
506 case (node,nodeList)::restGraph
507 algorithm
508 ✗ tmpGraph := List.fold2(nodeList,insertNodetoGraph,node,inEqualFunc,intmpGraph);
509 ✗ tmpGraph := transposeGraph(tmpGraph,restGraph,inEqualFunc);
510 then tmpGraph;
511 else
512 algorithm
513 ✗ Error.addSourceMessage(Error.INTERNAL_ERROR, {"Graph.transpose failed."}, sourceInfo());
514 ✗ then fail();
515 end matchcontinue;
516 end transposeGraph;
517
518 protected function insertNodetoGraph
519 " This function takes nodes and a vertex and inserts
520 the vertex to list of nodes of the graph.
521 "
522 input NodeType inNode;
523 input NodeType inVertex;
524 input EqualFunc inEqualFunc;
525 input list<tuple<NodeType, list<NodeType>>> inGraph;
526 output list<tuple<NodeType, list<NodeType>>> outGraph;
527
528 partial function EqualFunc
529 "Given two nodes, returns true if they are equal, otherwise false."
530 input NodeType inNode1;
531 input NodeType inNode2;
532 output Boolean isEqual;
533 end EqualFunc;
534
535 algorithm
536 outGraph := matchcontinue inGraph
537 local
538 NodeType node;
539 list<NodeType> rest;
540 list<tuple<NodeType, list<NodeType>>> restGraph;
541
542 case {} then {};
543 case (node,rest)::restGraph
544 algorithm
545 ✗ true := inEqualFunc(node, inNode);
546 ✗ rest := List.unionList({rest, {inVertex}});
547 ✗ restGraph := insertNodetoGraph(inNode, inVertex, inEqualFunc, restGraph);
548 ✗ then (node,rest)::restGraph;
549 case (node,rest)::restGraph
550 algorithm
551 ✗ false := inEqualFunc(node, inNode);
552 ✗ restGraph := insertNodetoGraph(inNode, inVertex, inEqualFunc, restGraph);
553 ✗ then (node,rest)::restGraph;
554 end matchcontinue;
555 end insertNodetoGraph;
556
557 public function allReachableNodes
558 "This function searches for a starting node in M
559 all reachable nodes. Call with start node in M: allReachableNodes((start,{}),graph,eqFn)."
560 input tuple<list<NodeType>,list<NodeType>> intmpstorage;//(M,L)
561 input list<tuple<NodeType, list<NodeType>>> inGraph;
562 input EqualFunc inEqualFunc;
563 output list<NodeType> reachableNodes "Is NONE() on error to prevent recursion";
564
565 partial function EqualFunc
566 "Given two nodes, returns true if they are equal, otherwise false."
567 input NodeType inNode1;
568 input NodeType inNode2;
569 output Boolean isEqual;
570 end EqualFunc;
571
572 algorithm
573 ✗ SOME(reachableNodes) := allReachableNodesWork(intmpstorage,inGraph,inEqualFunc);
574 end allReachableNodes;
575
576 protected function allReachableNodesWork
577 "This function searches for a starting node in M
578 all reachable nodes. Call with start node in M: allReachableNodes((start,{}),graph,eqFn)."
579 input tuple<list<NodeType>,list<NodeType>> intmpstorage;//(M,L)
580 input list<tuple<NodeType, list<NodeType>>> inGraph;
581 input EqualFunc inEqualFunc;
582 output Option<list<NodeType>> reachableNodes "Is NONE() on error to prevent recursion";
583
584 partial function EqualFunc
585 "Given two nodes, returns true if they are equal, otherwise false."
586 input NodeType inNode1;
587 input NodeType inNode2;
588 output Boolean isEqual;
589 end EqualFunc;
590
591 algorithm
592 reachableNodes := matchcontinue intmpstorage
593 local
594 NodeType node;
595 list<NodeType> edges,M,L;
596 case ({},L)
597 algorithm
598 ✗ L := listReverse(L);
599 then SOME(L);
600
601 case (node::M,L)
602 algorithm
603 ✗ List.getMemberOnTrue(node,L,inEqualFunc);
604 ✗ then allReachableNodesWork((M,L),inGraph,inEqualFunc);
605
606 case (node::M,L)
607 algorithm
608 L := node::L;
609 //print(" List size 1 " + intString(listLength(L)) + "\n");
610 ✗ (_,edges) := findNodeInGraph(node,inGraph,inEqualFunc);
611 //print(" List size 2 " + intString(listLength(edges)) + "\n");
612 //print(" List size 3 " + intString(listLength(edges)) + "\n");
613 ✗ M := listAppend(edges,M);
614 //print("Start new round!\n");
615 ✗ then allReachableNodesWork((M,L),inGraph,inEqualFunc);
616 else
617 algorithm
618 ✗ Error.addSourceMessage(Error.INTERNAL_ERROR, {"Graph.allReachableNodes failed."}, sourceInfo());
619 then NONE();
620 end matchcontinue;
621 end allReachableNodesWork;
622
623 public function partialDistance2color
624 "A greedy partial distance-2 coloring algorithm.
625 procedure G REEDY PARTIAL D2C OLORING(Gb = (V1 ,V2 , E))
626 Let u1 , u2 , . . ., un be a given ordering of V2 , where n = |V2 |
627 Initialize forbiddenColors with some value a in V2
628 for i = 1 to n do
629 for each vertex w such that (ui , w) in E do
630 for each colored vertex x such that (w, x) in E do
631 forbiddenColors[color[x]] <- ui
632 color[ui ] <- min{c > 0 : forbiddenColors[c] = ui }
633 "
634 input list<NodeType> toColorNodes;
635 input array<Option<list<NodeType>>> inforbiddenColor;
636 input list<Integer> inColors;
637 input list<tuple<NodeType, list<NodeType>>> inGraph;
638 input list<tuple<NodeType, list<NodeType>>> inGraphT;
639 input array<Integer> inColored;
640 input EqualFunc inEqualFunc;
641 input PrintFunc inPrintFunc;
642 output array<Integer> outColored;
643
644 partial function EqualFunc
645 "Given two nodes, returns true if they are equal, otherwise false."
646 input NodeType inNode1;
647 input NodeType inNode2;
648 output Boolean isEqual;
649 end EqualFunc;
650
651 partial function PrintFunc
652 "Given two nodes, returns true if they are equal, otherwise false."
653 input list<NodeType> inNode1;
654 input String inName;
655 end PrintFunc;
656 algorithm
657 outColored := matchcontinue toColorNodes
658 local
659 NodeType node;
660 list<NodeType> rest, nodes;
661 array<Option<list<NodeType>>> forbiddenColor;
662 array<Integer> colored;
663 Integer color, index;
664 case {} then inColored;
665 case node::rest
666 algorithm
667 ✗ index := arrayLength(inColored) - listLength(rest);
668 ✗ (_,nodes) := findNodeInGraph(node, inGraphT, inEqualFunc);
669 ✗ forbiddenColor := addForbiddenColors(node, nodes, inColored, inforbiddenColor, inGraph, inEqualFunc, inPrintFunc);
670 ✗ color := arrayFindMinColorIndex(forbiddenColor, node, 1, arrayLength(inColored)+1, inEqualFunc, inPrintFunc);
671 ✗ colored := arrayUpdate(inColored, index, color);
672 ✗ colored := partialDistance2color(rest, forbiddenColor, inColors, inGraph, inGraphT, colored, inEqualFunc, inPrintFunc);
673 then colored;
674 else
675 algorithm
676 ✗ Error.addSourceMessage(Error.INTERNAL_ERROR, {"Graph.partialDistance2color failed."}, sourceInfo());
677 ✗ then fail();
678 end matchcontinue;
679 end partialDistance2color;
680
681 protected function addForbiddenColors
682 input NodeType inNode;
683 input list<NodeType> inNodes;
684 input array<Integer> inColored;
685 input array<Option<list<NodeType>>> inForbiddenColor;
686 input list<tuple<NodeType, list<NodeType>>> inGraph;
687 input EqualFunc inEqualFunc;
688 input PrintFunc inPrintFunc;
689 output array<Option<list<NodeType>>> outForbiddenColor;
690
691 partial function EqualFunc
692 "Given two nodes, returns true if they are equal, otherwise false."
693 input NodeType inNode1;
694 input NodeType inNode2;
695 output Boolean isEqual;
696 end EqualFunc;
697
698 partial function PrintFunc
699 "Given two nodes, returns true if they are equal, otherwise false."
700 input list<NodeType> inNode1;
701 input String inName;
702 end PrintFunc;
703
704 algorithm
705 outForbiddenColor := matchcontinue(inNodes, inForbiddenColor)
706 local
707 NodeType node;
708 list<NodeType> rest,nodes;
709 list<Integer> indexes;
710 list<Integer> indexesColor;
711 array<Option<list<NodeType>>> forbiddenColor,forbiddenColor1;
712 case ({}, _) then inForbiddenColor;
713 case (node::rest, forbiddenColor)
714 algorithm
715 ✗ (_,nodes) := findNodeInGraph(node, inGraph, inEqualFunc);
716 ✗ indexes := List.map3(nodes, findIndexofNodeInGraph, inGraph, inEqualFunc, 1);
717 ✗ indexes := List.select1(indexes, arrayElemetGtZero, inColored);
718 ✗ indexesColor := List.map1(indexes, getArrayElem, inColored);
719 ✗ List.map2_0(indexesColor, arrayUpdateListAppend, forbiddenColor, SOME({inNode}));
720 ✗ forbiddenColor1 := addForbiddenColors(inNode, rest, inColored, forbiddenColor, inGraph, inEqualFunc, inPrintFunc);
721 then forbiddenColor1;
722 else
723 algorithm
724 ✗ Error.addSourceMessage(Error.INTERNAL_ERROR, {"Graph.addForbiddenColors failed."}, sourceInfo());
725 ✗ then fail();
726 end matchcontinue;
727 end addForbiddenColors;
728
729 protected function getArrayElem
730 input Integer inIndex;
731 input array<Type_a> inArray;
732 output Type_a outElem;
733 replaceable type Type_a subtypeof Any;
734 algorithm
735 ✗ outElem := arrayGet(inArray,inIndex);
736 end getArrayElem;
737
738 protected function arrayUpdateListAppend
739 input Integer inIndex;
740 input array<Option<list<NodeType>>> inArray;
741 input Option<list<NodeType>> inNode;
742 replaceable type NodeType subtypeof Any;
743 algorithm
744 () := matchcontinue inArray
745 local
746 case _
747 algorithm
748 ✗ arrayUpdate(inArray, inIndex, inNode);
749 then ();
750 else
751 algorithm
752 ✗ Error.addSourceMessage(Error.INTERNAL_ERROR, {"Graph.arrayUpdateListAppend failed."}, sourceInfo());
753 ✗ then fail();
754 end matchcontinue;
755 end arrayUpdateListAppend;
756
757 protected function arrayElemetGtZero
758 input Integer inIndex;
759 input array<Integer> inArray;
760 output Boolean outBoolean;
761 algorithm
762 ✗ outBoolean := intGt(arrayGet(inArray, inIndex), 0);
763 end arrayElemetGtZero;
764
765 protected function arrayFindMinColorIndex
766 input array<Option<list<NodeType>>> inForbiddenColor;
767 input NodeType inNode;
768 input Integer inIndex;
769 input Integer inmaxIndex;
770 input EqualFunc inEqualFunc;
771 input PrintFunc inPrintFunc;
772 output Integer outColor;
773
774 partial function EqualFunc
775 "Given two nodes, returns true if they are equal, otherwise false."
776 input NodeType inNode1;
777 input NodeType inNode2;
778 output Boolean isEqual;
779 end EqualFunc;
780 partial function PrintFunc
781 "Given two nodes, returns true if they are equal, otherwise false."
782 input list<NodeType> inNode1;
783 input String inName;
784 end PrintFunc;
785 algorithm
786 outColor := matchcontinue inPrintFunc
787 local
788 list<NodeType> nodes;
789 Integer index;
790 case _
791 algorithm
792 ✗ NONE() := arrayGet(inForbiddenColor, inIndex);
793 //print("Found color on index : " + intString(inIndex) + "\n");
794 then inIndex;
795 case _
796 algorithm
797 ✗ SOME(nodes) := arrayGet(inForbiddenColor, inIndex);
798 //inPrintFunc(nodes,"FobiddenColors:" );
799 ✗ failure(List.getMemberOnTrue(inNode, nodes, inEqualFunc));
800 //print("Found color on index : " + intString(inIndex) + "\n");
801 then inIndex;
802 else
803 algorithm
804 ✗ SOME(nodes) := arrayGet(inForbiddenColor, inIndex);
805 //inPrintFunc(nodes,"FobiddenColors:" );
806 ✗ List.getMemberOnTrue(inNode, nodes, inEqualFunc);
807 //print("Not found color on index : " + intString(inIndex) + "\n");
808 ✗ index := arrayFindMinColorIndex(inForbiddenColor, inNode, inIndex+1, inmaxIndex, inEqualFunc, inPrintFunc);
809 then index;
810 end matchcontinue;
811 end arrayFindMinColorIndex;
812
813 public function printGraph
814 input list<tuple<NodeType, list<NodeType>>> inGraph;
815 input NodeToString inPrintFunc;
816 output String outString;
817
818 partial function NodeToString
819 input NodeType inNode;
820 output String outString;
821 end NodeToString;
822 algorithm
823 ✗ outString := stringDelimitList(List.map1(inGraph, printNode, inPrintFunc), "\n");
824 end printGraph;
825
826 public function printNode
827 input tuple<NodeType, list<NodeType>> inNode;
828 input NodeToString inPrintFunc;
829 output String outString;
830
831 partial function NodeToString
832 input NodeType inNode;
833 output String outString;
834 end NodeToString;
835 protected
836 NodeType node;
837 list<NodeType> edges;
838 String node_str;
839 String edges_str;
840 algorithm
841 ✗ (node, edges) := inNode;
842 ✗ node_str := inPrintFunc(node);
843 ✗ edges_str := stringDelimitList(List.map(edges, inPrintFunc), ", ");
844 ✗ outString := node_str + ": " + edges_str;
845 end printNode;
846
847 /* Functions for Integer graphs */
848
849 public function printGraphInt
850 "This function prints an Integer Graph.
851 Useful for debuging."
852 input list<tuple<Integer, list<Integer>>> inGraph;
853 algorithm
854 () := match inGraph
855 local
856 Integer node;
857 list<Integer> edges;
858 list<String> strEdges;
859 list<tuple<Integer, list<Integer>>> restGraph;
860 case {} then ();
861 case (node,edges)::restGraph
862 algorithm
863 ✗ print("Node : " + intString(node) + " Edges: ");
864 ✗ strEdges := List.map(edges, intString);
865 ✗ strEdges := List.map1(strEdges, stringAppend, " ");
866 ✗ List.map_0(strEdges, print);
867 ✗ print("\n");
868 ✗ printGraphInt(restGraph);
869 then ();
870 end match;
871 end printGraphInt;
872
873 public function printNodesInt
874 "This function prints an Integer List Nodes.
875 Useful for debuging."
876 input list<Integer> inListNodes;
877 input String inName;
878 algorithm
879 () := match inListNodes
880 local
881 list<String> strNodes;
882 case {}
883 algorithm
884 ✗ print(inName + "\n");
885 then ();
886 case _
887 algorithm
888 ✗ print(inName + " : ");
889 ✗ strNodes := List.map(inListNodes, intString);
890 ✗ strNodes := List.map1(strNodes, stringAppend, " ");
891 ✗ List.map_0(strNodes, print);
892 ✗ print("\n");
893 then ();
894 end match;
895 end printNodesInt;
896
897 public function allReachableNodesInt
898 "This function searches for a starting node in M
899 all reachabel nodes. Call with start nodes in M. The
900 result is collected in L."
901 input tuple<list<Integer>,list<Integer>> intmpstorage;//(M,L)
902 input array<tuple<Integer, list<Integer>>> inGraph;
903 input Integer inMaxGraphNode;
904 input Integer inMaxNodexIndex;
905 output list<Integer> reachableNodes;
906 algorithm
907 reachableNodes := matchcontinue intmpstorage
908 local
909 Integer node;
910 list<Integer> edges,M,L;
911 case ({},L) then L;
912 case (node::M,L)
913 algorithm
914 ✗ L := List.union(L,{node});
915 ✗ false := intGe(node,inMaxGraphNode);
916 ✗ (_,edges) := arrayGet(inGraph, node);
917 ✗ edges := List.filter1OnTrue(edges, List.notMember, L);
918 ✗ M := List.union(M,edges);
919 ✗ reachableNodes := allReachableNodesInt((M,L),inGraph,inMaxGraphNode,inMaxNodexIndex);
920 then reachableNodes;
921 case (node::M,L)
922 algorithm
923 ✗ L := List.union(L,{node});
924 ✗ true := intGe(node,inMaxGraphNode);
925 ✗ reachableNodes := allReachableNodesInt((M,L),inGraph,inMaxGraphNode,inMaxNodexIndex);
926 then reachableNodes;
927 else
928 algorithm
929 ✗ Error.addSourceMessage(Error.INTERNAL_ERROR, {"Graph.allReachableNodesInt failed."}, sourceInfo());
930 ✗ then fail();
931 end matchcontinue;
932 end allReachableNodesInt;
933
934 public function partialDistance2colorInt
935 "A greedy partial distance-2 coloring algorithm.
936 procedure GREEDY PARTIAL D2COLORING(Gb = (V1 ,V2 , E))
937 Let u1 , u2 , . . ., un be a given ordering of V2 , where n = |V2 |
938 Initialize forbiddenColors with some value a in V2
939 for i = 1 to n do
940 for each vertex w such that (ui , w) in E do
941 for each colored vertex x such that (w, x) in E do
942 forbiddenColors[color[x]] <- ui
943 color[ui ] <- min{c > 0 : forbiddenColors[c] = ui }
944
945 The colors of each w's colored vertices are kept as a bit set, so the inner
946 loop is a union of bit sets rather than a walk over every x of w for every
947 ui of w, which is quadratic in the degree of w."
948 input list<tuple<Integer, list<Integer>>> inGraphT "each vertex of V2 with its neighbours in V1";
949 input Integer numNodes "size of V1";
950 input array<Integer> inColored "color per vertex of V2, 0 while uncolored";
951 protected
952 constant Integer wordBits = 30;
953 constant Integer fullWord = 1073741823;
954 Integer node, color, words = 1, usedWords = 1, k, w, bit;
955 list<Integer> nodes;
956 array<array<Integer>> nodeColors = arrayCreate(numNodes, arrayCreate(0, 0));
957 array<Integer> forbidden = arrayCreate(1, 0), colors;
958 algorithm
959
1/2
✓ Branch 0 taken 3040 times.
✗ Branch 1 not taken.
 19229 for i in 1:numNodes loop
960 16189 arrayUpdate(nodeColors, i, arrayCreate(words, 0));
961 end for;
962
2/2
✓ Branch 0 taken 16221 times.
✓ Branch 1 taken 3040 times.
 19261 for tpl in inGraphT loop
963 16221 (node, nodes) := tpl;
964
1/2
✓ Branch 0 taken 16221 times.
✗ Branch 1 not taken.
 33312 for j in 1:usedWords loop
965 17091 arrayUpdate(forbidden, j, 0);
966 end for;
967
2/2
✓ Branch 0 taken 77480 times.
✓ Branch 1 taken 16221 times.
 93701 for n in nodes loop
968 77480 colors := arrayGet(nodeColors, n);
969
1/2
✓ Branch 0 taken 77480 times.
✗ Branch 1 not taken.
 184346 for j in 1:usedWords loop
970 106866 arrayUpdate(forbidden, j, intBitOr(arrayGet(forbidden, j), arrayGet(colors, j)));
971 end for;
972 end for;
973 color := 0;
974 k := 1;
975
2/2
✓ Branch 0 taken 16694 times.
✓ Branch 1 taken 16221 times.
 32915 while color == 0 loop
976
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 16676 times.
 16694 if k > usedWords then
977 18 color := (k - 1) * wordBits + 1;
978 else
979 16676 w := arrayGet(forbidden, k);
980
2/2
✓ Branch 0 taken 16203 times.
✓ Branch 1 taken 473 times.
 16676 if w <> fullWord then
981 bit := 0;
982
2/2
✓ Branch 0 taken 35932 times.
✓ Branch 1 taken 16203 times.
 52135 while intBitAnd(w, intBitLShift(1, bit)) <> 0 loop
983 35932 bit := bit + 1;
984 end while;
985 16203 color := (k - 1) * wordBits + bit + 1;
986 end if;
987 16676 k := k + 1;
988 end if;
989 end while;
990 16221 arrayUpdate(inColored, node, color);
991 16221 k := intDiv(color - 1, wordBits) + 1;
992
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 16203 times.
 16221 if k > words then
993 18 words := 2 * words;
994 18 forbidden := Array.expandToSize(words, forbidden, 0);
995
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
 1783 for i in 1:numNodes loop
996 1765 arrayUpdate(nodeColors, i, Array.expandToSize(words, arrayGet(nodeColors, i), 0));
997 end for;
998 end if;
999 usedWords := intMax(usedWords, k);
1000 16221 bit := intBitLShift(1, intMod(color - 1, wordBits));
1001
2/2
✓ Branch 0 taken 77480 times.
✓ Branch 1 taken 16221 times.
 93701 for n in nodes loop
1002 77480 colors := arrayGet(nodeColors, n);
1003 77480 arrayUpdate(colors, k, intBitOr(arrayGet(colors, k), bit));
1004 end for;
1005 end for;
1006 end partialDistance2colorInt;
1007
1008 public function filterGraph
1009 "Removes any node for which the given function evaluates to false, as well as
1010 any edge pointing at that node."
1011 input list<tuple<NodeType, list<NodeType>>> inGraph;
1012 input CondFunc inCondFunc;
1013 output list<tuple<NodeType, list<NodeType>>> outGraph;
1014
1015 partial function CondFunc
1016 input NodeType inNode;
1017 output Boolean outCond;
1018 end CondFunc;
1019 algorithm
1020 144 outGraph := List.accumulateMapAccum(inGraph, function filterGraph2(inCondFunc = inCondFunc));
1021 end filterGraph;
1022
1023 protected function filterGraph2
1024 "Helper function to filterGraph."
1025 input tuple<NodeType, list<NodeType>> inNode;
1026 input CondFunc inCondFunc;
1027 input list<tuple<NodeType, list<NodeType>>> inAccumGraph;
1028 output list<tuple<NodeType, list<NodeType>>> outNode;
1029
1030 partial function CondFunc
1031 input NodeType inNode;
1032 output Boolean outCond;
1033 end CondFunc;
1034 algorithm
1035 outNode := matchcontinue inNode
1036 local
1037 NodeType node;
1038 list<NodeType> edges;
1039
1040 case (node, _)
1041 algorithm
1042
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 290 times.
✓ Branch 4 taken 284 times.
✓ Branch 5 taken 6 times.
 290 false := inCondFunc(node);
1043 then
1044 inAccumGraph;
1045
1046 case (node, edges)
1047 algorithm
1048 284 edges := List.filterOnTrue(edges, inCondFunc);
1049 284 then
1050 (node, edges) :: inAccumGraph;
1051
1052 end matchcontinue;
1053 end filterGraph2;
1054
1055 public function merge "Merges the nodes of two different graphs. Needs an ordering function in order to be efficient."
1056 input list<tuple<NodeType, list<NodeType>>> graph1;
1057 input list<tuple<NodeType, list<NodeType>>> graph2;
1058 input EqualFunc eqFunc;
1059 input CompareFunc compareFunc;
1060 output list<tuple<NodeType, list<NodeType>>> graph;
1061 partial function EqualFunc
1062 "Given two nodes, returns true if they are equal, otherwise false."
1063 input NodeType inNode1;
1064 input NodeType inNode2;
1065 output Boolean isEqual;
1066 end EqualFunc;
1067 partial function CompareFunc
1068 "Given two nodes, returns true if the first is ordered before the second."
1069 input tuple<NodeType,list<NodeType>> inNode1;
1070 input tuple<NodeType,list<NodeType>> inNode2;
1071 output Boolean isEqual;
1072 end CompareFunc;
1073 algorithm
1074 ✗ graph := merge2(List.sort(listAppend(graph1,graph2), compareFunc), eqFunc, {});
1075 end merge;
1076
1077 protected function merge2
1078 input list<tuple<NodeType, list<NodeType>>> inGraph;
1079 input EqualFunc eqFunc;
1080 input list<tuple<NodeType, list<NodeType>>> inAcc;
1081 output list<tuple<NodeType, list<NodeType>>> graph;
1082 partial function EqualFunc
1083 "Given two nodes, returns true if they are equal, otherwise false."
1084 input NodeType inNode1;
1085 input NodeType inNode2;
1086 output Boolean isEqual;
1087 end EqualFunc;
1088 algorithm
1089 graph := match inGraph
1090 local
1091 list<tuple<NodeType, list<NodeType>>> rest;
1092 tuple<NodeType, list<NodeType>> node;
1093 NodeType n1,n2;
1094 list<NodeType> e1,e2;
1095 Boolean b;
1096 ✗ case {} then listReverse(inAcc);
1097 ✗ case {node} then listReverse(node::inAcc);
1098 case (n1,e1)::(n2,e2)::rest
1099 algorithm
1100 ✗ b := eqFunc(n1,n2);
1101 ✗ (node,rest) := merge3(b,n1,e1,n2,e2,rest,eqFunc);
1102 ✗ then merge2(rest,eqFunc,node::inAcc);
1103 end match;
1104 end merge2;
1105
1106 protected function merge3
1107 input Boolean b;
1108 input NodeType n1;
1109 input list<NodeType> e1;
1110 input NodeType n2;
1111 input list<NodeType> e2;
1112 input list<tuple<NodeType, list<NodeType>>> rest;
1113 input EqualFunc eqFunc;
1114 output tuple<NodeType, list<NodeType>> elt;
1115 output list<tuple<NodeType, list<NodeType>>> outRest;
1116 partial function EqualFunc
1117 "Given two nodes, returns true if they are equal, otherwise false."
1118 input NodeType inNode1;
1119 input NodeType inNode2;
1120 output Boolean isEqual;
1121 end EqualFunc;
1122 algorithm
1123 (elt,outRest) := match b
1124 ✗ case true then ((n1,List.unionOnTrue(e1,e2,eqFunc)),rest);
1125 ✗ case false then ((n1,e1),(n2,e2)::rest);
1126 end match;
1127 end merge3;
1128
1129 annotation(__OpenModelica_Interface="util");
1130 end Graph;
1131