Empirical
Graph.h
Go to the documentation of this file.
1 
11 #ifndef EMP_GRAPH_H
12 #define EMP_GRAPH_H
13 
14 #include <iostream>
15 
16 #include "../base/assert.h"
17 #include "../base/vector.h"
18 
19 #include "BitVector.h"
20 
21 namespace emp {
22 
24  class Graph {
25  public:
27  class Node {
28  private:
29  BitVector edge_set;
30  public:
31  Node(size_t num_nodes) : edge_set(num_nodes) { ; }
32  Node(const Node & in_node) : edge_set(in_node.edge_set) { ; }
33  ~Node() { ; }
34 
36  Node & operator=(const Node & in_node) { edge_set = in_node.edge_set; return *this; }
37 
39  bool HasEdge(size_t to) const { return edge_set[to]; }
40 
42  void AddEdge(size_t to) { edge_set.Set(to, true); }
43 
45  void AddEdgeSet(BitVector in_set) { edge_set |= in_set; }
46 
48  void RemoveEdge(size_t to) { edge_set.Set(to, false); }
49 
51  void SetEdge(size_t to, bool val) { edge_set.Set(to, val); }
52 
54  const BitVector & GetEdgeSet() const { return edge_set; }
55 
57  void Resize(size_t new_size) { edge_set.Resize(new_size); }
58 
60  void Clear() { edge_set.Clear(); }
61 
63  size_t GetDegree() const { return edge_set.CountOnes(); }
64 
66  size_t GetMaskedDegree(const BitVector & mask) const { return (mask & edge_set).CountOnes(); }
67  };
68 
69  protected:
71 
72  public:
74  Graph(size_t num_nodes=0) : nodes(num_nodes, num_nodes) { ; }
75 
76  Graph(const Graph &) = default;
77  Graph(Graph &&) = default;
78  ~Graph() { ; }
79 
80  Graph & operator=(const Graph &) = default;
81  Graph & operator=(Graph &&) = default;
82 
84  size_t GetSize() const { return nodes.size(); }
85 
87  size_t GetEdgeCount() const {
88  size_t edge_count = 0;
89  for (size_t i = 0; i < nodes.size(); i++) edge_count += nodes[i].GetDegree();
90  return edge_count;
91  }
92 
94  void Resize(size_t new_size) {
95  nodes.resize(new_size, new_size);
96  for (auto & node : nodes) {
97  node.Resize(new_size);
98  node.Clear();
99  }
100  }
101 
103  const BitVector & GetEdgeSet(size_t id) const {
104  emp_assert(id < nodes.size());
105  return nodes[id].GetEdgeSet();
106  }
107 
109  size_t GetDegree(size_t id) const {
110  emp_assert(id < nodes.size());
111  return nodes[id].GetDegree();
112  }
113 
115  size_t GetMaskedDegree(size_t id, const BitVector & mask) const {
116  emp_assert(id < nodes.size());
117  return nodes[id].GetMaskedDegree(mask);
118  }
119 
121  bool HasEdge(size_t from, size_t to) const {
122  emp_assert(from < nodes.size() && to < nodes.size());
123  return nodes[from].HasEdge(to);
124  }
125 
127  void AddEdge(size_t from, size_t to) {
128  emp_assert(from < nodes.size() && to < nodes.size());
129  nodes[from].AddEdge(to);
130  }
131 
133  void RemoveEdge(size_t from, size_t to) {
134  emp_assert(from < nodes.size() && to < nodes.size());
135  nodes[from].RemoveEdge(to);
136  }
137 
139  void SetEdge(size_t from, size_t to, bool val) {
140  emp_assert(from < nodes.size() && to < nodes.size());
141  nodes[from].SetEdge(to, val);
142  }
143 
145  bool HasEdgePair(size_t from, size_t to) const {
146  emp_assert(from < nodes.size() && to < nodes.size());
147  return nodes[from].HasEdge(to) && nodes[to].HasEdge(from);
148  }
149 
151  void AddEdgePair(size_t from, size_t to) {
152  emp_assert(from < nodes.size() && to < nodes.size());
153  nodes[from].AddEdge(to);
154  nodes[to].AddEdge(from);
155  }
156 
158  void RemoveEdgePair(size_t from, size_t to) {
159  emp_assert(from < nodes.size() && to < nodes.size());
160  nodes[from].RemoveEdge(to);
161  nodes[to].RemoveEdge(from);
162  }
163 
165  void SetEdgePairs(size_t from, size_t to, bool val) {
166  emp_assert(from < nodes.size() && to < nodes.size());
167  nodes[from].SetEdge(to, val);
168  nodes[to].SetEdge(from, val);
169  }
170 
172  void Merge(const Graph & in_graph) {
173  const size_t start_size = nodes.size();
174  const size_t new_size = start_size + in_graph.GetSize();
175  nodes.resize(new_size, new_size);
176  for (auto & node : nodes) {
177  node.Resize(new_size);
178  }
179 
180  for (size_t i = 0; i < in_graph.GetSize(); i++) {
181  BitVector edge_set = in_graph.nodes[i].GetEdgeSet();
182  edge_set.Resize(new_size);
183  edge_set <<= start_size;
184  nodes[start_size + i].AddEdgeSet(edge_set);
185  }
186  }
187 
189  void PrintSym(std::ostream & os=std::cout) {
190  os << GetSize() << " " << (GetEdgeCount()/2) << std::endl;
191  for (size_t from = 0; from < nodes.size(); from++) {
192  for (size_t to=from+1; to < nodes.size(); to++) {
193  if (HasEdge(from, to) == false) continue;
194  emp_assert(HasEdge(to, from)); // This must be a symmetric graph!
195  os << from << " " << to << std::endl;
196  }
197  }
198  }
199 
201  void PrintDirected(std::ostream & os=std::cout) {
202  os << GetSize() << " " << GetEdgeCount() << std::endl;
203  for (size_t from = 0; from < nodes.size(); from++) {
204  for (size_t to = 0; to < nodes.size(); to++) {
205  if (HasEdge(from, to) == false) continue;
206  os << from << " " << to << std::endl;
207  }
208  }
209  }
210 
211  };
212 
213  class WeightedGraph : public Graph {
214  protected:
216 
217  public:
218  WeightedGraph(size_t num_nodes=0) : Graph(num_nodes), weights(num_nodes) {
219  for (auto & row : weights) row.resize(num_nodes, 0.0);
220  }
221 
222  WeightedGraph(const WeightedGraph &) = default;
223  WeightedGraph(WeightedGraph &&) = default;
225 
226  WeightedGraph & operator=(const WeightedGraph &) = default;
227  WeightedGraph & operator=(WeightedGraph &&) = default;
228 
229  void Resize(size_t new_size) {
230  Graph::Resize(new_size);
231  weights.resize(new_size);
232  for (auto & row : weights) row.resize(new_size,0.0);
233  }
234 
236  double GetWeight(size_t from, size_t to) const {
237  emp_assert(from < nodes.size() && to < nodes.size());
238  return weights[from][to];
239  }
240 
242  void AddEdge(size_t from, size_t to, double weight) {
243  Graph::AddEdge(from, to);
244  weights[from][to] = weight;
245  }
246 
248  void AddEdgePair(size_t from, size_t to, double weight) {
249  Graph::AddEdgePair(from, to);
250  weights[from][to] = weight;
251  weights[to][from] = weight;
252  }
253 
255  void Merge(const WeightedGraph & in_graph) {
256  const size_t start_size = nodes.size();
257  Graph::Merge(in_graph);
258  weights.resize(nodes.size());
259  for (auto & row : weights) row.resize(nodes.size(), 0.0);
260 
261  // Move the weights over.
262  for (size_t i = 0; i < in_graph.GetSize(); i++) {
263  for (size_t j = 0; j < in_graph.GetSize(); j++) {
264  weights[i+start_size][j+start_size] = in_graph.weights[i][j];
265  }
266  }
267  }
268 
270  void PrintSym(std::ostream & os=std::cout) {
271  os << GetSize() << " " << (GetEdgeCount()/2) << std::endl;
272  for (size_t from = 0; from < nodes.size(); from++) {
273  for (size_t to=from+1; to < nodes.size(); to++) {
274  if (HasEdge(from, to) == false) continue;
275  emp_assert(HasEdge(to, from)); // This must be a symmetric graph!
276  os << from << " " << to << " " << weights[from][to] << std::endl;
277  }
278  }
279  }
280 
282  void PrintDirected(std::ostream & os=std::cout) {
283  os << GetSize() << " " << GetEdgeCount() << std::endl;
284  for (size_t from = 0; from < nodes.size(); from++) {
285  for (size_t to = 0; to < nodes.size(); to++) {
286  if (HasEdge(from, to) == false) continue;
287  os << from << " " << to << " " << weights[from][to] << std::endl;
288  }
289  }
290  }
291 
292  };
293 }
294 
295 #endif
WeightedGraph(size_t num_nodes=0)
Definition: Graph.h:218
size_t GetMaskedDegree(const BitVector &mask) const
Identify how many other nodes from a provided set (a BitVector) this one is connected to...
Definition: Graph.h:66
void Clear()
Remove all edges from this node.
Definition: Graph.h:60
size_t CountOnes() const
Count the number of ones in the BitVector.
Definition: BitVector.h:544
void Clear()
Set all bits to 0.
Definition: BitVector.h:478
bool HasEdge(size_t to) const
Is this node connect to a specific other node?
Definition: Graph.h:39
void AddEdgeSet(BitVector in_set)
Add a full set of connections from this node to others.
Definition: Graph.h:45
~Graph()
Definition: Graph.h:78
void AddEdge(size_t from, size_t to)
Add a specified edge into this graph.
Definition: Graph.h:127
void SetEdgePairs(size_t from, size_t to, bool val)
Set the status as to whether a pair of edges (in both direction) exist.
Definition: Graph.h:165
void PrintSym(std::ostream &os=std::cout)
Print a symmetric graph to the provided output stream (defaulting to standard out) ...
Definition: Graph.h:270
Node(size_t num_nodes)
What other node IDs is this one connected to?
Definition: Graph.h:31
void AddEdge(size_t from, size_t to, double weight)
When Adding an edge, must also provide a weight.
Definition: Graph.h:242
void SetEdge(size_t to, bool val)
Set whether a connection to another specific node should exist or not.
Definition: Graph.h:51
Information about nodes within a graph.
Definition: Graph.h:27
BitVector & Resize(size_t new_bits)
Resize this BitVector to have the specified number of bits.
Definition: BitVector.h:297
size_t GetDegree() const
Identify how many other nodes this one is connected to.
Definition: Graph.h:63
void Resize(size_t new_size)
Change the number of potential node connections that we are tracking.
Definition: Graph.h:57
void RemoveEdge(size_t to)
Remove the connection (if there is one) between this node and another one.
Definition: Graph.h:48
void AddEdgePair(size_t from, size_t to, double weight)
When Adding an edge pair, must also provide a weight.
Definition: Graph.h:248
A drop-in replacement for std::vector<bool>, but with extra bitwise logic features.
Definition: BitVector.h:39
~WeightedGraph()
Definition: Graph.h:224
size_t GetEdgeCount() const
Get the total number of edges in this graph.
Definition: Graph.h:87
const BitVector & GetEdgeSet() const
Get a BitVector representing which nodes this one is connected to.
Definition: Graph.h:54
A drop-in replacement for std::vector<bool>, with additional bitwise logic features.
void PrintDirected(std::ostream &os=std::cout)
Print a directed graph to the provided output stream (defaulting to standard out) ...
Definition: Graph.h:201
Definition: Graph.h:213
bool HasEdgePair(size_t from, size_t to) const
Determine if edges exist in both directions between a pair of vertices.
Definition: Graph.h:145
size_t size() const
Definition: vector.h:151
void Resize(size_t new_size)
Change the number of vertices in this graph.
Definition: Graph.h:94
size_t GetDegree(size_t id) const
Get the degree of a specified node.
Definition: Graph.h:109
size_t GetSize() const
Get number of vertices in this graph.
Definition: Graph.h:84
void AddEdgePair(size_t from, size_t to)
Add a pair of edges between two vertieces (in both directions)
Definition: Graph.h:151
static const PrintStr endl("<br>")
Pre-define emp::endl to insert a "<br>" and thus acting like a newline.
void Merge(const WeightedGraph &in_graph)
Merge two WeightedGraphs into one.
Definition: Graph.h:255
void Resize(size_t new_size)
Definition: Graph.h:229
A graph class that maintains a set of vertices (nodes) and edges (connecting pairs of nodes) ...
Definition: Graph.h:24
void resize(size_t new_size)
Definition: vector.h:161
Node(const Node &in_node)
Definition: Graph.h:32
void RemoveEdgePair(size_t from, size_t to)
Remove edges in both directions between a pair of vertices.
Definition: Graph.h:158
bool HasEdge(size_t from, size_t to) const
Determine if a specific edge is included in this graph.
Definition: Graph.h:121
void PrintSym(std::ostream &os=std::cout)
Print a symmetric graph to the provided output stream (defaulting to standard out) ...
Definition: Graph.h:189
If we are in emscripten, make sure to include the header.
Definition: array.h:37
const BitVector & GetEdgeSet(size_t id) const
Get the set of nodes that a specified node is connected to.
Definition: Graph.h:103
Build a debug wrapper emp::vector around std::vector.
Definition: vector.h:42
void Merge(const Graph &in_graph)
Merge a second graph into this one.
Definition: Graph.h:172
#define emp_assert(...)
Definition: assert.h:199
size_t GetMaskedDegree(size_t id, const BitVector &mask) const
Get how many of a set of nodes that a specified node is connected to.
Definition: Graph.h:115
emp::vector< Node > nodes
Set of vertices in this graph.
Definition: Graph.h:70
void RemoveEdge(size_t from, size_t to)
Remove a specified edge from this graph.
Definition: Graph.h:133
void PrintDirected(std::ostream &os=std::cout)
Print a directed graph to the provided output stream (defaulting to standard out) ...
Definition: Graph.h:282
void AddEdge(size_t to)
Add a connection between this node and another.
Definition: Graph.h:42
Graph(size_t num_nodes=0)
Construct a new graph with the specified number of nodes.
Definition: Graph.h:74
Node & operator=(const Node &in_node)
Set this node to have the same connections as another node.
Definition: Graph.h:36
double GetWeight(size_t from, size_t to) const
Determine weight of a specific edge in this graph.
Definition: Graph.h:236
void SetEdge(size_t from, size_t to, bool val)
Set the status of a specified edge as to whether or not it should be in the graph.
Definition: Graph.h:139
emp::vector< emp::vector< double > > weights
Definition: Graph.h:215
void Set(size_t index, bool value=true)
Update the bit value at the specified index.
Definition: BitVector.h:379
~Node()
Definition: Graph.h:33