graph.h

#ifndef GRAPH_H
#define GRAPH_H
 
#ifdef GRAPH_VISUALIZATION_H
#include "../../visualization/graph_visual/graph_visualization.h"
#endif
 
#ifdef __cplusplus
#include <algorithm>
#include <climits>
#include <iostream>
#include <limits>
#include <queue>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#endif
 
template <typename T> class graph {
public:
  graph(std::string _type,
        std::vector<std::pair<T, std::vector<T>>> _adj = {}) {
    try {
      if (_type == "directed" || _type == "undirected") {
        this->_type = _type;
      } else {
        throw std::invalid_argument("Can't recognize the type of graph");
      }
      if (!_adj.empty()) {
        for (size_t i = 0; i < _adj.size(); i++) {
          for (T &neigh : _adj[i].second) {
            this->add_edge(_adj[i].first, neigh);
          }
        }
      }
    } catch (std::invalid_argument &e) {
      std::cerr << e.what() << '\n';
      return;
    }
  }
 
  graph(const graph &g) : adj(g.adj), _elements(g._elements), _type(g._type) {
  }
 
  graph &operator=(const graph &g) {
    adj = g.adj;
    _elements = g._elements;
    _type = g._type;
    return *this;
  }
 
  ~graph() { adj.clear(); }
 
  void add_edge(T u, T v) {
    if (_type == "undirected") {
      adj[u].push_back(v);
      adj[v].push_back(u);
    } else {
      adj[u].push_back(v);
    }
    _elements.insert(u);
    _elements.insert(v);
  }
 
  bool has_edge(T start, T end) {
    if (_elements.find(start) == _elements.end()) {
      return false;
    }
    for (T &x : adj[start]) {
      if (x == end) {
        return true;
      }
    }
    return false;
  }
 
  void clear() {
    _elements.clear();
    adj.clear();
  }
 
  bool empty() { return _elements.empty(); }
 
  size_t size();
 
  std::vector<T> dfs(T start);
 
  std::vector<T> bfs(T start);
 
  int64_t connected_components();
 
  bool cycle();
 
  std::vector<T> topological_sort();
 
  bool bipartite();
 
  std::vector<std::vector<T>> bridge(T start);
 
  int64_t scc();
 
  bool connected();
 
  int eulerian();
 
  void visualize();
 
  friend std::ostream &operator<<(std::ostream &out, graph<T> &g) {
    out << '{';
 
    std::vector<T> elements = g.topological_sort();
    for (T &x : elements) {
      out << x << ' ';
    }
    out << '}' << '\n';
    return out;
  }
 
private:
  std::unordered_map<T, std::vector<T>> adj;
  std::unordered_set<T> _elements;
  std::string _type;
 
  void dfs_bridge(T start, T parent, int64_t &time,
                  std::unordered_map<T, bool> &visited,
                  std::unordered_map<T, int64_t> &in,
                  std::unordered_map<T, int64_t> &out,
                  std::vector<std::vector<T>> &bridges) {
    visited[start] = true;
    in[start] = out[start] = time++;
    for (T &x : adj[start]) {
      if (x != parent) {
        if (visited.find(x) == visited.end()) {
          dfs_bridge(x, start, time, visited, in, out, bridges);
          if (out[x] > in[start]) {
            bridges.push_back({x, start});
          }
        }
        out[start] = std::min(out[start], out[x]);
      }
    }
  }
};
 
template <typename T> size_t graph<T>::size() { return _elements.size(); }
 
template <typename T> std::vector<T> graph<T>::dfs(T start) {
  std::vector<T> path;
  if (this->empty() || _elements.find(start) == _elements.end()) {
    return path;
  }
  std::stack<T> s;
  std::unordered_map<T, bool> visited;
  s.push(start);
  visited[start] = true;
  while (!s.empty()) {
    T current = s.top();
    path.push_back(current);
    s.pop();
    for (T &x : adj[current]) {
      if (visited.find(x) == visited.end()) {
        s.push(x);
        visited[x] = true;
      }
    }
  }
  return path;
}
 
template <typename T> std::vector<T> graph<T>::bfs(T start) {
  std::vector<T> path;
  if (this->empty() || _elements.find(start) == _elements.end()) {
    return path;
  }
  std::queue<T> q;
  std::unordered_map<T, bool> visited;
  q.push(start);
  visited[start] = true;
  while (!q.empty()) {
    int64_t size = q.size();
    for (int64_t i = 0; i < size; i++) {
      T current = q.front();
      path.push_back(current);
      q.pop();
      for (T &x : adj[current]) {
        if (visited.find(x) == visited.end()) {
          q.push(x);
          visited[x] = true;
        }
      }
    }
  }
  return path;
}
 
template <typename T> int64_t graph<T>::connected_components() {
  auto explore = [&](std::unordered_map<T, bool> &visited, T element) -> void {
    std::queue<T> q;
    q.push(element);
    visited[element] = true;
    while (!q.empty()) {
      T current = q.front();
      q.pop();
      for (T &x : adj[current]) {
        if (visited.find(x) == visited.end()) {
          q.push(x);
          visited[x] = true;
        }
      }
    }
  };
  size_t n = _elements.size();
  int64_t cc = 0;
  std::unordered_map<T, bool> visited;
  for (T x : _elements) {
    if (visited.find(x) == visited.end()) {
      explore(visited, x);
      cc++;
    }
  }
  return cc;
}
 
template <typename T> bool graph<T>::cycle() {
  std::unordered_map<T, int> indeg;
  std::queue<T> q;
  size_t visited = 0;
 
  for (T x : _elements) {
    for (T &y : adj[x]) {
      indeg[y]++;
    }
  }
 
  for (T x : _elements) {
    if (indeg[x] == 0) {
      q.push(x);
    }
  }
 
  while (!q.empty()) {
    T current = q.front();
    q.pop();
    visited++;
    for (T &x : adj[current]) {
      if (--indeg[x] == 0) {
        q.push(x);
      }
    }
  }
  return visited == 0;
}
 
template <typename T> std::vector<T> graph<T>::topological_sort() {
  std::vector<T> top_sort;
  std::unordered_map<T, bool> visited;
  std::unordered_map<T, int64_t> indeg;
  for (T x : _elements) {
    for (T &y : adj[x]) {
      indeg[y]++;
    }
  }
 
  std::queue<T> q;
  for (T x : _elements) {
    if (indeg[x] == 0) {
      q.push(x);
      visited[x] = true;
    }
  }
 
  while (!q.empty()) {
    T current = q.front();
    q.pop();
    top_sort.push_back(current);
    for (T &x : adj[current]) {
      if (visited.find(x) == visited.end()) {
        if (--indeg[x] == 0) {
          q.push(x);
          visited[x] = true;
        }
      }
    }
  }
 
  return top_sort;
}
 
template <typename T> bool graph<T>::bipartite() {
  std::unordered_map<T, int> color;
  std::queue<std::pair<T, int>> q;
 
  for (T x : _elements) {
    if (color.find(x) == color.end()) {
      q.push({x, 0});
      color[x] = 0;
      while (!q.empty()) {
        std::pair<T, int> current = q.front();
        q.pop();
        T v = current.first;
        int col = current.second;
        for (T &x : adj[v]) {
          if (color.find(x) != color.end() && color[x] == col) {
            return false;
          }
          if (color.find(x) == color.end()) {
            color[x] = (col) ? 0 : 1;
            q.push({x, color[x]});
          }
        }
      }
    }
  }
  return true;
}
 
template <typename T> std::vector<std::vector<T>> graph<T>::bridge(T start) {
  int64_t timer = 0;
  std::vector<std::vector<T>> bridges;
  std::unordered_map<T, bool> visited;
  std::unordered_map<T, int64_t> in, out;
  for (T x : _elements) {
    in[x] = 0;
    out[x] = 0;
  }
  dfs_bridge(start, -1, timer, visited, in, out, bridges);
  return bridges;
}
 
template <typename T> bool graph<T>::connected() {
  std::unordered_map<T, bool> visited;
  bool check = 0;
  T start;
  for (auto &ele : adj) {
    if (adj[ele.first].size() != 0) {
      start = ele.first;
      check = 1;
      break;
    }
  }
  if (!check) {
    return false;
  }
  std::stack<T> s;
  s.push(start);
  visited[start] = true;
  while (!s.empty()) {
    T current = s.top();
    s.pop();
    for (T &x : adj[current]) {
      if (visited.find(x) == visited.end()) {
        visited[x] = true;
        s.push(x);
      }
    }
  }
 
  for (T x : _elements) {
    if (visited.find(x) == visited.end() && adj[x].size() > 0) {
      return false;
    }
  }
  return true;
}
 
template <typename T> int graph<T>::eulerian() {
  if (this->connected() == false) {
    return false;
  }
 
  int64_t odd = 0;
  for (auto &el : adj) {
    if (adj[el.first].size() & 1) {
      odd++;
    }
  }
 
  if (odd > 2) {
    return false;
  }
  return (odd) ? 1 : 2;
}
 
#ifdef GRAPH_VISUALIZATION_H
template <typename T> void graph<T>::visualize() {
  std::string s;
  if (_type == "directed") {
    if (std::is_same_v<T, char> || std::is_same_v<T, std::string>) {
      for (auto &[element, neighbors] : adj) {
        for (T &x : neighbors) {
          s += element;
          s += "->";
          s += x;
          s += '\n';
        }
      }
    } else {
      for (auto &[element, neighbors] : adj) {
        for (T &x : neighbors) {
          s += std::to_string(element);
          s += "->";
          s += std::to_string(x);
          s += '\n';
        }
      }
    }
  } else {
    if (std::is_same_v<T, char> || std::is_same_v<T, std::string>) {
      for (auto &[element, neighbors] : adj) {
        for (T &x : neighbors) {
          s += element;
          s += "--";
          s += x;
          s += '\n';
        }
      }
    } else {
      for (auto &[element, neighbors] : adj) {
        for (T &x : neighbors) {
          s += std::to_string(element);
          s += "--";
          s += std::to_string(x);
          s += '\n';
        }
      }
    }
  }
  s += '\n';
  if (_type == "directed") {
    digraph_visualization::visualize(s);
  } else {
    graph_visualization::visualize(s);
  }
}
#endif
 
template <typename T> class weighted_graph {
public:
  weighted_graph(std::string _type,
                 std::vector<std::pair<std::pair<T, T>, int64_t>> _adj = {}) {
    try {
      if (_type == "directed" || _type == "undirected") {
        this->_type = _type;
      } else {
        throw std::invalid_argument("Can't recognize the type of graph");
      }
      if (!_adj.empty()) {
        for (size_t i = 0; i < _adj.size(); i++) {
          this->add_edge(_adj[i].first.first, _adj[i].first.second,
                         _adj[i].second);
        }
      }
    } catch (std::invalid_argument &e) {
      std::cerr << e.what() << '\n';
      return;
    }
  }
 
  explicit weighted_graph(const weighted_graph &g) : adj(g.adj), _elements(g._elements), _type(g._type) {
 
 
 
  }
 
  weighted_graph &operator=(const weighted_graph &g) {
    adj = g.adj;
    _elements = g._elements;
    _type = g._type;
    return *this;
  }
 
  ~weighted_graph() { adj.clear(); }
 
  void add_edge(T u, T v, int64_t w) {
    if (_type == "undirected") {
      adj[u].push_back(std::make_pair(v, w));
      adj[v].push_back(std::make_pair(u, w));
    } else if (_type == "directed") {
      adj[u].push_back(std::make_pair(v, w));
    }
    _elements.insert(u);
    _elements.insert(v);
  }
 
  bool has_edge(T start, T end) {
    if (_elements.find(start) == _elements.end()) {
      return false;
    }
    for (std::pair<T, double> &x : adj[start]) {
      if (x.first == end) {
        return true;
      }
    }
    return false;
  }
 
  void clear() {
    _elements.clear();
    adj.clear();
  }
  bool empty() { return _elements.empty(); }
 
  size_t size();
 
  std::vector<T> dfs(T start);
 
  std::vector<T> bfs(T start);
 
  double shortest_path(T start, T end);
 
  int64_t connected_components();
 
  bool cycle();
 
  std::vector<T> topological_sort();
 
  int64_t prim(T start);
 
  bool bipartite();
 
  std::vector<std::vector<T>> bridge(T start);
 
  int64_t scc();
 
  bool connected();
 
  int eulerian();
 
  std::unordered_map<T, double> bellman_ford(T start);
 
  void visualize();
 
  friend std::ostream &operator<<(std::ostream &out, weighted_graph<T> &g) {
    out << '{';
    std::vector<T> elements = g.topological_sort();
    for (T &x : elements) {
      out << x << ' ';
    }
    out << '}' << '\n';
    return out;
  }
 
private:
  std::unordered_map<T, std::vector<std::pair<T, double>>> adj;
  std::string _type;
  std::unordered_set<T> _elements;
 
  void dfs_bridge(T start, T parent, int64_t &time,
                  std::unordered_map<T, bool> &visited,
                  std::unordered_map<T, int64_t> &in,
                  std::unordered_map<T, int64_t> &out,
                  std::vector<std::vector<T>> &bridges) {
    visited[start] = true;
    in[start] = out[start] = time++;
    for (std::pair<T, double> &x : adj[start]) {
      if (x.first != parent) {
        if (visited.find(x.first) == visited.end()) {
          dfs_bridge(x.first, start, time, visited, in, out, bridges);
          if (out[x.first] > in[start]) {
            bridges.push_back({x.first, start});
          }
        }
        out[start] = std::min(out[start], out[x.first]);
      }
    }
  }
};
 
template <typename T> size_t weighted_graph<T>::size() {
  return _elements.size();
}
 
template <typename T> double weighted_graph<T>::shortest_path(T start, T end) {
  if (_elements.find(start) == _elements.end()) {
    std::cout << "Element: " << start << " is not found in the Graph" << '\n';
    return -1;
  }
  if (_elements.find(end) == _elements.end()) {
    std::cout << "Element: " << end << " is not found in the Graph" << '\n';
    return -1;
  }
 
  if (!cycle() && _type == "directed") {
    std::vector<T> top_sort = topological_sort();
    std::reverse(top_sort.begin(), top_sort.end());
    std::stack<T> s;
    std::unordered_map<T, double> dist;
    for (auto &x : _elements) {
      dist[x] = std::numeric_limits<int64_t>::max();
    }
    dist[start] = 0;
    while (!top_sort.empty()) {
      auto current = top_sort.back();
      top_sort.pop_back();
      if (dist[current] != std::numeric_limits<int64_t>::max()) {
        for (std::pair<T, double> &x : adj[current]) {
          if (dist[x.first] > dist[current] + x.second) {
            dist[x.first] = dist[current] + x.second;
            top_sort.push_back(x.first);
          }
        }
      }
    }
    return (dist[end] != std::numeric_limits<int64_t>::max()) ? dist[end] : -1;
  } else {
    std::unordered_map<T, double> dist;
    for (auto &x : _elements) {
      dist[x] = std::numeric_limits<int64_t>::max();
    }
    std::priority_queue<std::pair<double, T>,
                        std::vector<std::pair<double, T>>,
                        std::greater<std::pair<double, T>>>
        pq;
    pq.push(std::make_pair(0, start));
    dist[start] = 0;
    while (!pq.empty()) {
      T currentNode = pq.top().second;
      double currentDist = pq.top().first;
      pq.pop();
      for (std::pair<T, double> &edge : adj[currentNode]) {
        if (currentDist + edge.second < dist[edge.first]) {
          dist[edge.first] = currentDist + edge.second;
          pq.push(std::make_pair(dist[edge.first], edge.first));
        }
      }
    }
    return (dist[end] != std::numeric_limits<int64_t>::max()) ? dist[end] : -1;
  }
  return -1;
}
 
template <typename T> std::vector<T> weighted_graph<T>::dfs(T start) {
 
  std::vector<T> path;
  if (this->empty() || _elements.find(start) == _elements.end()) {
    return path;
  }
  std::stack<T> s;
  std::unordered_map<T, bool> visited;
  s.push(start);
  visited[start] = true;
  while (!s.empty()) {
    int64_t size = s.size();
    for (int64_t i = 0; i < size; i++) {
      T current = s.top();
      path.push_back(current);
      s.pop();
      for (std::pair<T, double> &x : adj[current]) {
        if (visited.find(x.first) == visited.end()) {
          s.push(x.first);
          visited[x.first] = true;
        }
      }
    }
  }
  return path;
}
 
template <typename T> std::vector<T> weighted_graph<T>::bfs(T start) {
  std::vector<T> path;
  if (this->empty() || _elements.find(start) == _elements.end()) {
    return path;
  }
  std::queue<T> q;
  std::unordered_map<T, bool> visited;
  q.push(start);
  visited[start] = true;
  while (!q.empty()) {
    int64_t size = q.size();
    for (int64_t i = 0; i < size; i++) {
      T current = q.front();
      path.push_back(current);
      q.pop();
      for (std::pair<T, double> &x : adj[current]) {
        if (visited.find(x.first) == visited.end()) {
          q.push(x.first);
          visited[x.first] = true;
        }
      }
    }
  }
  return path;
}
 
template <typename T> int64_t weighted_graph<T>::connected_components() {
  auto explore = [&](std::unordered_map<T, bool> &visited, T element) -> void {
    std::stack<T> s;
    s.push(element);
    visited[element] = true;
    while (!s.empty()) {
      T current = s.top();
      s.pop();
      for (std::pair<T, double> &x : adj[current]) {
        if (visited.find(x.first) == visited.end()) {
          s.push(x.first);
          visited[x.first] = true;
        }
      }
    }
  };
  size_t n = _elements.size();
  int64_t cc = 0;
  std::unordered_map<T, bool> visited;
  for (T x : _elements) {
    if (visited.find(x) == visited.end()) {
      explore(visited, x);
      cc++;
    }
  }
  return cc;
}
 
template <typename T> bool weighted_graph<T>::cycle() {
  std::unordered_map<T, int> indeg;
  std::queue<T> q;
  size_t visited = 0;
 
  for (T x : _elements) {
    for (std::pair<T, double> &y : adj[x]) {
      indeg[y.first]++;
    }
  }
 
  for (T x : _elements) {
    if (indeg[x] == 0) {
      q.push(x);
    }
  }
 
  while (!q.empty()) {
    T current = q.front();
    q.pop();
    visited++;
    for (std::pair<T, double> &x : adj[current]) {
      if (--indeg[x.first] == 0) {
        q.push(x.first);
      }
    }
  }
  return visited == 0;
}
 
template <typename T> std::vector<T> weighted_graph<T>::topological_sort() {
  std::vector<T> top_sort;
  std::unordered_map<T, bool> visited;
  std::unordered_map<T, int64_t> indeg;
  for (T x : _elements) {
    for (std::pair<T, double> &y : adj[x]) {
      indeg[y.first]++;
    }
  }
 
  std::queue<T> q;
  for (T x : _elements) {
    if (indeg[x] == 0) {
      q.push(x);
      visited[x] = true;
    }
  }
 
  while (!q.empty()) {
    T current = q.front();
    q.pop();
    top_sort.push_back(current);
    for (std::pair<T, double> &x : adj[current]) {
      if (visited.find(x.first) == visited.end()) {
        if (--indeg[x.first] == 0) {
          q.push(x.first);
          visited[x.first] = true;
        }
      }
    }
  }
 
  return top_sort;
}
 
template <typename T> int64_t weighted_graph<T>::prim(T _temp) {
  std::priority_queue<std::pair<T, int64_t>, std::vector<std::pair<T, int64_t>>,
                      std::greater<std::pair<T, int64_t>>>
      q;
  std::unordered_map<T, bool> visited;
  int64_t cost = 0;
  q.push(std::make_pair(0, _temp));
  while (!q.empty()) {
    std::pair<T, int64_t> current = q.top();
    q.pop();
    _temp = current.first;
    if (visited.find(_temp) != visited.end()) {
      continue;
    }
    cost += current.second;
    visited[_temp] = true;
    for (std::pair<T, double> &x : adj[current.first]) {
      if (visited.find(x.first) == visited.end()) {
        q.push(x);
      }
    }
  }
  return cost;
}
 
template <typename T> bool weighted_graph<T>::bipartite() {
  std::unordered_map<T, int> color;
  std::queue<std::pair<T, int>> q;
 
  for (T x : _elements) {
    if (color.find(x) == color.end()) {
      q.push({x, 0});
      color[x] = 0;
      while (!q.empty()) {
        std::pair<T, int> current = q.front();
        q.pop();
        T v = current.first;
        int col = current.second;
        for (std::pair<T, double> &x : adj[v]) {
          if (color.find(x.first) != color.end() && color[x.first] == col) {
            return false;
          }
          if (color.find(x.first) == color.end()) {
            color[x.first] = (col) ? 0 : 1;
            q.push({x.first, color[x.first]});
          }
        }
      }
    }
  }
  return true;
}
 
template <typename T>
std::vector<std::vector<T>> weighted_graph<T>::bridge(T start) {
  int64_t timer = 0;
  std::vector<std::vector<T>> bridges;
  std::unordered_map<T, bool> visited;
  std::unordered_map<T, int64_t> in, out;
  for (T x : _elements) {
    in[x] = 0;
    out[x] = 0;
  }
  dfs_bridge(start, -1, timer, visited, in, out, bridges);
  return bridges;
}
 
template <typename T> bool weighted_graph<T>::connected() {
  std::unordered_map<T, bool> visited;
  bool check = 0;
  T start;
  for (auto &ele : adj) {
    if (adj[ele.first].size() != 0) {
      start = ele.first;
      check = 1;
      break;
    }
  }
  if (!check) {
    return false;
  }
  std::stack<T> s;
  s.push(start);
  visited[start] = true;
  while (!s.empty()) {
    T current = s.top();
    s.pop();
    for (std::pair<T, double> &x : adj[current]) {
      if (visited.find(x.first) == visited.end()) {
        visited[x.first] = true;
        s.push(x.first);
      }
    }
  }
 
  for (T x : _elements) {
    if (visited.find(x) == visited.end() && adj[x].size() > 0) {
      return false;
    }
  }
  return true;
}
 
template <typename T> int weighted_graph<T>::eulerian() {
  if (this->connected() == false) {
    return false;
  }
 
  int odd = 0;
  for (auto &el : adj) {
    if (adj[el.first].size() & 1) {
      odd++;
    }
  }
 
  if (odd > 2) {
    return 0;
  }
 
  return (odd) ? 1 : 2;
}
 
template <typename T>
std::unordered_map<T, double> weighted_graph<T>::bellman_ford(T start) {
  std::unordered_map<T, double> dist;
  // Initialize the distance to all nodes to be infinity
  // except for the starting node which is zero.
  for (auto it : adj)
    dist[it.first] = std::numeric_limits<double>::infinity();
  dist[start] = 0;
 
  // Get number of vertices present in the graph
  int v = adj.size();
 
  // For each vertex, apply relaxation for all the edges
  for (int i = 0; i < v - 1; i++)
    for (const auto j : adj)
      for (const auto edge : adj[j.first])
        if (dist[j.first] + edge.second < dist[edge.first])
          dist[edge.first] = dist[j.first] + edge.second;
 
  // Run algorithm a second time to detect which nodes are part
  // of a negative cycle. A negative cycle has occurred if we
  // can find a better path beyond the optimal solution.
  for (int i = 0; i < v - 1; i++)
    for (const auto j : adj)
      for (const auto edge : adj[j.first])
        if (dist[j.first] + edge.second < dist[edge.first])
          dist[edge.first] = -std::numeric_limits<double>::infinity();
 
  // Return the array containing the shortest distance to every node
  return dist;
}
 
#ifdef GRAPH_VISUALIZATION_H
template <typename T> void weighted_graph<T>::visualize() {
  std::string s;
  if (_type == "directed") {
    if (std::is_same_v<T, char> || std::is_same_v<T, std::string>) {
      for (auto &[element, neighbors] : adj) {
        for (std::pair<T, double> &x : neighbors) {
          if (x.first == element) {
            continue;
          }
          s += element;
          s += "->";
          s += x.first;
          s += "[label=";
          s += std::to_string(x.second);
          s += "]";
          s += '\n';
        }
      }
    } else {
      for (auto &[element, neighbors] : adj) {
        for (std::pair<T, double> &x : neighbors) {
          if (x.first == element) {
            continue;
          }
          s += std::to_string(element);
          s += "->";
          s += std::to_string(x.first);
          s += "[label=";
          s += std::to_string(x.second);
          s += "]";
          s += '\n';
        }
      }
    }
  } else {
    if (std::is_same_v<T, char> || std::is_same_v<T, std::string>) {
      for (auto &[element, neighbors] : adj) {
        for (std::pair<T, double> &x : neighbors) {
          if (x.first == element) {
            continue;
          }
          s += element;
          s += "--";
          s += x.first;
          s += "[label=";
          s += std::to_string(x.second);
          s += "]";
          s += '\n';
        }
      }
    } else {
      for (auto &[element, neighbors] : adj) {
        for (std::pair<T, double> &x : neighbors) {
          if (x.first == element) {
            continue;
          }
          s += std::to_string(element);
          s += "--";
          s += std::to_string(x.first);
          s += "[label=";
          s += std::to_string(x.second);
          s += "]";
          s += '\n';
        }
      }
    }
  }
  if (_type == "directed") {
    digraph_visualization::visualize(s);
  } else {
    graph_visualization::visualize(s);
  }
}
#endif
 
#endif