Graaf Lib

Graaf is a general-purpose header-only graph library implemented in C++. It is designed as a lightweight alternative to the Boost Graph Library (BGL).

Hacktoberfest
The Graaf project participates in Hacktoberfest 2023. For a step-by-step guide on how to contribute, please take a look at our wiki. Also, feel free to join out Discord in case of any problems, or simply to hang out with other contributors.

About

Using the Graaf library is easy! Specializations are provided for a directed_graph as well as for undirected_graph. To create your first graph:

undirected_graph<int, float> my_graph{};

This creates an undirected graph with integer values on the vertices and float weights on the edges. Graaf is designed with generality in mind. As such, it can be used to store any user-defined vertex and edge class:

struct User {
  std::string name;
  int age;
};

// An edge type can also be unweighted if we don't derive from weighted_edge
struct Connection : public weighted_edge<float> {
  float strength;
  float get_weight() const override { return strength; }
};

undirected_graph<User, Connection> my_graph{};

Implementations for common graph algorithms are provided under the algorithm namespace. Combining this with built-in dot format support allows us to do things like visualizing the shortest path between two vertices:

To get started, take a look at our quickstart guide.

Installation

The most straightforward way to use the Graaf in your project is to include it as a header-only library. Please take a look at the installation guide for alternative installation methods.

Header-Only Library

The Graaf libary can be included as a header-only library. All it requires is a compiler with C++ 20 support.

Download the header-only library from our release page and add the include/graaflib directory to your include path. You can now use Graaf in your source files:

// main.cpp
#include <graaflib/directed_graph>

For more details or alternative installation methods, see the installation guide.

Algorithms

Algorithms implemented in the Graaf library include the following. For more information on individual algorithms please take a look at the docs.

1. Traversal Algorithms:
   • Breadth-First Search (BFS)
   • Depth-First Search (DFS)
2. Shortest Path Algorithms:
   • A* search
   • BFS-Based Shortest Path
   • Dijkstra
   • Bellman-Ford
3. Cycle Detection Algorithms:
   • DFS-Based Cycle Detection
4. Minimum Spanning Tree (MST) Algorithms
   • Kruskal's Algorithm
   • Prim's Algorithm
5. **Strongly Connected Components Algorithms **:
   • Tarjan's Strongly Connected Components
6. Topological Sorting Algorithms:
   • Topological sorting DFS-based
7. Graph Coloring Algorithms:
   • Greedy Graph Coloring

Contributing

The Graaf library welcomes contributions 🎊

If you're interested in improving, fixing bugs, or adding features, please refer to the wiki for guidelines. Check out our roadmap on YouTrack to stay up to date on planned features and improvements. We also have an issue tracker for bug reports and feature requests.

Feel free to join our Discord for assistance and a smooth contribution experience.

Acknowledgements

Special thanks to JetBrains for providing development tools for this project.

License

This project is licensed under the MIT license.