Graph.h

Go to the documentation of this file.

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

#ifndef BPP_GRAPH_GRAPH_H
#define BPP_GRAPH_GRAPH_H

#include <algorithm>
#include <iostream>
#include <map>
#include <memory>
#include <set>
#include <string>
#include <utility>
#include <vector>


// forward declaration to avoid circular dependancies.
// since we do not need its size in this header file (only using pointers to it)
namespace bpp
{
class GraphObserver;
}

namespace bpp
{
class Graph
{
public:
  typedef unsigned int NodeId;
  typedef unsigned int EdgeId;


  virtual ~Graph(){}

protected:
  virtual void setRoot(NodeId newRoot) = 0;

public:
  virtual NodeId getRoot() const = 0;

  virtual void makeDirected() = 0;

  virtual void makeUndirected() = 0;

  // /@}


  // /@{

  virtual NodeId createNode() = 0;

  virtual NodeId createNodeFromNode(NodeId origin) = 0;

  virtual NodeId createNodeOnEdge(NodeId edge) = 0;


  virtual NodeId createNodeFromEdge(NodeId origin) = 0;

protected:
  virtual EdgeId link(NodeId nodeA, NodeId nodeB) = 0;

  virtual void link(Graph::NodeId nodeA, Graph::NodeId nodeB, Graph::EdgeId edgeID) = 0;

  virtual std::vector<EdgeId> unlink(NodeId nodeA, NodeId nodeB) = 0;

public:
  virtual void deleteNode(NodeId node) = 0;

  // /@}

  // /@{

  virtual void registerObserver(GraphObserver* observer) = 0;

  virtual void unregisterObserver(GraphObserver* observer) = 0;

// /@}

  // /@{

  class NodeIterator
  {
public:
    virtual ~NodeIterator() {}

    virtual void next() = 0;
    virtual bool end() const = 0;
    virtual void start() = 0;

    virtual NodeId operator*() = 0;
  };

  struct ALLGRAPHITER {};
  struct OUTGOINGNEIGHBORITER {};
  struct INCOMINGNEIGHBORITER {};

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

  virtual std::unique_ptr<NodeIterator> allNodesIterator() = 0;

  virtual std::unique_ptr<NodeIterator> allNodesIterator() const = 0;

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

  virtual std::unique_ptr<NodeIterator> outgoingNeighborNodesIterator(NodeId node) = 0;

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

  virtual std::unique_ptr<NodeIterator> incomingNeighborNodesIterator(NodeId node) = 0;


  virtual size_t getNumberOfNodes() const = 0;

  virtual size_t getNumberOfEdges() const = 0;

  virtual size_t getDegree(NodeId node) const = 0;

  virtual bool isLeaf(NodeId node) const = 0;

  virtual size_t getNumberOfNeighbors(NodeId node) const = 0;

  virtual size_t getNumberOfOutgoingNeighbors(NodeId node) const = 0;

  virtual size_t getNumberOfIncomingNeighbors(const NodeId node) const = 0;

  virtual std::vector<NodeId> getNeighbors(const NodeId node) const = 0;

  virtual std::vector<NodeId> getOutgoingNeighbors(const NodeId node) const = 0;

  virtual std::vector<NodeId> getIncomingNeighbors(NodeId node) const = 0;

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

  virtual std::vector<NodeId> getAllLeaves() const = 0;

  virtual std::set<NodeId> getSetOfAllLeaves() const = 0;

  virtual std::vector<NodeId> getAllInnerNodes() const = 0;

  virtual std::vector<NodeId> getAllNodes() const = 0;

  virtual std::pair<NodeId, NodeId> getNodes(EdgeId edge) const = 0;

  virtual NodeId getTop(EdgeId edge) const = 0;

  virtual NodeId getBottom(EdgeId edge) const = 0;

  // /@}

  // /@{

  virtual bool isTree() const = 0;

  virtual bool isDA() const = 0;


  virtual void orientate() = 0;

  virtual bool isDirected() const = 0;


  virtual bool containsReciprocalRelations() const = 0;


  // /@}


  // /@{

  class EdgeIterator
  {
public:
    virtual ~EdgeIterator() {}

    virtual void next() = 0;
    virtual bool end() const = 0;
    virtual void start() = 0;

    virtual EdgeId operator*() = 0;
  };


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

  virtual std::unique_ptr<EdgeIterator> allEdgesIterator() = 0;

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

  virtual std::unique_ptr<EdgeIterator> outgoingEdgesIterator(NodeId node) = 0;

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

  virtual std::unique_ptr<EdgeIterator> incomingEdgesIterator(NodeId node) = 0;

  virtual std::vector<EdgeId> getEdges(const NodeId node) const = 0;

  virtual std::vector<EdgeId> getOutgoingEdges(const NodeId node) const = 0;

  virtual std::vector<EdgeId> getIncomingEdges(NodeId node) const = 0;

  virtual std::vector<EdgeId> getAllEdges() const = 0;

  virtual EdgeId getEdge(NodeId nodeA, NodeId nodeB) const = 0;

  virtual EdgeId getAnyEdge(NodeId nodeA, NodeId nodeB) const = 0;

  // /@}

protected:
  // /@{

  virtual void notifyDeletedEdges(const std::vector<EdgeId>& edgesToDelete) const = 0;

  virtual void notifyDeletedNodes(const std::vector<NodeId>& nodesToDelete) const = 0;


  // /@}

public:
  virtual void outputToDot(std::ostream& out, const std::string& name) const = 0;

  template<class N, class E, class GraphImpl>
  friend class AssociationGraphImplObserver;
};
}
#endif // BPP_GRAPH_GRAPH_H