http://www.andres.sc/graph.html
Graphs and Graph Algorithms in C++, including Minimum Cost (Lifted) Multicuts