A brief introduction to rucgraph

I am maintaining an open-source, easy-to-use library of cpp header files: rucgraph, which is mainly designed for performing graph computing tasks. Welcome to joining the development of rucgraph by pulling requests on github!

rucgraph contains different types of adjacency lists to represent a graph, including a simple adjacency list built using vectors, as well as a complex adjacency list built using a “dynamic” mixup of vectors and hashes. It is easy to use these adjacency lists. For example, the following codes first build a graph with 5 vertices and 2 edges, and then find and print 3 components of this graph.

graph_v_of_v_idealID g(5); // a graph with 5 vertices: 0, 1, 2, 3, 4
graph_v_of_v_idealID_add_edge(g, 0, 1, 0.3); // add edge (0,1) with the weight of 0.3 
graph_v_of_v_idealID_add_edge(g, 3, 4, 0.5); // add edge (3,4) with the weight of 0.5
auto cpns = graph_v_of_v_idealID_connected_components(g); // find the connected components of g
for (auto it = cpns.begin(); it != cpns.end(); it++) 
{
	print_a_sequence_of_elements(*it);
}
	
/*
Printing results:
0 1 // 1st component
2   // 2nd component
3 4 // 3rd component
*/

Highlights

A Pairing Heap that can change all keys in O(1) time

rucgraph contains an augmented Pairing Heap that can change all keys in O(1) time! It achieves this by associating an offset value with each node in the heap. To use this heap, include the following header file in your codes.

#include <data_structures/PairingHeapYS_with_offset.h>