MixedGraph.hpp

Go to the documentation of this file.

 
// Copyright (c) 2017 Czech Technical University in Prague | Faculty of Information Technology. All rights reserved.
 
#pragma once
 
#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:
    auto operator <=> ( const MixedGraph & other ) const {
        return std::tie(m_adjacency_list, m_succ_list, m_pred_list) <=> std::tie(other.getAdjacencyList(), other.getSuccessorList(), other.getPredecessorList());
    }
 
    bool operator == ( const MixedGraph & other ) const {
        return std::tie(m_adjacency_list, m_succ_list, m_pred_list) == std::tie(other.getAdjacencyList(), other.getSuccessorList(), other.getPredecessorList());
    }
 
  void operator>>(ext::ostream &ostream) 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>
void MixedGraph<TNode, TEdge>::operator>>(ext::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 << ")";
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
} // namespace graph
 
// =====================================================================================================================
 
namespace core {
 
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;
  }
};
 
}
 
// =====================================================================================================================