data.zip contains a sample of the data used as input, based on datasets obtained from the 9th [1] and 10th [2] DIMACS Implementation Challenges.

The two source files reconstruct.cpp and reconstruct_ESA.cpp respectively contain implementations for our algorithm and the algorithm introduced by Mathieu & Zhou [3].

To compile, run make

Then, for example, to reconstruct HI.tmp (located in the data directory), run ./reconstruct HI or ./reconstruct_ESA HI

which will store the results in the directories out and out_ESA respectively.

[1] http://www.diag.uniroma1.it/~challenge9/data/tiger

[2] David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner, editors. Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, February 13-14, 2012. Proceedings, volume 588 of Contemporary Mathematics. American Mathematical Society, 2013. doi:10.1090/conm/588.

[3] Claire Mathieu and Hang Zhou. A simple algorithm for graph reconstruction. In 29th Annual European Symposium on Algorithms (ESA 2021), 2021.