11 #ifndef EMP_GRAPH_UTILS_H 12 #define EMP_GRAPH_UTILS_H 19 #include "../base/assert.h" 20 #include "../base/vector.h" 31 const size_t N = in_graph.
GetSize();
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] );
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];
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)];
90 const size_t max_edges = v_count * (v_count-1) / 2;
94 emp_assert(e_count <= max_edges, e_count, max_edges);
108 while (e_cur < e_count) {
109 const size_t from = random.
GetUInt(v_count);
110 const size_t to = random.
GetUInt(v_count);
112 if (from == to || graph.
HasEdge(from,to))
continue;
125 const size_t v_count = width * height;
128 Graph graph(v_count);
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)) {
139 if (y != (height-1) && random.
P(prob_use)) {
151 double extra_prob=0.5) {
152 emp_assert(clique_size > 0 && clique_count > 0);
154 const size_t v_count = clique_size * clique_count;
155 Graph graph(v_count);
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++) {
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;
178 if (random.
P(extra_prob)) graph.
AddEdgePair(v_map[node1], v_map[node2]);
193 const size_t max_edges = v_count * (v_count-1) / 2;
199 Graph graph(v_count);
211 for (
size_t i = 1; i < v_count; i++) {
212 size_t from = v_map[i];
213 size_t to = v_map[random.
GetUInt(i)];
214 if (from > to) std::swap(from, to);
222 while (e_cur < e_count) {
223 size_t from = random.
GetUInt(v_count);
224 size_t to = random.
GetUInt(v_count);
226 if (from == to || graph.
HasEdge(from,to))
continue;
227 if (from > to) std::swap(from, to);
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);
260 size_t min_weight,
size_t max_weight,
261 Random & random,
bool connected=
true)
263 const size_t max_edges = v_count * (v_count-1) / 2;
267 emp_assert(e_count <= max_edges, e_count, max_edges);
281 while (e_cur < e_count) {
282 const size_t from = random.
GetUInt(v_count);
283 const size_t to = random.
GetUInt(v_count);
285 if (from == to || graph.
HasEdge(from,to))
continue;
302 size_t n_vert, n_edge;
303 is >> n_vert >> n_edge;
305 Graph out_graph(n_vert);
307 for (
size_t i = 0; i < n_edge; i++) {
309 if (sub1) { from--; to--; }
318 std::ifstream ifile(filename);
328 Graph out_graph(n_vert);
330 for (
size_t i = 0; i < n_vert; i++) {
331 for (
size_t j = 0; j < n_vert; j++) {
333 if (val) out_graph.
AddEdge(i, j);
342 std::ifstream ifile(filename);
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
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