Empirical
graph_utils.h
Go to the documentation of this file.
1 
11 #ifndef EMP_GRAPH_UTILS_H
12 #define EMP_GRAPH_UTILS_H
13 
14 #include <fstream>
15 #include <iostream>
16 #include <string>
17 #include <tuple>
18 
19 #include "../base/assert.h"
20 #include "../base/vector.h"
21 
22 #include "Graph.h"
23 #include "Random.h"
24 #include "random_utils.h"
25 
26 namespace emp {
27 
30  Graph shuffle_graph(const Graph & in_graph, Random & random) {
31  const size_t N = in_graph.GetSize();
32  Graph out_graph(N);
33 
34  // Determine new vertex IDs
35  emp::vector<size_t> v_map = BuildRange<size_t>(0, N);
36  Shuffle(random, v_map);
37 
38  // Put the mapped edges into the new graph.
39  for (size_t from = 0; from < N; from++) {
40  for (size_t to = 0; to < N; to++) {
41  if (in_graph.HasEdge(from, to)) {
42  out_graph.AddEdge( v_map[from], v_map[to] );
43  }
44  }
45  }
46 
47  return out_graph;
48  }
49 
51  Graph build_graph_ring(size_t v_count, Random & random) {
52  Graph graph(v_count);
53 
54  emp::vector<size_t> v_map = BuildRange<size_t>(0, v_count);
55  Shuffle(random, v_map);
56 
57  for (size_t i = 1; i < v_count; i++) {
58  const size_t from = v_map[i];
59  const size_t to = v_map[i-1];
60  graph.AddEdgePair(from, to);
61  }
62 
63  graph.AddEdgePair(v_map[0], v_map[v_count-1]);
64 
65  return graph;
66  }
67 
70  Graph build_graph_tree(size_t v_count, Random & random) {
71  Graph graph(v_count);
72 
73  emp::vector<size_t> v_map = BuildRange<size_t>(0, v_count);
74  Shuffle(random, v_map);
75 
76  for (size_t i = 1; i < v_count; i++) {
77  const size_t from = v_map[i];
78  const size_t to = v_map[random.GetUInt(i)];
79  graph.AddEdgePair(from, to);
80  }
81 
82  return graph;
83  }
84 
88  Graph build_graph_random(size_t v_count, size_t e_count, Random & random, bool connected=true)
89  {
90  const size_t max_edges = v_count * (v_count-1) / 2;
91  (void) max_edges;
92 
93  emp_assert(v_count >= 2 && e_count > 0); // We need at least two vertices to support an edge.
94  emp_assert(e_count <= max_edges, e_count, max_edges); // Shouldn't have more edges than can fit!
95 
96  Graph graph(v_count);
97  size_t e_cur = 0; // How many edges have we added?
98 
99  // If the graph should be connected, start by building a tree.
100  if (connected) {
101  emp_assert(e_count >= v_count - 1); // We need enough edges to build a connected graph.
102  graph = build_graph_tree(v_count, random);
103  e_cur = v_count - 1;
104  }
105 
106  // @CAO -- we should do something better if we are filling in most of the edges.
107 
108  while (e_cur < e_count) {
109  const size_t from = random.GetUInt(v_count);
110  const size_t to = random.GetUInt(v_count);
111 
112  if (from == to || graph.HasEdge(from,to)) continue;
113 
114  graph.AddEdgePair(from, to);
115  ++e_cur;
116  }
117 
118  return graph;
119  }
120 
122  Graph build_graph_grid(size_t width, size_t height, Random & random, double prob_use=1.0) {
123  emp_assert(width > 0 && height > 0);
124 
125  const size_t v_count = width * height;
126  // const size_t e_count = (width-1)*height + width*(height-1);
127 
128  Graph graph(v_count);
129 
130  emp::vector<size_t> v_map = BuildRange<size_t>(0, v_count);
131  Shuffle(random, v_map);
132 
133  for (size_t x=0; x < width; ++x) {
134  for (size_t y=0; y < height; ++y) {
135  const size_t from = y*width + x;
136  if (x != (width-1) && random.P(prob_use)) {
137  graph.AddEdgePair(v_map[from], v_map[from+1]); // Horizontal
138  }
139  if (y != (height-1) && random.P(prob_use)) {
140  graph.AddEdgePair(v_map[from], v_map[from+width]); // Vertical
141  }
142  }
143  }
144 
145  return graph;
146  }
147 
150  Graph build_graph_clique_set(size_t clique_size, size_t clique_count, Random & random,
151  double extra_prob=0.5) {
152  emp_assert(clique_size > 0 && clique_count > 0);
153 
154  const size_t v_count = clique_size * clique_count;
155  Graph graph(v_count);
156 
157  emp::vector<size_t> v_map = BuildRange<size_t>(0, v_count);
158  Shuffle(random, v_map);
159 
160  // Fill out all of the edges within a clique
161  for (size_t start_id = 0; start_id < v_count; start_id += clique_size) {
162  const size_t end_id = start_id + clique_size;
163  for (size_t node1 = start_id; node1 < end_id; node1++) {
164  for (size_t node2 = node1+1; node2 < end_id; node2++) {
165  graph.AddEdgePair(v_map[node1], v_map[node2]);
166  }
167  }
168  }
169 
170  // Add on extra edges.
171  for (size_t start1 = 0; start1 < v_count; start1 += clique_size) {
172  const size_t end1 = start1 + clique_size;
173  for (size_t start2 = start1+clique_size; start2 < v_count; start2 += clique_size) {
174  const size_t end2 = start2 + clique_size;
175  for (size_t node1 = start1; node1 < end1; node1++) {
176  for (size_t node2 = start2; node2< end2; node2++) {
177  if (node1 == start1 && node2 == start2) continue; // Both part of IS.
178  if (random.P(extra_prob)) graph.AddEdgePair(v_map[node1], v_map[node2]);
179  }
180  }
181  }
182  }
183 
184  return graph;
185  }
186 
187 
191  Graph build_graph_dag(size_t v_count, size_t e_count, Random & random, bool connected=true)
192  {
193  const size_t max_edges = v_count * (v_count-1) / 2;
194  (void) max_edges;
195 
196  emp_assert(v_count >= 2 && e_count > 0); // We need at least two vertices to support an edge.
197  emp_assert(e_count <= max_edges); // Shouldn't have more edges than can fit!
198 
199  Graph graph(v_count); //
200  size_t e_cur = 0; // How many edges have we added?
201 
202  // If the graph should be connected, start by building a tree.
203  if (connected) {
204  emp_assert(e_count >= v_count - 1); // We need enough edges to build a connected graph.
205 
206  // Determine order to connect in new vertices.
207  emp::vector<size_t> v_map = BuildRange<size_t>(0, v_count);
208  Shuffle(random, v_map);
209 
210  // Connect in each vertex to the tree.
211  for (size_t i = 1; i < v_count; i++) {
212  size_t from = v_map[i]; // Pick the next node in the shuffle.
213  size_t to = v_map[random.GetUInt(i)]; // Pick node already in the tree.
214  if (from > to) std::swap(from, to); // Make sure lower number is first.
215  graph.AddEdge(from, to);
216  }
217  e_cur = v_count - 1;
218  }
219 
220  // @CAO -- we should do something better if we are filling in most of the edges.
221 
222  while (e_cur < e_count) {
223  size_t from = random.GetUInt(v_count);
224  size_t to = random.GetUInt(v_count);
225 
226  if (from == to || graph.HasEdge(from,to)) continue;
227  if (from > to) std::swap(from, to); // Make sure lower number is first.
228 
229  graph.AddEdge(from, to);
230  ++e_cur;
231  }
232 
233  // Make sure the edge ID numbers that we return are not all in order.
234  return shuffle_graph(graph, random);
235  }
236 
239  WeightedGraph build_weighted_graph_tree(size_t v_count, size_t min_weight, size_t max_weight,
240  Random & random) {
241  WeightedGraph graph(v_count);
242 
243  emp::vector<size_t> v_map = BuildRange<size_t>(0, v_count);
244  Shuffle(random, v_map);
245 
246  for (size_t i = 1; i < v_count; i++) {
247  const size_t from = v_map[i];
248  const size_t to = v_map[random.GetUInt(i)];
249  const size_t weight = (size_t) random.GetDouble(min_weight, max_weight);
250  graph.AddEdgePair(from, to, weight);
251  }
252 
253  return graph;
254  }
255 
259  WeightedGraph build_weighted_graph_random(size_t v_count, size_t e_count,
260  size_t min_weight, size_t max_weight,
261  Random & random, bool connected=true)
262  {
263  const size_t max_edges = v_count * (v_count-1) / 2;
264  (void) max_edges;
265 
266  emp_assert(v_count >= 2 && e_count > 0); // We need at least two vertices to support an edge.
267  emp_assert(e_count <= max_edges, e_count, max_edges); // Shouldn't have more edges than can fit!
268 
269  WeightedGraph graph(v_count);
270  size_t e_cur = 0; // How many edges have we added?
271 
272  // If the graph should be connected, start by building a tree.
273  if (connected) {
274  emp_assert(e_count >= v_count - 1); // We need enough edges to build a connected graph.
275  graph = build_weighted_graph_tree(v_count, min_weight, max_weight, random);
276  e_cur = v_count - 1;
277  }
278 
279  // @CAO -- we should do something better if we are filling in most of the edges.
280 
281  while (e_cur < e_count) {
282  const size_t from = random.GetUInt(v_count);
283  const size_t to = random.GetUInt(v_count);
284 
285  if (from == to || graph.HasEdge(from,to)) continue;
286 
287  graph.AddEdgePair(from, to, (size_t) random.GetDouble(min_weight, max_weight));
288  ++e_cur;
289  }
290 
291  return graph;
292  }
293 
294 
295 
296 
297 
300  // @CAO Need some error checking here...
301  Graph load_graph_sym(std::istream & is, bool sub1=false) {
302  size_t n_vert, n_edge;
303  is >> n_vert >> n_edge;
304 
305  Graph out_graph(n_vert);
306  size_t from, to;
307  for (size_t i = 0; i < n_edge; i++) {
308  is >> from >> to;
309  if (sub1) { from--; to--; }
310  out_graph.AddEdgePair(from, to);
311  }
312 
313  return out_graph;
314  }
315 
317  Graph load_graph_sym(std::string filename, bool sub1=false) {
318  std::ifstream ifile(filename);
319  return load_graph_sym(ifile, sub1);
320  }
321 
324  Graph load_graph_table(std::istream & is) {
325  size_t n_vert;
326  is >> n_vert;
327 
328  Graph out_graph(n_vert);
329  size_t val;
330  for (size_t i = 0; i < n_vert; i++) {
331  for (size_t j = 0; j < n_vert; j++) {
332  is >> val;
333  if (val) out_graph.AddEdge(i, j);
334  }
335  }
336 
337  return out_graph;
338  }
339 
341  Graph load_graph_table(std::string filename) {
342  std::ifstream ifile(filename);
343  return load_graph_table(ifile);
344  }
345 }
346 
347 #endif
Graph load_graph_table(std::istream &is)
Definition: graph_utils.h:324
void AddEdge(size_t from, size_t to)
Add a specified edge into this graph.
Definition: Graph.h:127
Helper functions for emp::Random for common random tasks.
void Shuffle(Random &random, emp::vector< T > &v, size_t max_count)
Definition: random_utils.h:25
A versatile and non-patterned pseudo-random-number generator (Mersenne Twister).
Definition: ce_random.h:52
void AddEdgePair(size_t from, size_t to, double weight)
When Adding an edge pair, must also provide a weight.
Definition: Graph.h:248
Graph build_graph_clique_set(size_t clique_size, size_t clique_count, Random &random, double extra_prob=0.5)
Definition: graph_utils.h:150
Definition: Graph.h:213
Graph build_graph_random(size_t v_count, size_t e_count, Random &random, bool connected=true)
Definition: graph_utils.h:88
Graph build_graph_tree(size_t v_count, Random &random)
Definition: graph_utils.h:70
Graph load_graph_sym(std::istream &is, bool sub1=false)
Definition: graph_utils.h:301
constexpr uint32_t GetUInt(const uint32_t max)
Definition: ce_random.h:191
Graph build_graph_ring(size_t v_count, Random &random)
Construct a graph where all vertics are degree two and form a single ring.
Definition: graph_utils.h:51
Graph build_graph_grid(size_t width, size_t height, Random &random, double prob_use=1.0)
Construct a graph with width x height vertices setup into a grid structure.
Definition: graph_utils.h:122
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
constexpr double GetDouble()
Definition: ce_random.h:166
A versatile and non-patterned pseudo-random-number generator.
A graph class that maintains a set of vertices (nodes) and edges (connecting pairs of nodes) ...
Definition: Graph.h:24
WeightedGraph build_weighted_graph_random(size_t v_count, size_t e_count, size_t min_weight, size_t max_weight, Random &random, bool connected=true)
Definition: graph_utils.h:259
A simple, fast class for managing verticies (nodes) and edges.
bool HasEdge(size_t from, size_t to) const
Determine if a specific edge is included in this graph.
Definition: Graph.h:121
WeightedGraph build_weighted_graph_tree(size_t v_count, size_t min_weight, size_t max_weight, Random &random)
Definition: graph_utils.h:239
If we are in emscripten, make sure to include the header.
Definition: array.h:37
#define emp_assert(...)
Definition: assert.h:199
Graph build_graph_dag(size_t v_count, size_t e_count, Random &random, bool connected=true)
Definition: graph_utils.h:191
constexpr bool P(const double _p)
Definition: ce_random.h:216
Graph shuffle_graph(const Graph &in_graph, Random &random)
Definition: graph_utils.h:30