Head

GCC Code Coverage Report
Directory:	./		Exec	Total	Coverage
File:	tmp_project/PhoenixGraph/src/Graph_impl.h	Lines:	210	217	96.8 %
Date:	2024-12-09 15:41:43	Branches:	186	228	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
 * 	@param reconnectParentToChildren : true to reconnect parents of the node to be removed to its children
*/
template<typename T, typename UIdx>
void Graph<T, UIdx>::removeNode(UIdx index, bool reconnectParentToChildren){
	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);
	}
	if(reconnectParentToChildren && listParent.size() != 0lu && listChild.size() != 0lu){
		for(typename std::list<UIdx>::iterator it(listParent.begin()); it != listParent.end(); ++it){
			connectNode(*it, listChild);
		}
	}
	//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)