About

Graph is an abstract data type that is widely used in computer science. It is a collection of vertices (nodes) and edges that connect these vertices. Graphs are used to model many real-world problems, such as social networks, road networks, and computer networks. As such, graph algorithms are used in many applications, including route planning, network analysis, and data mining.

Graaf: A Lightweight, Header-Only C++20 Graph Library

Key Features:

• Header-only: No separate compilation or linking required.
• Generality: Supports user-defined vertex and edge classes.
• Algorithm Support: Provides a range of graph algorithms.

Purpose: Graaf is designed with the goal of simplifying graph-related tasks. It offers a lightweight alternative to the Boost Graph Library (BGL) and is built for simplicity and extensibility. With Graaf, you can easily create, manipulate, and analyze graphs, making it suitable for a wide range of applications.

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.

How to use Graaf

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.

Algorithms

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

1. Cycle Detection Algorithms:
   • DFS-Based Cycle Detection
2. Graph Coloring Algorithms:
   • Greedy Graph Coloring
   • [Welsh-Powell Algorithm]
3. Minimum Spanning Tree (MST) Algorithms
   • Kruskal's Algorithm
   • Prim's Algorithm
4. Shortest Path Algorithms:
   • A* search
   • Bellman-Ford Shortest Path
   • BFS-Based Shortest Path
   • Dijkstra Shortest Path
   • Floyd-Warshall Algorithm
5. Strongly Connected Components Algorithms:
   • Tarjan's Strongly Connected Components
   • Kosaraju's Strongly Connected Components
6. Topological Sorting Algorithms:
7. Traversal Algorithms:
   • Breadth-First Search (BFS)
   • Depth-First Search (DFS)
8. Clique Detection
   • Bron-Kerbosch

Contributing

The Graaf library welcomes contributions 🎊

If you're interested in improving, fixing bugs, or adding features, please refer to the wiki for guidelines and have your development environment set up before you start. 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.

Contributors

Acknowledgements

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

License

This project is licensed under the MIT license.