Kruskals_MSP

#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);
}

DSU description taken here: http://e-maxx.ru/algo/dsu

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)