base_graph.hpp

Go to the documentation of this file.

#ifndef INDIGOX_GRAPH_BASE_HPP
#define INDIGOX_GRAPH_BASE_HPP

#include "../utils/fwd_declares.hpp"
#include "../utils/simple_bimap.hpp"
#include <boost/graph/adjacency_list.hpp>

#include <cstdint>
#include <memory>
#include <vector>

namespace indigox::graph {

  struct Directed {
    using is_directed_t = boost::bidirectionalS;
    static constexpr bool is_directed = true;
  };

  struct Undirected {
    using is_directed_t = boost::undirectedS;
    static constexpr bool is_directed = false;
  };

  struct GraphLabel {
    union {
      int32_t component;
      uint64_t isomorphism;
    };
  };

  template <class V, class E, class S, class D = Undirected,
            class VP = GraphLabel, class EP = GraphLabel>
  class BaseGraph {
    friend class cereal::access;
    friend struct algorithm::access;

  public:
    using graph_type =
        boost::adjacency_list<boost::setS,               // Edge container
                              boost::listS,              // Vertex container
                              typename D::is_directed_t, // Directed nature
                              VP,                        // Vertex Properties
                              EP>;                       // Edge Properties

    // May need to replace graph_t:: with boost::graph_traits<graph_t>::
    using VertType = typename graph_type::vertex_descriptor;
    using VertIter = typename graph_type::vertex_iterator;
    using NbrsIter = typename graph_type::adjacency_iterator;
    using PredIter = typename graph_type::inv_adjacency_iterator;
    using EdgeType = typename graph_type::edge_descriptor;
    using EdgeIter = typename graph_type::edge_iterator;

    using VertMap = indigox::utils::SimpleBiMap<V, VertType>;
    using EdgeMap = indigox::utils::SimpleBiMap<E, EdgeType>;
    using VertContain = std::vector<V>;
    using EdgeContain = std::vector<E>;
    using NbrsContain = std::map<V, VertContain>;
    using ComponentContain = std::vector<VertContain>;
    using CycleVertContain = std::vector<VertContain>;
    using CycleEdgeContain = std::vector<EdgeContain>;
    using SubgraphType = S;

  protected:
    struct BaseImpl;
    std::shared_ptr<BaseImpl> m_basedata;

    //    //! \brief Underlying boost graph.
    //    graph_type _g;
    //    //! \brief Map vertices to their descriptors.
    //    VertMap _vm;
    //    //! \brief Map edges to their descriptors.
    //    EdgeMap _em;
    //    //! \brief Container for giving access to all vertices
    //    VertContain _v;
    //    //! \brief Container for giving access to all edges
    //    EdgeContain _e;
    //    //! \brief Container for predecessors of a vertex (v such that edge
    //    u->v
    //    //! exists)
    //    NbrsContain _pre;
    //    //! \brief Container for successors of a vertex. Only used in directed
    //    //! graphs
    //    NbrsContain _suc;
    //    //! \brief Components container
    //    ComponentContain _comp_cache;
    //    //! \brief State when components were last calculated
    //    utils::ModifiableObject::State _comp_state;
    //    //! \brief Cyclic vertices container
    //    VertContain _vcyclic_cache;
    //    //! \brief Cyclic edges container
    //    EdgeContain _ecyclic_cache;
    //    //! \brief Cycles container
    //    CycleEdgeContain _cycles_cache;
    //    //! \brief State when cycles were last calculated
    //    utils::ModifiableObject::State _cycle_state;

  private:
    template <typename Archive>
    void serialise(Archive &archive, const uint32_t);

  public:
    BaseGraph() : m_basedata(std::make_shared<BaseImpl>()){};

    virtual ~BaseGraph() {}

  protected:
    // Modification methods protected.
    //    void Clear();

    void AddVertex(const V &v);

    void RemoveVertex(const V &v);

    void AddEdge(const V &u, const V &v, const E &e);

    void RemoveEdge(const E &e);

    void RemoveEdge(const V &u, const V &v);

  public:
    bool HasVertex(const V &v) const;

    bool HasEdge(const E &e) const;

    bool HasEdge(const V &u, const V &v) const;

    int64_t NumVertices() const;

    int64_t NumEdges() const;

    int64_t Degree(const V &v) const;

    int64_t InDegree(const V &v) const;

    const VertContain &GetNeighbours(const V &v);

    const VertContain &GetPredecessors(const V &v);

    const VertContain &GetSuccessors(const V &v);

    std::pair<V, V> GetVertices(const E &e) const;

    const VertContain &GetVertices() const;

    const EdgeContain &GetEdges() const;

    E GetEdge(const V &u, const V &v) const;

    V GetSourceVertex(const E &e) const;

    V GetTargetVertex(const E &e) const;

    bool IsConnected();

    int64_t NumConnectedComponents();

    const ComponentContain &GetConnectedComponents();

    bool IsCyclic(const V &v);

    bool IsCyclic(const V &v, uint32_t sz);

    bool IsCyclic(const E &e);

    bool IsCyclic(const E &e, uint32_t sz);

    const CycleEdgeContain &GetCycles();

    int64_t NumCycles();

    virtual S Subgraph(std::vector<V> &verts) = 0;
    virtual S Subgraph(std::vector<V> &verts, std::vector<E> &edges) = 0;

  private:
    VertType GetDescriptor(const V &v) const;

    V GetV(VertType v) const;

    EdgeType GetDescriptor(const E &e) const;

    E GetE(EdgeType e) const;

    int64_t OutDegree(VertType v) const;

    int64_t InDegree(VertType v) const;
  };

} // namespace indigox::graph

#include "base_graph_impl.hpp"

#endif /* INDIGOX_GRAPH_BASE_HPP */