OMCompiler/Compiler/Util/SBGraph.mo - Linux GNU 11.4.0 Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	21.9%	14 / 0 / 64
Functions:	-%	0 / 1 / 1
Branches:	1.7%	1 / 0 / 58

    OMCompiler/Compiler/Util/SBGraph.mo
    
        Line
        Branch
        Exec
        Source
      
        /*
      
         * This file is part of OpenModelica.
      
         *
      
         * Copyright (c) 1998-2026, 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 AGPL VERSION 3 LICENSE OR
      
         * THIS OSMC PUBLIC LICENSE (OSMC-PL) VERSION 1.8.
      
         * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS PROGRAM CONSTITUTES
      
         * RECIPIENT'S ACCEPTANCE OF THE OSMC PUBLIC LICENSE OR THE GNU AGPL
      
         * VERSION 3, ACCORDING TO RECIPIENTS CHOICE.
      
         *
      
         * The OpenModelica software and the OSMC (Open Source Modelica Consortium)
      
         * Public License (OSMC-PL) are obtained from OSMC, either from the above
      
         * address, from the URLs:
      
         * http://www.openmodelica.org or
      
         * https://github.com/OpenModelica/ or
      
         * http://www.ida.liu.se/projects/OpenModelica,
      
         * and in the OpenModelica distribution.
      
         *
      
         * GNU AGPL version 3 is obtained from:
      
         * https://www.gnu.org/licenses/licenses.html#GPL
      
         *
      
         * 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 package SBGraph<VertexT, EdgeT>
      
          import Vector;
      
        protected
      
          import Error;
      
          import List;
      
          import SBSet;
      
          import StringUtil;
      
        public
      
          partial function VertexEq
      
            input VertexT v1;
      
            input VertexT v2;
      
            output Boolean equal;
      
          end VertexEq;
      
          partial function EdgeEq
      
            input EdgeT e1;
      
            input EdgeT e2;
      
            output Boolean equal;
      
          end EdgeEq;
      
          partial function VertexStr
      
            input VertexT v;
      
            output String str;
      
          end VertexStr;
      
          partial function EdgeStr
      
            input EdgeT e;
      
            output String str;
      
          end EdgeStr;
      
          type VertexDescriptor = Integer;
      
          // types of sets
      
          // V - generic vertex set (F u U)
      
          // F - function/equation vertex set
      
          // U - unknown/variable vertex set
      
          // E - edge set
      
          type SetType = enumeration(V, F, U, E);
      
          function edge_finder
      
            input Integer index;
      
            input EdgeT e;
      
            input Vector<EdgeT> edges;
      
            input EdgeEq eqFn;
      
            output Boolean matching = eqFn(e, Vector.get(edges, index));
      
          end edge_finder;
      
          uniontype IncidenceList<VertexT, EdgeT>
      
          public
      
            record INCIDENCE_LIST
      
              Vector<VertexT> vertices;
      
              Vector<EdgeT> edges;
      
              Vector<list<Integer>> graph;
      
              VertexEq vertEqFn;
      
              EdgeEq edgeEqFn;
      
              VertexStr vertToString;
      
              EdgeStr edgeToString;
      
            end INCIDENCE_LIST;
      
            function new
      
              input VertexEq vertexEq;
      
              input EdgeEq edgeEq;
      
              input VertexStr vertexStr;
      
              input EdgeStr edgeStr;
      
              output IncidenceList<VertexT, EdgeT> il;
      
            protected
      
              type Indices = list<Integer>;
      
            algorithm
      
        3
              il := INCIDENCE_LIST(Vector.new<VertexT>(), Vector.new<EdgeT>(), Vector.new<Indices>(), vertexEq, edgeEq, vertexStr, edgeStr);
      
            end new;
      
            function getRow
      
              input IncidenceList<VertexT, EdgeT> il;
      
              input VertexDescriptor d;
      
              output list<Integer> row;
      
            algorithm
      
        23
              row := Vector.get(il.graph, d);
      
            end getRow;
      
            function addVertex
      
              input IncidenceList<VertexT, EdgeT> il;
      
              input VertexT v;
      
              output VertexDescriptor d;
      
            algorithm
      
        23
              Vector.push(il.vertices, v);
      
        23
              Vector.push(il.graph, {});
      
        23
              d := Vector.size(il.vertices);
      
            end addVertex;
      
            function findVertex
      
              input IncidenceList<VertexT, EdgeT> il;
      
              input PredFn predFn;
      
              output Option<VertexDescriptor> od;
      
              partial function PredFn
      
                input VertexT e;
      
                output Boolean res;
      
              end PredFn;
      
            protected
      
              Integer index;
      
            algorithm
      
        ✗
              (_, index) := Vector.find(il.vertices, predFn);
      
        ✗
              od := if index > 0 then SOME(index) else NONE();
      
            end findVertex;
      
            function getVertex
      
              input IncidenceList<VertexT, EdgeT> il;
      
              input VertexDescriptor d;
      
              output VertexT v;
      
            algorithm
      
        143
              v := Vector.get(il.vertices, d);
      
            end getVertex;
      
            function getVerticesFromSet
      
              "kabdelhak: seems inefficient. There has to be a better solution"
      
              input IncidenceList<VertexT, EdgeT> il;
      
              input SBSet set;
      
              input getSetFn getSet;
      
              output list<VertexT> set_vertices = {};
      
              partial function getSetFn
      
                input VertexT v;
      
                output SBSet s;
      
              end getSetFn;
      
            algorithm
      
        ✗
              for v in vertices(il) loop
      
        ✗
                if not SBSet.isEmpty(SBSet.intersection(getSet(v), set)) then
      
                  set_vertices := v :: set_vertices;
      
                end if;
      
              end for;
      
            end getVerticesFromSet;
      
            function addEdge
      
              input IncidenceList<VertexT, EdgeT> il;
      
              input VertexDescriptor d1;
      
              input VertexDescriptor d2;
      
              input EdgeT e;
      
              output Integer ei;
      
            protected
      
              list<Integer> eil;
      
            algorithm
      
        15
              eil := Vector.get(il.graph, d1);
      
        15
              ei := List.positionOnTrue(eil,
      
                function edge_finder(e = e, edges = il.edges, eqFn = il.edgeEqFn));
      
          1/2✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.

        15
              if ei == -1 then
      
        15
                Vector.push(il.edges, e);
      
        15
                ei := Vector.size(il.edges);
      
        15
                Vector.update(il.graph, d1, ei :: eil);
      
        30
                Vector.update(il.graph, d2, ei :: Vector.get(il.graph, d2));
      
              else
      
        ✗
                Vector.update(il.edges, ei, e);
      
              end if;
      
            end addEdge;
      
            function getEdge
      
              input IncidenceList<VertexT, EdgeT> il;
      
              input Integer d;
      
              output EdgeT e;
      
            algorithm
      
        12
              e := Vector.get(il.edges, d);
      
            end getEdge;
      
            function isEmpty
      
              input IncidenceList<VertexT, EdgeT> il;
      
              output Boolean empty = Vector.size(il.vertices) == 0;
      
            end isEmpty;
      
            function vertexCount
      
              input IncidenceList<VertexT, EdgeT> il;
      
              output Integer count = Vector.size(il.vertices);
      
            end vertexCount;
      
            function edgeCount
      
              input IncidenceList<VertexT, EdgeT> il;
      
              output Integer count = Vector.size(il.edges);
      
            end edgeCount;
      
            function vertices
      
              input IncidenceList<VertexT, EdgeT> il;
      
              output list<VertexT> vl = Vector.toList(il.vertices);
      
            end vertices;
      
            function edges
      
              input IncidenceList<VertexT, EdgeT> il;
      
              output list<EdgeT> el = Vector.toList(il.edges);
      
            end edges;
      
            function toString
      
              input IncidenceList<VertexT, EdgeT> il;
      
              output String str;
      
            protected
      
              // somehow this is needed and can't be applied directly
      
              VertexStr vertToString = il.vertToString;
      
              EdgeStr edgeToString = il.edgeToString;
      
            algorithm
      
        ✗
              str := StringUtil.headline_2("Set-Based Graph") + "\n";
      
        ✗
              str := str + stringDelimitList(list(vertToString(v) for v in Vector.toList(il.vertices)), "\n") + "\n";
      
        ✗
              str := str + stringDelimitList(list(edgeToString(e) for e in Vector.toList(il.edges)), "\n") + "\n";
      
            end toString;
      
          end IncidenceList;
      
          uniontype BipartiteIncidenceList<VertexT, EdgeT>
      
          public
      
            record BIPARTITE_INCIDENCE_LIST
      
              Vector<VertexT> F_vertices;
      
              Vector<VertexT> U_vertices;
      
              Vector<EdgeT> edges;
      
              Vector<list<Integer>> graph;
      
              VertexEq vertEqFn;
      
              EdgeEq edgeEqFn;
      
              VertexStr vertToString;
      
              EdgeStr edgeToString;
      
            end BIPARTITE_INCIDENCE_LIST;
      
            function new
      
              input VertexEq vertexEq;
      
              input EdgeEq edgeEq;
      
              input VertexStr vertexStr;
      
              input EdgeStr edgeStr;
      
              output BipartiteIncidenceList<VertexT, EdgeT> il;
      
            protected
      
              type Indices = list<Integer>;
      
            algorithm
      
        ✗
              il := BIPARTITE_INCIDENCE_LIST(Vector.new<VertexT>(), Vector.new<VertexT>(), Vector.new<EdgeT>(), Vector.new<Indices>(), vertexEq, edgeEq, vertexStr, edgeStr);
      
            end new;
      
            function getRow
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input VertexDescriptor d;
      
              output list<Integer> row = Vector.get(il.graph, d);
      
            end getRow;
      
            function addVertex
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input VertexT v;
      
              input SetType ST;
      
              output VertexDescriptor d;
      
            algorithm
      
              d := match ST
      
                case SetType.F algorithm
      
        ✗
                  Vector.push(il.F_vertices, v);
      
        ✗
                  Vector.push(il.graph, {});
      
        ✗
                then Vector.size(il.F_vertices);
      
                case SetType.U algorithm
      
        ✗
                  Vector.push(il.U_vertices, v);
      
        ✗
                  Vector.push(il.graph, {});
      
        ✗
                then Vector.size(il.U_vertices);
      
                else algorithm
      
        ✗
                  Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: F,U", sourceInfo());
      
        ✗
                then fail();
      
              end match;
      
            end addVertex;
      
            function findVertex
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input SetType ST;
      
              input PredFn predFn;
      
              output Option<VertexDescriptor> od;
      
              partial function PredFn
      
                input VertexT e;
      
                output Boolean res;
      
              end PredFn;
      
            protected
      
              Integer index;
      
            algorithm
      
              index := match ST
      
        ✗
                case SetType.F algorithm (_, index) := Vector.find(il.F_vertices, predFn); then index;
      
        ✗
                case SetType.U algorithm (_, index) := Vector.find(il.U_vertices, predFn); then index;
      
                else algorithm
      
        ✗
                  Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: F,U", sourceInfo());
      
        ✗
                then fail();
      
              end match;
      
        ✗
              od := if index > 0 then SOME(index) else NONE();
      
            end findVertex;
      
            function getVertex
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input VertexDescriptor d;
      
              input SetType ST;
      
              output VertexT v;
      
            algorithm
      
              v := match ST
      
        ✗
                case SetType.F  then Vector.get(il.F_vertices, d);
      
        ✗
                case SetType.U  then Vector.get(il.U_vertices, d);
      
                else algorithm
      
        ✗
                  Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: F,U", sourceInfo());
      
        ✗
                then fail();
      
              end match;
      
            end getVertex;
      
            function getVerticesFromSet
      
              "kabdelhak: seems inefficient. There has to be a better solution"
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input SBSet set;
      
              input SetType ST;
      
              input getSetFn getSet;
      
              output list<VertexT> set_vertices = {};
      
              partial function getSetFn
      
                input VertexT v;
      
                output SBSet s;
      
              end getSetFn;
      
            algorithm
      
        ✗
              for v in vertices(il, ST) loop
      
        ✗
                if not SBSet.isEmpty(SBSet.intersection(getSet(v), set)) then
      
                  set_vertices := v :: set_vertices;
      
                end if;
      
              end for;
      
            end getVerticesFromSet;
      
            function addEdge
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input VertexDescriptor d1;
      
              input VertexDescriptor d2;
      
              input EdgeT e;
      
              output Integer ei;
      
            protected
      
              list<Integer> eil;
      
            algorithm
      
        ✗
              eil := getRow(il, d1);
      
        ✗
              ei := List.positionOnTrue(eil,
      
                function edge_finder(e = e, edges = il.edges, eqFn = il.edgeEqFn));
      
        ✗
              if ei == -1 then
      
        ✗
                Vector.push(il.edges, e);
      
        ✗
                ei := Vector.size(il.edges);
      
        ✗
                Vector.update(il.graph, d1, ei :: eil);
      
        ✗
                Vector.update(il.graph, d2, ei :: Vector.get(il.graph, d2));
      
              else
      
        ✗
                Vector.update(il.edges, ei, e);
      
              end if;
      
            end addEdge;
      
            function getEdgesFromSet
      
              "kabdelhak: seems inefficient. There has to be a better solution"
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input SBSet set;
      
              input getSetFn getSet;
      
              output list<EdgeT> set_edges = {};
      
              partial function getSetFn
      
                input EdgeT e;
      
                output SBSet s;
      
              end getSetFn;
      
            algorithm
      
        ✗
              for e in edges(il) loop
      
        ✗
                if not SBSet.isEmpty(SBSet.intersection(getSet(e), set)) then
      
                  set_edges := e :: set_edges;
      
                end if;
      
              end for;
      
            end getEdgesFromSet;
      
            function getEdge
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input Integer d;
      
              output EdgeT e = Vector.get(il.edges, d);
      
            end getEdge;
      
            function isEmpty
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              output Boolean empty = (Vector.size(il.F_vertices) == 0) and (Vector.size(il.U_vertices) == 0);
      
            end isEmpty;
      
            function vertexCount
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input SetType ST = SetType.V;
      
              output Integer count;
      
            algorithm
      
              count := match ST
      
        ✗
                case SetType.V then Vector.size(il.F_vertices) + Vector.size(il.U_vertices);
      
        ✗
                case SetType.F then Vector.size(il.F_vertices);
      
        ✗
                case SetType.U then Vector.size(il.U_vertices);
      
                else algorithm
      
        ✗
                  Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: V,F,U", sourceInfo());
      
        ✗
                then fail();
      
              end match;
      
            end vertexCount;
      
            function edgeCount
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              output Integer count = Vector.size(il.edges);
      
            end edgeCount;
      
            function vertices
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              input SetType ST;
      
              output list<VertexT> vl;
      
            algorithm
      
              vl := match ST
      
        ✗
                case SetType.V then listAppend(Vector.toList(il.F_vertices), Vector.toList(il.U_vertices));
      
        ✗
                case SetType.F then Vector.toList(il.F_vertices);
      
        ✗
                case SetType.U then Vector.toList(il.U_vertices);
      
                else algorithm
      
        ✗
                  Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: V,F,U", sourceInfo());
      
        ✗
                then fail();
      
              end match;
      
            end vertices;
      
            function edges
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              output list<EdgeT> el = Vector.toList(il.edges);
      
            end edges;
      
            function toString
      
              input BipartiteIncidenceList<VertexT, EdgeT> il;
      
              output String str;
      
            protected
      
              VertexStr vertToString;
      
              EdgeStr edgeToString;
      
            algorithm
      
        ✗
              BIPARTITE_INCIDENCE_LIST(vertToString = vertToString, edgeToString = edgeToString) := il;
      
        ✗
              str := StringUtil.headline_2("Set-Based Graph") + "\n"
      
                     + StringUtil.headline_3("F-Vertices") + "\n"
      
                     + stringDelimitList(list(vertToString(v) for v in Vector.toList(il.F_vertices)), "\n") + "\n"
      
                     + StringUtil.headline_3("U-Vertices") + "\n"
      
                     + stringDelimitList(list(vertToString(v) for v in Vector.toList(il.U_vertices)), "\n") + "\n"
      
                     + StringUtil.headline_3("Edges") + "\n"
      
                     + stringDelimitList(list(edgeToString(e) for e in Vector.toList(il.edges)), "\n") + "\n";
      
            end toString;
      
            function setTypeString
      
              input SetType ST;
      
              output String str;
      
            algorithm
      
              str := match ST
      
                case SetType.V    then "V (generic vertex set)";
      
                case SetType.F    then "F (function vertex set)";
      
                case SetType.U    then "U (unknown vertex set)";
      
                case SetType.E    then "E (edge set)";
      
                else getInstanceName() + " ERROR";
      
              end match;
      
            end setTypeString;
      
          end BipartiteIncidenceList;
      
          annotation(__OpenModelica_Interface="util");
      
        end SBGraph;

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 SBGraph<VertexT, EdgeT>
37			import Vector;
38
39			protected
40			import Error;
41			import List;
42			import SBSet;
43			import StringUtil;
44
45			public
46			partial function VertexEq
47			input VertexT v1;
48			input VertexT v2;
49			output Boolean equal;
50			end VertexEq;
51
52			partial function EdgeEq
53			input EdgeT e1;
54			input EdgeT e2;
55			output Boolean equal;
56			end EdgeEq;
57
58			partial function VertexStr
59			input VertexT v;
60			output String str;
61			end VertexStr;
62
63			partial function EdgeStr
64			input EdgeT e;
65			output String str;
66			end EdgeStr;
67
68			type VertexDescriptor = Integer;
69
70			// types of sets
71			// V - generic vertex set (F u U)
72			// F - function/equation vertex set
73			// U - unknown/variable vertex set
74			// E - edge set
75			type SetType = enumeration(V, F, U, E);
76
77			function edge_finder
78			input Integer index;
79			input EdgeT e;
80			input Vector<EdgeT> edges;
81			input EdgeEq eqFn;
82			output Boolean matching = eqFn(e, Vector.get(edges, index));
83			end edge_finder;
84
85			uniontype IncidenceList<VertexT, EdgeT>
86
87			public
88			record INCIDENCE_LIST
89			Vector<VertexT> vertices;
90			Vector<EdgeT> edges;
91			Vector<list<Integer>> graph;
92			VertexEq vertEqFn;
93			EdgeEq edgeEqFn;
94			VertexStr vertToString;
95			EdgeStr edgeToString;
96			end INCIDENCE_LIST;
97
98			function new
99			input VertexEq vertexEq;
100			input EdgeEq edgeEq;
101			input VertexStr vertexStr;
102			input EdgeStr edgeStr;
103			output IncidenceList<VertexT, EdgeT> il;
104			protected
105			type Indices = list<Integer>;
106			algorithm
107		3	il := INCIDENCE_LIST(Vector.new<VertexT>(), Vector.new<EdgeT>(), Vector.new<Indices>(), vertexEq, edgeEq, vertexStr, edgeStr);
108			end new;
109
110			function getRow
111			input IncidenceList<VertexT, EdgeT> il;
112			input VertexDescriptor d;
113			output list<Integer> row;
114			algorithm
115		23	row := Vector.get(il.graph, d);
116			end getRow;
117
118			function addVertex
119			input IncidenceList<VertexT, EdgeT> il;
120			input VertexT v;
121			output VertexDescriptor d;
122			algorithm
123		23	Vector.push(il.vertices, v);
124		23	Vector.push(il.graph, {});
125		23	d := Vector.size(il.vertices);
126			end addVertex;
127
128			function findVertex
129			input IncidenceList<VertexT, EdgeT> il;
130			input PredFn predFn;
131			output Option<VertexDescriptor> od;
132
133			partial function PredFn
134			input VertexT e;
135			output Boolean res;
136			end PredFn;
137			protected
138			Integer index;
139			algorithm
140		✗	(_, index) := Vector.find(il.vertices, predFn);
141		✗	od := if index > 0 then SOME(index) else NONE();
142			end findVertex;
143
144			function getVertex
145			input IncidenceList<VertexT, EdgeT> il;
146			input VertexDescriptor d;
147			output VertexT v;
148			algorithm
149		143	v := Vector.get(il.vertices, d);
150			end getVertex;
151
152			function getVerticesFromSet
153			"kabdelhak: seems inefficient. There has to be a better solution"
154			input IncidenceList<VertexT, EdgeT> il;
155			input SBSet set;
156			input getSetFn getSet;
157			output list<VertexT> set_vertices = {};
158			partial function getSetFn
159			input VertexT v;
160			output SBSet s;
161			end getSetFn;
162			algorithm
163		✗	for v in vertices(il) loop
164		✗	if not SBSet.isEmpty(SBSet.intersection(getSet(v), set)) then
165			set_vertices := v :: set_vertices;
166			end if;
167			end for;
168			end getVerticesFromSet;
169
170			function addEdge
171			input IncidenceList<VertexT, EdgeT> il;
172			input VertexDescriptor d1;
173			input VertexDescriptor d2;
174			input EdgeT e;
175			output Integer ei;
176			protected
177			list<Integer> eil;
178			algorithm
179		15	eil := Vector.get(il.graph, d1);
180
181		15	ei := List.positionOnTrue(eil,
182			function edge_finder(e = e, edges = il.edges, eqFn = il.edgeEqFn));
183
184	1/2 ✓ Branch 0 taken 15 times. ✗ Branch 1 not taken.	15	if ei == -1 then
185		15	Vector.push(il.edges, e);
186		15	ei := Vector.size(il.edges);
187		15	Vector.update(il.graph, d1, ei :: eil);
188		30	Vector.update(il.graph, d2, ei :: Vector.get(il.graph, d2));
189			else
190		✗	Vector.update(il.edges, ei, e);
191			end if;
192			end addEdge;
193
194			function getEdge
195			input IncidenceList<VertexT, EdgeT> il;
196			input Integer d;
197			output EdgeT e;
198			algorithm
199		12	e := Vector.get(il.edges, d);
200			end getEdge;
201
202			function isEmpty
203			input IncidenceList<VertexT, EdgeT> il;
204			output Boolean empty = Vector.size(il.vertices) == 0;
205			end isEmpty;
206
207			function vertexCount
208			input IncidenceList<VertexT, EdgeT> il;
209			output Integer count = Vector.size(il.vertices);
210			end vertexCount;
211
212			function edgeCount
213			input IncidenceList<VertexT, EdgeT> il;
214			output Integer count = Vector.size(il.edges);
215			end edgeCount;
216
217			function vertices
218			input IncidenceList<VertexT, EdgeT> il;
219			output list<VertexT> vl = Vector.toList(il.vertices);
220			end vertices;
221
222			function edges
223			input IncidenceList<VertexT, EdgeT> il;
224			output list<EdgeT> el = Vector.toList(il.edges);
225			end edges;
226
227			function toString
228			input IncidenceList<VertexT, EdgeT> il;
229			output String str;
230			protected
231			// somehow this is needed and can't be applied directly
232			VertexStr vertToString = il.vertToString;
233			EdgeStr edgeToString = il.edgeToString;
234			algorithm
235		✗	str := StringUtil.headline_2("Set-Based Graph") + "\n";
236		✗	str := str + stringDelimitList(list(vertToString(v) for v in Vector.toList(il.vertices)), "\n") + "\n";
237		✗	str := str + stringDelimitList(list(edgeToString(e) for e in Vector.toList(il.edges)), "\n") + "\n";
238			end toString;
239
240			end IncidenceList;
241
242			uniontype BipartiteIncidenceList<VertexT, EdgeT>
243
244			public
245			record BIPARTITE_INCIDENCE_LIST
246			Vector<VertexT> F_vertices;
247			Vector<VertexT> U_vertices;
248			Vector<EdgeT> edges;
249			Vector<list<Integer>> graph;
250			VertexEq vertEqFn;
251			EdgeEq edgeEqFn;
252			VertexStr vertToString;
253			EdgeStr edgeToString;
254			end BIPARTITE_INCIDENCE_LIST;
255
256			function new
257			input VertexEq vertexEq;
258			input EdgeEq edgeEq;
259			input VertexStr vertexStr;
260			input EdgeStr edgeStr;
261			output BipartiteIncidenceList<VertexT, EdgeT> il;
262			protected
263			type Indices = list<Integer>;
264			algorithm
265		✗	il := BIPARTITE_INCIDENCE_LIST(Vector.new<VertexT>(), Vector.new<VertexT>(), Vector.new<EdgeT>(), Vector.new<Indices>(), vertexEq, edgeEq, vertexStr, edgeStr);
266			end new;
267
268			function getRow
269			input BipartiteIncidenceList<VertexT, EdgeT> il;
270			input VertexDescriptor d;
271			output list<Integer> row = Vector.get(il.graph, d);
272			end getRow;
273
274			function addVertex
275			input BipartiteIncidenceList<VertexT, EdgeT> il;
276			input VertexT v;
277			input SetType ST;
278			output VertexDescriptor d;
279			algorithm
280			d := match ST
281
282			case SetType.F algorithm
283		✗	Vector.push(il.F_vertices, v);
284		✗	Vector.push(il.graph, {});
285		✗	then Vector.size(il.F_vertices);
286
287			case SetType.U algorithm
288		✗	Vector.push(il.U_vertices, v);
289		✗	Vector.push(il.graph, {});
290		✗	then Vector.size(il.U_vertices);
291
292			else algorithm
293		✗	Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: F,U", sourceInfo());
294		✗	then fail();
295			end match;
296			end addVertex;
297
298			function findVertex
299			input BipartiteIncidenceList<VertexT, EdgeT> il;
300			input SetType ST;
301			input PredFn predFn;
302			output Option<VertexDescriptor> od;
303			partial function PredFn
304			input VertexT e;
305			output Boolean res;
306			end PredFn;
307			protected
308			Integer index;
309			algorithm
310			index := match ST
311		✗	case SetType.F algorithm (_, index) := Vector.find(il.F_vertices, predFn); then index;
312		✗	case SetType.U algorithm (_, index) := Vector.find(il.U_vertices, predFn); then index;
313			else algorithm
314		✗	Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: F,U", sourceInfo());
315		✗	then fail();
316			end match;
317		✗	od := if index > 0 then SOME(index) else NONE();
318			end findVertex;
319
320			function getVertex
321			input BipartiteIncidenceList<VertexT, EdgeT> il;
322			input VertexDescriptor d;
323			input SetType ST;
324			output VertexT v;
325			algorithm
326			v := match ST
327		✗	case SetType.F then Vector.get(il.F_vertices, d);
328		✗	case SetType.U then Vector.get(il.U_vertices, d);
329			else algorithm
330		✗	Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: F,U", sourceInfo());
331		✗	then fail();
332			end match;
333			end getVertex;
334
335			function getVerticesFromSet
336			"kabdelhak: seems inefficient. There has to be a better solution"
337			input BipartiteIncidenceList<VertexT, EdgeT> il;
338			input SBSet set;
339			input SetType ST;
340			input getSetFn getSet;
341			output list<VertexT> set_vertices = {};
342			partial function getSetFn
343			input VertexT v;
344			output SBSet s;
345			end getSetFn;
346			algorithm
347		✗	for v in vertices(il, ST) loop
348		✗	if not SBSet.isEmpty(SBSet.intersection(getSet(v), set)) then
349			set_vertices := v :: set_vertices;
350			end if;
351			end for;
352			end getVerticesFromSet;
353
354			function addEdge
355			input BipartiteIncidenceList<VertexT, EdgeT> il;
356			input VertexDescriptor d1;
357			input VertexDescriptor d2;
358			input EdgeT e;
359			output Integer ei;
360			protected
361			list<Integer> eil;
362			algorithm
363		✗	eil := getRow(il, d1);
364		✗	ei := List.positionOnTrue(eil,
365			function edge_finder(e = e, edges = il.edges, eqFn = il.edgeEqFn));
366
367		✗	if ei == -1 then
368		✗	Vector.push(il.edges, e);
369		✗	ei := Vector.size(il.edges);
370		✗	Vector.update(il.graph, d1, ei :: eil);
371		✗	Vector.update(il.graph, d2, ei :: Vector.get(il.graph, d2));
372			else
373		✗	Vector.update(il.edges, ei, e);
374			end if;
375			end addEdge;
376
377			function getEdgesFromSet
378			"kabdelhak: seems inefficient. There has to be a better solution"
379			input BipartiteIncidenceList<VertexT, EdgeT> il;
380			input SBSet set;
381			input getSetFn getSet;
382			output list<EdgeT> set_edges = {};
383			partial function getSetFn
384			input EdgeT e;
385			output SBSet s;
386			end getSetFn;
387			algorithm
388		✗	for e in edges(il) loop
389		✗	if not SBSet.isEmpty(SBSet.intersection(getSet(e), set)) then
390			set_edges := e :: set_edges;
391			end if;
392			end for;
393			end getEdgesFromSet;
394
395			function getEdge
396			input BipartiteIncidenceList<VertexT, EdgeT> il;
397			input Integer d;
398			output EdgeT e = Vector.get(il.edges, d);
399			end getEdge;
400
401			function isEmpty
402			input BipartiteIncidenceList<VertexT, EdgeT> il;
403			output Boolean empty = (Vector.size(il.F_vertices) == 0) and (Vector.size(il.U_vertices) == 0);
404			end isEmpty;
405
406			function vertexCount
407			input BipartiteIncidenceList<VertexT, EdgeT> il;
408			input SetType ST = SetType.V;
409			output Integer count;
410			algorithm
411			count := match ST
412		✗	case SetType.V then Vector.size(il.F_vertices) + Vector.size(il.U_vertices);
413		✗	case SetType.F then Vector.size(il.F_vertices);
414		✗	case SetType.U then Vector.size(il.U_vertices);
415			else algorithm
416		✗	Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: V,F,U", sourceInfo());
417		✗	then fail();
418			end match;
419			end vertexCount;
420
421			function edgeCount
422			input BipartiteIncidenceList<VertexT, EdgeT> il;
423			output Integer count = Vector.size(il.edges);
424			end edgeCount;
425
426			function vertices
427			input BipartiteIncidenceList<VertexT, EdgeT> il;
428			input SetType ST;
429			output list<VertexT> vl;
430			algorithm
431			vl := match ST
432		✗	case SetType.V then listAppend(Vector.toList(il.F_vertices), Vector.toList(il.U_vertices));
433		✗	case SetType.F then Vector.toList(il.F_vertices);
434		✗	case SetType.U then Vector.toList(il.U_vertices);
435			else algorithm
436		✗	Error.terminate(getInstanceName() + " failed for wrong SetType: " + setTypeString(ST) + "\nAllowed: V,F,U", sourceInfo());
437		✗	then fail();
438			end match;
439			end vertices;
440
441			function edges
442			input BipartiteIncidenceList<VertexT, EdgeT> il;
443			output list<EdgeT> el = Vector.toList(il.edges);
444			end edges;
445
446			function toString
447			input BipartiteIncidenceList<VertexT, EdgeT> il;
448			output String str;
449			protected
450			VertexStr vertToString;
451			EdgeStr edgeToString;
452			algorithm
453		✗	BIPARTITE_INCIDENCE_LIST(vertToString = vertToString, edgeToString = edgeToString) := il;
454		✗	str := StringUtil.headline_2("Set-Based Graph") + "\n"
455			+ StringUtil.headline_3("F-Vertices") + "\n"
456			+ stringDelimitList(list(vertToString(v) for v in Vector.toList(il.F_vertices)), "\n") + "\n"
457			+ StringUtil.headline_3("U-Vertices") + "\n"
458			+ stringDelimitList(list(vertToString(v) for v in Vector.toList(il.U_vertices)), "\n") + "\n"
459			+ StringUtil.headline_3("Edges") + "\n"
460			+ stringDelimitList(list(edgeToString(e) for e in Vector.toList(il.edges)), "\n") + "\n";
461			end toString;
462
463			function setTypeString
464			input SetType ST;
465			output String str;
466			algorithm
467			str := match ST
468			case SetType.V then "V (generic vertex set)";
469			case SetType.F then "F (function vertex set)";
470			case SetType.U then "U (unknown vertex set)";
471			case SetType.E then "E (edge set)";
472			else getInstanceName() + " ERROR";
473			end match;
474			end setTypeString;
475
476			end BipartiteIncidenceList;
477
478			annotation(__OpenModelica_Interface="util");
479			end SBGraph;
480