GCC Code Coverage Report

Directory: ./
File: src/Graph_impl.h
Date: 2025-11-27 16:38:08
Exec Total Coverage
Lines: 219 227 96.5%
Functions: 38 40 95.0%
Branches: 192 222 86.5%
Line Branch Exec Source
1 /***************************************
2 Auteur : Pierre Aubert
3 Mail : pierre.aubert@lapp.in2p3.fr
4 Licence : CeCILL-C
5 ****************************************/
6
7 #ifndef __GRAPH_H_IMPL__
8 #define __GRAPH_H_IMPL__
9
10 #include <stdlib.h>
11 #include <iostream>
12
13 #include "Graph.h"
14
15 ///Default constructeur of Graph
16 template<typename T, typename UIdx>
17 5 Graph<T, UIdx>::Graph(){
18 5 initialisationGraph();
19 5 }
20
21 ///Copy constructor of Graph
22 /** @param other : class to copy
23 */
24 template<typename T, typename UIdx>
25 1 Graph<T, UIdx>::Graph(const Graph<T, UIdx> & other){
26
1/1
✓ Branch 0 (5→6) taken 1 times.
 1 copyGraph(other);
27 1 }
28
29 ///Destructeur of Graph
30 template<typename T, typename UIdx>
31 6 Graph<T, UIdx>::~Graph(){
32
33 6 }
34
35 ///Definition of equal operator of Graph
36 /** @param other : class to copy
37 * @return copied class
38 */
39 template<typename T, typename UIdx>
40 Graph<T, UIdx> & Graph<T, UIdx>::operator = (const Graph<T, UIdx> & other){
41 copyGraph(other);
42 return *this;
43 }
44
45 ///Save a png file of the graph
46 /** @param fileNamePng : name of the png file
47 * @return true on success, false otherwise
48 */
49 template<typename T, typename UIdx>
50 9 bool Graph<T, UIdx>::savePng(const std::string & fileNamePng) const{
51
3/3
✓ Branch 0 (2→3) taken 9 times.
✓ Branch 2 (3→4) taken 1 times.
✓ Branch 3 (3→5) taken 8 times.
 9 if(fileNamePng == "") return false;
52
1/1
✓ Branch 0 (7→8) taken 8 times.
 8 std::string fileTxt("output.dot");
53
2/3
✓ Branch 0 (9→10) taken 8 times.
✗ Branch 2 (10→11) not taken.
✓ Branch 3 (10→16) taken 8 times.
 8 if(!saveDot(fileTxt)){
54 ✗ std::cerr << "Graph<T, UIdx>::savePng : can't create file '" << fileTxt << "'" << std::endl;
55 ✗ return false;
56 }
57
5/5
✓ Branch 0 (16→17) taken 8 times.
✓ Branch 2 (17→18) taken 8 times.
✓ Branch 4 (18→19) taken 8 times.
✓ Branch 6 (19→20) taken 8 times.
✓ Branch 8 (20→21) taken 8 times.
 8 std::string commande("dot -Tpng -o " + fileNamePng + " " + fileTxt + " && rm " + fileTxt);
58
3/3
✓ Branch 0 (26→27) taken 8 times.
✓ Branch 2 (27→28) taken 1 times.
✓ Branch 3 (27→33) taken 7 times.
 8 if(system(commande.c_str()) != 0){
59
4/4
✓ Branch 0 (28→29) taken 1 times.
✓ Branch 2 (29→30) taken 1 times.
✓ Branch 4 (30→31) taken 1 times.
✓ Branch 6 (31→32) taken 1 times.
 1 std::cerr << "Graph<T, UIdx>::savePng : can't create png file '" << fileNamePng << "'" << std::endl;
60 1 return false;
61 }
62 7 return true;
63 8 }
64
65 ///Save the Graph in a dot file
66 /** @param fileName : name of the file to be created
67 */
68 template<typename T, typename UIdx>
69 10 bool Graph<T, UIdx>::saveDot(const std::string & fileName) const{
70
3/3
✓ Branch 0 (2→3) taken 10 times.
✓ Branch 2 (3→4) taken 1 times.
✓ Branch 3 (3→5) taken 9 times.
 10 if(fileName == ""){return false;}
71
1/1
✓ Branch 0 (5→6) taken 9 times.
 9 std::ofstream fs;
72
1/1
✓ Branch 0 (7→8) taken 9 times.
 9 fs.open(fileName.c_str());
73
2/2
✓ Branch 0 (9→10) taken 1 times.
✓ Branch 1 (9→15) taken 8 times.
 9 if(!fs.is_open()){
74
4/4
✓ Branch 0 (10→11) taken 1 times.
✓ Branch 2 (11→12) taken 1 times.
✓ Branch 4 (12→13) taken 1 times.
✓ Branch 6 (13→14) taken 1 times.
 1 std::cerr << "Graph<T, UIdx>::saveDot : can't open file '" << fileName << "'" << std::endl;
75 1 return false;
76 }
77
1/1
✓ Branch 0 (15→16) taken 8 times.
 8 bool b(saveDot(fs));
78
1/1
✓ Branch 0 (16→17) taken 8 times.
 8 fs.close();
79 8 return b;
80 9 }
81
82 ///Save the Graph in a dot file
83 /** @param[out] fs : file stream to be modified
84 */
85 template<typename T, typename UIdx>
86 8 bool Graph<T, UIdx>::saveDot(std::ofstream & fs) const{
87
2/2
✓ Branch 0 (2→3) taken 8 times.
✓ Branch 2 (3→4) taken 8 times.
 8 fs << toDot();
88 8 return true;
89 }
90
91 ///Convert the graph to dot language
92 /** @return dot
93 */
94 template<typename T, typename UIdx>
95 8 std::string Graph<T, UIdx>::toDot() const{
96
1/1
✓ Branch 0 (4→5) taken 8 times.
 8 std::string body("");
97
1/1
✓ Branch 0 (6→7) taken 8 times.
 8 body += "digraph G{\n";
98 //save the node definition
99
2/2
✓ Branch 0 (15→8) taken 41 times.
✓ Branch 1 (15→16) taken 8 times.
 49 for(typename std::map<UIdx, Node<T, UIdx> >::const_iterator it(p_mapNode.begin()); it != p_mapNode.end(); ++it){
100
2/2
✓ Branch 0 (9→10) taken 41 times.
✓ Branch 2 (10→11) taken 41 times.
 41 body += it->second.getDotDefinition();
101 }
102 //save the connections between nodes
103
2/2
✓ Branch 0 (47→17) taken 41 times.
✓ Branch 1 (47→48) taken 8 times.
 49 for(typename std::map<UIdx, Node<T, UIdx> >::const_iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
104
1/1
✓ Branch 0 (18→19) taken 41 times.
 41 const std::string & parentNodeName(itNode->second.getDotName());
105 41 const std::list<UIdx> & listChild = itNode->second.getListChild();
106
2/2
✓ Branch 0 (42→22) taken 37 times.
✓ Branch 1 (42→43) taken 41 times.
 78 for(typename std::list<UIdx>::const_iterator it(listChild.begin()); it != listChild.end(); ++it){
107
2/2
✓ Branch 0 (23→24) taken 37 times.
✓ Branch 2 (24→25) taken 4 times.
 37 const Node<T, UIdx> * childNode = getNode(*it);
108
1/2
✗ Branch 0 (24→25) not taken.
✓ Branch 1 (24→26) taken 37 times.
 37 if(childNode == NULL){continue;}
109
1/1
✓ Branch 0 (26→27) taken 37 times.
 37 const std::string & childNodeName(childNode->getDotName());
110
5/5
✓ Branch 0 (27→28) taken 37 times.
✓ Branch 2 (28→29) taken 37 times.
✓ Branch 4 (29→30) taken 37 times.
✓ Branch 6 (30→31) taken 37 times.
✓ Branch 8 (31→32) taken 37 times.
 37 body += "\t" + parentNodeName + " -> " + childNodeName + "[color=\"red\"];\n";
111 }
112 }
113
1/1
✓ Branch 0 (48→49) taken 8 times.
 8 body += "}\n\n";
114 8 return body;
115 ✗ }
116
117 ///Create a node and get its index
118 /** @param data : data of the Node
119 * @param name : name of the Node
120 * @return index of the Node
121 */
122 template<typename T, typename UIdx>
123 21 UIdx Graph<T, UIdx>::createNode(const T & data, const std::string & name){
124 21 UIdx nodeIndex(p_mapNode.size());
125
2/3
✓ Branch 0 (5→6) taken 21 times.
✗ Branch 2 (6→4) not taken.
✓ Branch 3 (6→7) taken 21 times.
 21 while(getNode(nodeIndex) != NULL){
126 ✗ ++nodeIndex;
127 }
128
1/1
✓ Branch 0 (7→8) taken 21 times.
 21 Node<T, UIdx> node(data, name);
129 21 node.setIndex(nodeIndex);
130
2/2
✓ Branch 0 (9→10) taken 21 times.
✓ Branch 2 (10→11) taken 21 times.
 21 p_mapNode[nodeIndex] = node;
131 21 return nodeIndex;
132 21 }
133
134 ///Create a node and get its pointer
135 /** @param data : data of the Node
136 * @param name : name of the Node
137 * @return pointer of the Node
138 */
139 template<typename T, typename UIdx>
140 Node<T, UIdx> * Graph<T, UIdx>::createNodePtr(const T & data, const std::string & name){
141 UIdx node = createNode(data, name);
142 return getNode(node);
143 }
144
145 ///Create a node and get its index
146 /** @param data : data of the Node
147 * @param index : index of the Node
148 * @param name : name of the Node
149 * @return true if the node can be created, false if the index is already taken by an other Node
150 */
151 template<typename T, typename UIdx>
152 5 bool Graph<T, UIdx>::createNode(const T & data, const UIdx & index, const std::string & name){
153
3/4
✓ Branch 0 (2→3) taken 5 times.
✓ Branch 2 (3→4) taken 5 times.
✗ Branch 4 (5→6) not taken.
✓ Branch 5 (5→7) taken 5 times.
 5 if(getNode(index) != NULL){ //Check if the Node already exists
154 ✗ return false;
155 }
156
1/1
✓ Branch 0 (7→8) taken 5 times.
 5 Node<T, UIdx> node(data, name);
157
2/2
✓ Branch 0 (8→9) taken 5 times.
✓ Branch 2 (9→10) taken 5 times.
 5 node.setIndex(index);
158
2/2
✓ Branch 0 (11→12) taken 5 times.
✓ Branch 2 (12→13) taken 5 times.
 5 p_mapNode[index] = node;
159 5 return true;
160 5 }
161
162 ///Create a node and get its pointer
163 /** @param data : data of the Node
164 * @param index : index of the Node
165 * @param name : name of the Node
166 * @return pointer of the Node
167 */
168 template<typename T, typename UIdx>
169 Node<T, UIdx> * Graph<T, UIdx>::createNodePtr(const T & data, const UIdx & index, const std::string & name){
170 if(createNode(data, index, name)){
171 return getNode(index);
172 }else{
173 return NULL;
174 }
175 }
176
177 ///Clear the isUpdated attriburte of the Node
178 template<typename T, typename UIdx>
179 2 void Graph<T, UIdx>::clearIsUpdated(){
180
2/2
✓ Branch 0 (8→3) taken 10 times.
✓ Branch 1 (8→9) taken 2 times.
 12 for(typename std::map<UIdx, Node<T, UIdx> >::iterator it(p_mapNode.begin()); it != p_mapNode.end(); ++it){
181 10 it->second.setIsUpdated(false);
182 }
183 2 }
184
185 ///Clear the map of Node
186 template<typename T, typename UIdx>
187 void Graph<T, UIdx>::clearMapNode(){p_mapNode.clear();}
188
189 ///Clear the list of first Node
190 template<typename T, typename UIdx>
191 1 void Graph<T, UIdx>::clearFirstNode(){p_listFirstNode.clear();}
192
193 ///Clear the list of last Node
194 template<typename T, typename UIdx>
195 1 void Graph<T, UIdx>::clearLastNode(){p_listLastNode.clear();}
196
197 //Clear all Node
198 template<typename T, typename UIdx>
199 void Graph<T, UIdx>::clearAll(){
200 clearFirstNode();
201 clearLastNode();
202 clearMapNode();
203 }
204
205 ///Remove a Node from the Graph
206 /** @param index : index of the Node to be removed
207 * @param reconnectParentToChildren : true to reconnect parents of the node to be removed to its children
208 */
209 template<typename T, typename UIdx>
210 2 void Graph<T, UIdx>::removeNode(UIdx index, bool reconnectParentToChildren){
211 2 Node<T, UIdx> * indexNode = getNode(index);
212
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 2 times.
 2 if(indexNode == NULL){return;} //If the Node does not exist, we stop
213 //Get the parents of the current Node
214 2 std::list<UIdx> & listParent = indexNode->getListParent();
215
1/2
✓ Branch 0 (7→8) taken 2 times.
✗ Branch 1 (7→19) not taken.
 2 if(listParent.size() != 0lu){
216 //Tell them they do not have child anymore
217
2/2
✓ Branch 0 (17→9) taken 2 times.
✓ Branch 1 (17→18) taken 2 times.
 4 for(typename std::list<UIdx>::iterator it(listParent.begin()); it != listParent.end(); ++it){
218
1/1
✓ Branch 0 (10→11) taken 2 times.
 2 Node<T, UIdx> * parentNode = getNode(*it);
219
1/2
✗ Branch 0 (11→12) not taken.
✓ Branch 1 (11→13) taken 2 times.
 2 if(parentNode == NULL){continue;}
220
1/1
✓ Branch 0 (13→14) taken 2 times.
 2 parentNode->removeChild(index);
221 }
222 }else{
223 //Let's remove the current Node from first Node
224 ✗ listindex_remove(p_listFirstNode, index);
225 }
226 //Get the children of the current Node
227 2 std::list<UIdx> & listChild = indexNode->getListChild();
228
1/2
✓ Branch 0 (22→23) taken 2 times.
✗ Branch 1 (22→34) not taken.
 2 if(listChild.size() != 0lu){
229 //Tell them they do not have parent anymore
230
2/2
✓ Branch 0 (32→24) taken 2 times.
✓ Branch 1 (32→33) taken 2 times.
 4 for(typename std::list<UIdx>::iterator it(listChild.begin()); it != listChild.end(); ++it){
231
1/1
✓ Branch 0 (25→26) taken 2 times.
 2 Node<T, UIdx> * childNode = getNode(*it);
232
1/2
✗ Branch 0 (26→27) not taken.
✓ Branch 1 (26→28) taken 2 times.
 2 if(childNode == NULL){continue;}
233 2 childNode->removeParent(index);
234 }
235 }else{
236 //Let's remove the current Node from last Node
237 ✗ listindex_remove(p_listLastNode, index);
238 }
239
6/8
✓ Branch 0 (35→36) taken 1 times.
✓ Branch 1 (35→41) taken 1 times.
✓ Branch 2 (37→38) taken 1 times.
✗ Branch 3 (37→41) not taken.
✓ Branch 4 (39→40) taken 1 times.
✗ Branch 5 (39→41) not taken.
✓ Branch 6 (42→43) taken 1 times.
✓ Branch 7 (42→51) taken 1 times.
 2 if(reconnectParentToChildren && listParent.size() != 0lu && listChild.size() != 0lu){
240
2/2
✓ Branch 0 (49→44) taken 1 times.
✓ Branch 1 (49→50) taken 1 times.
 2 for(typename std::list<UIdx>::iterator it(listParent.begin()); it != listParent.end(); ++it){
241
1/1
✓ Branch 0 (45→46) taken 1 times.
 1 connectNode(*it, listChild);
242 }
243 }
244 //Now, let's remove the current Node
245 2 p_mapNode.erase(index);
246 }
247
248 ///Update the first and last Node of the Graph
249 template<typename T, typename UIdx>
250 1 void Graph<T, UIdx>::updateFirstLastNode(){
251 1 clearFirstNode();
252 1 clearLastNode();
253
2/2
✓ Branch 0 (18→5) taken 5 times.
✓ Branch 1 (18→19) taken 1 times.
 6 for(typename std::map<UIdx, Node<T, UIdx> >::iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
254
2/2
✓ Branch 0 (7→8) taken 3 times.
✓ Branch 1 (7→10) taken 2 times.
 5 if(itNode->second.isStart()){ //If the Node does not have any parent, it is a first Node
255
1/1
✓ Branch 0 (9→10) taken 3 times.
 3 p_listFirstNode.push_back(itNode->first);
256 }
257
2/2
✓ Branch 0 (12→13) taken 1 times.
✓ Branch 1 (12→15) taken 4 times.
 5 if(itNode->second.isEnd()){ //If the Node does not have any child, it is a last Node
258
1/1
✓ Branch 0 (14→15) taken 1 times.
 1 p_listLastNode.push_back(itNode->first);
259 }
260 }
261 1 }
262
263 ///Connect a parent to its child
264 /** @param parent : index of the parent Node
265 * @param child : index of the child Node
266 */
267 template<typename T, typename UIdx>
268 24 void Graph<T, UIdx>::connectNode(UIdx parent, UIdx child){
269
2/2
✓ Branch 0 (2→3) taken 4 times.
✓ Branch 2 (3→4) taken 4 times.
 24 Node<T, UIdx> * parentNode = getNode(parent);
270
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 24 times.
 24 if(parentNode == NULL){return;}
271
2/2
✓ Branch 0 (7→8) taken 4 times.
✓ Branch 2 (8→9) taken 4 times.
 24 Node<T, UIdx> * childNode = getNode(child);
272
1/2
✗ Branch 0 (6→7) not taken.
✓ Branch 1 (6→8) taken 24 times.
 24 if(childNode == NULL){return;}
273
2/2
✓ Branch 0 (12→13) taken 4 times.
✓ Branch 2 (13→14) taken 4 times.
 24 parentNode->addChild(child);
274
2/2
✓ Branch 0 (15→16) taken 4 times.
✓ Branch 2 (16→17) taken 4 times.
 24 childNode->addParent(parent);
275 }
276
277 ///Connect a parent to its children
278 /** @param parent : index of the parent Node
279 * @param listChildren : list of the children index
280 */
281 template<typename T, typename UIdx>
282 1 void Graph<T, UIdx>::connectNode(UIdx parent, const std::list<UIdx> & listChildren){
283 1 Node<T, UIdx> * parentNode = getNode(parent);
284
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 1 times.
 1 if(parentNode == NULL){return;}
285
2/2
✓ Branch 0 (15→6) taken 1 times.
✓ Branch 1 (15→16) taken 1 times.
 2 for(typename std::list<UIdx>::const_iterator it(listChildren.begin()); it != listChildren.end(); ++it){
286 1 UIdx child = *it;
287
1/1
✓ Branch 0 (7→8) taken 1 times.
 1 Node<T, UIdx> * childNode = getNode(child);
288
1/2
✗ Branch 0 (8→9) not taken.
✓ Branch 1 (8→10) taken 1 times.
 1 if(childNode == NULL){continue;}
289
1/1
✓ Branch 0 (10→11) taken 1 times.
 1 parentNode->addChild(child);
290
1/1
✓ Branch 0 (11→12) taken 1 times.
 1 childNode->addParent(parent);
291 }
292 }
293
294 ///Connect a parent to its children
295 /** @param parent : index of the parent Node
296 * @param vecChildren : vector of the children index
297 */
298 template<typename T, typename UIdx>
299 void Graph<T, UIdx>::connectNode(UIdx parent, const std::vector<UIdx> & vecChildren){
300 Node<T, UIdx> * parentNode = getNode(parent);
301 if(parentNode == NULL){return;}
302 for(typename std::vector<UIdx>::const_iterator it(vecChildren.begin()); it != vecChildren.end(); ++it){
303 UIdx child = *it;
304 Node<T, UIdx> * childNode = getNode(child);
305 if(childNode == NULL){continue;}
306 parentNode->addChild(child);
307 childNode->addParent(parent);
308 }
309 }
310
311 ///Get a Node by pointer
312 /** @param index : index of the node to be used
313 * @return pointer to this Node or NULL if the Node does not exist
314 */
315 template<typename T, typename UIdx>
316 58 const Node<T, UIdx> * Graph<T, UIdx>::getNode(UIdx index) const{
317
1/1
✓ Branch 0 (2→3) taken 58 times.
 58 typename std::map<UIdx, Node<T, UIdx> >::const_iterator it(p_mapNode.find(index));
318
1/2
✓ Branch 0 (5→6) taken 58 times.
✗ Branch 1 (5→8) not taken.
 58 if(it != p_mapNode.end()){
319 58 return &(it->second);
320 }else{
321 ✗ return NULL;
322 }
323 }
324
325 ///Get a Node by pointer
326 /** @param index : index of the node to be used
327 * @return pointer to this Node or NULL if the Node does not exist
328 */
329 template<typename T, typename UIdx>
330 100 Node<T, UIdx> * Graph<T, UIdx>::getNode(UIdx index){
331
1/1
✓ Branch 0 (2→3) taken 100 times.
 100 typename std::map<UIdx, Node<T, UIdx> >::iterator it(p_mapNode.find(index));
332
2/2
✓ Branch 0 (5→6) taken 74 times.
✓ Branch 1 (5→8) taken 26 times.
 100 if(it != p_mapNode.end()){
333 74 return &(it->second);
334 }else{
335 26 return NULL;
336 }
337 }
338
339 ///Get the first node which is not udpated (getIsUpdated() == false)
340 /** @return pointer to the first node which is not udpated or NULL if there is no
341 */
342 template<typename T, typename UIdx>
343 const Node<T, UIdx> * Graph<T, UIdx>::getFirstNotUpdatedNode() const{
344 for(typename std::map<UIdx, Node<T, UIdx> >::const_iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
345 if(!itNode->second.getIsUpdated()){
346 return &(itNode->second);
347 }
348 }
349 return NULL;
350 }
351
352 ///Get the first node which is not udpated (getIsUpdated() == false)
353 /** @return pointer to the first node which is not udpated or NULL if there is no
354 */
355 template<typename T, typename UIdx>
356 Node<T, UIdx> * Graph<T, UIdx>::getFirstNotUpdatedNode(){
357 for(typename std::map<UIdx, Node<T, UIdx> >::iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
358 if(!itNode->second.getIsUpdated()){
359 return &(itNode->second);
360 }
361 }
362 return NULL;
363 }
364
365 ///Say if the node at index does exit
366 /** @param index : index of the node to be searched
367 * @return true if the Node does exist, false otheriwse
368 */
369 template<typename T, typename UIdx>
370 bool Graph<T, UIdx>::isNodeExist(UIdx index) const{
371 typename std::map<UIdx, Node<T, UIdx> >::iterator it(p_mapNode.find(index));
372 return it != p_mapNode.end();
373 }
374
375 ///Get the number of nodes inside the graph
376 /** @return number of nodes inside the graph
377 */
378 template<typename T, typename UIdx>
379 1 size_t Graph<T, UIdx>::size() const{
380 1 return p_mapNode.size();
381 }
382
383 ///Get the list of the first nodes (without parent)
384 /** @return list of the first nodes (without parent)
385 */
386 template<typename T, typename UIdx>
387 2 const std::list<UIdx> & Graph<T, UIdx>::getListFirstNode() const{
388 2 return p_listFirstNode;
389 }
390
391 ///Get the list of the last nodes (without child)
392 /** @return list of the last nodes (without child)
393 */
394 template<typename T, typename UIdx>
395 2 const std::list<UIdx> & Graph<T, UIdx>::getListLastNode() const{
396 2 return p_listLastNode;
397 }
398
399 ///Iterate from parents to chidren
400 /** @param[out] listNode : list node which can be treated simultaneously
401 * @return true if the returned list of nodes is not empty, false if the bottom of the Graph has been reached
402 */
403 template<typename T, typename UIdx>
404 4 bool Graph<T, UIdx>::iterateChildren(std::list<UIdx> & listNode) const{
405
2/2
✓ Branch 0 (3→4) taken 1 times.
✓ Branch 1 (3→6) taken 3 times.
 4 if(listNode.size() == 0lu){
406 1 listNode = getListFirstNode();
407 }else{
408 3 std::map<UIdx, bool> mapListChildren;
409
2/2
✓ Branch 0 (23→8) taken 6 times.
✓ Branch 1 (23→24) taken 3 times.
 9 for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
410
1/1
✓ Branch 0 (9→10) taken 6 times.
 6 const Node<T, UIdx> * node = getNode(*itNode);
411
1/2
✓ Branch 0 (10→11) taken 6 times.
✗ Branch 1 (10→20) not taken.
 6 if(node != NULL){
412 6 const std::list<UIdx> & listChildren = node->getListChild();
413
2/2
✓ Branch 0 (18→13) taken 4 times.
✓ Branch 1 (18→19) taken 6 times.
 10 for(typename std::list<UIdx>::const_iterator it(listChildren.begin()); it != listChildren.end(); ++it){
414
1/1
✓ Branch 0 (14→15) taken 4 times.
 4 mapListChildren[*it] = true;
415 }
416 }
417 }
418 3 std::list<UIdx> listNodeOut;
419
2/2
✓ Branch 0 (31→26) taken 3 times.
✓ Branch 1 (31→32) taken 3 times.
 6 for(typename std::map<UIdx, bool>::iterator it(mapListChildren.begin()); it != mapListChildren.end(); ++it){
420
1/1
✓ Branch 0 (27→28) taken 3 times.
 3 listNodeOut.push_back(it->first);
421 }
422
1/1
✓ Branch 0 (32→33) taken 3 times.
 3 listNode = listNodeOut;
423 3 }
424 4 return listNode.size() != 0lu;
425 }
426
427 ///Iterate from children to parents
428 /** @param[out] listNode : list node which can be treated simultaneously
429 * @return true if the returned list of nodes is not empty, false if the top of the Graph has been reached
430 */
431 template<typename T, typename UIdx>
432 4 bool Graph<T, UIdx>::iterateParent(std::list<UIdx> & listNode) const{
433
2/2
✓ Branch 0 (3→4) taken 1 times.
✓ Branch 1 (3→6) taken 3 times.
 4 if(listNode.size() == 0lu){
434 1 listNode = getListLastNode();
435 }else{
436 3 std::map<UIdx, bool> mapListParent;
437
2/2
✓ Branch 0 (23→8) taken 5 times.
✓ Branch 1 (23→24) taken 3 times.
 8 for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
438
1/1
✓ Branch 0 (9→10) taken 5 times.
 5 const Node<T, UIdx> * node = getNode(*itNode);
439
1/2
✓ Branch 0 (10→11) taken 5 times.
✗ Branch 1 (10→20) not taken.
 5 if(node != NULL){
440 5 const std::list<UIdx> & listParent = node->getListParent();
441
2/2
✓ Branch 0 (18→13) taken 4 times.
✓ Branch 1 (18→19) taken 5 times.
 9 for(typename std::list<UIdx>::const_iterator it(listParent.begin()); it != listParent.end(); ++it){
442
1/1
✓ Branch 0 (14→15) taken 4 times.
 4 mapListParent[*it] = true;
443 }
444 }
445 }
446 3 std::list<UIdx> listNodeOut;
447
2/2
✓ Branch 0 (31→26) taken 4 times.
✓ Branch 1 (31→32) taken 3 times.
 7 for(typename std::map<UIdx, bool>::iterator it(mapListParent.begin()); it != mapListParent.end(); ++it){
448
1/1
✓ Branch 0 (27→28) taken 4 times.
 4 listNodeOut.push_back(it->first);
449 }
450
1/1
✓ Branch 0 (32→33) taken 3 times.
 3 listNode = listNodeOut;
451 3 }
452 4 return listNode.size() != 0lu;
453 }
454
455 ///Check if the list of given nodes are all updated or not
456 /** @param listNode : list of nodes to be checked
457 * @return true fi all nodes are updated, false otherwise
458 */
459 template<typename T, typename UIdx>
460 7 bool Graph<T, UIdx>::isListNodeUdpated(const std::list<UIdx> & listNode) const{
461 7 bool b(true);
462
5/6
✓ Branch 0 (11→12) taken 10 times.
✓ Branch 1 (11→14) taken 7 times.
✓ Branch 2 (12→13) taken 10 times.
✗ Branch 3 (12→14) not taken.
✓ Branch 4 (15→3) taken 10 times.
✓ Branch 5 (15→16) taken 7 times.
 17 for(typename std::list<UIdx>::const_iterator itNode(listNode.begin()); itNode != listNode.end() && b; ++itNode){
463
1/1
✓ Branch 0 (4→5) taken 10 times.
 10 const Node<T, UIdx> * node = getNode(*itNode);
464
1/2
✓ Branch 0 (5→6) taken 10 times.
✗ Branch 1 (5→8) not taken.
 10 if(node != NULL){
465 10 b &= node->getIsUpdated();
466 }
467 }
468 7 return b;
469 }
470
471 ///Iterate from parents to chidren (all node are iterated only once)
472 /** @param[out] listNode : list node which can be treated simultaneously
473 * @return true if the returned list of nodes is not empty, false if the bottom of the Graph has been reached
474 */
475 template<typename T, typename UIdx>
476 3 bool Graph<T, UIdx>::iterateChildrenCheckUpdate(std::list<UIdx> & listNode){
477
2/2
✓ Branch 0 (3→4) taken 1 times.
✓ Branch 1 (3→7) taken 2 times.
 3 if(listNode.size() == 0lu){
478 1 clearIsUpdated();
479 1 listNode = getListFirstNode();
480 }else{
481 2 std::map<UIdx, bool> mapListChildren;
482
2/2
✓ Branch 0 (34→9) taken 5 times.
✓ Branch 1 (34→35) taken 2 times.
 7 for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
483
1/1
✓ Branch 0 (10→11) taken 5 times.
 5 Node<T, UIdx> * node = getNode(*itNode);
484
1/2
✓ Branch 0 (11→12) taken 5 times.
✗ Branch 1 (11→31) not taken.
 5 if(node != NULL){
485 5 node->setIsUpdated(true); //This node has been iterated, so we do not want to pick it as a child
486 5 std::list<UIdx> & listChildren = node->getListChild();
487
2/2
✓ Branch 0 (29→15) taken 4 times.
✓ Branch 1 (29→30) taken 5 times.
 9 for(typename std::list<UIdx>::iterator it(listChildren.begin()); it != listChildren.end(); ++it){
488
1/1
✓ Branch 0 (16→17) taken 4 times.
 4 Node<T, UIdx> * nodeChild = getNode(*it);
489
1/2
✓ Branch 0 (17→18) taken 4 times.
✗ Branch 1 (17→26) not taken.
 4 if(nodeChild != NULL){
490
2/2
✓ Branch 0 (19→20) taken 3 times.
✓ Branch 1 (19→26) taken 1 times.
 4 if(!nodeChild->getIsUpdated()){
491 //The child node is added only if its parents are updated
492
3/3
✓ Branch 0 (21→22) taken 3 times.
✓ Branch 2 (22→23) taken 2 times.
✓ Branch 3 (22→26) taken 1 times.
 3 if(isListNodeUdpated(nodeChild->getListParent())){
493
1/1
✓ Branch 0 (24→25) taken 2 times.
 2 mapListChildren[*it] = true;
494 2 nodeChild->setIsUpdated(true);
495 }
496 }
497 }
498 }
499 }
500 }
501 2 std::list<UIdx> listNodeOut;
502
2/2
✓ Branch 0 (42→37) taken 2 times.
✓ Branch 1 (42→43) taken 2 times.
 4 for(typename std::map<UIdx, bool>::iterator it(mapListChildren.begin()); it != mapListChildren.end(); ++it){
503
1/1
✓ Branch 0 (38→39) taken 2 times.
 2 listNodeOut.push_back(it->first);
504 }
505
1/1
✓ Branch 0 (43→44) taken 2 times.
 2 listNode = listNodeOut;
506 2 }
507 3 return listNode.size() != 0lu;
508 }
509
510 ///Iterate from children to parents (all node are iterated only once)
511 /** @param[out] listNode : list node which can be treated simultaneously
512 * @return true if the returned list of nodes is not empty, false if the top of the Graph has been reached
513 */
514 template<typename T, typename UIdx>
515 4 bool Graph<T, UIdx>::iterateParentCheckUpdate(std::list<UIdx> & listNode){
516
2/2
✓ Branch 0 (3→4) taken 1 times.
✓ Branch 1 (3→7) taken 3 times.
 4 if(listNode.size() == 0lu){
517 1 clearIsUpdated();
518 1 listNode = getListLastNode();
519 }else{
520 3 std::map<UIdx, bool> mapListParent;
521
2/2
✓ Branch 0 (34→9) taken 5 times.
✓ Branch 1 (34→35) taken 3 times.
 8 for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
522
1/1
✓ Branch 0 (10→11) taken 5 times.
 5 Node<T, UIdx> * node = getNode(*itNode);
523
1/2
✓ Branch 0 (11→12) taken 5 times.
✗ Branch 1 (11→31) not taken.
 5 if(node != NULL){
524 5 node->setIsUpdated(true); //This node has been iterated, so we do not want to pick it as a parent
525 5 std::list<UIdx> & listParent = node->getListParent();
526
2/2
✓ Branch 0 (29→15) taken 4 times.
✓ Branch 1 (29→30) taken 5 times.
 9 for(typename std::list<UIdx>::iterator it(listParent.begin()); it != listParent.end(); ++it){
527
1/1
✓ Branch 0 (16→17) taken 4 times.
 4 Node<T, UIdx> * nodeParent = getNode(*it);
528
1/2
✓ Branch 0 (17→18) taken 4 times.
✗ Branch 1 (17→26) not taken.
 4 if(nodeParent != NULL){
529
1/2
✓ Branch 0 (19→20) taken 4 times.
✗ Branch 1 (19→26) not taken.
 4 if(!nodeParent->getIsUpdated()){
530 //The parent node is added only if its children are updated
531
2/3
✓ Branch 0 (21→22) taken 4 times.
✓ Branch 2 (22→23) taken 4 times.
✗ Branch 3 (22→26) not taken.
 4 if(isListNodeUdpated(nodeParent->getListChild())){
532
1/1
✓ Branch 0 (24→25) taken 4 times.
 4 mapListParent[*it] = true;
533 4 nodeParent->setIsUpdated(true);
534 }
535 }
536 }
537 }
538 }
539 }
540 3 std::list<UIdx> listNodeOut;
541
2/2
✓ Branch 0 (42→37) taken 4 times.
✓ Branch 1 (42→43) taken 3 times.
 7 for(typename std::map<UIdx, bool>::iterator it(mapListParent.begin()); it != mapListParent.end(); ++it){
542
1/1
✓ Branch 0 (38→39) taken 4 times.
 4 listNodeOut.push_back(it->first);
543 }
544
1/1
✓ Branch 0 (43→44) taken 3 times.
 3 listNode = listNodeOut;
545 3 }
546 4 return listNode.size() != 0lu;
547 }
548
549 ///Copy function of Graph
550 /** @param other : class to copy
551 */
552 template<typename T, typename UIdx>
553 1 void Graph<T, UIdx>::copyGraph(const Graph<T, UIdx> & other){
554 1 p_mapNode = other.p_mapNode;
555 1 p_listFirstNode = other.p_listFirstNode;
556 1 p_listLastNode = other.p_listLastNode;
557 1 }
558
559 ///Initialisation function of the class Graph
560 template<typename T, typename UIdx>
561 5 void Graph<T, UIdx>::initialisationGraph(){
562
563 5 }
564
565
566
567
568
569 #endif
570
571
572
573