16 #include "../base/assert.h" 17 #include "../base/vector.h" 31 Node(
size_t num_nodes) : edge_set(num_nodes) { ; }
32 Node(
const Node & in_node) : edge_set(in_node.edge_set) { ; }
39 bool HasEdge(
size_t to)
const {
return edge_set[to]; }
51 void SetEdge(
size_t to,
bool val) { edge_set.
Set(to, val); }
74 Graph(
size_t num_nodes=0) : nodes(num_nodes, num_nodes) { ; }
88 size_t edge_count = 0;
89 for (
size_t i = 0; i < nodes.
size(); i++) edge_count += nodes[i].
GetDegree();
95 nodes.
resize(new_size, new_size);
96 for (
auto & node : nodes) {
97 node.Resize(new_size);
105 return nodes[id].GetEdgeSet();
111 return nodes[id].GetDegree();
117 return nodes[id].GetMaskedDegree(mask);
123 return nodes[from].HasEdge(to);
129 nodes[from].AddEdge(to);
135 nodes[from].RemoveEdge(to);
139 void SetEdge(
size_t from,
size_t to,
bool val) {
141 nodes[from].SetEdge(to, val);
147 return nodes[from].HasEdge(to) && nodes[to].HasEdge(from);
153 nodes[from].AddEdge(to);
154 nodes[to].AddEdge(from);
160 nodes[from].RemoveEdge(to);
161 nodes[to].RemoveEdge(from);
167 nodes[from].SetEdge(to, val);
168 nodes[to].SetEdge(from, val);
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);
180 for (
size_t i = 0; i < in_graph.
GetSize(); i++) {
182 edge_set.
Resize(new_size);
183 edge_set <<= start_size;
184 nodes[start_size + i].AddEdgeSet(edge_set);
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;
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;
219 for (
auto & row : weights) row.
resize(num_nodes, 0.0);
232 for (
auto & row : weights) row.resize(new_size,0.0);
238 return weights[from][to];
242 void AddEdge(
size_t from,
size_t to,
double weight) {
244 weights[from][to] = weight;
250 weights[from][to] = weight;
251 weights[to][from] = weight;
256 const size_t start_size =
nodes.size();
259 for (
auto & row : weights) row.resize(
nodes.size(), 0.0);
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];
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;
276 os << from <<
" " << to <<
" " << weights[from][to] <<
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;
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
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