DAGraphImpl.h

Go to the documentation of this file.

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

#ifndef BPP_GRAPH_DAGRAPHIMPL_H
#define BPP_GRAPH_DAGRAPHIMPL_H

#include <iostream>
#include <ostream>
#include <string>
#include <vector>

#include "../Exceptions.h"
#include "../Numeric/VectorTools.h"
#include "DAGraph.h"
#include "GlobalGraph.h"

namespace bpp
{
template<class GraphImpl>
class DAGraphImpl :
  public virtual DAGraph,
  public GraphImpl
{
protected:
  mutable bool isValid_;

  mutable bool isRooted_;

  // unvalidate the DAG
  virtual void topologyHasChanged_() const;

  // will throw an exception if the DA is not valid
  void mustBeValid_() const;

  // will throw an exception if the DA is not rooted, ie as more
  // than one node with no father.

  void mustBeRooted_() const;

  // test the validity of the DAG
  bool validate_() const;

  void propagateDirection_(Graph::NodeId node);

  void orientGraphFrom_(std::set<Graph::NodeId>& metNodes, Graph::NodeId localRoot);

public:
  DAGraphImpl(bool b = true);

  bool isValid() const;

  bool isRooted() const;

  bool isLeaf(Graph::NodeId node) const;

  bool hasFather(Graph::NodeId node) const;

  std::vector<Graph::NodeId> getFathers(Graph::NodeId nodeid) const;

  size_t getNumberOfFathers(Graph::NodeId node) const;

  void addFather(Graph::NodeId node, Graph::NodeId father);

  void addFather(Graph::NodeId node, Graph::NodeId father, Graph::EdgeId edgeId);

  void removeFather(Graph::NodeId node, Graph::NodeId father);

  std::vector<Graph::NodeId> removeFathers(Graph::NodeId node);

  std::vector<Graph::NodeId> getLeavesUnderNode(Graph::NodeId node) const;

  std::vector<Graph::NodeId> getSons(Graph::NodeId node) const;

  size_t getNumberOfSons(Graph::NodeId node) const;

  void addSon(Graph::NodeId node, Graph::NodeId sonNode);

  void addSon(Graph::NodeId node, Graph::NodeId sonNode, Graph::EdgeId edge);

  std::vector<Graph::NodeId> removeSons(Graph::NodeId node);

  void removeSon(Graph::NodeId node, Graph::NodeId son);

  void rootAt(Graph::NodeId newRoot);

  std::vector<Graph::NodeId> getBelowNodes(Graph::NodeId localRoot) const;

  std::vector<Graph::EdgeId> getBelowEdges(Graph::NodeId localRoot) const;

  // recursive function for getSubtreeNodes
  void fillSubtreeMetNodes_(std::vector<Graph::NodeId>& metNodes, Graph::NodeId localRoot) const;

  // recursive function for getSubtreeEdges
  void fillSubtreeMetEdges_(std::vector<Graph::EdgeId>& metEdges, Graph::NodeId localRoot) const;

  // recursive function for getLeavesUnderNode
  void fillListOfLeaves_(Graph::NodeId startingNode, std::vector<Graph::NodeId>& foundLeaves) const;
};


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

typedef DAGraphImpl<GlobalGraph> DAGlobalGraph;

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


template<class GraphImpl>
DAGraphImpl<GraphImpl>::DAGraphImpl(bool b) :
  GraphImpl(true),
  isValid_(false),
  isRooted_(false)
{}


template<class GraphImpl>
bool DAGraphImpl<GraphImpl>::isValid() const
{
  return isValid_ || validate_();
}


template<class GraphImpl>
bool DAGraphImpl<GraphImpl>::isRooted() const
{
  if (isRooted_)
    return true;

  std::unique_ptr<Graph::NodeIterator> allIt = allNodesIterator();
  bool seen = false;

  for ( ; !allIt->end(); allIt->next())
  {
    if (getNumberOfFathers(**allIt) == 0)
    {
      if (seen)
        return false;
      seen = true;
    }
  }

  isRooted_ = seen;
  return true;
}

template<class GraphImpl>
bool DAGraphImpl<GraphImpl>::isLeaf(Graph::NodeId node) const
{
  return GraphImpl::isLeaf(node);
}

template<class GraphImpl>
bool DAGraphImpl<GraphImpl>::hasFather(Graph::NodeId node) const
{
  return GraphImpl::getNumberOfIncomingNeighbors(node) >= 1;
}

template<class GraphImpl>
std::vector<Graph::NodeId> DAGraphImpl<GraphImpl>::getFathers(Graph::NodeId node) const
{
  return getIncomingNeighbors(node);
}

template<class GraphImpl>
size_t DAGraphImpl<GraphImpl>::getNumberOfFathers(Graph::NodeId node) const
{
  return GraphImpl::getNumberOfIncomingNeighbors(node);
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::addFather(Graph::NodeId node, Graph::NodeId fatherNode)
{
  GraphImpl::link(fatherNode, node);
  topologyHasChanged_();
  isRooted_ = false;
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::addFather(Graph::NodeId node, Graph::NodeId fatherNode, Graph::EdgeId edge)
{
  GraphImpl::link(fatherNode, node, edge);
  topologyHasChanged_();
  isRooted_ = false;
}

template<class GraphImpl>
std::vector<Graph::NodeId> DAGraphImpl<GraphImpl>::removeFathers(Graph::NodeId node)
{
  std::vector<Graph::NodeId> fathers = getFathers(node);
  for (std::vector<Graph::NodeId>::iterator currFather = fathers.begin(); currFather != fathers.end(); currFather++)
  {
    removeFather(node, *currFather);
  }
  return fathers;
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::removeFather(Graph::NodeId node, Graph::NodeId father)
{
  if (getNumberOfIncomingNeighbors(node) == 1)
    isRooted_ = false;

  GraphImpl::unlink(father, node);
}

template<class GraphImpl>
std::vector<Graph::NodeId> DAGraphImpl<GraphImpl>::getLeavesUnderNode(Graph::NodeId node) const
{
  std::vector<Graph::NodeId> foundLeaves;
  fillListOfLeaves_(node, foundLeaves);

  return foundLeaves;
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::fillListOfLeaves_(Graph::NodeId startingNode, std::vector<Graph::NodeId>& foundLeaves) const
{
  const std::vector<Graph::NodeId> sons = getSons(startingNode);
  if (sons.size() > 1)
  {
    for (std::vector<Graph::NodeId>::const_iterator currNeighbor = sons.begin(); currNeighbor != sons.end(); currNeighbor++)
    {
      fillListOfLeaves_(*currNeighbor, foundLeaves);
    }
  }
  else
  {
    foundLeaves.push_back(startingNode);
  }
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::mustBeRooted_() const
{
  if (!isRooted())
    throw Exception("DAGraphImpl<GraphImpl>: The DAG must be rooted.");
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::mustBeValid_() const
{
  if (!isValid())
    throw Exception("DAGraphImpl<GraphImpl>: The DAG is not valid.");
}


template<class GraphImpl>
bool DAGraphImpl<GraphImpl>::validate_() const
{
  isValid_ = GraphImpl::isDA();
  return isValid_;
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::topologyHasChanged_() const
{
  isValid_ = false;
}


template<class GraphImpl>
std::vector<Graph::NodeId> DAGraphImpl<GraphImpl>::getSons(Graph::NodeId node) const
{
  return GraphImpl::getOutgoingNeighbors(node);
}

template<class GraphImpl>
size_t DAGraphImpl<GraphImpl>::getNumberOfSons(Graph::NodeId node) const
{
  return GraphImpl::getNumberOfOutgoingNeighbors(node);
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::addSon(Graph::NodeId node, Graph::NodeId sonNode)
{
  GraphImpl::link(node, sonNode);
  topologyHasChanged_();
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::addSon(Graph::NodeId node, Graph::NodeId sonNode, Graph::EdgeId edge)
{
  GraphImpl::link(node, sonNode, edge);
  topologyHasChanged_();
}


template<class GraphImpl>
std::vector<Graph::NodeId> DAGraphImpl<GraphImpl>::removeSons(Graph::NodeId node)
{
  std::vector<Graph::NodeId> sons = getSons(node);
  for (std::vector<Graph::NodeId>::iterator currSon = sons.begin(); currSon != sons.end(); currSon++)
  {
    removeSon(node, *currSon);
  }
  return sons;
}


template<class GraphImpl>
void DAGraphImpl<GraphImpl>::removeSon(Graph::NodeId node, Graph::NodeId son)
{
  GraphImpl::unlink(node, son);
}


template<class GraphImpl>
void DAGraphImpl<GraphImpl>::rootAt(Graph::NodeId newRoot)
{
  GraphImpl::setRoot(newRoot);

  // change edge direction between the new node and the former fathers
  if (isRooted() && isValid())
    propagateDirection_(newRoot);
  else
  {
    GraphImpl::orientate();
    isRooted_ = true;
  }
}


template<class GraphImpl>
void DAGraphImpl<GraphImpl>::propagateDirection_(Graph::NodeId node)
{
  std::vector<Graph::NodeId> vFat = getFathers(node);
  for (auto fat:vFat)
  {
    propagateDirection_(fat);
  }

  for (auto fat:vFat)
  {
    GraphImpl::switchNodes(fat, node);
  }
}


template<class GraphImpl>
std::vector<Graph::NodeId> DAGraphImpl<GraphImpl>::getBelowNodes(Graph::NodeId localRoot) const
{
  mustBeValid_();
  std::vector<Graph::EdgeId> metNodes;
  fillSubtreeMetNodes_(metNodes, localRoot);
  return metNodes;
}

template<class GraphImpl>
std::vector<Graph::EdgeId> DAGraphImpl<GraphImpl>::getBelowEdges(Graph::NodeId localRoot) const
{
  mustBeValid_();
  std::vector<Graph::EdgeId> metEdges;
  fillSubtreeMetEdges_(metEdges, localRoot);
  return metEdges;
}


template<class GraphImpl>
void DAGraphImpl<GraphImpl>::fillSubtreeMetNodes_(std::vector<Graph::NodeId>& metNodes, Graph::NodeId localRoot) const
{
  metNodes.push_back(localRoot);
  std::vector<Graph::NodeId> sons = GraphImpl::getOutgoingNeighbors(localRoot);
  for (std::vector<Graph::NodeId>::iterator currSon = sons.begin(); currSon != sons.end(); currSon++)
  {
    fillSubtreeMetNodes_(metNodes, *currSon);
  }
}

template<class GraphImpl>
void DAGraphImpl<GraphImpl>::fillSubtreeMetEdges_(std::vector<Graph::EdgeId>& metEdges, Graph::NodeId localRoot) const
{
  std::vector<Graph::EdgeId> edgesToSons = GraphImpl::getOutgoingEdges(localRoot);
  for (std::vector<Graph::EdgeId>::iterator currEdgeToSon = edgesToSons.begin(); currEdgeToSon != edgesToSons.end(); currEdgeToSon++)
  {
    metEdges.push_back(*currEdgeToSon);
    fillSubtreeMetEdges_(metEdges, GraphImpl::getBottom(*currEdgeToSon));
  }
}
}
#endif // BPP_GRAPH_DAGRAPHIMPL_H