Created
June 14, 2015 15:05
-
-
Save lsem/f26c35f8d713141c4415 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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); | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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)