Graph_impl.h

Go to the documentation of this file.

/***************************************
        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"

template<typename T, typename UIdx>
Graph<T, UIdx>::Graph(){
        initialisationGraph();
}


template<typename T, typename UIdx>
Graph<T, UIdx>::Graph(const Graph<T, UIdx> & other){
        copyGraph(other);
}

template<typename T, typename UIdx>
Graph<T, UIdx>::~Graph(){
        
}


template<typename T, typename UIdx>
Graph<T, UIdx> & Graph<T, UIdx>::operator = (const Graph<T, UIdx> & other){
        copyGraph(other);
        return *this;
}


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;
}


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;
}


template<typename T, typename UIdx>
bool Graph<T, UIdx>::saveDot(std::ofstream & fs) const{
        fs << toDot();
        return true;
}


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;
}


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;
}


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);
}


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;
}


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;
        }
}

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);
        }
}

template<typename T, typename UIdx>
void Graph<T, UIdx>::clearMapNode(){p_mapNode.clear();}

template<typename T, typename UIdx>
void Graph<T, UIdx>::clearFirstNode(){p_listFirstNode.clear();}

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();
}


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);
}

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);
                }
        }
}


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);
}


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);
        }
}


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);
        }
}


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;
        }
}


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;
        }
}


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;
}


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;
}


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();
}


template<typename T, typename UIdx>
size_t Graph<T, UIdx>::size() const{
        return p_mapNode.size();
}


template<typename T, typename UIdx>
const std::list<UIdx> & Graph<T, UIdx>::getListFirstNode() const{
        return p_listFirstNode;
}


template<typename T, typename UIdx>
const std::list<UIdx> & Graph<T, UIdx>::getListLastNode() const{
        return p_listLastNode;
}


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;
}


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;
}


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;
}


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;
}


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;
}


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;
}

template<typename T, typename UIdx>
void Graph<T, UIdx>::initialisationGraph(){
        
}
 
 
 
 
 
#endif