MixedGraph.hpp

// MixedGraph.hpp
//
//     Created on: 05. 02. 2018
//         Author: Jan Uhlik
//    Modified by:
//
// Copyright (c) 2017 Czech Technical University in Prague | Faculty of Information Technology. All rights reserved.
// Git repository: https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library

#ifndef ALIB2_MIXEDGRAPH_HPP
#define ALIB2_MIXEDGRAPH_HPP

#include <alib/map>
#include <alib/tuple>
#include <alib/set>
#include <alib/vector>
#include <functional>
#include <alib/pair>
#include <object/Object.h>
#include <core/normalize.hpp>

#include <common/Normalize.hpp>
#include <graph/GraphInterface.hpp>
#include <graph/GraphFeatures.hpp>

namespace graph {

template<typename TNode, typename TEdge>
class MixedGraph : public GraphInterface<TNode, TEdge> {
// ---------------------------------------------------------------------------------------------------------------------
 public:
  using node_type = TNode;
  using edge_type = TEdge;

// ---------------------------------------------------------------------------------------------------------------------

 protected:
  // Container for edge
  ext::map<TNode, ext::map<TNode, TEdge>> m_adjacency_list;

  // Two containers for arc
  ext::map<TNode, ext::map<TNode, TEdge>> m_succ_list;
  ext::map<TNode, ext::map<TNode, TEdge>> m_pred_list;

// =====================================================================================================================
// Constructor, Destructor, Operators
 public:

// ---------------------------------------------------------------------------------------------------------------------

  const ext::map<TNode, ext::map<TNode, TEdge>> &getAdjacencyList() const &;
  ext::map<TNode, ext::map<TNode, TEdge>> &&getAdjacencyList() &&;

  const ext::map<TNode, ext::map<TNode, TEdge>> &getSuccessorList() const &;
  ext::map<TNode, ext::map<TNode, TEdge>> &&getSuccessorList() &&;

  const ext::map<TNode, ext::map<TNode, TEdge>> &getPredecessorList() const &;
  ext::map<TNode, ext::map<TNode, TEdge>> &&getPredecessorList() &&;

// ---------------------------------------------------------------------------------------------------------------------

// =====================================================================================================================
// GraphBase interface
 public:
  int compare(const GraphBase &other) const override;

  virtual int compare(const MixedGraph &other) const;

  void operator>>(std::ostream &ostream) const override;

  explicit operator std::string() const override;

// =====================================================================================================================
// Graph interface

 public:
  void addNode(const TNode &n);
  void addNode(TNode &&n);
  template<typename ... Params>
  void addNode(Params &&... params);

// ---------------------------------------------------------------------------------------------------------------------

  bool addEdge(const TEdge &e);
  bool addEdge(TEdge &&e);
  template<typename ... Params>
  bool addEdge(Params &&... params);

  bool addArc(const TEdge &e);
  bool addArc(TEdge &&e);
  template<typename ... Params>
  bool addArc(Params &&... params);

// ---------------------------------------------------------------------------------------------------------------------

// =====================================================================================================================
// GraphInterface interface

  size_t nodeCount() const override;
  size_t edgeCount() const override;

// ---------------------------------------------------------------------------------------------------------------------

  ext::set<TNode> getNodes() const override;
  ext::vector<TEdge> getEdges() const override;

// ---------------------------------------------------------------------------------------------------------------------

  ext::set<TNode> successors(const TNode &n) const override;
  ext::vector<TEdge> successorEdges(const TNode &n) const override;
  ext::set<TNode> predecessors(const TNode &n) const override;
  ext::vector<TEdge> predecessorEdges(const TNode &n) const override;

// ---------------------------------------------------------------------------------------------------------------------

  std::string name() const override;

// ---------------------------------------------------------------------------------------------------------------------

};

// =====================================================================================================================

template<typename TNode, typename TEdge>
const ext::map<TNode, ext::map<TNode, TEdge>> &MixedGraph<TNode, TEdge>::getAdjacencyList() const &{
  return m_adjacency_list;
}

template<typename TNode, typename TEdge>
ext::map<TNode, ext::map<TNode, TEdge>> &&MixedGraph<TNode, TEdge>::getAdjacencyList() &&{
  return std::move(m_adjacency_list);
}

template<typename TNode, typename TEdge>
const ext::map<TNode, ext::map<TNode, TEdge>> &MixedGraph<TNode, TEdge>::getSuccessorList() const &{
  return m_succ_list;
}

template<typename TNode, typename TEdge>
ext::map<TNode, ext::map<TNode, TEdge>> &&MixedGraph<TNode, TEdge>::getSuccessorList() &&{
  return std::move(m_succ_list);
}

template<typename TNode, typename TEdge>
const ext::map<TNode, ext::map<TNode, TEdge>> &MixedGraph<TNode, TEdge>::getPredecessorList() const &{
  return m_pred_list;
}

template<typename TNode, typename TEdge>
ext::map<TNode, ext::map<TNode, TEdge>> &&MixedGraph<TNode, TEdge>::getPredecessorList() &&{
  return std::move(m_pred_list);
}

// ---------------------------------------------------------------------------------------------------------------------

template<typename TNode, typename TEdge>
void MixedGraph<TNode, TEdge>::addNode(const TNode &n) {
  m_adjacency_list[n];
  m_succ_list[n];
  m_pred_list[n];
}

template<typename TNode, typename TEdge>
void MixedGraph<TNode, TEdge>::addNode(TNode &&n) {
  m_adjacency_list[n];
  m_succ_list[n];
  m_pred_list[std::forward<TNode>(n)];
}

template<typename TNode, typename TEdge>
template<typename... Params>
void MixedGraph<TNode, TEdge>::addNode(Params &&... params) {
  addNode(TNode(std::forward<Params>(params) ...));
}

// ---------------------------------------------------------------------------------------------------------------------

template<typename TNode, typename TEdge>
bool MixedGraph<TNode, TEdge>::addEdge(const TEdge &e) {
  auto search_succ = m_succ_list.find(e.first);
  auto search_pred = m_pred_list.find(e.first);

  if (search_succ != m_succ_list.end() && search_succ->second.find(e.second) != search_succ->second.end()) {
    return false;
  } else if (search_pred != m_pred_list.end() && search_pred->second.find(e.second) != search_pred->second.end()) {
    return false;
  }

  // Check if edge doesn't already exists
  if (m_adjacency_list.find(e.first) != m_adjacency_list.end()
      && m_adjacency_list[e.first].find(e.second) != m_adjacency_list[e.first].end()) {
    return false;
  }

  addNode(e.first); // because of consistency
  addNode(e.second); // because of consistency
  m_adjacency_list[e.first].insert(ext::make_pair(e.second, e));
  m_adjacency_list[e.second].insert(ext::make_pair(e.first, e));

  return true;
}

template<typename TNode, typename TEdge>
bool MixedGraph<TNode, TEdge>::addEdge(TEdge &&e) {
  auto search_succ = m_succ_list.find(e.first);
  auto search_pred = m_pred_list.find(e.first);

  if (search_succ != m_succ_list.end() && search_succ->second.find(e.second) != search_succ->second.end()) {
    return false;
  } else if (search_pred != m_pred_list.end() && search_pred->second.find(e.second) != search_pred->second.end()) {
    return false;
  }

  // Check if edge doesn't already exists
  if (m_adjacency_list.find(e.first) != m_adjacency_list.end()
      && m_adjacency_list[e.first].find(e.second) != m_adjacency_list[e.first].end()) {
    return false;
  }

  addNode(e.first); // because of consistency
  addNode(e.second); // because of consistency
  m_adjacency_list[e.first].insert(ext::make_pair(e.second, e));
  m_adjacency_list[e.second].insert(ext::make_pair(e.first, std::forward<TEdge>(e)));

  return true;
}

template<typename TNode, typename TEdge>
template<typename... Params>
bool MixedGraph<TNode, TEdge>::addEdge(Params &&... params) {
  return addEdge(TEdge(std::forward<Params>(params) ...));
}

template<typename TNode, typename TEdge>
bool MixedGraph<TNode, TEdge>::addArc(const TEdge &e) {
  // Check if edge doesn't already exists
  if (m_adjacency_list.find(e.first) != m_adjacency_list.end()
      && m_adjacency_list[e.first].find(e.second) != m_adjacency_list[e.first].end()) {
    return false;
  }

  // Check if arc doesn't already exits
  auto search_succ = m_succ_list.find(e.first);
  if (search_succ != m_succ_list.end() && search_succ->second.find(e.second) != search_succ->second.end()) {
    return false;
  }

  addNode(e.first); // because of consistency
  addNode(e.second); // because of consistency
  m_succ_list[e.first].insert(ext::make_pair(e.second, e));
  m_pred_list[e.second].insert(ext::make_pair(e.first, e));

  return true;
}

template<typename TNode, typename TEdge>
bool MixedGraph<TNode, TEdge>::addArc(TEdge &&e) {
  // Check if edge doesn't already exists
  if (m_adjacency_list.find(e.first) != m_adjacency_list.end()
      && m_adjacency_list[e.first].find(e.second) != m_adjacency_list[e.first].end()) {
    return false;
  }

  // Check if arc doesn't already exits
  auto search_succ = m_succ_list.find(e.first);
  if (search_succ != m_succ_list.end() && search_succ->second.find(e.second) != search_succ->second.end()) {
    return false;
  }

  addNode(e.first); // because of consistency
  addNode(e.second); // because of consistency
  m_succ_list[e.first].insert(ext::make_pair(e.second, e));
  m_pred_list[e.second].insert(ext::make_pair(e.first, std::forward<TEdge>(e)));

  return true;
}

template<typename TNode, typename TEdge>
template<typename... Params>
bool MixedGraph<TNode, TEdge>::addArc(Params &&... params) {
  return addArc(TEdge(std::forward<Params>(params)...));
}

// ---------------------------------------------------------------------------------------------------------------------

template<typename TNode, typename TEdge>
size_t MixedGraph<TNode, TEdge>::nodeCount() const {
  return m_adjacency_list.size();
}
template<typename TNode, typename TEdge>
size_t MixedGraph<TNode, TEdge>::edgeCount() const {
  size_t cnt = 0;

  for (const auto &i: m_adjacency_list) {
    cnt += i.second.size();
  }

  cnt /= 2;

  for (const auto &i: m_succ_list) {
    cnt += i.second.size();
  }

  return cnt;
}

// ---------------------------------------------------------------------------------------------------------------------

template<typename TNode, typename TEdge>
ext::set<TNode> MixedGraph<TNode, TEdge>::getNodes() const {
  ext::set<TNode> set;

  for (const auto &i: m_adjacency_list) {
    set.insert(i.first);
  }

  return set;
}

template<typename TNode, typename TEdge>
ext::vector<TEdge> MixedGraph<TNode, TEdge>::getEdges() const {
  ext::vector<TEdge> vec;

  for (const auto &i: m_adjacency_list) {
    for (const auto &j : i.second) {
      vec.push_back(j.second);
    }
  }

  for (const auto &i: m_succ_list) {
    for (const auto &j : i.second) {
      vec.push_back(j.second);
    }
  }

  return vec;
}

// ---------------------------------------------------------------------------------------------------------------------

template<typename TNode, typename TEdge>
ext::set<TNode> MixedGraph<TNode, TEdge>::successors(const TNode &n) const {
  ext::set<TNode> set;

  if (m_adjacency_list.count(n) == 0) {
    return set;
  }

  for (const auto &i: m_adjacency_list.at(n)) {
    set.insert(i.first);
  }

  for (const auto &i: m_succ_list.at(n)) {
    set.insert(i.first);
  }

  return set;
}

template<typename TNode, typename TEdge>
ext::vector<TEdge> MixedGraph<TNode, TEdge>::successorEdges(const TNode &n) const {
  ext::vector<TEdge> vec;

  if (m_succ_list.count(n) == 0) {
    return vec;
  }

  for (const auto &i: m_adjacency_list.at(n)) {
    vec.push_back(i.second);
  }

  for (const auto &i: m_succ_list.at(n)) {
    vec.push_back(i.second);
  }

  return vec;
}

template<typename TNode, typename TEdge>
ext::set<TNode> MixedGraph<TNode, TEdge>::predecessors(const TNode &n) const {
  ext::set<TNode> set;

  if (m_pred_list.count(n) == 0) {
    return set;
  }

  for (const auto &i: m_adjacency_list.at(n)) {
    set.insert(i.first);
  }

  for (const auto &i: m_pred_list.at(n)) {
    set.insert(i.first);
  }

  return set;
}

template<typename TNode, typename TEdge>
ext::vector<TEdge> MixedGraph<TNode, TEdge>::predecessorEdges(const TNode &n) const {
  ext::vector<TEdge> vec;

  if (m_pred_list.count(n) == 0) {
    return vec;
  }

  for (const auto &i: m_adjacency_list.at(n)) {
    vec.push_back(i.second);
  }

  for (const auto &i: m_pred_list.at(n)) {
    vec.push_back(i.second);
  }

  return vec;
}

// ---------------------------------------------------------------------------------------------------------------------

template<typename TNode, typename TEdge>
std::string MixedGraph<TNode, TEdge>::name() const {
  return "MixedGraph";
}

// ---------------------------------------------------------------------------------------------------------------------

template<typename TNode, typename TEdge>
int MixedGraph<TNode, TEdge>::compare(const GraphBase &other) const {
  if (ext::type_index(typeid(*this)) == ext::type_index(typeid(other))) return this->compare((decltype(*this)) other);
  return ext::type_index(typeid(*this)) - ext::type_index(typeid(other));
}

template<typename TNode, typename TEdge>
int MixedGraph<TNode, TEdge>::compare(const MixedGraph &other) const {
  auto first = ext::tie(m_adjacency_list, m_succ_list, m_pred_list);
  auto second = ext::tie(other.getAdjacencyList(), other.getSuccessorList(), other.getPredecessorList());

  static ext::compare<decltype(first)> comp;

  return comp(first, second);
}

template<typename TNode, typename TEdge>
void MixedGraph<TNode, TEdge>::operator>>(std::ostream &ostream) const {
  ostream << "(" << name() << " ";
  for (const auto &i : m_adjacency_list) {
    ostream << i.first << " <-->" << std::endl;

    for (const auto &j : i.second) {
      ostream << "\t\t" << j.first << " " << j.second << std::endl;
    }

    ostream << i.first << "  -->" << std::endl;
    for (const auto &j : m_succ_list.at(i.first)) {
      ostream << "\t\t" << j.first << " " << j.second << std::endl;
    }
  }
  ostream << ")";
}

template<typename TNode, typename TEdge>
MixedGraph<TNode, TEdge>::operator std::string() const {
  std::stringstream ss;
  ss << "<";
  for (const auto &i : m_adjacency_list) {
    ss << i.first << " <-->" << std::endl;

    for (const auto &j : i.second) {
      ss << "\t\t" << j.first << " " << j.second << std::endl;
    }

    ss << i.first << "  -->" << std::endl;
    for (const auto &j : m_succ_list.at(i.first)) {
      ss << "\t\t" << j.first << " " << j.second << std::endl;
    }
  }
  ss << ">";
  return std::move(ss).str();
}

// ---------------------------------------------------------------------------------------------------------------------

} // namespace graph

// =====================================================================================================================

namespace core {

/**
 * Helper for normalisation of types specified by templates used as internal datatypes of symbols and states.
 *
 * \returns new instance of the graph with default template parameters or unmodified instance if the template parameters were already the default ones
 */

template<typename TNode, typename TEdge>
struct normalize < graph::MixedGraph < TNode, TEdge > > {
  static graph::MixedGraph<> eval(graph::MixedGraph<TNode, TEdge> &&value) {
    graph::MixedGraph<> graph;

    // Create edges
    for (auto &&i: ext::make_mover(std::move(value).getAdjacencyList())) {
      DefaultNodeType first = graph::GraphNormalize::normalizeNode(std::move(i.first));
      for (auto &&j: i.second) {
        DefaultNodeType second = graph::GraphNormalize::normalizeNode(std::move(j.first));
        DefaultEdgeType edge = graph::GraphNormalize::normalizeEdge(std::move(j.second));

        graph.addNode(first);
        graph.addNode(second);
        graph.addEdge(edge);
      }
    }

    // Create successor
    for (auto &&i: ext::make_mover(std::move(value).getSuccessorList())) {
      DefaultNodeType first = graph::GraphNormalize::normalizeNode(std::move(i.first));
      for (auto &&j: i.second) {
        DefaultNodeType second = graph::GraphNormalize::normalizeNode(std::move(j.first));
        DefaultEdgeType edge = graph::GraphNormalize::normalizeEdge(std::move(j.second));

        graph.addNode(first);
        graph.addNode(second);
        graph.addEdge(edge);
      }
    }

    // Create predecessors
    for (auto &&i: ext::make_mover(std::move(value).getPredecessorList())) {
      DefaultNodeType first = graph::GraphNormalize::normalizeNode(std::move(i.first));
      for (auto &&j: i.second) {
        DefaultNodeType second = graph::GraphNormalize::normalizeNode(std::move(j.first));
        DefaultEdgeType edge = graph::GraphNormalize::normalizeEdge(std::move(j.second));

        graph.addNode(first);
        graph.addNode(second);
        graph.addEdge(edge);
      }
    }

    return graph;
  }
};

}

// =====================================================================================================================
#endif //ALIB2_MIXEDGRAPH_HPP