Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	tmp_project/PhoenixGraph/src/Graph_impl.h	Lines:	190	197	96.4 %
Date:	2023-10-11 10:52:07	Branches:	169	207	81.6 %


/***************************************
	Auteur : Pierre Aubert
	Mail : pierre.aubert@lapp.in2p3.fr
	Licence : CeCILL-C
****************************************/

#ifndef __GRAPH_H_IMPL__
#define __GRAPH_H_IMPL__

#include <stdlib.h>
#include <iostream>

#include "Graph.h"

///Default constructeur of Graph
template<typename T, typename UIdx>
Graph<T, UIdx>::Graph(){
	initialisationGraph();
}

///Copy constructor of Graph
/**	@param other : class to copy
*/
template<typename T, typename UIdx>
Graph<T, UIdx>::Graph(const Graph<T, UIdx> & other){
	copyGraph(other);
}

///Destructeur of Graph
template<typename T, typename UIdx>
Graph<T, UIdx>::~Graph(){

}

///Definition of equal operator of Graph
/**	@param other : class to copy
 * 	@return copied class
*/
template<typename T, typename UIdx>
Graph<T, UIdx> & Graph<T, UIdx>::operator = (const Graph<T, UIdx> & other){
	copyGraph(other);
	return *this;
}

///Save a png file of the graph
/**	@param fileNamePng : name of the png file
 * 	@return true on success, false otherwise
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::savePng(const std::string & fileNamePng) const{
	if(fileNamePng == "") return false;
	std::string fileTxt("output.dot");
	if(!saveDot(fileTxt)){
		std::cerr << "Graph<T, UIdx>::savePng : can't create file '" << fileTxt << "'" << std::endl;
		return false;
	}
	std::string commande("dot -Tpng -o " + fileNamePng + " " + fileTxt + " && rm " + fileTxt);
	if(system(commande.c_str()) != 0){
		std::cerr << "Graph<T, UIdx>::savePng : can't create png file '" << fileNamePng << "'" << std::endl;
		return false;
	}
	return true;
}

///Save the Graph in a dot file
/**	@param fileName : name of the file to be created
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::saveDot(const std::string & fileName) const{
	if(fileName == ""){return false;}
	std::ofstream fs;
	fs.open(fileName.c_str());
	if(!fs.is_open()){
		std::cerr << "Graph<T, UIdx>::saveDot : can't open file '" << fileName << "'" << std::endl;
		return false;
	}
	bool b(saveDot(fs));
	fs.close();
	return b;
}

///Save the Graph in a dot file
/**	@param[out] fs : file stream to be modified
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::saveDot(std::ofstream & fs) const{
	fs << toDot();
	return true;
}

///Convert the graph to dot language
/**	@return dot
*/
template<typename T, typename UIdx>
std::string Graph<T, UIdx>::toDot() const{
	std::string body("");
	body += "digraph G{\n";
	//save the node definition
	for(typename std::map<UIdx, Node<T, UIdx> >::const_iterator it(p_mapNode.begin()); it != p_mapNode.end(); ++it){
		body += it->second.getDotDefinition();
	}
	//save the connections between nodes
	for(typename std::map<UIdx, Node<T, UIdx> >::const_iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
		const std::string & parentNodeName(itNode->second.getDotName());
		const std::list<UIdx> & listChild = itNode->second.getListChild();
		for(typename std::list<UIdx>::const_iterator it(listChild.begin()); it != listChild.end(); ++it){
			const Node<T, UIdx> * childNode = getNode(*it);
			if(childNode == NULL){continue;}
			const std::string & childNodeName(childNode->getDotName());
			body += "\t" + parentNodeName + " -> " + childNodeName + "[color=\"red\"];\n";
		}
	}
	body += "}\n\n";
	return body;
}

///Create a node and get its index
/**	@param data : data of the Node
 * 	@param name : name of the Node
 * 	@return index of the Node
*/
template<typename T, typename UIdx>
UIdx Graph<T, UIdx>::createNode(const T & data, const std::string & name){
	UIdx nodeIndex(p_mapNode.size());
	while(getNode(nodeIndex) != NULL){
		++nodeIndex;
	}
	Node<T, UIdx> node(data, name);
	node.setIndex(nodeIndex);
	p_mapNode[nodeIndex] = node;
	return nodeIndex;
}

///Create a node and get its pointer
/**	@param data : data of the Node
 * 	@param name : name of the Node
 * 	@return pointer of the Node
*/
template<typename T, typename UIdx>
Node<T, UIdx> * Graph<T, UIdx>::createNodePtr(const T & data, const std::string & name){
	UIdx node = createNode(data, name);
	return getNode(node);
}

///Create a node and get its index
/**	@param data : data of the Node
 * 	@param index : index of the Node
 * 	@param name : name of the Node
 * 	@return true if the node can be created, false if the index is already taken by an other Node
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::createNode(const T & data, const UIdx & index, const std::string & name){
	if(getNode(index) != NULL){	//Check if the Node already exists
		return false;
	}
	Node<T, UIdx> node(data, name);
	node.setIndex(index);
	p_mapNode[index] = node;
	return true;
}

///Create a node and get its pointer
/**	@param data : data of the Node
 * 	@param index : index of the Node
 * 	@param name : name of the Node
 * 	@return pointer of the Node
*/
template<typename T, typename UIdx>
Node<T, UIdx> * Graph<T, UIdx>::createNodePtr(const T & data, const UIdx & index, const std::string & name){
	if(createNode(data, index, name)){
		return getNode(index);
	}else{
		return NULL;
	}
}

///Clear the isUpdated attriburte of the Node
template<typename T, typename UIdx>
void Graph<T, UIdx>::clearIsUpdated(){
	for(typename std::map<UIdx, Node<T, UIdx> >::iterator it(p_mapNode.begin()); it != p_mapNode.end(); ++it){
		it->second.setIsUpdated(false);
	}
}

///Clear the map of Node
template<typename T, typename UIdx>
void Graph<T, UIdx>::clearMapNode(){p_mapNode.clear();}

///Clear the list of first Node
template<typename T, typename UIdx>
void Graph<T, UIdx>::clearFirstNode(){p_listFirstNode.clear();}

///Clear the list of last Node
template<typename T, typename UIdx>
void Graph<T, UIdx>::clearLastNode(){p_listLastNode.clear();}

//Clear all Node
template<typename T, typename UIdx>
void Graph<T, UIdx>::clearAll(){
	clearFirstNode();
	clearLastNode();
	clearMapNode();
}

///Remove a Node from the Graph
/**	@param index : index of the Node to be removed
*/
template<typename T, typename UIdx>
void Graph<T, UIdx>::removeNode(UIdx index){
	Node<T, UIdx> * indexNode = getNode(index);
	if(indexNode == NULL){return;}	//If the Node does not exist, we stop
	//Get the parents of the current Node
	std::list<UIdx> & listParent = indexNode->getListParent();
	if(listParent.size() != 0lu){
		//Tell them they do not have child anymore
		for(typename std::list<UIdx>::iterator it(listParent.begin()); it != listParent.end(); ++it){
			Node<T, UIdx> * parentNode = getNode(*it);
			if(parentNode == NULL){continue;}
			parentNode->removeChild(index);
		}
	}else{
		//Let's remove the current Node from first Node
		listindex_remove(p_listFirstNode, index);
	}
	//Get the children of the current Node
	std::list<UIdx> & listChild = indexNode->getListChild();
	if(listChild.size() != 0lu){
		//Tell them they do not have parent anymore
		for(typename std::list<UIdx>::iterator it(listChild.begin()); it != listChild.end(); ++it){
			Node<T, UIdx> * childNode = getNode(*it);
			if(childNode == NULL){continue;}
			childNode->removeParent(index);
		}
	}else{
		//Let's remove the current Node from last Node
		listindex_remove(p_listLastNode, index);
	}
	//Now, let's remove the current Node
	p_mapNode.erase(index);
}

///Update the first and last Node of the Graph
template<typename T, typename UIdx>
void Graph<T, UIdx>::updateFirstLastNode(){
	clearFirstNode();
	clearLastNode();
	for(typename std::map<UIdx, Node<T, UIdx> >::iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
		if(itNode->second.isStart()){	//If the Node does not have any parent, it is a first Node
			p_listFirstNode.push_back(itNode->first);
		}
		if(itNode->second.isEnd()){	//If the Node does not have any child, it is a last Node
			p_listLastNode.push_back(itNode->first);
		}
	}
}

///Connect a parent to its child
/**	@param parent : index of the parent Node
 * 	@param child : index of the child Node
*/
template<typename T, typename UIdx>
void Graph<T, UIdx>::connectNode(UIdx parent, UIdx child){
	Node<T, UIdx> * parentNode = getNode(parent);
	if(parentNode == NULL){return;}
	Node<T, UIdx> * childNode = getNode(child);
	if(childNode == NULL){return;}
	parentNode->addChild(child);
	childNode->addParent(parent);
}

///Connect a parent to its children
/**	@param parent : index of the parent Node
 * 	@param listChildren : list of the children index
*/
template<typename T, typename UIdx>
void Graph<T, UIdx>::connectNode(UIdx parent, const std::list<UIdx> & listChildren){
	Node<T, UIdx> * parentNode = getNode(parent);
	if(parentNode == NULL){return;}
	for(typename std::list<UIdx>::const_iterator it(listChildren.begin()); it != listChildren.end(); ++it){
		UIdx child = *it;
		Node<T, UIdx> * childNode = getNode(child);
		if(childNode == NULL){continue;}
		parentNode->addChild(child);
		childNode->addParent(parent);
	}
}

///Connect a parent to its children
/**	@param parent : index of the parent Node
 * 	@param vecChildren : vector of the children index
*/
template<typename T, typename UIdx>
void Graph<T, UIdx>::connectNode(UIdx parent, const std::vector<UIdx> & vecChildren){
	Node<T, UIdx> * parentNode = getNode(parent);
	if(parentNode == NULL){return;}
	for(typename std::vector<UIdx>::const_iterator it(vecChildren.begin()); it != vecChildren.end(); ++it){
		UIdx child = *it;
		Node<T, UIdx> * childNode = getNode(child);
		if(childNode == NULL){continue;}
		parentNode->addChild(child);
		childNode->addParent(parent);
	}
}

///Get a Node by pointer
/**	@param index : index of the node to be used
 * 	@return pointer to this Node or NULL if the Node does not exist
*/
template<typename T, typename UIdx>
const Node<T, UIdx> * Graph<T, UIdx>::getNode(UIdx index) const{
	typename std::map<UIdx, Node<T, UIdx> >::const_iterator it(p_mapNode.find(index));
	if(it != p_mapNode.end()){
		return &(it->second);
	}else{
		return NULL;
	}
}

///Get a Node by pointer
/**	@param index : index of the node to be used
 * 	@return pointer to this Node or NULL if the Node does not exist
*/
template<typename T, typename UIdx>
Node<T, UIdx> * Graph<T, UIdx>::getNode(UIdx index){
	typename std::map<UIdx, Node<T, UIdx> >::iterator it(p_mapNode.find(index));
	if(it != p_mapNode.end()){
		return &(it->second);
	}else{
		return NULL;
	}
}

///Get the first node which is not udpated (getIsUpdated() == false)
/**	@return pointer to the first node which is not udpated or NULL if there is no
*/
template<typename T, typename UIdx>
const Node<T, UIdx> * Graph<T, UIdx>::getFirstNotUpdatedNode() const{
	for(typename std::map<UIdx, Node<T, UIdx> >::const_iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
		if(!itNode->second.getIsUpdated()){
			return &(itNode->second);
		}
	}
	return NULL;
}

///Get the first node which is not udpated (getIsUpdated() == false)
/**	@return pointer to the first node which is not udpated or NULL if there is no
*/
template<typename T, typename UIdx>
Node<T, UIdx> * Graph<T, UIdx>::getFirstNotUpdatedNode(){
	for(typename std::map<UIdx, Node<T, UIdx> >::iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
		if(!itNode->second.getIsUpdated()){
			return &(itNode->second);
		}
	}
	return NULL;
}

///Say if the node at index does exit
/**	@param index : index of the node to be searched
 * 	@return true if the Node does exist, false otheriwse
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::isNodeExist(UIdx index) const{
	typename std::map<UIdx, Node<T, UIdx> >::iterator it(p_mapNode.find(index));
	return it != p_mapNode.end();
}

///Get the number of nodes inside the graph
/**	@return number of nodes inside the graph
*/
template<typename T, typename UIdx>
size_t Graph<T, UIdx>::size() const{
	return p_mapNode.size();
}

///Get the list of the first nodes (without parent)
/**	@return list of the first nodes (without parent)
*/
template<typename T, typename UIdx>
const std::list<UIdx> & Graph<T, UIdx>::getListFirstNode() const{
	return p_listFirstNode;
}

///Get the list of the last nodes (without child)
/**	@return list of the last nodes (without child)
*/
template<typename T, typename UIdx>
const std::list<UIdx> & Graph<T, UIdx>::getListLastNode() const{
	return p_listLastNode;
}

///Iterate from parents to chidren
/**	@param[out] listNode : list node which can be treated simultaneously
 * 	@return true if the returned list of nodes is not empty, false if the bottom of the Graph has been reached
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::iterateChildren(std::list<UIdx> & listNode) const{
	if(listNode.size() == 0lu){
		listNode = getListFirstNode();
	}else{
		std::map<UIdx, bool> mapListChildren;
		for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
			const Node<T, UIdx> * node = getNode(*itNode);
			if(node != NULL){
				const std::list<UIdx> & listChildren = node->getListChild();
				for(typename std::list<UIdx>::const_iterator it(listChildren.begin()); it != listChildren.end(); ++it){
					mapListChildren[*it] = true;
				}
			}
		}
		std::list<UIdx> listNodeOut;
		for(typename std::map<UIdx, bool>::iterator it(mapListChildren.begin()); it != mapListChildren.end(); ++it){
			listNodeOut.push_back(it->first);
		}
		listNode = listNodeOut;
	}
	return listNode.size() != 0lu;
}

///Iterate from children to parents
/**	@param[out] listNode : list node which can be treated simultaneously
 * 	@return true if the returned list of nodes is not empty, false if the top of the Graph has been reached
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::iterateParent(std::list<UIdx> & listNode) const{
	if(listNode.size() == 0lu){
		listNode = getListLastNode();
	}else{
		std::map<UIdx, bool> mapListParent;
		for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
			const Node<T, UIdx> * node = getNode(*itNode);
			if(node != NULL){
				const std::list<UIdx> & listParent = node->getListParent();
				for(typename std::list<UIdx>::const_iterator it(listParent.begin()); it != listParent.end(); ++it){
					mapListParent[*it] = true;
				}
			}
		}
		std::list<UIdx> listNodeOut;
		for(typename std::map<UIdx, bool>::iterator it(mapListParent.begin()); it != mapListParent.end(); ++it){
			listNodeOut.push_back(it->first);
		}
		listNode = listNodeOut;
	}
	return listNode.size() != 0lu;
}

///Check if the list of given nodes are all updated or not
/**	@param listNode : list of nodes to be checked
 * 	@return true fi all nodes are updated, false otherwise
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::isListNodeUdpated(const std::list<UIdx> & listNode) const{
	bool b(true);
	for(typename std::list<UIdx>::const_iterator itNode(listNode.begin()); itNode != listNode.end() && b; ++itNode){
		const Node<T, UIdx> * node = getNode(*itNode);
		if(node != NULL){
			b &= node->getIsUpdated();
		}
	}
	return b;
}

///Iterate from parents to chidren (all node are iterated only once)
/**	@param[out] listNode : list node which can be treated simultaneously
 * 	@return true if the returned list of nodes is not empty, false if the bottom of the Graph has been reached
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::iterateChildrenCheckUpdate(std::list<UIdx> & listNode){
	if(listNode.size() == 0lu){
		clearIsUpdated();
		listNode = getListFirstNode();
	}else{
		std::map<UIdx, bool> mapListChildren;
		for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
			Node<T, UIdx> * node = getNode(*itNode);
			if(node != NULL){
				node->setIsUpdated(true);	//This node has been iterated, so we do not want to pick it as a child
				std::list<UIdx> & listChildren = node->getListChild();
				for(typename std::list<UIdx>::iterator it(listChildren.begin()); it != listChildren.end(); ++it){
					Node<T, UIdx> * nodeChild = getNode(*it);
					if(nodeChild != NULL){
						if(!nodeChild->getIsUpdated()){
							//The child node is added only if its parents are updated
							if(isListNodeUdpated(nodeChild->getListParent())){
								mapListChildren[*it] = true;
								nodeChild->setIsUpdated(true);
							}
						}
					}
				}
			}
		}
		std::list<UIdx> listNodeOut;
		for(typename std::map<UIdx, bool>::iterator it(mapListChildren.begin()); it != mapListChildren.end(); ++it){
			listNodeOut.push_back(it->first);
		}
		listNode = listNodeOut;
	}
	return listNode.size() != 0lu;
}

///Iterate from children to parents (all node are iterated only once)
/**	@param[out] listNode : list node which can be treated simultaneously
 * 	@return true if the returned list of nodes is not empty, false if the top of the Graph has been reached
*/
template<typename T, typename UIdx>
bool Graph<T, UIdx>::iterateParentCheckUpdate(std::list<UIdx> & listNode){
	if(listNode.size() == 0lu){
		clearIsUpdated();
		listNode = getListLastNode();
	}else{
		std::map<UIdx, bool> mapListParent;
		for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
			Node<T, UIdx> * node = getNode(*itNode);
			if(node != NULL){
				node->setIsUpdated(true);	//This node has been iterated, so we do not want to pick it as a parent
				std::list<UIdx> & listParent = node->getListParent();
				for(typename std::list<UIdx>::iterator it(listParent.begin()); it != listParent.end(); ++it){
					Node<T, UIdx> * nodeParent = getNode(*it);
					if(nodeParent != NULL){
						if(!nodeParent->getIsUpdated()){
							//The parent node is added only if its children are updated
							if(isListNodeUdpated(nodeParent->getListChild())){
								mapListParent[*it] = true;
								nodeParent->setIsUpdated(true);
							}
						}
					}
				}
			}
		}
		std::list<UIdx> listNodeOut;
		for(typename std::map<UIdx, bool>::iterator it(mapListParent.begin()); it != mapListParent.end(); ++it){
			listNodeOut.push_back(it->first);
		}
		listNode = listNodeOut;
	}
	return listNode.size() != 0lu;
}

///Copy function of Graph
/**	@param other : class to copy
*/
template<typename T, typename UIdx>
void Graph<T, UIdx>::copyGraph(const Graph<T, UIdx> & other){
	p_mapNode = other.p_mapNode;
	p_listFirstNode = other.p_listFirstNode;
	p_listLastNode = other.p_listLastNode;
}

///Initialisation function of the class Graph
template<typename T, typename UIdx>
void Graph<T, UIdx>::initialisationGraph(){

}





#endif





Generated by: GCOVR (Version 4.2)

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			Graph<T, UIdx>::Graph(const Graph<T, UIdx> & other){
26			copyGraph(other);
27			}
28
29			///Destructeur of Graph
30			template<typename T, typename UIdx>
31		10	Graph<T, UIdx>::~Graph(){
32
33			}
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		8	bool Graph<T, UIdx>::savePng(const std::string & fileNamePng) const{
51	✓✓	8	if(fileNamePng == "") return false;
52	✓	14	std::string fileTxt("output.dot");
53	✓✗✓	7	if(!saveDot(fileTxt)){
54			std::cerr << "Graph<T, UIdx>::savePng : can't create file '" << fileTxt << "'" << std::endl;
55			return false;
56			}
57	✓✓✓✓ ✓	21	std::string commande("dot -Tpng -o " + fileNamePng + " " + fileTxt + " && rm " + fileTxt);
58	✓✓✓	7	if(system(commande.c_str()) != 0){
59	✓✗✓✗ ✓✗✓✗	1	std::cerr << "Graph<T, UIdx>::savePng : can't create png file '" << fileNamePng << "'" << std::endl;
60		1	return false;
61			}
62		6	return true;
63			}
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		9	bool Graph<T, UIdx>::saveDot(const std::string & fileName) const{
70	✓✓	9	if(fileName == ""){return false;}
71	✓	16	std::ofstream fs;
72	✓	8	fs.open(fileName.c_str());
73	✓✓✓	8	if(!fs.is_open()){
74	✓✗✓✗ ✓✗✓✗	1	std::cerr << "Graph<T, UIdx>::saveDot : can't open file '" << fileName << "'" << std::endl;
75		1	return false;
76			}
77	✓	7	bool b(saveDot(fs));
78	✓	7	fs.close();
79		7	return b;
80			}
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		7	bool Graph<T, UIdx>::saveDot(std::ofstream & fs) const{
87	✓	7	fs << toDot();
88		7	return true;
89			}
90
91			///Convert the graph to dot language
92			/** @return dot
93			*/
94			template<typename T, typename UIdx>
95		7	std::string Graph<T, UIdx>::toDot() const{
96	✓	7	std::string body("");
97	✓	7	body += "digraph G{\n";
98			//save the node definition
99	✓✓	43	for(typename std::map<UIdx, Node<T, UIdx> >::const_iterator it(p_mapNode.begin()); it != p_mapNode.end(); ++it){
100	✓✓	36	body += it->second.getDotDefinition();
101			}
102			//save the connections between nodes
103	✓✓	43	for(typename std::map<UIdx, Node<T, UIdx> >::const_iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
104	✓	72	const std::string & parentNodeName(itNode->second.getDotName());
105		36	const std::list<UIdx> & listChild = itNode->second.getListChild();
106	✓✓	68	for(typename std::list<UIdx>::const_iterator it(listChild.begin()); it != listChild.end(); ++it){
107	✓✓	32	const Node<T, UIdx> * childNode = getNode(*it);
108	✗✓	32	if(childNode == NULL){continue;}
109	✓	32	const std::string & childNodeName(childNode->getDotName());
110	✓✓✓✓ ✓	32	body += "\t" + parentNodeName + " -> " + childNodeName + "[color=\"red\"];\n";
111			}
112			}
113	✓	7	body += "}\n\n";
114		7	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	✓✗✓	21	while(getNode(nodeIndex) != NULL){
126			++nodeIndex;
127			}
128	✓	21	Node<T, UIdx> node(data, name);
129		21	node.setIndex(nodeIndex);
130	✓✓	21	p_mapNode[nodeIndex] = node;
131		42	return nodeIndex;
132			}
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	✓✓✗✓	5	if(getNode(index) != NULL){ //Check if the Node already exists
154			return false;
155			}
156	✓	5	Node<T, UIdx> node(data, name);
157	✓✓	5	node.setIndex(index);
158	✓✓	5	p_mapNode[index] = node;
159		5	return true;
160			}
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	✓✓	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			*/
208			template<typename T, typename UIdx>
209		1	void Graph<T, UIdx>::removeNode(UIdx index){
210		1	Node<T, UIdx> * indexNode = getNode(index);
211	✗✓	1	if(indexNode == NULL){return;} //If the Node does not exist, we stop
212			//Get the parents of the current Node
213		1	std::list<UIdx> & listParent = indexNode->getListParent();
214	✓✗	1	if(listParent.size() != 0lu){
215			//Tell them they do not have child anymore
216	✓✓	2	for(typename std::list<UIdx>::iterator it(listParent.begin()); it != listParent.end(); ++it){
217	✓	1	Node<T, UIdx> * parentNode = getNode(*it);
218	✗✓	1	if(parentNode == NULL){continue;}
219	✓	1	parentNode->removeChild(index);
220			}
221			}else{
222			//Let's remove the current Node from first Node
223			listindex_remove(p_listFirstNode, index);
224			}
225			//Get the children of the current Node
226		1	std::list<UIdx> & listChild = indexNode->getListChild();
227	✓✗	1	if(listChild.size() != 0lu){
228			//Tell them they do not have parent anymore
229	✓✓	2	for(typename std::list<UIdx>::iterator it(listChild.begin()); it != listChild.end(); ++it){
230	✓	1	Node<T, UIdx> * childNode = getNode(*it);
231	✗✓	1	if(childNode == NULL){continue;}
232		1	childNode->removeParent(index);
233			}
234			}else{
235			//Let's remove the current Node from last Node
236			listindex_remove(p_listLastNode, index);
237			}
238			//Now, let's remove the current Node
239		1	p_mapNode.erase(index);
240			}
241
242			///Update the first and last Node of the Graph
243			template<typename T, typename UIdx>
244		1	void Graph<T, UIdx>::updateFirstLastNode(){
245		1	clearFirstNode();
246		1	clearLastNode();
247	✓✓	6	for(typename std::map<UIdx, Node<T, UIdx> >::iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
248	✓✓	5	if(itNode->second.isStart()){ //If the Node does not have any parent, it is a first Node
249	✓	3	p_listFirstNode.push_back(itNode->first);
250			}
251	✓✓	5	if(itNode->second.isEnd()){ //If the Node does not have any child, it is a last Node
252	✓	1	p_listLastNode.push_back(itNode->first);
253			}
254			}
255		1	}
256
257			///Connect a parent to its child
258			/** @param parent : index of the parent Node
259			* @param child : index of the child Node
260			*/
261			template<typename T, typename UIdx>
262		24	void Graph<T, UIdx>::connectNode(UIdx parent, UIdx child){
263	✓	24	Node<T, UIdx> * parentNode = getNode(parent);
264	✗✓	24	if(parentNode == NULL){return;}
265	✓	24	Node<T, UIdx> * childNode = getNode(child);
266	✗✓	24	if(childNode == NULL){return;}
267	✓	24	parentNode->addChild(child);
268	✓	24	childNode->addParent(parent);
269			}
270
271			///Connect a parent to its children
272			/** @param parent : index of the parent Node
273			* @param listChildren : list of the children index
274			*/
275			template<typename T, typename UIdx>
276			void Graph<T, UIdx>::connectNode(UIdx parent, const std::list<UIdx> & listChildren){
277			Node<T, UIdx> * parentNode = getNode(parent);
278			if(parentNode == NULL){return;}
279			for(typename std::list<UIdx>::const_iterator it(listChildren.begin()); it != listChildren.end(); ++it){
280			UIdx child = *it;
281			Node<T, UIdx> * childNode = getNode(child);
282			if(childNode == NULL){continue;}
283			parentNode->addChild(child);
284			childNode->addParent(parent);
285			}
286			}
287
288			///Connect a parent to its children
289			/** @param parent : index of the parent Node
290			* @param vecChildren : vector of the children index
291			*/
292			template<typename T, typename UIdx>
293			void Graph<T, UIdx>::connectNode(UIdx parent, const std::vector<UIdx> & vecChildren){
294			Node<T, UIdx> * parentNode = getNode(parent);
295			if(parentNode == NULL){return;}
296			for(typename std::vector<UIdx>::const_iterator it(vecChildren.begin()); it != vecChildren.end(); ++it){
297			UIdx child = *it;
298			Node<T, UIdx> * childNode = getNode(child);
299			if(childNode == NULL){continue;}
300			parentNode->addChild(child);
301			childNode->addParent(parent);
302			}
303			}
304
305			///Get a Node by pointer
306			/** @param index : index of the node to be used
307			* @return pointer to this Node or NULL if the Node does not exist
308			*/
309			template<typename T, typename UIdx>
310		53	const Node<T, UIdx> * Graph<T, UIdx>::getNode(UIdx index) const{
311	✓	53	typename std::map<UIdx, Node<T, UIdx> >::const_iterator it(p_mapNode.find(index));
312	✓✗	53	if(it != p_mapNode.end()){
313		53	return &(it->second);
314			}else{
315			return NULL;
316			}
317			}
318
319			///Get a Node by pointer
320			/** @param index : index of the node to be used
321			* @return pointer to this Node or NULL if the Node does not exist
322			*/
323			template<typename T, typename UIdx>
324		95	Node<T, UIdx> * Graph<T, UIdx>::getNode(UIdx index){
325	✓	95	typename std::map<UIdx, Node<T, UIdx> >::iterator it(p_mapNode.find(index));
326	✓✓	95	if(it != p_mapNode.end()){
327		69	return &(it->second);
328			}else{
329		26	return NULL;
330			}
331			}
332
333			///Get the first node which is not udpated (getIsUpdated() == false)
334			/** @return pointer to the first node which is not udpated or NULL if there is no
335			*/
336			template<typename T, typename UIdx>
337			const Node<T, UIdx> * Graph<T, UIdx>::getFirstNotUpdatedNode() const{
338			for(typename std::map<UIdx, Node<T, UIdx> >::const_iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
339			if(!itNode->second.getIsUpdated()){
340			return &(itNode->second);
341			}
342			}
343			return NULL;
344			}
345
346			///Get the first node which is not udpated (getIsUpdated() == false)
347			/** @return pointer to the first node which is not udpated or NULL if there is no
348			*/
349			template<typename T, typename UIdx>
350			Node<T, UIdx> * Graph<T, UIdx>::getFirstNotUpdatedNode(){
351			for(typename std::map<UIdx, Node<T, UIdx> >::iterator itNode(p_mapNode.begin()); itNode != p_mapNode.end(); ++itNode){
352			if(!itNode->second.getIsUpdated()){
353			return &(itNode->second);
354			}
355			}
356			return NULL;
357			}
358
359			///Say if the node at index does exit
360			/** @param index : index of the node to be searched
361			* @return true if the Node does exist, false otheriwse
362			*/
363			template<typename T, typename UIdx>
364			bool Graph<T, UIdx>::isNodeExist(UIdx index) const{
365			typename std::map<UIdx, Node<T, UIdx> >::iterator it(p_mapNode.find(index));
366			return it != p_mapNode.end();
367			}
368
369			///Get the number of nodes inside the graph
370			/** @return number of nodes inside the graph
371			*/
372			template<typename T, typename UIdx>
373		1	size_t Graph<T, UIdx>::size() const{
374		1	return p_mapNode.size();
375			}
376
377			///Get the list of the first nodes (without parent)
378			/** @return list of the first nodes (without parent)
379			*/
380			template<typename T, typename UIdx>
381		2	const std::list<UIdx> & Graph<T, UIdx>::getListFirstNode() const{
382		2	return p_listFirstNode;
383			}
384
385			///Get the list of the last nodes (without child)
386			/** @return list of the last nodes (without child)
387			*/
388			template<typename T, typename UIdx>
389		2	const std::list<UIdx> & Graph<T, UIdx>::getListLastNode() const{
390		2	return p_listLastNode;
391			}
392
393			///Iterate from parents to chidren
394			/** @param[out] listNode : list node which can be treated simultaneously
395			* @return true if the returned list of nodes is not empty, false if the bottom of the Graph has been reached
396			*/
397			template<typename T, typename UIdx>
398		4	bool Graph<T, UIdx>::iterateChildren(std::list<UIdx> & listNode) const{
399	✓✓	4	if(listNode.size() == 0lu){
400		1	listNode = getListFirstNode();
401			}else{
402		6	std::map<UIdx, bool> mapListChildren;
403	✓✓	9	for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
404	✓	6	const Node<T, UIdx> * node = getNode(*itNode);
405	✓✗	6	if(node != NULL){
406		6	const std::list<UIdx> & listChildren = node->getListChild();
407	✓✓	10	for(typename std::list<UIdx>::const_iterator it(listChildren.begin()); it != listChildren.end(); ++it){
408	✓	4	mapListChildren[*it] = true;
409			}
410			}
411			}
412		6	std::list<UIdx> listNodeOut;
413	✓✓	6	for(typename std::map<UIdx, bool>::iterator it(mapListChildren.begin()); it != mapListChildren.end(); ++it){
414	✓	3	listNodeOut.push_back(it->first);
415			}
416	✓	3	listNode = listNodeOut;
417			}
418		4	return listNode.size() != 0lu;
419			}
420
421			///Iterate from children to parents
422			/** @param[out] listNode : list node which can be treated simultaneously
423			* @return true if the returned list of nodes is not empty, false if the top of the Graph has been reached
424			*/
425			template<typename T, typename UIdx>
426		4	bool Graph<T, UIdx>::iterateParent(std::list<UIdx> & listNode) const{
427	✓✓	4	if(listNode.size() == 0lu){
428		1	listNode = getListLastNode();
429			}else{
430		6	std::map<UIdx, bool> mapListParent;
431	✓✓	8	for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
432	✓	5	const Node<T, UIdx> * node = getNode(*itNode);
433	✓✗	5	if(node != NULL){
434		5	const std::list<UIdx> & listParent = node->getListParent();
435	✓✓	9	for(typename std::list<UIdx>::const_iterator it(listParent.begin()); it != listParent.end(); ++it){
436	✓	4	mapListParent[*it] = true;
437			}
438			}
439			}
440		6	std::list<UIdx> listNodeOut;
441	✓✓	7	for(typename std::map<UIdx, bool>::iterator it(mapListParent.begin()); it != mapListParent.end(); ++it){
442	✓	4	listNodeOut.push_back(it->first);
443			}
444	✓	3	listNode = listNodeOut;
445			}
446		4	return listNode.size() != 0lu;
447			}
448
449			///Check if the list of given nodes are all updated or not
450			/** @param listNode : list of nodes to be checked
451			* @return true fi all nodes are updated, false otherwise
452			*/
453			template<typename T, typename UIdx>
454		7	bool Graph<T, UIdx>::isListNodeUdpated(const std::list<UIdx> & listNode) const{
455		7	bool b(true);
456	✓✓✓✗ ✓✓	17	for(typename std::list<UIdx>::const_iterator itNode(listNode.begin()); itNode != listNode.end() && b; ++itNode){
457	✓	10	const Node<T, UIdx> * node = getNode(*itNode);
458	✓✗	10	if(node != NULL){
459		10	b &= node->getIsUpdated();
460			}
461			}
462		7	return b;
463			}
464
465			///Iterate from parents to chidren (all node are iterated only once)
466			/** @param[out] listNode : list node which can be treated simultaneously
467			* @return true if the returned list of nodes is not empty, false if the bottom of the Graph has been reached
468			*/
469			template<typename T, typename UIdx>
470		3	bool Graph<T, UIdx>::iterateChildrenCheckUpdate(std::list<UIdx> & listNode){
471	✓✓	3	if(listNode.size() == 0lu){
472		1	clearIsUpdated();
473		1	listNode = getListFirstNode();
474			}else{
475		4	std::map<UIdx, bool> mapListChildren;
476	✓✓	7	for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
477	✓	5	Node<T, UIdx> * node = getNode(*itNode);
478	✓✗	5	if(node != NULL){
479		5	node->setIsUpdated(true); //This node has been iterated, so we do not want to pick it as a child
480		5	std::list<UIdx> & listChildren = node->getListChild();
481	✓✓	9	for(typename std::list<UIdx>::iterator it(listChildren.begin()); it != listChildren.end(); ++it){
482	✓	4	Node<T, UIdx> * nodeChild = getNode(*it);
483	✓✗	4	if(nodeChild != NULL){
484	✓✓	4	if(!nodeChild->getIsUpdated()){
485			//The child node is added only if its parents are updated
486	✓✓✓	3	if(isListNodeUdpated(nodeChild->getListParent())){
487	✓	2	mapListChildren[*it] = true;
488		2	nodeChild->setIsUpdated(true);
489			}
490			}
491			}
492			}
493			}
494			}
495		4	std::list<UIdx> listNodeOut;
496	✓✓	4	for(typename std::map<UIdx, bool>::iterator it(mapListChildren.begin()); it != mapListChildren.end(); ++it){
497	✓	2	listNodeOut.push_back(it->first);
498			}
499	✓	2	listNode = listNodeOut;
500			}
501		3	return listNode.size() != 0lu;
502			}
503
504			///Iterate from children to parents (all node are iterated only once)
505			/** @param[out] listNode : list node which can be treated simultaneously
506			* @return true if the returned list of nodes is not empty, false if the top of the Graph has been reached
507			*/
508			template<typename T, typename UIdx>
509		4	bool Graph<T, UIdx>::iterateParentCheckUpdate(std::list<UIdx> & listNode){
510	✓✓	4	if(listNode.size() == 0lu){
511		1	clearIsUpdated();
512		1	listNode = getListLastNode();
513			}else{
514		6	std::map<UIdx, bool> mapListParent;
515	✓✓	8	for(typename std::list<UIdx>::iterator itNode(listNode.begin()); itNode != listNode.end(); ++itNode){
516	✓	5	Node<T, UIdx> * node = getNode(*itNode);
517	✓✗	5	if(node != NULL){
518		5	node->setIsUpdated(true); //This node has been iterated, so we do not want to pick it as a parent
519		5	std::list<UIdx> & listParent = node->getListParent();
520	✓✓	9	for(typename std::list<UIdx>::iterator it(listParent.begin()); it != listParent.end(); ++it){
521	✓	4	Node<T, UIdx> * nodeParent = getNode(*it);
522	✓✗	4	if(nodeParent != NULL){
523	✓✗	4	if(!nodeParent->getIsUpdated()){
524			//The parent node is added only if its children are updated
525	✓✓✗	4	if(isListNodeUdpated(nodeParent->getListChild())){
526	✓	4	mapListParent[*it] = true;
527		4	nodeParent->setIsUpdated(true);
528			}
529			}
530			}
531			}
532			}
533			}
534		6	std::list<UIdx> listNodeOut;
535	✓✓	7	for(typename std::map<UIdx, bool>::iterator it(mapListParent.begin()); it != mapListParent.end(); ++it){
536	✓	4	listNodeOut.push_back(it->first);
537			}
538	✓	3	listNode = listNodeOut;
539			}
540		4	return listNode.size() != 0lu;
541			}
542
543			///Copy function of Graph
544			/** @param other : class to copy
545			*/
546			template<typename T, typename UIdx>
547			void Graph<T, UIdx>::copyGraph(const Graph<T, UIdx> & other){
548			p_mapNode = other.p_mapNode;
549			p_listFirstNode = other.p_listFirstNode;
550			p_listLastNode = other.p_listLastNode;
551			}
552
553			///Initialisation function of the class Graph
554			template<typename T, typename UIdx>
555		5	void Graph<T, UIdx>::initialisationGraph(){
556
557		5	}
558
559
560
561
562
563			#endif
564
565
566