AssociationGraphImplObserver.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: The Bio++ Development Group
//
// SPDX-License-Identifier: CECILL-2.1

#ifndef BPP_GRAPH_ASSOCIATIONGRAPHIMPLOBSERVER_H
#define BPP_GRAPH_ASSOCIATIONGRAPHIMPLOBSERVER_H

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <memory>
#include <ostream>
#include <type_traits>
#include <vector>

#include "../Clonable.h"
#include "../Exceptions.h"
#include "../Text/TextTools.h"
#include "AssociationGraphObserver.h"
#include "GlobalGraph.h"

namespace bpp
{
template<class N, class E, class GraphImpl>
class AssociationGraphImplObserver : public virtual AssociationGraphObserver<N, E>
{
public:
  typedef typename AssociationGraphObserver<N, E>::NodeIndex NodeIndex;
  typedef typename AssociationGraphObserver<N, E>::EdgeIndex EdgeIndex;

  typedef Graph::NodeId NodeGraphid;
  typedef Graph::EdgeId EdgeGraphid;

  using Eref = std::shared_ptr<E>;
  using Nref = std::shared_ptr<N>;

protected:
  std::shared_ptr<GraphImpl> subjectGraph_;

private:
  std::vector<Nref > graphidToN_;

  std::vector<Eref > graphidToE_;

  std::map<Nref, NodeGraphid> NToGraphid_;

  std::map<Eref, EdgeGraphid> EToGraphid_;

  /*
   * @}
   */

  std::vector<Nref > indexToN_;

  std::vector<Eref > indexToE_;

  std::map<Nref, NodeIndex> NToIndex_;

  std::map<Eref, EdgeIndex> EToIndex_;

  /*
   * @}
   */

public:
  AssociationGraphImplObserver(bool directed = false) :
    subjectGraph_(std::shared_ptr<GraphImpl>(new GraphImpl(directed))),
    graphidToN_(),
    graphidToE_(),
    NToGraphid_(),
    EToGraphid_(),
    indexToN_(),
    indexToE_(),
    NToIndex_(),
    EToIndex_()
  {
    getGraph()->registerObserver(this);
  }

  AssociationGraphImplObserver(std::shared_ptr<GraphImpl> subjectGraph = 00) :
    subjectGraph_(subjectGraph ? subjectGraph : std::shared_ptr<GraphImpl>(new GraphImpl(true))),
    graphidToN_(),
    graphidToE_(),
    NToGraphid_(),
    EToGraphid_(),
    indexToN_(),
    indexToE_(),
    NToIndex_(),
    EToIndex_()
  {
    getGraph()->registerObserver(this);
  }

  template<class N2, class E2>
  AssociationGraphImplObserver(AssociationGraphImplObserver<N2, E2, GraphImpl> const& graphObserver) :
    subjectGraph_(graphObserver.getGraph()),
    graphidToN_(graphObserver.graphidToN_.size()),
    graphidToE_(graphObserver.graphidToE_.size()),
    NToGraphid_(),
    EToGraphid_(),
    indexToN_(graphObserver.indexToN_.size()),
    indexToE_(graphObserver.indexToE_.size()),
    NToIndex_(),
    EToIndex_()
  {
    for (const auto& itN:graphObserver.NToGraphid_)
    {
      Nref node(AssociationGraphObserver<N, E>::template copy<N2, N>(*itN.first));

      NToGraphid_[node] = itN.second;
      graphidToN_[itN.second] = node;

      const auto& indN = graphObserver.NToIndex_.find(itN.first);

      if (indN != graphObserver.NToIndex_.end())
      {
        NToIndex_[node] = indN->second;
        indexToN_[indN->second] = node;
      }
    }

    for (const auto& itE:graphObserver.EToGraphid_)
    {
      Eref edge(AssociationGraphObserver<N, E>::template copy<E2, E>(*itE.first));

      EToGraphid_[edge] = itE.second;
      graphidToE_[itE.second] = edge;

      const auto& indE = graphObserver.EToIndex_.find(itE.first);

      if (indE != graphObserver.EToIndex_.end())
      {
        EToIndex_[edge] = indE->second;
        indexToE_[indE->second] = edge;
      }
    }

    getGraph()->registerObserver(this);
  }

  AssociationGraphImplObserver(AssociationGraphImplObserver<N, E, GraphImpl> const& graphObserver) :
    subjectGraph_(graphObserver.subjectGraph_),
    graphidToN_(graphObserver.graphidToN_.size()),
    graphidToE_(graphObserver.graphidToE_.size()),
    NToGraphid_(),
    EToGraphid_(),
    indexToN_(graphObserver.indexToN_.size()),
    indexToE_(graphObserver.indexToE_.size()),
    NToIndex_(),
    EToIndex_()
  {
    for (const auto& itN:graphObserver.NToGraphid_)
    {
      Nref node(AssociationGraphObserver<N, E>::template copy<N, N>(*itN.first));

      NToGraphid_[node] = itN.second;
      graphidToN_[itN.second] = node;

      const auto& indN = graphObserver.NToIndex_.find(itN.first);

      if (indN != graphObserver.NToIndex_.end())
      {
        NToIndex_[node] = indN->second;
        indexToN_[indN->second] = node;
      }
    }

    for (const auto& itE:graphObserver.EToGraphid_)
    {
      Eref edge(AssociationGraphObserver<N, E>::template copy<E, E>(*itE.first));

      EToGraphid_[edge] = itE.second;
      graphidToE_[itE.second] = edge;

      const auto& indE = graphObserver.EToIndex_.find(itE.first);

      if (indE != graphObserver.EToIndex_.end())
      {
        EToIndex_[edge] = indE->second;
        indexToE_[indE->second] = edge;
      }
    }

    getGraph()->registerObserver(this);
  }


  AssociationGraphImplObserver<N, E, GraphImpl>& operator=(bpp::AssociationGraphImplObserver<N, E, GraphImpl> const& graphObserver)
  {
    this->graphidToN_.resize(graphObserver.graphidToN_.size());
    this->graphidToE_.resize(graphObserver.graphidToE_.size());
    this->indexToN_.resize(graphObserver.indexToN_.size());
    this->indexToE_.resize(graphObserver.indexToE_.size());

    for (const auto& itN:graphObserver.NToGraphid_)
    {
      Nref node(AssociationGraphObserver<N, E>::template copy<N, N>(*itN.first));

      NToGraphid_[node] = itN.second;
      graphidToN_[itN.second] = node;

      const auto& indN = graphObserver.NToIndex_.find(itN.first);

      if (indN != graphObserver.NToIndex_.end())
      {
        NToIndex_[node] = indN->second;
        indexToN_[indN->second] = node;
      }
    }

    for (const auto& itE:graphObserver.EToGraphid_)
    {
      Eref edge(AssociationGraphObserver<N, E>::template copy<E, E>(*itE.first));

      EToGraphid_[edge] = itE.second;
      graphidToE_[itE.second] = edge;

      const auto& indE = graphObserver.EToIndex_.find(itE.first);

      if (indE != graphObserver.EToIndex_.end())
      {
        EToIndex_[edge] = indE->second;
        indexToE_[indE->second] = edge;
      }
    }

    this->subjectGraph_ = graphObserver.getGraph();

    this->getGraph()->registerObserver(this);

    return *this;
  }


  ~AssociationGraphImplObserver()
  {
    getGraph()->unregisterObserver(this);
  }

  AssociationGraphImplObserver<N, E, GraphImpl>* clone() const { return new AssociationGraphImplObserver<N, E, GraphImpl>(*this); }

  const std::shared_ptr<GraphImpl> getGraph() const
  {
    return subjectGraph_;
  }

  std::shared_ptr<GraphImpl> getGraph()
  {
    return subjectGraph_;
  }

public:
/*
 *@brief Check if has node/edge
 *
 */
  bool hasNode(Nref nodeObject) const
  {
    if (nodeObject == 0)
      return false;
    return NToGraphid_.find(nodeObject) != NToGraphid_.end();
  }

  bool hasEdge(Eref edgeObject) const
  {
    if (edgeObject == 0)
      return false;
    return EToGraphid_.find(edgeObject) != EToGraphid_.end();
  }

  /*
   * @brief Text description of objects
   */
  std::string nodeToString(const Nref nodeObject) const
  {
    auto mess = TextTools::toString(nodeObject);

    if (!hasNode(nodeObject))
      return mess;

    mess += ":Id=" + TextTools::toString(NToGraphid_.at(nodeObject));
    if (hasNodeIndex(nodeObject))
      mess += ":Index=" + TextTools::toString(getNodeIndex(nodeObject));

    return mess;
  }

  std::string edgeToString(const Eref edgeObject) const
  {
    auto mess = TextTools::toString(edgeObject);

    if (!hasEdge(edgeObject))
      return mess;

    mess += ":Id=" + TextTools::toString(EToGraphid_.at(edgeObject));
    if (hasEdgeIndex(edgeObject))
      mess += ":Index=" + TextTools::toString(getEdgeIndex(edgeObject));

    return mess;
  }

private:
  enum neighborType {INCOMING, OUTGOING, BOTH};

  std::vector<Nref > getNeighbors_(const Nref nodeObject, neighborType type) const
  {
    NodeGraphid node = getNodeGraphid(nodeObject);

    // PHASE 1: getting the right neighbors
    std::vector<NodeGraphid> neighbors;
    switch (type)
    {
    case OUTGOING:
      neighbors = getGraph()->getOutgoingNeighbors(node);
      break;
    case INCOMING:
      neighbors = getGraph()->getIncomingNeighbors(node);
      break;
    case BOTH:
      neighbors = getGraph()->getNeighbors(node);
    }
    return getNodesFromGraphid(neighbors);
  }

  std::vector<Eref > getEdges_(const Nref nodeObject, neighborType type) const
  {
    NodeGraphid node = getNodeGraphid(nodeObject);

    // PHASE 1: getting the right neighbors
    std::vector<EdgeGraphid> edges;
    switch (type)
    {
    case OUTGOING:
      edges = getGraph()->getOutgoingEdges(node);
      break;
    case INCOMING:
      edges = getGraph()->getIncomingEdges(node);
      break;
    case BOTH:
      edges = getGraph()->getEdges(node);
    }
    return getEdgesFromGraphid(edges);
  }

  // /@{

public:
  void createNode(Nref nodeObject)
  {
    if (hasNode(nodeObject))
      throw Exception("AssociationGraphImplObserver::createNode : node already exists: " + nodeToString(nodeObject));

    unsigned int newGraphNode = getGraph()->createNode();
    associateNode(nodeObject, newGraphNode);
  }

  void createNode(Nref objectOriginNode, Nref newNodeObject, Eref newEdgeObject = 00)
  {
    createNode(newNodeObject);
    link(objectOriginNode, newNodeObject, newEdgeObject);
  }

public:
  void link(Nref nodeObjectA, Nref nodeObjectB, Eref edgeObject = 00)
  {
    // checking the nodes
    if (!hasNode(nodeObjectA))
      throw Exception("First node is not in the graph observer: " + nodeToString(nodeObjectA));
    if (!hasNode(nodeObjectB))
      throw Exception("Second node is not in the graph observer:" + nodeToString(nodeObjectB));

    // checking if the edge is not already in the GraphObserver
    if (edgeObject != 00 && hasEdge(edgeObject))
    {
      auto nodes = getNodes(edgeObject);
      throw Exception("AssociationGraphImplObserver::link: The given edge is already associated to a relation in the subjectGraph: " + edgeToString(edgeObject) + ":" + nodeToString(nodes.first) + " -> " + nodeToString(nodes.second));
    }

    EdgeGraphid newGraphEdge = getGraph()->link(NToGraphid_.at(nodeObjectA), NToGraphid_.at(nodeObjectB));

    if (graphidToE_.size() < newGraphEdge + 1)
      graphidToE_.resize(newGraphEdge + 1);
    graphidToE_.at(newGraphEdge) = edgeObject;
    EToGraphid_[edgeObject] = newGraphEdge;
  }


  void unlink(Nref nodeObjectA, Nref nodeObjectB)
  {
    // checking the nodes
    if (!hasNode(nodeObjectA))
      throw Exception("First node is not in the graph observer: " + nodeToString(nodeObjectA));
    if (!hasNode(nodeObjectB))
      throw Exception("Second node is not in the graph observer:" + nodeToString(nodeObjectB));

    getGraph()->unlink(NToGraphid_.at(nodeObjectA), NToGraphid_.at(nodeObjectB));
  }

public:
  void deleteNode(Nref nodeObject)
  {
    // first deleting the node in the graph
    getGraph()->deleteNode(getNodeGraphid(nodeObject));
    // then forgetting
    dissociateNode(nodeObject);
  }


  // /@}

  // /@{

  void associateNode(Nref nodeObject, NodeGraphid graphNode)
  {
    if (hasNode(nodeObject))
      throw Exception("AssociationGraphImplObserver::associateNode : node already exists: " + nodeToString(nodeObject));

    // nodes vector must be the right size. Eg: to store a node with
    // the ID 3, the vector must be of size 4: {0,1,2,3} (size = 4)
    if (graphidToN_.size() < graphNode + 1)
      graphidToN_.resize(graphNode + 1);

    // now storing the node
    graphidToN_.at(graphNode) = nodeObject;
    NToGraphid_[nodeObject] = graphNode;
  }

  void associateEdge(Eref edgeObject, EdgeGraphid graphEdge)
  {
    if (hasEdge(edgeObject))
      throw Exception("AssociationGraphImplObserver::associateEdge : edge already exists: " + edgeToString(edgeObject));

    // edges vector must be the right size. Eg: to store an edge with
    // the ID 3, the vector must be of size 4: {0,1,2,3} (size = 4)
    if (graphidToE_.size() < graphEdge + 1)
      graphidToE_.resize(graphEdge + 1);

    // now storing the edge
    graphidToE_.at(graphEdge) = edgeObject;
    EToGraphid_[edgeObject] = graphEdge;
  }

  void dissociateNode(Nref nodeObject)
  {
    typename std::map<Nref, NodeGraphid>::iterator nodeToForget = NToGraphid_.find(nodeObject);
    graphidToN_.at(nodeToForget->second) = 00;
    NToGraphid_.erase(nodeToForget);
  }


  void dissociateEdge(Eref edgeObject)
  {
    typename std::map<Eref, EdgeGraphid>::iterator edgeToForget = EToGraphid_.find(edgeObject);
    graphidToE_.at(edgeToForget->second) = 00;
    EToGraphid_.erase(edgeToForget);
  }


  NodeGraphid getNodeGraphid(const Nref nodeObject) const
  {
    typename std::map<Nref, NodeGraphid>::const_iterator found = NToGraphid_.find(nodeObject);
    if (found == NToGraphid_.end())
      throw Exception("Unexisting node object: " + TextTools::toString(nodeObject));
    return found->second;
  }


  EdgeGraphid getEdgeGraphid(const Eref edgeObject) const
  {
    typename std::map<Eref, EdgeGraphid>::const_iterator found = EToGraphid_.find(edgeObject);
    if (found == EToGraphid_.end())
      throw Exception("Unexisting edge object: " + TextTools::toString(edgeObject));
    return found->second;
  }


  Nref getNodeFromGraphid(NodeGraphid node)
  {
    if (node >= graphidToN_.size())
      return 0;
    return graphidToN_.at(node);
  }

  const Nref getNodeFromGraphid(NodeGraphid node) const
  {
    if (node >= graphidToN_.size())
      return 0;
    return graphidToN_.at(node);
  }

  std::vector<Nref > getNodesFromGraphid(std::vector<NodeGraphid> nodes) const
  {
    std::vector<Nref > nodeObjects;
    for (typename std::vector<NodeGraphid>::iterator currNode = nodes.begin(); currNode != nodes.end(); currNode++)
    {
      if (*currNode > graphidToN_.size())
        continue;
      Nref foundNodeObject = graphidToN_.at(*currNode);
      if (!foundNodeObject)
        continue;
      nodeObjects.push_back(foundNodeObject);
    }
    return nodeObjects;
  }

  Eref getEdgeFromGraphid(EdgeGraphid edge)
  {
    if (edge >= graphidToE_.size())
      return 0;

    return graphidToE_.at(edge);
  }

  const Eref getEdgeFromGraphid(EdgeGraphid edge) const
  {
    if (edge >= graphidToE_.size())
      return 0;

    return graphidToE_.at(edge);
  }

  std::vector<Eref > getEdgesFromGraphid(std::vector<EdgeGraphid> edges) const
  {
    std::vector<Eref > edgeObjects;
    for (const auto& currEdge:edges)
    {
      if (currEdge > graphidToE_.size())
        continue;
      Eref foundEdgeObject = graphidToE_.at(currEdge);
      if (!foundEdgeObject)
        continue;
      edgeObjects.push_back(foundEdgeObject);
    }
    return edgeObjects;
  }


  void setRoot(const Nref newRoot)
  {
    return getGraph()->setRoot(getNodeGraphid(newRoot));
  }

  Nref getRoot() const
  {
    return this->getNodeFromGraphid(this->getGraph()->getRoot());
  }

  NodeIndex getRootIndex() const
  {
    return this->getNodeIndex(this->getNodeFromGraphid(this->getGraph()->getRoot()));
  }

  // /@}

  // /@{

  /*
   * @brief Return if object has an index.
   *
   */
  bool hasNodeIndex(const Nref nodeObject) const
  {
    return NToIndex_.find(nodeObject) != NToIndex_.end();
  }

  bool hasEdgeIndex(const Eref edgeObject) const
  {
    return EToIndex_.find(edgeObject) != EToIndex_.end();
  }

  NodeIndex getNodeIndex(const Nref nodeObject) const
  {
    const auto found = NToIndex_.find(nodeObject);
    if (found == NToIndex_.end())
      throw Exception("getNodeIndex: Node object has no index : " + nodeToString(nodeObject));

    return found->second;
  }

  std::vector<NodeIndex> getNodeIndexes(std::vector<Nref > nodes) const
  {
    std::vector<NodeIndex> nodeIndexes(nodes.size());

    std::transform(nodes.begin(), nodes.end(), nodeIndexes.begin(), [this](const Nref& nodeObject){return this->getNodeIndex(nodeObject);});

    return nodeIndexes;
  }

  EdgeIndex getEdgeIndex(const Eref edgeObject) const
  {
    auto found = EToIndex_.find(edgeObject);
    if (found == EToIndex_.end())
      throw Exception("getEdgeIndex: Edge object has no index: " + edgeToString(edgeObject));
    return found->second;
  }

  std::vector<EdgeIndex> getEdgeIndexes(std::vector<Eref > edges) const
  {
    std::vector<EdgeIndex> edgeIndexes(edges.size());

    std::transform(edges.begin(), edges.end(), edgeIndexes.begin(), [this](const Eref& edgeObject){return this->getEdgeIndex(edgeObject);});

    return edgeIndexes;
  }

  NodeIndex setNodeIndex(const Nref nodeObject, NodeIndex index)
  {
    // nodes vector must be the right size. Eg: to store a node with
    // the index 3, the vector must be of size 4: {0,1,2,3} (size = 4)
    if (hasNode(index))
      throw Exception("AssociationGraphImplObserver::setNodeIndex : index already exists: " + nodeToString(nodeObject));
    if (NToIndex_.find(nodeObject) != NToIndex_.end())
      throw Exception("AssociationGraphImplObserver::setNodeIndex : nodeObject has already an index: " + nodeToString(nodeObject));

    if (index >= indexToN_.size())
      indexToN_.resize(index + 1);

    // now storing the node
    indexToN_.at(index) = nodeObject;
    NToIndex_[nodeObject] = index;
    return index;
  }

  EdgeIndex setEdgeIndex(const Eref edgeObject, EdgeIndex index)
  {
    // nodes vector must be the right size. Eg: to store an edge with
    // the index 3, the vector must be of size 4: {0,1,2,3} (size = 4)
    if (hasEdge(index))
      throw Exception("AssociationGraphImplObserver::setEdgeIndex : index already exists: " + edgeToString(edgeObject));
    if (EToIndex_.find(edgeObject) != EToIndex_.end())
      throw Exception("AssociationGraphImplObserver::setEdgeIndex : edgeObject has already an index: " + edgeToString(edgeObject));

    if (index >= indexToE_.size())
      indexToE_.resize(index + 1);

    // now storing the edge
    indexToE_.at(index) = edgeObject;
    EToIndex_[edgeObject] = index;
    return index;
  }

  NodeIndex addNodeIndex(const Nref nodeObject)
  {
    // nodes vector must be the right size. Eg: to store a node with
    // the index 3, the vector must be of size 4: {0,1,2,3} (size = 4)
    if (NToIndex_.find(nodeObject) != NToIndex_.end())
      throw Exception("AssociationGraphImplObserver::addNodeIndex : nodeObject has already an index: " + nodeToString(nodeObject));

    NodeIndex index = NodeIndex(indexToN_.size());
    for (auto i = 0; i < indexToN_.size(); i++)
    {
      if (!indexToN_.at(size_t(i)))
      {
        index = NodeIndex(i);
        break;
      }
    }

    if (index >= indexToN_.size())
      indexToN_.resize(index + 1);

    // now storing the node
    indexToN_.at(index) = nodeObject;
    NToIndex_[nodeObject] = index;
    return index;
  }

  EdgeIndex addEdgeIndex(const Eref edgeObject)
  {
    // nodes vector must be the right size. Eg: to store an edge with
    // the index 3, the vector must be of size 4: {0,1,2,3} (size = 4)
    if (EToIndex_.find(edgeObject) != EToIndex_.end())
      throw Exception("AssociationGraphImplObserver::addEdgeIndex : edgeObject has already an index: " + edgeToString(edgeObject));

    EdgeIndex index = indexToE_.size();
    for (auto i = 0; i < indexToE_.size(); i++)
    {
      if (!indexToE_.at(i))
      {
        index = i;
        break;
      }
    }

    if (index >= indexToE_.size())
      indexToE_.resize(index + 1);

    // now storing the edge
    indexToE_.at(index) = edgeObject;
    EToIndex_[edgeObject] = index;
    return index;
  }

  bool hasNode(NodeIndex node) const
  {
    return node < indexToN_.size() && indexToN_.at(node);
  }

  bool hasEdge(EdgeIndex edge) const
  {
    return edge < indexToE_.size() && indexToE_.at(edge);
  }

  Nref getNode(NodeIndex node) const
  {
    return indexToN_.at(node);
  }

  Eref getEdge(EdgeIndex edge) const
  {
    return indexToE_.at(edge);
  }

  // /@}

  // /@{

  /*
   * @brief Output graph in a dot format.
   *
   * Nodes are labeled as "n[Index_]Id", and edge are labeled as
   * "e[Index]_Id".
   *
   * Existing edge between nodes are plain, otherwise dotted.
   *
   * @param fname the name of the file where the DOT format will be output
   * @param name a string naming the graph
   *
   */
  void outputToDot(const std::string& fname, const std::string& name) const
  {
    std::ofstream out;
    out.open(fname);
    outputToDot(out, name);
    out.close();
  }

  void outputToDot(std::ostream& out, const std::string& name) const
  {
    out << (getGraph()->isDirected() ? "digraph" : "graph") << " " << name << " {\n   ";
    std::set<std::pair<Nref, Nref>> alreadyFigured;
    auto allNodes = getAllNodes();

    for (const auto& node: allNodes)
    {
      auto children = getOutgoingNeighbors(node);
      for (const auto& currChild : children)
      {
        if (alreadyFigured.find(std::pair<Nref, Nref>(node, currChild)) != alreadyFigured.end() || (getGraph()->isDirected() && alreadyFigured.find(std::pair<Nref, Nref>(currChild, node)) != alreadyFigured.end()))
          continue;

        alreadyFigured.insert(std::pair<Nref, Nref>(node, currChild));

        out << "n";
        if (hasNodeIndex(node))
          out << getNodeIndex(node) << "_";
        out << NToGraphid_.at(node);

        out << (getGraph()->isDirected() ? " -> " : " -- ");

        out << "n";
        if (hasNodeIndex(currChild))
          out << getNodeIndex(currChild) << "_";
        out << NToGraphid_.at(currChild);

        auto edge = getEdgeLinking(node, currChild);
        if (!edge)
          out << " [style = dotted]";
        else
        {
          out << " [label = e";
          if (hasEdgeIndex(edge))
            out << getEdgeIndex(edge) << "_";
          out << EToGraphid_.at(edge) << "]";
        }
        out << ";\n   ";
      }
    }
    out << "}";
  }

  template<class GraphIterator, bool is_const>
  class NodeIteratorClass :
    virtual public AssociationGraphObserver<N, E>::NodeIterator
  {
private:
    NodesIteratorClass<GraphIterator, is_const> it_;
    const AssociationGraphImplObserver<N, E, GraphImpl>& agio_;

public:
    NodeIteratorClass<GraphIterator, is_const>(AssociationGraphImplObserver<N, E, GraphImpl>& agio) : it_(*agio.getGraph()),
      agio_(agio) { start(); }

    NodeIteratorClass<GraphIterator, is_const>(const AssociationGraphImplObserver<N, E, GraphImpl>& agio) : it_(*agio.getGraph()),
      agio_(agio) { start(); }

    NodeIteratorClass<GraphIterator, is_const>(AssociationGraphImplObserver<N, E, GraphImpl>& agio, Nref n) : it_(*agio.getGraph(), agio.getNodeGraphid(n)),
      agio_(agio) {start(); }

    NodeIteratorClass<GraphIterator, is_const>(const AssociationGraphImplObserver<N, E, GraphImpl>& agio, Nref n) : it_(*agio.getGraph(), agio.getNodeGraphid(n)),
      agio_(agio) {start(); }

    ~NodeIteratorClass<GraphIterator, is_const>() {}

    void next() {it_.next(); while (!it_.end() && agio_.getNodeFromGraphid(*it_) == 0) it_.next(); }

    bool end() const {return it_.end(); }

    void start() { it_.start(); while (!it_.end() && (agio_.getNodeFromGraphid(*it_) == 0)) it_.next(); }

    Nref operator*() {return agio_.getNodeFromGraphid(*it_); }
  };


  std::unique_ptr<typename AssociationGraphObserver<N, E>::NodeIterator> allNodesIterator()
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::ALLGRAPHITER, false>>(new AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::ALLGRAPHITER, false>(*this));
  }

  std::unique_ptr<typename AssociationGraphObserver<N, E>::NodeIterator> allNodesIterator() const
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::ALLGRAPHITER, true>>(new AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::ALLGRAPHITER, true>(*this));
  }


  /*
   * @brief builds iterator on the neighbor nodes of a Node
   *
   */
  std::unique_ptr<typename AssociationGraphObserver<N, E>::NodeIterator> outgoingNeighborNodesIterator(Nref node)
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::OUTGOINGNEIGHBORITER, false>>(new AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::OUTGOINGNEIGHBORITER, false>(*this, node));
  }

  std::unique_ptr<typename AssociationGraphObserver<N, E>::NodeIterator> outgoingNeighborNodesIterator(Nref node) const
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::OUTGOINGNEIGHBORITER, true>>(new AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::OUTGOINGNEIGHBORITER, true>(*this, node));
  }


  /*
   * @brief builds iterator on the neighbor nodes of a Node
   *
   */
  std::unique_ptr<typename AssociationGraphObserver<N, E>::NodeIterator> incomingNeighborNodesIterator(Nref node)
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::INCOMINGNEIGHBORITER, false>>(new AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::INCOMINGNEIGHBORITER, false>(*this, node));
  }

  std::unique_ptr<typename AssociationGraphObserver<N, E>::NodeIterator> incomingNeighborNodesIterator(Nref node) const
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::INCOMINGNEIGHBORITER, true>>(new AssociationGraphImplObserver<N, E, GraphImpl>::NodeIteratorClass<Graph::INCOMINGNEIGHBORITER, true>(*this, node));
  }


  std::vector<Nref > getNeighbors(const Nref node) const
  {
    return getNodesFromGraphid(getGraph()->getNeighbors(getNodeGraphid(node)));
  }

  std::vector<NodeIndex> getNeighbors(NodeIndex node) const
  {
    return getNodeIndexes(getNeighbors(getNode(node)));
  }

  std::vector<Eref > getEdges(const Nref node) const
  {
    return getEdgesFromGraphid(getGraph()->getEdges(getNodeGraphid(node)));
  }

  std::vector<EdgeIndex> getEdges(NodeIndex node) const
  {
    return getEdgeIndexes(getEdges(getNode(node)));
  }


  std::vector<Nref > getOutgoingNeighbors(const Nref node) const
  {
    return getNodesFromGraphid(getGraph()->getOutgoingNeighbors(getNodeGraphid(node)));
  }

  std::vector<NodeIndex> getOutgoingNeighbors(NodeIndex node) const
  {
    return getNodeIndexes(getOutgoingNeighbors(getNode(node)));
  }

  std::vector<Eref > getOutgoingEdges(const Nref node) const
  {
    return getEdgesFromGraphid(getGraph()->getOutgoingEdges(getNodeGraphid(node)));
  }

  std::vector<EdgeIndex> getOutgoingEdges(NodeIndex node) const
  {
    return getEdgeIndexes(getOutgoingEdges(getNode(node)));
  }

  std::vector<Nref > getIncomingNeighbors(const Nref node) const
  {
    return getNodesFromGraphid(getGraph()->getIncomingNeighbors(getNodeGraphid(node)));
  }

  std::vector<NodeIndex> getIncomingNeighbors(NodeIndex node) const
  {
    return getNodeIndexes(getIncomingNeighbors(getNode(node)));
  }


  std::vector<Eref > getIncomingEdges(const Nref node) const
  {
    return getEdgesFromGraphid(getGraph()->getIncomingEdges(getNodeGraphid(node)));
  }

  std::vector<EdgeIndex> getIncomingEdges(NodeIndex node) const
  {
    return getEdgeIndexes(getIncomingEdges(getNode(node)));
  }

  std::vector<Nref > getLeavesFromNode(Nref node, unsigned int maxDepth) const
  {
    return getNodesFromGraphid(getGraph()->getLeavesFromNode(getNodeGraphid(node), maxDepth));
  }

  std::vector<Nref > getAllLeaves() const
  {
    std::vector<Nref > leavesToReturn;
    // fetching all the graph Leaves
    std::vector<NodeGraphid> graphLeaves = getGraph()->getAllLeaves();
    // testing if they are defined in this observer
    for (typename std::vector<NodeGraphid>::iterator currGraphLeave = graphLeaves.begin(); currGraphLeave != graphLeaves.end(); currGraphLeave++)
    {
      Nref foundLeafObject = graphidToN_.at(*currGraphLeave);
      if (foundLeafObject != 00)
        leavesToReturn.push_back(foundLeafObject);
    }
    return leavesToReturn;
  }

  std::vector<NodeIndex> getAllLeavesIndexes() const
  {
    std::vector<NodeIndex> leavesToReturn;

    // fetching all the graph Leaves
    std::vector<NodeGraphid> graphLeaves = getGraph()->getAllLeaves();
    // testing if they are defined in this observer
    for (typename std::vector<NodeGraphid>::iterator currGraphLeave = graphLeaves.begin(); currGraphLeave != graphLeaves.end(); currGraphLeave++)
    {
      Nref foundLeafObject = graphidToN_.at(*currGraphLeave);
      if (foundLeafObject != 00)
        leavesToReturn.push_back(getNodeIndex(foundLeafObject));
    }
    return leavesToReturn;
  }

  std::vector<Nref > getAllInnerNodes() const
  {
    std::vector<Nref > nodesToReturn;
    // fetching all the graph Leaves
    std::vector<NodeGraphid> graphNodes = getGraph()->getAllInnerNodes();
    // testing if they are defined in this observer
    for (const auto& currGraphNode : graphNodes)
    {
      Nref foundNodeObject = graphidToN_.at(currGraphNode);
      if (foundNodeObject != 00)
        nodesToReturn.push_back(foundNodeObject);
    }
    return nodesToReturn;
  }

  std::vector<NodeIndex> getAllInnerNodesIndexes() const
  {
    std::vector<NodeIndex> nodesToReturn;
    // fetching all the graph Leaves
    std::vector<NodeGraphid> graphNodes = getGraph()->getAllInnerNodes();
    // testing if they are defined in this observer
    for (const auto& currGraphNode : graphNodes)
    {
      Nref foundNodeObject = graphidToN_.at(currGraphNode);
      if (foundNodeObject != 00)
        nodesToReturn.push_back(getNodeIndex(foundNodeObject));
    }
    return nodesToReturn;
  }

  std::vector<Nref > getAllNodes() const
  {
    std::vector<Nref > nodesToReturn;
    for (typename std::vector<Nref >::const_iterator currNodeObject = graphidToN_.begin(); currNodeObject != graphidToN_.end(); currNodeObject++)
    {
      if (*currNodeObject != 00)
      {
        nodesToReturn.push_back(*currNodeObject);
      }
    }
    return nodesToReturn;
  }

  std::vector<NodeIndex> getAllNodesIndexes() const
  {
    std::vector<NodeIndex> indexesToReturn;
    for (const auto& currNodeObject : graphidToN_)
    {
      if (currNodeObject != 00)
      {
        indexesToReturn.push_back(getNodeIndex(currNodeObject));
      }
    }
    return indexesToReturn;
  }

  std::vector<EdgeIndex> getAllEdgesIndexes() const
  {
    std::vector<typename AssociationGraphObserver<N, E>::EdgeIndex > indexesToReturn;
    for (typename std::vector<Eref >::const_iterator currEdgeObject = graphidToE_.begin(); currEdgeObject != graphidToE_.end(); currEdgeObject++)
    {
      if (*currEdgeObject != 00)
      {
        indexesToReturn.push_back(getEdgeIndex(*currEdgeObject));
      }
    }
    return indexesToReturn;
  }


  template<class GraphIterator, bool is_const>
  class EdgeIteratorClass :
    public AssociationGraphObserver<N, E>::EdgeIterator
  {
private:
    EdgesIteratorClass<GraphIterator, is_const> it_;
    const AssociationGraphImplObserver<N, E, GraphImpl>& agio_;

public:
    EdgeIteratorClass<GraphIterator, is_const>(AssociationGraphImplObserver<N, E, GraphImpl>& agio) : it_(*agio.getGraph()),
      agio_(agio) { start(); }

    EdgeIteratorClass<GraphIterator, is_const>(AssociationGraphImplObserver<N, E, GraphImpl>& agio, Nref n) : it_(*agio.getGraph(), agio.getNodeGraphid(n)),
      agio_(agio) { start(); }

    EdgeIteratorClass<GraphIterator, is_const>(const AssociationGraphImplObserver<N, E, GraphImpl>& agio) : it_(*agio.getGraph()),
      agio_(agio) { start(); }

    EdgeIteratorClass<GraphIterator, is_const>(const AssociationGraphImplObserver<N, E, GraphImpl>& agio, Nref n) : it_(*agio.getGraph(), agio.getNodeGraphid(n)),
      agio_(agio) { start(); }

    ~EdgeIteratorClass<GraphIterator, is_const>() {}

    void next() {it_.next(); while (!it_.end() && (agio_.getEdgeFromGraphid(*it_) == 0)) it_.next(); }

    bool end() const {return it_.end(); }

    void start() { it_.start(); while (!it_.end() && (agio_.getEdgeFromGraphid(*it_) == 0)) it_.next(); }

    Eref operator*() {return agio_.getEdgeFromGraphid(*it_); }
  };


  std::unique_ptr<typename AssociationGraphObserver<N, E>::EdgeIterator> allEdgesIterator()
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::ALLGRAPHITER, false>>(new AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::ALLGRAPHITER, false>(*this));
  }

  std::unique_ptr<typename AssociationGraphObserver<N, E>::EdgeIterator> allEdgesIterator() const
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::ALLGRAPHITER, true>>(new AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::ALLGRAPHITER, true>(*this));
  }

  /*
   * @brief builds iterator on the outgoing neighbor nodes of a Edge
   *
   */
  std::unique_ptr<typename AssociationGraphObserver<N, E>::EdgeIterator> outgoingEdgesIterator(Nref node)
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::OUTGOINGNEIGHBORITER, false>>(new AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::OUTGOINGNEIGHBORITER, false>(*this, node));
  }

  std::unique_ptr<typename AssociationGraphObserver<N, E>::EdgeIterator> outgoingEdgesIterator(Nref node) const
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::OUTGOINGNEIGHBORITER, true>>(new AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::OUTGOINGNEIGHBORITER, true>(*this, node));
  }

  /*
   * @brief builds iterator on the incoming neighbor nodes of a Edge
   *
   */
  std::unique_ptr<typename AssociationGraphObserver<N, E>::EdgeIterator> incomingEdgesIterator(Nref node)
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::INCOMINGNEIGHBORITER, false>>(new AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::INCOMINGNEIGHBORITER, false>(*this, node));
  }

  std::unique_ptr<typename AssociationGraphObserver<N, E>::EdgeIterator> incomingEdgesIterator(Nref node) const
  {
    return std::unique_ptr<AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::INCOMINGNEIGHBORITER, true>>(new AssociationGraphImplObserver<N, E, GraphImpl>::EdgeIteratorClass<Graph::INCOMINGNEIGHBORITER, true>(*this, node));
  }

  std::vector<Eref > getAllEdges() const
  {
    std::vector<Eref > branchesToReturn;
    for (typename std::vector<Eref >::const_iterator currBrObject = graphidToE_.begin(); currBrObject != graphidToE_.end(); currBrObject++)
    {
      if (*currBrObject != 00)
      {
        branchesToReturn.push_back(*currBrObject);
      }
    }
    return branchesToReturn;
  }

  bool isLeaf(const Nref node) const
  {
    return getGraph()->isLeaf(this->getNodeGraphid(node));
  }

  bool isLeaf(const NodeIndex nodeid) const
  {
    return getGraph()->isLeaf(this->getNodeGraphid(getNode(nodeid)));
  }

  std::pair<Nref, Nref> getNodes(Eref edge) const
  {
    std::pair<NodeGraphid, NodeGraphid> nodes = getGraph()->getNodes(getEdgeGraphid(edge));
    return std::pair<Nref, Nref >(getNodeFromGraphid(nodes.first), getNodeFromGraphid(nodes.second));
  }

  Eref getEdgeLinking(Nref nodeA, Nref nodeB) const
  {
    return getEdgeFromGraphid(getGraph()->getEdge(getNodeGraphid(nodeA), getNodeGraphid(nodeB)));
  }

  void setEdgeLinking(Nref nodeA, Nref nodeB, Eref edge)
  {
    associateEdge(edge, getGraph()->getEdge(getNodeGraphid(nodeA), getNodeGraphid(nodeB)));
  }

  // /@}


  // /@{

  void deletedEdgesUpdate(const std::vector< unsigned int >& edgesToDelete)
  {
    for (typename std::vector<EdgeGraphid>::const_iterator currEdge = edgesToDelete.begin(); currEdge != edgesToDelete.end(); currEdge++)
    {
      if (graphidToE_.size() > *currEdge)
      {
        Eref edgeObject = graphidToE_.at(*currEdge);
        graphidToE_.at(*currEdge) = 00;

        EToGraphid_.erase(edgeObject);
      }
    }
  }

  void deletedNodesUpdate(const std::vector< unsigned int >& nodesToDelete)
  {
    for (typename std::vector<EdgeGraphid>::const_iterator currNode = nodesToDelete.begin(); currNode != nodesToDelete.end(); currNode++)
    {
      if (graphidToN_.size() > *currNode)
      {
        Nref nodeObject = graphidToN_.at(*currNode);
        graphidToN_.at(*currNode) = 00;

        NToGraphid_.erase(nodeObject);
      }
    }
  }

  // /@}

  // /@{

  size_t getNumberOfNodes() const
  {
    return NToGraphid_.size();
  }

  size_t getNumberOfEdges() const
  {
    return EToGraphid_.size();
  }


  size_t getNumberOfLeaves() const
  {
    size_t nb = 0;
    for (typename std::vector<Nref >::const_iterator currNodeObject = graphidToN_.begin(); currNodeObject != graphidToN_.end(); currNodeObject++)
    {
      if ((*currNodeObject != 00) && (isLeaf(*currNodeObject)))
        nb++;
    }

    return nb;
  }

  size_t getDegree(const Nref node) const
  {
    return getGraph()->getDegree(getNodeGraphid(node));
  }

  // /@}

  template<typename N2, typename E2, typename G2> friend class AssociationGraphImplObserver;
};

/***************/

template<class N, class E>
using AssociationGlobalGraphObserver = AssociationGraphImplObserver<N, E, GlobalGraph>;
}
#endif // BPP_GRAPH_ASSOCIATIONGRAPHIMPLOBSERVER_H