GlobalGraph.h

Go to the documentation of this file.

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

#ifndef BPP_GRAPH_GLOBALGRAPH_H
#define BPP_GRAPH_GLOBALGRAPH_H

#include <limits>
#include <map>
#include <set>
#include <string>

#include "../Clonable.h"
#include "Graph.h"

namespace bpp
{
class GlobalGraph :
  public virtual Graph,
  public virtual Clonable
{
public:
  typedef Graph::NodeId Node;
  typedef Graph::EdgeId Edge;

  typedef std::map<Node, std::pair<std::map<Node, Edge>, std::map<Node, Edge>>> nodeStructureType;

  typedef std::map<Edge, std::pair<Node, Node>> edgeStructureType;

private:
  bool directed_;

  std::set<GraphObserver*> observers_;

  Node highestNodeID_;
  Edge highestEdgeID_;

  nodeStructureType nodeStructure_;

  edgeStructureType edgeStructure_;

  Node root_;

  virtual void topologyHasChanged_() const
  {
    // do nothing: a Graph does not care to be modified
  }

  void notify_();

  void linkInNodeStructure_(const Node& nodeA, const Node& nodeB, const Edge& edge);

  void linkInEdgeStructure_(const Node& nodeA, const Node& nodeB, const Edge& edge);


  Edge unlinkInNodeStructure_(const Node& nodeA, const Node& nodeB);

  void unlinkInEdgeStructure_(const Edge& edge);

protected:
  void nodeMustExist_(const Node& node, std::string name = "") const;

  void edgeMustExist_(const Edge& edge, std::string name = "") const;

private:
  std::vector<Node> getNeighbors_(const Node& node, bool outgoing = true) const;

  std::vector<Edge> getEdges_(const Node& node, bool outgoing = true) const;

  void isolate_(Node& node);

  void fillListOfLeaves_(const Node& startingNode, std::vector<Node>& foundLeaves, const Node& originNode, unsigned int maxRecursions) const;

  bool nodesAreMetOnlyOnce_(const Node& node, std::set<Node>& metNodes, const Node& originNode) const;

  void nodeToDot_(const Node& node, std::ostream& out, std::set<std::pair<Node, Node>>& alreadyFigured) const;

public:
  // /@{


  GlobalGraph(bool directed = false);

  GlobalGraph(const GlobalGraph& gg);

  GlobalGraph& operator=(const GlobalGraph& gg);

  GlobalGraph* clone() const {return new GlobalGraph(*this); }

  ~GlobalGraph() {}

protected:
  void setRoot(Graph::NodeId newRoot);

public:
  Graph::NodeId getRoot() const;

  void makeDirected();

  void makeUndirected();

  // /@}


  // /@{

  Graph::NodeId createNode();

  Graph::NodeId createNodeFromNode(Graph::NodeId origin);

  Graph::NodeId createNodeOnEdge(Graph::EdgeId edge);

  Graph::NodeId createNodeFromEdge(Graph::NodeId origin);

protected:
  Graph::EdgeId link(Graph::NodeId nodeA, Graph::NodeId nodeB);

  void link(Graph::NodeId nodeA, Graph::NodeId nodeB, GlobalGraph::Edge edgeID);

  void switchNodes(Graph::NodeId nodeA, Graph::NodeId nodeB);


  std::vector<Graph::EdgeId> unlink(Graph::NodeId nodeA, Graph::NodeId nodeB);

public:
  void deleteNode(Graph::NodeId node);

  // /@}


  // /@{

  void registerObserver(GraphObserver* observer);
  void unregisterObserver(GraphObserver* observer);
  // /@}


  // /@{

  template<typename T, bool is_const>
  friend class NodesIteratorClass;

  template<typename T, bool is_const>
  friend class EdgesIteratorClass;

  /*
   * @brief builds iterator on all Nodes of the graph
   *
   */

  std::unique_ptr<Graph::NodeIterator> allNodesIterator();
  std::unique_ptr<Graph::NodeIterator> allNodesIterator() const;


  /*
   * @brief builds iterator on the neighbor nodes of a Node
   *
   */

  std::unique_ptr<Graph::NodeIterator> outgoingNeighborNodesIterator(NodeId node);
  std::unique_ptr<Graph::NodeIterator> outgoingNeighborNodesIterator(NodeId node) const;

  /*
   * @brief builds iterator on the neighbor nodes of a Node
   *
   */

  std::unique_ptr<Graph::NodeIterator> incomingNeighborNodesIterator(NodeId node);
  std::unique_ptr<Graph::NodeIterator> incomingNeighborNodesIterator(NodeId node) const;

  size_t getNumberOfNodes() const;

  size_t getNumberOfEdges() const;

  size_t getDegree(Graph::NodeId node) const;

  bool isLeaf(Graph::NodeId node) const;

  size_t getNumberOfNeighbors(Graph::NodeId node) const;

  size_t getNumberOfOutgoingNeighbors(Graph::NodeId node) const;

  size_t getNumberOfIncomingNeighbors(Graph::NodeId node) const;

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

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

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

  std::vector<Graph::NodeId> getLeavesFromNode(Graph::NodeId node, unsigned int maxDepth) const;

  std::vector<Graph::NodeId> getAllLeaves() const;
  std::set<NodeId> getSetOfAllLeaves() const;

  std::vector<Graph::NodeId> getAllNodes() const;

  std::vector<Graph::NodeId> getAllInnerNodes() const;

  std::pair<Graph::NodeId, Graph::NodeId> getNodes(Graph::EdgeId edge) const;

  Graph::NodeId getTop(Graph::EdgeId edge) const;

  Graph::NodeId getBottom(Graph::EdgeId edge) const;


  // /@}

  // /@{

  bool isTree() const;

  bool isDA() const;

  void orientate();

  bool isDirected() const;


  bool containsReciprocalRelations() const;


  // /@}

  /*
   * @brief builds iterator on all Nodes of the graph
   *
   */

  std::unique_ptr<EdgeIterator> allEdgesIterator();
  std::unique_ptr<EdgeIterator> allEdgesIterator() const;

  /*
   * @brief builds iterator on the outgoing neighbor nodes of a Node
   *
   */

  std::unique_ptr<EdgeIterator> outgoingEdgesIterator(NodeId node);
  std::unique_ptr<EdgeIterator> outgoingEdgesIterator(NodeId node) const;

  /*
   * @brief builds iterator on the incoming neighbor nodes of a Node
   *
   */

  std::unique_ptr<EdgeIterator> incomingEdgesIterator(NodeId node);
  std::unique_ptr<EdgeIterator> incomingEdgesIterator(NodeId node) const;

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

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

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

  Graph::EdgeId getEdge(Graph::NodeId nodeA, Graph::NodeId nodeB) const;

  Graph::EdgeId getAnyEdge(Graph::NodeId nodeA, Graph::NodeId nodeB) const;

  std::vector<Graph::EdgeId> getAllEdges() const;

  // /@}


  // /@{

  void notifyDeletedEdges(const std::vector<Graph::EdgeId>& edgesToDelete) const;

  void notifyDeletedNodes(const std::vector<Graph::NodeId>& nodesToDelete) const;


  // /@}

  void outputToDot(std::ostream& out, const std::string& name) const;

  template<class N, class E, class GraphImpl>
  friend class AssociationGraphImplObserver;
};


/************************************************/
/************************************************/
/************************************************/
/* ITERATORS */
/************************************************/

/************************************************/
/* NODES ITERATORS */
/************************************************/

template<class T, bool is_const>
class NodesIteratorClass :
  virtual public Graph::NodeIterator
{
  ~NodesIteratorClass<T, is_const>(){}
};


template<bool is_const>
class NodesIteratorClass<Graph::ALLGRAPHITER, is_const> :
  virtual public Graph::NodeIterator
{
private:
  typedef typename std::conditional<is_const,
          GlobalGraph::nodeStructureType::const_iterator,
          GlobalGraph::nodeStructureType::iterator >::type itType;

  itType it_,  begin_, end_;

public:
  template<bool B = is_const>
  NodesIteratorClass<Graph::ALLGRAPHITER, is_const>(const GlobalGraph& gg, typename std::enable_if<B>::type* = 0) : it_(gg.nodeStructure_.begin()),
    begin_(gg.nodeStructure_.begin()),
    end_(gg.nodeStructure_.end()) {}

  template<bool B = is_const>
  NodesIteratorClass<Graph::ALLGRAPHITER, is_const>(GlobalGraph& gg, typename std::enable_if<!B>::type* = 0) : it_(gg.nodeStructure_.begin()),
    begin_(gg.nodeStructure_.begin()),
    end_(gg.nodeStructure_.end()) {}

  ~NodesIteratorClass<Graph::ALLGRAPHITER, is_const>(){}

  void next() { it_++; }
  bool end() const { return it_ == end_;  }
  void start() { it_ = begin_; }

  Graph::NodeId operator*() {return it_->first; }
};


template<bool is_const>
class NeighborIteratorClass
{
protected:
  typedef typename std::conditional<is_const,
          const std::map<GlobalGraph::Node, GlobalGraph::Edge>&,
          std::map<GlobalGraph::Node, GlobalGraph::Edge>&>::type mapType;

  mapType map_;

  typedef typename std::conditional<is_const,
          std::map<GlobalGraph::Node, GlobalGraph::Edge>::const_iterator,
          std::map<GlobalGraph::Node, GlobalGraph::Edge>::iterator>::type itType;

  itType it_, begin_, end_;

public:
  virtual ~NeighborIteratorClass<is_const>(){}

  template<bool B = is_const>
  NeighborIteratorClass<is_const>(const std::map<GlobalGraph::Node, GlobalGraph::Edge>& map, typename std::enable_if<B>::type* = 0) :
    map_(map),
    it_(map_.begin()),
    begin_(map_.begin()),
    end_(map_.end()) {}

  template<bool B = is_const>
  NeighborIteratorClass<is_const>(std::map<GlobalGraph::Node, GlobalGraph::Edge>& map, typename std::enable_if<!B>::type* = 0) :
    map_(map),
    it_(map_.begin()),
    begin_(map_.begin()),
    end_(map_.end()) {}

  void next() { it_++; }
  bool end() const { return it_ == end_;  }
  void start() { it_ = begin_; }
};


template<bool is_const>
class NodesIteratorClass<Graph::OUTGOINGNEIGHBORITER, is_const> :
  virtual public NeighborIteratorClass<is_const>,
  virtual public Graph::NodeIterator
{
public:
  NodesIteratorClass<Graph::OUTGOINGNEIGHBORITER, is_const>(const GlobalGraph& gg, GlobalGraph::NodeId node) : NeighborIteratorClass<is_const>(gg.nodeStructure_.find(node)->second.first) {}

  NodesIteratorClass<Graph::OUTGOINGNEIGHBORITER, is_const>(GlobalGraph& gg, GlobalGraph::NodeId node) : NeighborIteratorClass<is_const>(gg.nodeStructure_.find(node)->second.first) {}

  ~NodesIteratorClass<Graph::OUTGOINGNEIGHBORITER, is_const>(){}

  void next() { NeighborIteratorClass<is_const>::next(); }
  bool end() const { return NeighborIteratorClass<is_const>::end(); }
  void start() { NeighborIteratorClass<is_const>::start(); }

  Graph::NodeId operator*() {return NeighborIteratorClass<is_const>::it_->first; }
};


template<bool is_const>
class NodesIteratorClass<Graph::INCOMINGNEIGHBORITER, is_const> :
  virtual public NeighborIteratorClass<is_const>,
  virtual public Graph::NodeIterator
{
public:
  NodesIteratorClass<Graph::INCOMINGNEIGHBORITER, is_const>(const GlobalGraph& gg, GlobalGraph::NodeId node) : NeighborIteratorClass<is_const>(gg.nodeStructure_.find(node)->second.second) {}

  NodesIteratorClass<Graph::INCOMINGNEIGHBORITER, is_const>(GlobalGraph& gg, GlobalGraph::NodeId node) : NeighborIteratorClass<is_const>(gg.nodeStructure_.find(node)->second.second) {}

  ~NodesIteratorClass<Graph::INCOMINGNEIGHBORITER, is_const>(){}

  void next() { NeighborIteratorClass<is_const>::next(); }
  bool end() const { return NeighborIteratorClass<is_const>::end(); }
  void start() { NeighborIteratorClass<is_const>::start(); }

  Graph::NodeId operator*() {return NeighborIteratorClass<is_const>::it_->first; }
};


/************************************************/
/* EDGES ITERATORS */
/************************************************/

template<class T, bool is_const>
class EdgesIteratorClass :
  virtual public Graph::EdgeIterator
{};

template<bool is_const>
class EdgesIteratorClass<Graph::ALLGRAPHITER, is_const> :
  virtual public Graph::EdgeIterator
{
private:
  typedef typename std::conditional<is_const,
          GlobalGraph::edgeStructureType::const_iterator,
          GlobalGraph::edgeStructureType::iterator >::type itType;

  itType it_, begin_, end_;

public:
  template<bool B = is_const>
  EdgesIteratorClass<Graph::ALLGRAPHITER, is_const>(const GlobalGraph& gg, typename std::enable_if<B>::type* = 0) : it_(gg.edgeStructure_.begin()),
    begin_(gg.edgeStructure_.begin()),
    end_(gg.edgeStructure_.end()) {}

  template<bool B = is_const>
  EdgesIteratorClass<Graph::ALLGRAPHITER, is_const>(GlobalGraph& gg, typename std::enable_if<!B>::type* = 0) : it_(gg.edgeStructure_.begin()),
    begin_(gg.edgeStructure_.begin()),
    end_(gg.edgeStructure_.end()) {}

  ~EdgesIteratorClass<Graph::ALLGRAPHITER, is_const>(){}

  void next() { it_++; }
  bool end() const { return it_ == end_;  }
  void start() { it_ = begin_; }

  Graph::EdgeId operator*() {return it_->first; }
};


template<bool is_const>
class EdgesIteratorClass<Graph::OUTGOINGNEIGHBORITER, is_const> :
  public NeighborIteratorClass<is_const>,
  public Graph::EdgeIterator
{
public:
  EdgesIteratorClass<Graph::OUTGOINGNEIGHBORITER, is_const>(const GlobalGraph& gg, GlobalGraph::NodeId node) : NeighborIteratorClass<is_const>(gg.nodeStructure_.find(node)->second.first) {}

  EdgesIteratorClass<Graph::OUTGOINGNEIGHBORITER, is_const>(GlobalGraph& gg, GlobalGraph::NodeId node) : NeighborIteratorClass<is_const>(gg.nodeStructure_.find(node)->second.first) {}

  ~EdgesIteratorClass<Graph::OUTGOINGNEIGHBORITER, is_const>(){}

  void next() { NeighborIteratorClass<is_const>::next(); }
  bool end() const { return NeighborIteratorClass<is_const>::end(); }
  void start() { NeighborIteratorClass<is_const>::start(); }

  Graph::EdgeId operator*() {return NeighborIteratorClass<is_const>::it_->second; }
};

template<bool is_const>
class EdgesIteratorClass<Graph::INCOMINGNEIGHBORITER, is_const> :
  public NeighborIteratorClass<is_const>,
  public Graph::EdgeIterator
{
public:
  EdgesIteratorClass<Graph::INCOMINGNEIGHBORITER, is_const>(const GlobalGraph& gg, GlobalGraph::NodeId node) : NeighborIteratorClass<is_const>(gg.nodeStructure_.find(node)->second.second) {}

  EdgesIteratorClass<Graph::INCOMINGNEIGHBORITER, is_const>(GlobalGraph& gg, GlobalGraph::NodeId node) : NeighborIteratorClass<is_const>(gg.nodeStructure_.find(node)->second.second) {}

  ~EdgesIteratorClass<Graph::INCOMINGNEIGHBORITER, is_const>(){}

  void next() { NeighborIteratorClass<is_const>::next(); }
  bool end() const { return NeighborIteratorClass<is_const>::end(); }
  void start() { NeighborIteratorClass<is_const>::start(); }

  Graph::EdgeId operator*() {return NeighborIteratorClass<is_const>::it_->second; }
};
}
#endif // BPP_GRAPH_GLOBALGRAPH_H