depth_research/graph_utils.hpp at master · iamnotnader/depth_research · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#ifndef BARRIER_GRAPH_UTILS_HPP
#define BARRIER_GRAPH_UTILS_HPP

#include "graph_utils.h"

#include <vector>
#include "status_defs.h"
#include <iostream>
#include <assert.h>
#include <sstream>
#include "logging_utils.h"

using std::vector;
using status_defs::Status;
using std::cout;
using std::endl;
using std::tuple;
using std::string;
using std::pair;

namespace graph_utils {

// Node class for representing a graph.
template<typename ValueType, typename WeightType>
void Node<ValueType,WeightType>::add_neighbor(Node<ValueType,WeightType>* node,
                                              WeightType weight) {
  neighbors.push_back(node);
  weights.push_back(weight);
}

template<typename ValueType, typename WeightType>
void Node<ValueType,WeightType>::add_neighbor_safe(
    Node<ValueType,WeightType>* node, WeightType weight) {
  for (int i = 0; i < neighbors.size(); i++) {
    assert(neighbors[i]->id != node->id);
  }
  neighbors.push_back(node);
  weights.push_back(weight);
}

template<typename ValueType, typename WeightType>
void Node<ValueType,WeightType>::remove_neighbor(
    Node<ValueType,WeightType>* node) {
  int node_index = -1;
  for (int i = 0; i < neighbors.size(); i++) {
    if (neighbors[i] == node) {
      node_index = i;
      break;
    }
  }
  if (node_index != -1) {
    neighbors.erase(neighbors.begin() + node_index);
    weights.erase(weights.begin() + node_index);
  }
}

template<typename ValueType, typename WeightType>
void Node<ValueType,WeightType>::remove_neighbor(int node_id) {
  int node_index = -1;
  for (int i = 0; i < neighbors.size(); i++) {
    if (neighbors[i].id == node_id) {
      node_index = i;
      break;
    }
  }
  if (node_index != -1) {
    neighbors.erase(neighbors.begin() + node_index);
    weights.erase(weights.begin() + node_index);
  }
}

template<typename ValueType, typename WeightType, bool is_directed>
Graph<ValueType,WeightType,is_directed>::Graph(const vector<ValueType>& values,
    const vector<pair<int, int>>& edges, const vector<WeightType>& weights) {
  assert(edges.size() == weights.size());
  for (size_t i = 0; i < values.size(); i++) {
    nodes.push_back(Node<ValueType,WeightType>(values[i], i));
  }
  for (size_t i = 0; i < edges.size(); i++) {
    const pair<int, int>& edge = edges[i];
    add_edge(edge.first, edge.second, weights[i]);
  }
}

template<typename ValueType, typename WeightType, bool is_directed>
void  Graph<ValueType,WeightType,is_directed>::add_edge(int id1, int id2,
    WeightType weight) {
  assert(id1 < nodes.size());
  assert(id2 < nodes.size());

  auto& nodes = this->nodes;
  // If the graph is undirected, we add an edge in both directions.
  // TODO(daddy): Make this not a disgusting hack...
  #ifdef RUN_FAST
  nodes[id1].add_neighbor(&(nodes[id2]), weight);
  if (!is_directed) {
    nodes[id2].add_neighbor(&(nodes[id1]), weight);
  }
  #else
  nodes[id1].add_neighbor_safe(&(nodes[id2]), weight);
  if (!is_directed) {
    nodes[id2].add_neighbor_safe(&(nodes[id1]), weight);
  }
  #endif
}

template<typename ValueType, typename WeightType, bool is_directed>
void Graph<ValueType,WeightType,is_directed>::remove_edge(int id1, int id2) {
  nodes[id1].remove_neighbor(&nodes[id2]);
  if (!is_directed) {
    nodes[id2].remove_neighbor(&nodes[id1]);
  }
}

template<typename ValueType, typename WeightType, bool is_directed>
bool Graph<ValueType,WeightType,is_directed>::has_edge(int id1, int id2,
    WeightType* weight) {
  auto& n1 = this->nodes[id1];
  for (size_t i = 0; i < n1.neighbors.size(); i++) {
    if (n1.neighbors[i]->id == id2) {
      *weight = n1.weights[i];
      return true;
    }
  }
  return false;
}

template<typename ValueType, typename WeightType, bool is_directed>
string Graph<ValueType,WeightType,is_directed>::to_string() const {
  std::ostringstream oss;
  oss << *this;
  return oss.str();
}

} // namespace graph_utils
#endif