UndirectedGraph.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/pair>
#include <alib/set>
#include <alib/vector>
#include <functional>
#include <object/Object.h>
#include <core/normalize.hpp>
#include <alib/tuple>
 
#include <common/Normalize.hpp>
#include <graph/GraphInterface.hpp>
#include <graph/GraphFeatures.hpp>
 
namespace graph {
 
template<typename TNode, typename TEdge>
class UndirectedGraph : public GraphInterface<TNode, TEdge> {
// ---------------------------------------------------------------------------------------------------------------------
 
 public:
  using node_type = TNode;
  using edge_type = TEdge;
 
// ---------------------------------------------------------------------------------------------------------------------
 
 protected:
  ext::map<TNode, ext::map<TNode, TEdge>> m_adjacency_list;
 
// =====================================================================================================================
// Constructor, Destructor, Operators
 public:
 
// ---------------------------------------------------------------------------------------------------------------------
 
  const ext::map<TNode, ext::map<TNode, TEdge>> &getAdjacencyList() const &;
 
  ext::map<TNode, ext::map<TNode, TEdge>> &&getAdjacencyList() &&;
 
// ---------------------------------------------------------------------------------------------------------------------
 
// =====================================================================================================================
// GraphBase interface
 public:
    auto operator <=> (const UndirectedGraph &other) const {
        return std::tie(m_adjacency_list) <=> std::tie(other.getAdjacencyList());
    }
 
    bool operator == (const UndirectedGraph &other) const {
        return std::tie(m_adjacency_list) == std::tie(other.getAdjacencyList());
    }
 
  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);
 
// ---------------------------------------------------------------------------------------------------------------------
 
// =====================================================================================================================
// GraphInterface interface
 public:
 
  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>> &UndirectedGraph<TNode,
                                                               TEdge>::getAdjacencyList() const &{
  return m_adjacency_list;
}
 
template<typename TNode, typename TEdge>
ext::map<TNode, ext::map<TNode, TEdge>> &&UndirectedGraph<TNode, TEdge>::getAdjacencyList() &&{
  return std::move(m_adjacency_list);
}
 
 
// ---------------------------------------------------------------------------------------------------------------------
 
template<typename TNode, typename TEdge>
void UndirectedGraph<TNode, TEdge>::addNode(const TNode &n) {
  m_adjacency_list[n];
}
 
template<typename TNode, typename TEdge>
void UndirectedGraph<TNode, TEdge>::addNode(TNode &&n) {
  m_adjacency_list[std::forward<TNode>(n)];
}
 
template<typename TNode, typename TEdge>
template<typename... Params>
void UndirectedGraph<TNode, TEdge>::addNode(Params &&... params) {
  addNode(TNode(std::forward<Params>(params) ...));
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
template<typename TNode, typename TEdge>
bool UndirectedGraph<TNode, TEdge>::addEdge(const TEdge &e) {
  if (e.first == e.second) {
    return false;
  }
 
  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;
  }
 
  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 UndirectedGraph<TNode, TEdge>::addEdge(TEdge &&e) {
  if (e.first == e.second) {
    return false;
  }
 
  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;
  }
 
  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 UndirectedGraph<TNode, TEdge>::addEdge(Params &&... params) {
  return addEdge(TEdge(std::forward<Params>(params) ...));
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
template<typename TNode, typename TEdge>
size_t UndirectedGraph<TNode, TEdge>::nodeCount() const {
  return m_adjacency_list.size();
}
 
template<typename TNode, typename TEdge>
size_t UndirectedGraph<TNode, TEdge>::edgeCount() const {
  size_t cnt = 0;
 
  for (const auto &i: m_adjacency_list) {
    cnt += i.second.size();
  }
 
  return cnt / 2;
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
template<typename TNode, typename TEdge>
ext::set<TNode> UndirectedGraph<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> UndirectedGraph<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);
    }
  }
 
  return vec;
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
template<typename TNode, typename TEdge>
ext::set<TNode> UndirectedGraph<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);
  }
 
  return set;
}
 
template<typename TNode, typename TEdge>
ext::vector<TEdge> UndirectedGraph<TNode, TEdge>::successorEdges(const TNode &n) const {
  ext::vector<TEdge> vec;
 
  if (m_adjacency_list.count(n) == 0) {
    return vec;
  }
 
  for (const auto &i: m_adjacency_list.at(n)) {
    vec.push_back(i.second);
  }
 
  return vec;
}
 
template<typename TNode, typename TEdge>
ext::set<TNode> UndirectedGraph<TNode, TEdge>::predecessors(const TNode &n) const {
  return successors(n);
}
 
template<typename TNode, typename TEdge>
ext::vector<TEdge> UndirectedGraph<TNode, TEdge>::predecessorEdges(const TNode &n) const {
  return successorEdges(n);
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
template<typename TNode, typename TEdge>
std::string UndirectedGraph<TNode, TEdge>::name() const {
  return "UndirectedGraph";
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
template<typename TNode, typename TEdge>
void UndirectedGraph<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 << ")";
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
} // namespace graph
 
// =====================================================================================================================
 
namespace core {
 
template<typename TNode, typename TEdge>
struct normalize < graph::UndirectedGraph < TNode, TEdge > > {
  static graph::UndirectedGraph<> eval(graph::UndirectedGraph<TNode, TEdge> &&value) {
    graph::UndirectedGraph<> graph;
 
    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);
      }
    }
 
    return graph;
  }
};
 
}
 
// =====================================================================================================================