-
-
Save lsem/f26c35f8d713141c4415 to your computer and use it in GitHub Desktop.
#include <cstdio> | |
#include <cstdlib> | |
#include <string> | |
#include <vector> | |
#include <cassert> | |
#include <array> | |
#include "dsu.h" | |
using std::string; | |
#define GRAPH_VERTEX_COUNT 6 | |
struct DSU | |
{ | |
unsigned *parent_indices; | |
unsigned capacity; | |
}; | |
void dsu_init(DSU *dsu, unsigned capacity) | |
{ | |
assert(capacity > 0); | |
assert(dsu->parent_indices == nullptr); | |
dsu->capacity = capacity; | |
dsu->parent_indices = new unsigned[capacity]; | |
for (unsigned i = 0; i != capacity; ++i) | |
dsu->parent_indices[i] = ~(unsigned)0; | |
} | |
void dsu_finalize(DSU *dsu) | |
{ | |
delete[] dsu->parent_indices; | |
} | |
void dsu_make_set(DSU *dsu, int vertex_id) | |
{ | |
assert(dsu->capacity > vertex_id); | |
dsu->parent_indices[vertex_id] = vertex_id; | |
} | |
unsigned dsu_get_leader(DSU *dsu, int vertex_id) | |
{ | |
assert(dsu->capacity > vertex_id); | |
if (dsu->parent_indices[vertex_id] == vertex_id) | |
return vertex_id; | |
return dsu_get_leader(dsu, dsu->parent_indices[vertex_id]); // ask a leader to its parent | |
} | |
// Add (union) vertex vertex_id to vertex_receiver set | |
void dsu_union_set(DSU *dsu, int accumulator_vertex, int vertex_id) | |
{ | |
unsigned accumulator_leader = dsu_get_leader(dsu, accumulator_vertex); | |
unsigned vertex_leader = dsu_get_leader(dsu, vertex_id); | |
if (accumulator_leader != vertex_leader) | |
dsu->parent_indices[accumulator_leader] = vertex_leader; | |
} | |
void dsu_compact_set(DSU *dsu) | |
{ | |
// go trhough all components and connect them | |
for (unsigned index = 0; index != dsu->capacity; ++index) | |
{ | |
dsu->parent_indices[index] = dsu_get_leader(dsu, dsu->parent_indices[index]); | |
} | |
} | |
struct Edge | |
{ | |
unsigned vertex = -1; // end vertex | |
unsigned begin_vertex = -1; | |
int weight = -1; | |
Edge *next_edge = nullptr; | |
}; | |
struct Vertex | |
{ | |
string vertex_name; | |
unsigned rank = 0; | |
Edge *edges = nullptr; | |
}; | |
struct Graph | |
{ | |
Vertex *vertices; | |
unsigned vertices_count; | |
}; | |
namespace Names { | |
static const int A = 0; | |
static const int B = 1; | |
static const int C = 2; | |
static const int D = 3; | |
static const int E = 4; | |
static const int F = 5; | |
}; | |
string get_vertex_name(unsigned vertex_id) | |
{ | |
switch(vertex_id) | |
{ | |
case Names::A: return "A"; | |
case Names::B: return "B"; | |
case Names::C: return "C"; | |
case Names::D: return "D"; | |
case Names::E: return "E"; | |
case Names::F: return "F"; | |
} | |
return "<>"; | |
} | |
bool are_vertices_connected(Graph *graph, unsigned vertex_a, unsigned vertex_b, bool check_reverse=false) | |
{ | |
Edge *current = graph->vertices[vertex_a].edges; | |
for ( ; current != nullptr; current = current->next_edge) | |
{ | |
if (current->vertex == vertex_b) | |
{ | |
if (check_reverse) | |
{ | |
assert(are_vertices_connected(graph, vertex_b, vertex_a, false)); | |
} | |
return true; | |
} | |
} | |
return false; | |
} | |
void connect_vertex(Graph *graph, unsigned a, unsigned b, int weight, bool directed=false) | |
{ | |
if (are_vertices_connected(graph, a, b, true)) | |
return; | |
auto t = graph->vertices[a].edges; | |
graph->vertices[a].edges = new Edge(); | |
graph->vertices[a].edges->next_edge = t; | |
graph->vertices[a].edges->weight = weight; | |
graph->vertices[a].edges->vertex = b; | |
graph->vertices[a].edges->begin_vertex = a; | |
graph->vertices[a].rank++; | |
if (!directed) | |
connect_vertex(graph, b, a, weight, /*directed*/true); | |
} | |
void init_graph(Graph **graph, bool directed=false) | |
{ | |
//a | |
*graph = new Graph {}; | |
(*graph)->vertices_count = GRAPH_VERTEX_COUNT; | |
(*graph)->vertices = new Vertex[GRAPH_VERTEX_COUNT]; | |
// A | |
connect_vertex(*graph, Names::A, Names::B, 1); | |
connect_vertex(*graph, Names::A, Names::E, 3); | |
connect_vertex(*graph, Names::A, Names::D, 4); | |
// B | |
connect_vertex(*graph, Names::B, Names::A, 1); | |
connect_vertex(*graph, Names::B, Names::D, 4); | |
connect_vertex(*graph, Names::B, Names::E, 2); | |
// C | |
connect_vertex(*graph, Names::C, Names::E, 4); | |
connect_vertex(*graph, Names::C, Names::F, 5); | |
// D | |
connect_vertex(*graph, Names::D, Names::A, 4); | |
connect_vertex(*graph, Names::D, Names::B, 4); | |
connect_vertex(*graph, Names::D, Names::E, 4); | |
// E | |
connect_vertex(*graph, Names::E, Names::A, 3); | |
connect_vertex(*graph, Names::E, Names::B, 2); | |
connect_vertex(*graph, Names::E, Names::C, 4); | |
connect_vertex(*graph, Names::E, Names::D, 4); | |
connect_vertex(*graph, Names::E, Names::F, 7); | |
} | |
void free_graph(Graph **graph) | |
{ | |
delete[] (*graph)->vertices; | |
delete *graph; | |
*graph = nullptr; | |
} | |
void print_edges_list(Edge *head) | |
{ | |
Edge *current = head; | |
while (current != nullptr) | |
{ | |
printf("%s -> %s (%d)\n",get_vertex_name(current->begin_vertex).c_str(), | |
get_vertex_name(current->vertex).c_str(), | |
current->weight); | |
current = current->next_edge; | |
} | |
std::printf("\n"); | |
} | |
Edge *edges_list_merge(Edge *left, Edge *right) | |
{ | |
Edge dummyHead; | |
Edge *current = &dummyHead; | |
Edge *l = left, *r = right; | |
while (l != nullptr && r != nullptr) | |
{ | |
if (l->weight < r->weight) | |
{ | |
current->next_edge = l; | |
l = l->next_edge; | |
} | |
else | |
{ | |
current->next_edge = r; | |
r = r->next_edge; | |
} | |
current = current->next_edge ; | |
} | |
current->next_edge = l == nullptr? r : l; | |
return dummyHead.next_edge; | |
} | |
bool is_sorted(Edge *edges) | |
{ | |
for (auto *current = edges; current != nullptr; current = current->next_edge) | |
if (current->next_edge && current->weight > current->next_edge->weight) | |
return false; | |
return true; | |
} | |
Edge *edges_list_merge_sort(Edge *edges, unsigned edges_count) | |
{ | |
if (edges_count < 2) | |
return edges; // nothing to sort | |
// 1. partition | |
unsigned middle_index = edges_count / 2; | |
Edge *left_list, *right_list, *middle_node; | |
middle_node = edges; | |
for (unsigned node_index = 0; node_index != (middle_index - 1); ++node_index) | |
middle_node = middle_node->next_edge; | |
left_list = edges; | |
right_list = middle_node->next_edge; | |
middle_node->next_edge = nullptr; | |
// std::printf("left list (%d size):\n", middle_index); print_edges_list(left_list); | |
// std::printf("right list (%d size):\n", edges_count - middle_index); print_edges_list(right_list); | |
auto *left_sorted = edges_list_merge_sort(left_list, middle_index); assert(is_sorted(left_sorted)); | |
auto *right_sorted = edges_list_merge_sort(right_list, edges_count - middle_index); assert(is_sorted(right_sorted)); | |
return edges_list_merge(left_sorted, right_sorted); | |
} | |
void free_edges_list(Edge *edge) | |
{ | |
auto *current = edge; | |
while (current != nullptr) | |
{ | |
auto *t = current->next_edge; | |
delete current; | |
current = t; | |
} | |
} | |
Edge *duplicate_and_append(Edge *original, Edge *list_tail) | |
{ | |
auto *edge_copy = new Edge{}; | |
edge_copy->weight = original->weight; | |
edge_copy->next_edge = nullptr; | |
edge_copy->vertex = original->vertex; | |
edge_copy->begin_vertex = original->begin_vertex; | |
list_tail->next_edge = edge_copy; | |
return edge_copy; | |
} | |
void build_graph_edges_visit_list(Graph *graph, Edge **list) | |
{ | |
Edge all_adges; | |
all_adges.next_edge = nullptr; | |
// Merge all edges list to single list | |
// O(E) | |
Edge *current_edge = &all_adges; | |
unsigned total_count = 0; | |
for (unsigned vertex_index = 0; vertex_index != graph->vertices_count; ++vertex_index) | |
{ | |
Vertex *vertex = &(graph->vertices[vertex_index]); | |
for (auto *edge = vertex->edges; edge != nullptr; edge = edge->next_edge) | |
{ | |
current_edge = duplicate_and_append(edge, current_edge); | |
++total_count; | |
} | |
} | |
auto *merged_sorted = edges_list_merge_sort(all_adges.next_edge, total_count); | |
*list = merged_sorted; | |
} | |
void find_msp(Graph *graph) | |
{ | |
// printf("All edges merged\n"); print_edges_list(all_adges.next_edge); | |
Edge *visit_list; | |
build_graph_edges_visit_list(graph, &visit_list); | |
printf("%s\n", "Visiting order"); | |
print_edges_list(visit_list); | |
DSU dsu; // disjoin set union | |
dsu.parent_indices = nullptr; | |
dsu_init(&dsu, GRAPH_VERTEX_COUNT); | |
// add all vertices to dsu | |
for (unsigned vertex_index = 0; vertex_index != graph->vertices_count; ++vertex_index) | |
{ | |
dsu_make_set(&dsu, vertex_index); | |
} | |
const unsigned first_vertex = visit_list->vertex; | |
Edge msp_root; | |
Edge *current_msp_edge = &msp_root; | |
for (Edge *current = visit_list; current != nullptr; current = current->next_edge) | |
{ | |
const unsigned this_edge_weight = current->weight; | |
const unsigned this_edge_vertex = current->vertex; | |
const unsigned this_edge_begin_vertex = current->begin_vertex; | |
// Check whether this edge make cycles by quering leader of this vertex, | |
// if it has leader the same as current | |
const unsigned edge_vertex_leader = dsu_get_leader(&dsu, this_edge_vertex); | |
const unsigned first_vertex_leader = dsu_get_leader(&dsu, first_vertex); | |
if (first_vertex_leader == edge_vertex_leader) | |
{ | |
// already in set, discard this edge | |
std::printf("%15s [%s -> %s] of weight %d\n", "discarded edge", | |
get_vertex_name(this_edge_begin_vertex).c_str(), | |
get_vertex_name(this_edge_vertex).c_str(), | |
this_edge_weight); | |
} | |
else | |
{ | |
// independent vertex, add to MSP | |
current_msp_edge = duplicate_and_append(current, current_msp_edge); | |
std::printf("%15s [%s -> %s] of weight %d\n", "taken edge", | |
get_vertex_name(this_edge_begin_vertex).c_str(), | |
get_vertex_name(this_edge_vertex).c_str(), | |
this_edge_weight); | |
// add new vertex to DSU | |
dsu_union_set(&dsu, this_edge_begin_vertex, edge_vertex_leader); | |
} | |
} | |
printf("msp is:\n"); print_edges_list(msp_root.next_edge); | |
dsu_finalize(&dsu); | |
free_edges_list(visit_list); | |
} | |
int main() | |
{ | |
Graph *graph; | |
init_graph(&graph); | |
find_msp(graph); | |
free_graph(&graph); | |
} | |
Output example:
Visiting order:
B -> A (1)
A -> B (1)
E -> B (2)
B -> E (2)
E -> A (3)
A -> E (3)
E -> C (4)
E -> D (4)
D -> A (4)
D -> B (4)
D -> E (4)
C -> E (4)
B -> D (4)
A -> D (4)
F -> C (5)
C -> F (5)
F -> E (7)
E -> F (7)
discarded edge [B -> A] of weight 1
taken edge [A -> B] of weight 1
discarded edge [E -> B] of weight 2
taken edge [B -> E] of weight 2
discarded edge [E -> A] of weight 3
discarded edge [A -> E] of weight 3
taken edge [E -> C] of weight 4
taken edge [E -> D] of weight 4
discarded edge [D -> A] of weight 4
discarded edge [D -> B] of weight 4
discarded edge [D -> E] of weight 4
discarded edge [C -> E] of weight 4
discarded edge [B -> D] of weight 4
discarded edge [A -> D] of weight 4
discarded edge [F -> C] of weight 5
taken edge [C -> F] of weight 5
discarded edge [F -> E] of weight 7
discarded edge [E -> F] of weight 7
msp is:
A -> B (1)
B -> E (2)
E -> C (4)
E -> D (4)
C -> F (5)
DSU description taken here: http://e-maxx.ru/algo/dsu