bobluppes / graaf

A general-purpose lightweight C++ graph library

Graaf Library

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).

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.

graaf's Issues

Remove usage of fmt in library

In order for clients to include the library header-only, we should not have any external dependencies. As such, I would like to remove the usage of fmt in the library. We can keep it in the tests and examples.

Ideally we would replace it by std::format, but I remember GCC and Clang having some issues with their implementations in the std.

The goal of this issue is to investigate whether we can use std::format instead of fmt, and replace it if possible. If this is not (yet) possible, we should do the string concatenation manually.

[ALGO] A Star Search

A Star Search

The A Star algorithm (or A*) is an informed search algorithm which finds the shortest path between a start vertex and a target vertex. The search is guided by a heuristic, which prioritizes the traversal order of the candidate paths.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds the shortest path between a start_vertex and target_vertex
 *        using the A* search algorithm.
 *
 * @param graph The graph to search in.
 * @param start_vertex The starting vertex for the search.
 * @param target_vertex The target vertex to reach.
 * @param heuristic A heuristic function estimating the cost from a vertex to the target.
 * @return An optional containing the shortest path if found, or std::nullopt if no path exists.
 */
template <typename V, typename E, graph_type T, typename HEURISTIC_T, typename WEIGHT_T = decltype(get_weight(std::declval<E>()))>
  requires std::is_invocable_r_v<WEIGHT_T, HEURISTIC_T&, vertex_id_t>
std::optional<graph_path<WEIGHT_T>> a_star_search(
    const graph<V, E, T> &graph, vertex_id_t start_vertex, vertex_id_t target_vertex,
    const HEURISTIC_T &heuristic);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/shortest_path.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/shortest_path_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

Installation guide is inconsistent

The installation guide in the readme and the one in the user documentation is different. We should unify these to avoid confusion. Furthermore we should check to see if the installation steps still work and update the guide where necessary.

Add minimum spanning tree algorithm

It would be nice to add an algorithm to compute the minimum spanning tree of a graph. Two possible implementations here are Prim's algorithm and Kruskal's algorithm. Both implementations are valid candidates and could be added under this issue:

• Prim's algorithm (@derekjtong)
• Kruskal's algorithm (#22)

The implementation should go under src/graaflib/algorithm/minimum_spanning_tree.h. Each implementation should be covered with unit tests and should have it's public interface documented with javadoc-style comments.

[BENCH] Benchmark DFS cycle detection

Benchmark DFS cycle detection

The goal of this issues is to add a benchmark for the DFS cycle detection algorithm. The algorithm implementation is located under include/graaflib/algorithm/cycle_detection/dfs_cycle_detection.h. Benchmarks are vital to our library and allow us to measure the impact of future performance improvements.

We use the Google benchmark framework. For inspiration, please take a look at the existing benchmarks in /perf.

The benchmark should be added under /perf in a directory which resembles the file structure of the original algorithm. i.e. if the algorithm is implemented in include/graaflib/algorithm/coloring/greedy_graph_coloring.h then the benchmark should be added to perf/graaflib/algorithm/coloring/greedy_graph_coloring_benchmark.cpp.

The benchmark should measure the runtime performance of the algorithm for increasing input sizes.

Running Benchmarks

If you IDE has the necessary integrations for it, all benchmarks can be run in the IDE from the perf/graaflib/benchmark.cpp file.

Otherwise, we can run the benchmarks from the command line:

# run all benchmarks
cd build/perf && ./Graaf_perf

To run an individual benchmark:

./Graaf_perf --benchmark_filter=YOUR_BENCHMARK_NAME

For more options, pass the --help flag.

Definition of Done

• A benchmark is added for the algorithm
• Benchmark results (copy past of the output is fine) is added to the PR

Improve documentation

This is an open-ended ticket and we welcome multiple PRs.

In general, it would be nice to go over our documentation in the following locations:

• README.md
• In-code documentation on:
  • The core data structures in include/graaflib/graph.h, include/graaflib/edge.h, and include/graaflib/types.h
  • The algorithms in include/graaflib/algorithm/**/*.h
• The user-facing algorithm documentation in docs/docs/algorithms/**/*.md. This documentation can also be viewed here.

In particular it would be great if we can fix any spelling/grammar issues, as well as clarify anything which might be unclear to you on the documentation.

[DOCS] Document Depth First Search (DFS)

Documentation Depth First Search (DFS)

The goal of this issue if the improve the documentation of an existing algorithm. This documentation should go into the algorithms section of our docusaurus docs.

More detail on how to build the documentation locally can be found on the wiki.

An existing documentation page exists, which should be extended. The page can be found under docs/docs/algorithms/traversal/depth-first-search.md.

The corresponding algorithm is called depth_first_traverse and can be found under include/graaflib/algorithm/graph_traversal.h.

Documentation Contents

The documentation entry should adhere to the following template:

# [ALGORITHM_NAME]
- A short description of the algorithm, what does it do and in which use cases is it used.
- What are the limitations of the algorithm, does it work on both directed and undirected graphs? Does it consider edge weights, and if yes, does it support negative weights?
- Link to the wikipedia entry on the algorithm.

## Syntax
- A code block with the syntax of the algorithm. This should now include any javadoc comments.
- An explanation of the parameters (including template parameters) and the return type.

## (Optional) See also
- If there are similar algorithms, or we have a slightly different version of the same algorithm, you can link it here.
- If we have an example (found on the example page of the docs) which uses this algorithm, you can link it here.

Fix formatting in README

The project's README.md contains an overview of all currently implemented algorithms. The fifth item in this list ("Strongly Connected Component Algorithms") is not correctly formatted, resulting in preceding and succeeding **. This is probably due to an extra newline character in the markdown file.

The goal of this issue if to fix the formatting of the entry. Current:

5. **Strongly Connected Components Algorithms
   **:
   • Tarjan's Strongly Connected Components

Expected:

5. Strongly Connected Components Algorithms:
   • Tarjan's Strongly Connected Components

While we are at it, let's also change the order of the algorithm categories such that they are in alphabetical order.

[BUG] Graph coloring unstable for directed graphs

Issue

While investigating the failing tests of #118, I noticed a more fundamental issue that breaks both this PRs tests as well as the greedy graph coloring introduced in #94:
For directed graphs, the tests only succeed if the vertices are added in a certain order, i.e. the reversed order they are subsequently iterated over.

Steps to reproduce

In the BasicGraphColoring test in greedy_graph_coloring_test.cpp, reverse the order in which the nodes are added:

  const auto vertex_3{graph.add_vertex(30)};
  const auto vertex_2{graph.add_vertex(20)};
  const auto vertex_1{graph.add_vertex(10)};

This will fail the test.

Root Cause

Both the greedy graph coloring and the Welsh-Powell iterate over the neighbors and increment the color if the neighbor is already colored in the same color:

  // Iterate through each vertex
  for (const auto& [current_vertex_id, _] : vertices) {
    // Iterate through neighboring vertices
    // Find the smallest available color for the current vertex
    int available_color{0};
    for (const auto neighbor_id : graph.get_neighbors(current_vertex_id)) {
      if (coloring.contains(neighbor_id)) {
        const auto neighbor_color{coloring.at(neighbor_id)};
        if (neighbor_color >= available_color) {
          available_color = neighbor_color + 1;
        }
      }
    }

However, for directed graphs, get_neighbors will only return the succeeding vertices.
For the following directed graph, the coloring will be successful if the nodes are visited in the order C-B-A, and fails otherwise. The order of the iteration depends on the order the vertices are added to the graph, thus the algorithm is unstable.

flowchart LR
    A --> B
    B --> C

Fix Ideas

get_neighbors accesses adjacency_list_ that does not have predecessor vertices for directed graphs. We could think of extending it by this and provide something like get_predecessors for directed graphs. Well-knowing this will have impact on memory consumption of directed graphs, there might be more elegant solutions. Curious what you guys think @bobluppes @ndcroos 🤔

Extract common test fixtures

We use the GoogleTest framework for our unit tests. Since the Graaf library supports arbitrary vertex and edge types, we make use of TYPED_TEST_SUITEs to run our tests for different types of graph instances (i.e. directed_graph<int, int>, directed_graph<long, std::string>, ...).

Currently, most tests redefine the same fixtures over and over. For instance, consider dijkstra_shortest_path_test.cpp and a_star_test.cpp, which both define two sets of types (weighted_graph_types and weighted_graph_signed_types) in their anonymous namespace.

The goal of this issue is to extract these types and fixture definitions to a separate file test/utils/fixtures.h. This should make it easier to write tests in the future, as we can simply reuse the existing fixtures.

I would give all test files a once over to identify the fixtures we can extract, but in general I think all fixtures can be consolidated into either a fixture containing unsigned edge weights or a fixture containing signed edge weights.

More info on gtest's TYPED_TEST_SUITE can be found here.

[DOCS] Document DFS Based Cycle Detection

Documentation DFS Based Cycle Detection

The goal of this issue if the improve the documentation of an existing algorithm. This documentation should go into the algorithms section of our docusaurus docs.

More detail on how to build the documentation locally can be found on the wiki.

An existing documentation page exists, which should be extended. The page can be found under docs/docs/algorithms/cycle-detection/dfs-based.md.

The corresponding algorithm is called dfs_cycle_detection and can be found under include/graaflib/algorithm/cycle_detection.h. There are two versions of the algorithm, one for directed graphs and one for undirected graphs. Both should be documented on the same page, where we list both available syntaxes.

Documentation Contents

The documentation entry should adhere to the following template:

# [ALGORITHM_NAME]
- A short description of the algorithm, what does it do and in which use cases is it used.
- What are the limitations of the algorithm, does it work on both directed and undirected graphs? Does it consider edge weights, and if yes, does it support negative weights?
- Link to the wikipedia entry on the algorithm.

## Syntax
- A code block with the syntax of the algorithm. This should now include any javadoc comments.
- An explanation of the parameters (including template parameters) and the return type.

## (Optional) See also
- If there are similar algorithms, or we have a slightly different version of the same algorithm, you can link it here.
- If we have an example (found on the example page of the docs) which uses this algorithm, you can link it here.

Add serialization

I would like to add support for writing graphs to files. At first, I would focus on the following formats:

• dot (handled by @bobluppes)
• graphml
• json (handled by @misarb)

Each of these could be implemented as a free function. Implementations should go under src/graaflib/io.

Improve test coverage

I would like to increase the coverage of our unit tests.

A coverage report can be found here.

[BENCH] Benchmark Welsh-Powell Algorithm

Benchmark Welsh-Powell

The goal of this issues is to add a benchmark for the Welsh-Powell algorithm. The algorithm implementation is located under include/graaflib/algorithm/coloring/welsh_powell.h. Benchmarks are vital to our library and allow us to measure the impact of future performance improvements.

We use the Google benchmark framework. For inspiration, please take a look at the existing benchmarks in /perf.

The benchmark should be added under /perf in a directory which resembles the file structure of the original algorithm. i.e. if the algorithm is implemented in include/graaflib/algorithm/coloring/greedy_graph_coloring.h then the benchmark should be added to perf/graaflib/algorithm/coloring/greedy_graph_coloring_benchmark.cpp.

The benchmark should measure the runtime performance of the algorithm for increasing input sizes.

Running Benchmarks

If you IDE has the necessary integrations for it, all benchmarks can be run in the IDE from the perf/graaflib/benchmark.cpp file.

Otherwise, we can run the benchmarks from the command line:

# run all benchmarks
cd build/perf && ./Graaf_perf

To run an individual benchmark:

./Graaf_perf --benchmark_filter=YOUR_BENCHMARK_NAME

For more options, pass the --help flag.

Definition of Done

• A benchmark is added for the algorithm
• Benchmark results (copy past of the output is fine) is added to the PR

Improve documentation of interfaces

The documentation here is automatically generated using doxygen. In order to improve it, we should annotate the interfaces of graph.h, directed_graph.h, and undirected_graph.h with Javadoc-style comments. i.e.:

/**
 * Checks whether a vertex with a given ID is contained in the graph. 
 * 
 * @param vertex_id The ID of the vertex we want to check
 * @return A boolean indicating whether the vertex is contained in the graph
 */
[[nodiscard]] bool has_vertex(vertex_id_t vertex_id) const noexcept {...}

Add cycle detection algorithm

It would be nice to add an algorithm to detect whether a graph contains cycles. Two possible implementations here are Tarjan's algorithm and a depth-first search approach. Both implementations are valid candidates and could be added under this issue:

• Tarjan's algorithm (@bobluppes)
• DFS cycle detection

The implementation should go under src/graaflib/algorithm/cycle_detection.h. Each implementation should be covered with unit tests and should have it's public interface documented with javadoc-style comments.

[ALGO] Kosaraju's Algorithm

Kosaraju's Algorithm

Kosaraju's algorithm identifies the strongly connected components (SCCs) in a directed graph. A strongly connected component is a subgraph in which there is a path from every vertex to every other vertex. The algorithm uses two depth-first searches to identify these components.

When possible, it would be nice to see if we can reuse the existing DFS functionality in algorithm/graph_traversal/depth_first_search.h.

For more details, see the wikipedia entry.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds strongly connected components in a directed graph using Kosaraju's algorithm.
 *
 * Kosaraju's algorithm identifies strongly connected components (SCCs) in a directed graph.
 * The algorithm uses two depth-first searches to discover these components. 
 *
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @param graph The input directed graph.
 * 
 * @return A std::vector of vectors, each of which contains the vertex IDs forming
 *         a strongly connected component.
 */
template <typename V, typename E>
std::vector<std::vector<vertex_id_t>> kosarajus_strongly_connected_components(
    const graph<V, E, graph_type::DIRECTED>& graph
);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/strongly_connected_components/kosarajus.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/strongly_connected_components/kosarajus_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[FEAT] Type overflow exception throw

I think we should add a type overflow exception. The problem might occur while processing large inputs, especially in weighted shortest path algorithms.
I suggest using built-in functions or adding custom functions for integer and float point values.
As a temporary solution, we could use basic comparison, but in the future, do something more time and precision efficient.

What do you think about this?

Wikipedia
Integer values https://en.wikipedia.org/wiki/Integer_overflow
Floating type values https://en.wikipedia.org/wiki/Floating-point_arithmetic

Also, if no one wants to do this, I would like to try. This one seems interesting.

Consistent naming of algorithm categories in documentation

The goal of this issue is to use a consistent naming scheme for the algorithm categories in the documentation.

Some algorithm categories have the Algorithms suffix (i.e. Cycle Detection Algorithms), while other categories do not (i.e. Minimum Spanning Tree). Lastly, not all algorithm descriptions are contained in a category (i.e. Topological sort algorithm).

I would propose to follow the algorithm category structure as present in the source code:

include
  + graaflib
     + algorithms
        + coloring
        + cycle detection
        + graph traversal
        + minimum spanning tree
        + shortest path
        + strongly connected components
        + topological sorting 

This issue is done when:

• The documentation contains all categories listed above. Each category contains one or multiple .md files for the algorithms in that category.
• The naming of the algorithm categories follows the convention where each word is capitalized (Cycle Detection instead of cycle detection).
• The links in the README.md's algorithm overview are adjusted to point to the new urls.

More details on how to generate the documentation locally can be found on this wiki page.

[DOCS] Document Welsh-Powell Algorithm

Documentation Welsh-Powell

The goal of this issue if the improve the documentation of an existing algorithm. This documentation should go into the algorithms section of our docusaurus docs.

More detail on how to build the documentation locally can be found on the wiki.

A new documentation page should be created under docs/docs/algorithms/coloring.

The corresponding algorithm is called Welsh-Powell and can be found under include/graaflib/algorithm/coloring/welsh_powell.h.

Documentation Contents

The documentation entry should adhere to the following template:

# [ALGORITHM_NAME]
- A short description of the algorithm, what does it do and in which use cases is it used.
- What are the limitations of the algorithm, does it work on both directed and undirected graphs? Does it consider edge weights, and if yes, does it support negative weights?
- Link to the wikipedia entry on the algorithm.

## Syntax
- A code block with the syntax of the algorithm. This should now include any javadoc comments.
- An explanation of the parameters (including template parameters) and the return type.

## (Optional) See also
- If there are similar algorithms, or we have a slightly different version of the same algorithm, you can link it here.
- If we have an example (found on the example page of the docs) which uses this algorithm, you can link it here.

[ALGO] Page Rank

Page Rank

The PageRank algorithm calculates the importance of each node in a graph based on the structure of incoming links. Originally designed for ranking web pages, it's widely applicable in various network analysis tasks. The algorithm iteratively distributes "rank" across nodes and converges to a steady state.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

 * @brief Computes the PageRank of each node in the graph.
 * 
 * This function calculates the PageRank values for each node in a given graph
 * based on the transition probabilities between nodes. The method iteratively
 * updates the rank values until they converge or reach the maximum number of iterations.
 *
 * @tparam GraphType Type of the graph
 * @param graph The graph object.
 * @param damping_factor The damping factor usually set between 0.8 to 0.9. Default is 0.85.
 * @param max_iterations The maximum number of iterations before the algorithm terminates. Default is 100.
 * @param tolerance The value to check for convergence of the PageRank values. Default is 1.0e-6.
 * 
 * @return std::optional<std::unordered_map<Vertex, double>> An optional containing the
 *         unordered map of PageRank values for each vertex if the algorithm converged,
 *         otherwise std::nullopt.
 */
template <typename GRAPH>
std::optional<std::unordered_map<vertex_id_t, double>> compute_pagerank(
    const GRAPH& graph,
    double damping_factor = 0.85,
    unsigned int max_iterations = 100,
    double tolerance = 1.0e-6
);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/page_rank.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/page_rank_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[ALGO] Floyd-Warshall Shortest Paths

Floyd-Warshall Shortest Paths

The Floyd-Warshall algorithm calculates the shortest distances between all pairs of vertices in a weighted graph. It is efficient and also works for graphs with negative edge weights, as long as there are no negative weight cycles. The algorithm is to be implemented as a free function in the Graaf library.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Floyd-Warshall Algorithm
 *
 * This function computes the shortest paths between all pairs of vertices in a
 * given weighted graph. It works for graphs with negative weight edges as well,
 * but not for graphs with negative weight cycles. The function returns an
 * adjacency matrix representing the shortest distances.
 *
 * @tparam V The type of a graph vertex
 * @tparam E The type of a graph edge
 * @tparam T the graph type (DIRECTED or UNDIRECTED)
 * @tparam WEIGHT_T The weight type of an edge in the graph
 * @param graph The graph object
 * @return A 2D vector where element at [i][j] is the shortest distance from vertex i to vertex j.
 */
template <typename V, typename E, graph_type T, typename WEIGHT_T = decltype(get_weight(std::declval<E>()))>
std::vector<std::vector<WEIGHT_T>> floyd_warshall_shortest_paths(const graph<V, E, T>& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/shortest_path/floyd_warshall.h. There already exists a source file include/graaflib/algorithm/shortest_path.h, but I would like to split this up in the future. Therefore please create a directory shortest_path in which we can place floyd_warshall.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/shortest_path/floyd_warshall_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[BENCH] Benchmark Bron-Kerbosch Algorithm

Benchmark Bron-Kerbosch

The goal of this issues is to add a benchmark for the Bron-Kerbosch algorithm. The algorithm implementation is located under include/graaflib/algorithm/clique_detection/bron_kerbosch.h. Benchmarks are vital to our library and allow us to measure the impact of future performance improvements.

We use the Google benchmark framework. For inspiration, please take a look at the existing benchmarks in /perf.

The benchmark should be added under /perf in a directory which resembles the file structure of the original algorithm. i.e. if the algorithm is implemented in include/graaflib/algorithm/coloring/greedy_graph_coloring.h then the benchmark should be added to perf/graaflib/algorithm/coloring/greedy_graph_coloring_benchmark.cpp.

The benchmark should measure the runtime performance of the algorithm for increasing input sizes.

Running Benchmarks

If you IDE has the necessary integrations for it, all benchmarks can be run in the IDE from the perf/graaflib/benchmark.cpp file.

Otherwise, we can run the benchmarks from the command line:

# run all benchmarks
cd build/perf && ./Graaf_perf

To run an individual benchmark:

./Graaf_perf --benchmark_filter=YOUR_BENCHMARK_NAME

For more options, pass the --help flag.

Definition of Done

• A benchmark is added for the algorithm
• Benchmark results (copy past of the output is fine) is added to the PR

[ALGO] Kruskal's Minimum Spanning Tree

Kruskal's Minimum Spanning Tree

Kruskal's algorithm find a minimum spanning forest of a (weighted) undirected graph. If the graph is connected this is a minimum spanning tree. See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * Computes the minimum spanning tree (MST) or minimum spanning forest of a graph 
 * using Kruskal's algorithm.
 *
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @param graph The input graph.
 * @return A vector of edges forming the MST or minimum spanning forest.
 */
template <typename V, typename E>
[[nodiscard]] std::vector<edge_id_t>
kruskal_minimum_spanning_tree(const graph<V, E, graph_type::UNDIRECTED>& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/minimum_spanning_tree.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/minimum_spanning_tree_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[ALGO] Dijkstra Shortest Path (Tree Version)

Dijkstra Shortest Path (Tree Version)

Dijkstra's algorithm finds the shortest path between a source vertex and all other vertices in the graph. Currently, we already have a version of the algorithm which takes a source and target vertex. The goal of this ticket is to add an overload which computes computes a shortest path between a source vertex and all other vertices, resulting in a shortest path tree. See wikipedia for more details.

Syntax

The algorithm should have the following syntax:

/**
 * Find the shortest paths from a source vertex to all other vertices in the graph using Dijkstra's algorithm.
 *
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @tparam T The graph type (directed or undirected).
 * @tparam WEIGHT_T The type of edge weights.
 * @param graph The graph we want to search.
 * @param source_vertex The source vertex from which to compute shortest paths.
 * @return A map containing the shortest paths from the source vertex to all other vertices.
 *         The map keys are target vertex IDs, and the values are instances of graph_path, representing
 *         the shortest distance and the path (list of vertex IDs) from the source to the target.
 *         If a vertex is not reachable from the source, its entry will be absent from the map.
 */
template <typename V, typename E, graph_type T, typename WEIGHT_T = decltype(get_weight(std::declval<E>()))>
[[nodiscard]] std::unordered_map<vertex_id_t, graph_path<WEIGHT_T>>
dijkstra_shortest_paths(const graph<V, E, T>& graph, vertex_id_t source_vertex);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/shortest_path.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/shortest_path_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[DOCS] Document Dijkstra Shortest Path

Documentation Dijkstra Shortest Path

The goal of this issue if the improve the documentation of an existing algorithm. This documentation should go into the algorithms section of our docusaurus docs.

More detail on how to build the documentation locally can be found on the wiki.

An existing documentation page exists, which should be extended. The page can be found under docs/docs/algorithms/shortest-path/dijkstra.md.

The corresponding algorithm is called dijkstra_shortest_path and can be found under include/graaflib/algorithm/shortest_path.h.

Documentation Contents

The documentation entry should adhere to the following template:

# [ALGORITHM_NAME]
- A short description of the algorithm, what does it do and in which use cases is it used.
- What are the limitations of the algorithm, does it work on both directed and undirected graphs? Does it consider edge weights, and if yes, does it support negative weights?
- Link to the wikipedia entry on the algorithm.

## Syntax
- A code block with the syntax of the algorithm. This should now include any javadoc comments.
- An explanation of the parameters (including template parameters) and the return type.

## (Optional) See also
- If there are similar algorithms, or we have a slightly different version of the same algorithm, you can link it here.
- If we have an example (found on the example page of the docs) which uses this algorithm, you can link it here.

[ALGO] Topological Sorting (DFS-Based)

Topological Sorting (DFS-Based)

A topological sort is a linear ordering of all vertices in a directed graph such that a vertex is only visited after its dependencies are visited. The goal of this issue is to implement topological sorting based on DFS.

The existing DFS functionality (depth_first_traverse) should be re-used, rather than implementing a new DFS traversal.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

template <typename V, typename E, graph_type T>
[[nodiscard]] return_type your_algorithm_name(const graph<V, E, T>& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/topological_sorting.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/topological_sorting_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[DOCS] Document Breadth First Search (BFS)

Documentation Breadth First Search (BFS)

The goal of this issue if the improve the documentation of an existing algorithm. This documentation should go into the algorithms section of our docusaurus docs.

More detail on how to build the documentation locally can be found on the wiki.

An existing documentation page exists, which should be extended. The page can be found under docs/docs/algorithms/traversal/breadth-first-search.md.

The corresponding algorithm is called breadth_first_traverse and can be found under include/graaflib/algorithm/graph_traversal.h.

Documentation Contents

The documentation entry should adhere to the following template:

# [ALGORITHM_NAME]
- A short description of the algorithm, what does it do and in which use cases is it used.
- What are the limitations of the algorithm, does it work on both directed and undirected graphs? Does it consider edge weights, and if yes, does it support negative weights?
- Link to the wikipedia entry on the algorithm.

## Syntax
- A code block with the syntax of the algorithm. This should now include any javadoc comments.
- An explanation of the parameters (including template parameters) and the return type.

## (Optional) See also
- If there are similar algorithms, or we have a slightly different version of the same algorithm, you can link it here.
- If we have an example (found on the example page of the docs) which uses this algorithm, you can link it here.

[ALGO] Tarjan's Strongly Connected Components

Tarjan's Strongly Connected Components

Tarjan's algorithm can be used to find the Strongly Connected Components (SCCs) of a directed graph. An SCC is a subset of vertices in the graph for which every vertex is reachable from every other vertex in the subset. See the wikipedia entry for more details on Tarjan's algorithm.

Syntax

The algorithm should have the following syntax:

/**
 * Computes the Strongly Connected Components (SCCs) of a graph using Tarjan's algorithm.
 *
 * This function takes a graph and returns a vector of vectors representing the SCCs.
 * Each inner vector contains the vertices of a strongly connected component, and the outer vector
 * contains all the strongly connected components in the graph.
 *
 * @tparam V Vertex type.
 * @tparam E Edge type.
 * @param graph The graph for which to compute SCCs.
 * @return std::vector<std::vector<vertex_id_t>> A vector of vectors representing SCCs.
 */
template <typename V, typename E>
[[nodiscard]] std::vector<std::vector<vertex_id_t>> tarjans_strongly_connected_components(const graph<V, E, graph_type::DIRECTED>& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/strongly_connected_components.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/strongly_connected_components_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[DOCS] Create Example Sections

Create Example Sections

This is an open-ended issue and we welcome multiple PRs.

I would like to add a few example sections to the documentation. Each example should be self-contained and should demonstrate a potential usage of the Graaf library.

If you are interested, you can pick an example from the proposals below, or (even better) suggest your own example. The scope of a PR is restricted to a single example.

Definition of Done

Each example should contain the following:

• A complete and self-contained example under examples/EXAMPLE_NAME/main.cpp.
  • To verify that the example compiles and runs.
  • This can be used to generate any graphics (via dot files) for the public documentation.
  • See the dot serialization example for inspiration.
• An entry on our public documentation.
  • A short description of the example, what is the use case and why is it typical.
  • A list of the Graaf algorithms and data structures which are demonstrated in the example. Here you can link to the respective algorithms page in the documentation.
  • Code pointers (in the form of code blocks) to the important sections of the example. It is not necessary to cover the entirety of the added main.cpp, but the most important concepts should be captured.
  • Non-trivial parts in the code blocks should be explained in-text.
  • Graphics (i.e. in the form of visualized dot files) can be used. Any graphics should go under `docs/static/img/examples/.
  • Instructions on how to build the documentation locally can be found on the wiki.
  • An example entry can be found here.

Proposed Examples

• Dot serialization
• Shortest path (directed graph)
• Shortest path (undirected graph) [@Hromz]
• Cycle detection [@Hromz]
• Social network use case
• Minimal CNN implementation
• ...

Create common graph scenarios for unit tests

Currently a lot of the unit tests construct arbitrary graphs to run the algorithm which is to be tested on. In an ongoing effort, we would like to extract some common graph structures to "graph scenarios" such that they can be reused in the various unit tests.

Two such scenario's can be found in tests/utils/scenarios.h.

The goal of this issue is to create two new scenarios:

• A fully connected graph
• A disconnected graph, where the graph can be divided into two connected subgraphs

The ASCII art for the scenarios was made using this dot to ASCII tool

[ALGO] Kahn's Algorithm

Kahn's Algorithm

Kahn's algorithm is used for finding a topological order in a directed graph that has no cycles. The algorithm works by iteratively removing vertices that have an in-degree of zero and removing all outgoing edges from these vertices. The topological order is the sequence in which the nodes are removed.

We already have a function which computes the in-degree of a vertex in graaflib/properties/vertex_properties.h. It would be nice if we could reuse this.

For more details, see the wikipedia entry.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds a topological ordering of a directed graph using Kahn's algorithm.
 *
 * Kahn's algorithm works by iteratively removing nodes with an in-degree of zero
 * and all their outgoing edges. The order in which nodes are removed forms the 
 * topological order. This implementation returns a vector of vertex IDs representing
 * the topological order.
 *
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @param graph The input directed graph.
 * 
 * @return An std::optional containing a std::vector of vertex IDs that make up the 
 *         topological order. Returns an empty std::optional if the graph contains a cycle.
 */
template <typename V, typename E>
std::optional<std::vector<vertex_id_t>> kahns_topological_sort(
    const graph<V, E, graph_type::DIRECTED>& graph
);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/topological_sorting/kahn.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/topological_sorting/kahn_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[ALGO] Welsh-Powell Algorithm

Welsh-Powell Algorithm

The Welsh-Powell algorithm is a greedy graph coloring algorithm. It works by sorting the vertices by their degrees in descending order and then assigning colors in a manner that no two adjacent vertices share the same color. This algorithm is particularly efficient for coloring sparse graphs and is generally simpler to implement than other coloring algorithms.

Since it is a variant of the greedy coloring algorithm (which is already implemented under algorithm/coloring/greedy_graph_coloring.h), it would be nice if we could reuse that implementation.

More details on this variant of greedy coloring can be found in the wikipedia entry.

Syntax

The algorithm should have the following syntax:

/**
  * @brief Applies the Welsh-Powell greedy graph coloring algorithm to the given graph.
  * 
 * The function sorts the vertices by their degree in descending order, then attempts
 * to color the graph in a way that no two adjacent vertices share the same color.
 *
 * @tparam GRAPH The graph type.
 * @param graph The input graph to color.
 * @return std::unordered_map<vertex_id_t, int> An map from vertex ID to color if the graph could be colored, or an empty map otherwise.
 */
template <typename GRAPH>
std::unordered_map<vertex_id_t, int> welsh_powell_coloring(const GRAPH& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/coloring/welsh_powell.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/coloring/welsh_powell_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

Display test coverage in readme

[BENCH] Benchmark Greedy Graph Coloring Algorithm

Benchmark Greedy Graph Coloring

The goal of this issues is to add a benchmark for the Greedy Graph Coloring algorithm. The algorithm implementation is located under include/graaflib/algorithm/coloring/greedy_graph_coloring.h. Benchmarks are vital to our library and allow us to measure the impact of future performance improvements.

We use the Google benchmark framework. For inspiration, please take a look at the existing benchmarks in /perf.

The benchmark should be added under /perf in a directory which resembles the file structure of the original algorithm. i.e. if the algorithm is implemented in include/graaflib/algorithm/coloring/greedy_graph_coloring.h then the benchmark should be added to perf/graaflib/algorithm/coloring/greedy_graph_coloring_benchmark.cpp.

The benchmark should measure the runtime performance of the algorithm for increasing input sizes.

Running Benchmarks

If you IDE has the necessary integrations for it, all benchmarks can be run in the IDE from the perf/graaflib/benchmark.cpp file.

Otherwise, we can run the benchmarks from the command line:

# run all benchmarks
cd build/perf && ./Graaf_perf

To run an individual benchmark:

./Graaf_perf --benchmark_filter=YOUR_BENCHMARK_NAME

For more options, pass the --help flag.

Definition of Done

• A benchmark is added for the algorithm
• Benchmark results (copy past of the output is fine) is added to the PR

[FEAT] report visited edges in BFS/DFS

Feature Request

Why is this important?

Most use cases that make use of breadth_first_traverse or depth_first_traverse are actually interested in finding the traversed edges, rather than the traversed nodes.

Describe the solution you'd like

Instead of the BFS/DFS callback having the signature void(vertex_id_t), I would propose to change the signature of the callback to void(vertex_id_t, vertex_id_t) and to call it for every visited edge.

Additional context

We should probably do something similar for the shortest_path algorithms.

Checklist

Please check the following before submitting the issue:

• I have searched for similar feature requests in the issues.
• This feature is not already implemented in the library.
• I have provided a clear and concise description of the feature request.
• I have explained why this feature is important and how it benefits the library and users.
• I am willing to contribute to the development of this feature (if applicable).

Please note that feature requests are subject to review and may or may not be implemented in the library.

Dockerized build

The goal of this issue is to dockerize the build process. This would be helpful since it enables developers to work on the project without installing all the build tools on their machine.

[ALGO] Graph Isomorphism

Graph Isomorphism

In graph theory, an isomorphism between graphs G and H is a structure-preserving bijection between their vertex sets that also preserves adjacency. If such an isomorphism exists, the graphs are considered isomorphic, denoted as G≃HG≃H. Determining graph isomorphism efficiently is a major open question in computer science, known as the Graph Isomorphism problem.

The proposal is to implement the VF2 algorithm. The VF2 algorithm is a backtracking algorithm that provides a generic way to perform both subgraph and graph isomorphism tests. It is designed to be efficient and can handle both directed and undirected graphs. The algorithm is implemented in a way that allows for attributes to be associated with vertices and edges, and for those attributes to be considered as part of the isomorphism test if needed.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Checks if two graphs are isomorphic.
 *
 * This function checks whether two given graphs are isomorphic, meaning
 * they are structurally identical up to vertex and edge relabeling.
 * If the graphs are isomorphic, the function returns an optional containing
 * a mapping from the vertices of the first graph to the vertices of the second graph.
 * If the graphs are not isomorphic, the function returns std::nullopt.
 *
 * @tparam V The vertex type of the graphs.
 * @tparam E The edge type of the graphs.
 * @tparam T The graph type of the graphs (directed or undirected).
 * @param lhs The first graph to compare.
 * @param rhs The second graph to compare.
 * @return An optional containing a mapping from the vertices of lhs to those of rhs if isomorphic; otherwise std::nullopt.
 */
template <
    typename V, typename E, graph_type T
>
std::optional<std::unordered_map<vertex_id_t, vertex_id_t>> check_isomorphism(
    const graph<V, E, T>& lhs,
    const graph<V, E, T>& rhs
);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/graph_isomorphism.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/graph_isomorphism_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[ALGO] Bellman-Ford Shortest Path

Bellman-Ford Shortest Path

The Bellman-Ford algorithm computes the shortest path between a source vertex and all other vertices in the graph. Compared to Dijkstra, it can handle negative edge weights. See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

template <typename V, typename E, graph_type T>
[[nodiscard]] return_type your_algorithm_name(const graph<V, E, T>& graph);

/**
 * Find the shortest paths from a source vertex to all other vertices using
 * the Bellman-Ford algorithm.
 *
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @tparam T The graph specialization (directed or undirected).
 * @tparam WEIGHT_T The type of weight associated with the edges.
 * @param graph The graph in which to find the shortest paths.
 * @param start_vertex The source vertex for the shortest paths.
 * @return A map of target vertex IDs to shortest path structures. Each
 *         value contains a graph_path object representing the
 *         shortest path from the source vertex to the respective vertex.
 *         If a vertex is unreachable from the source, its entry will be
 *         absent from the map.
 */
template <typename V, typename E, graph_spec T, typename WEIGHT_T = decltype(get_weight(std::declval<E>()))>
std::unordered_map<vertex_id_t, graph_path<WEIGHT_T>>
bellman_ford_shortest_paths(const graph<V, E, T>& graph, vertex_id_t start_vertex);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/shortest_path.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/shortest_path_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

New design of documentation site

We use Docusaurus for our documentation site.

The site still uses the default Docusaurus theme. It would be nice to have something more customized. The Graaf project does not have any brand guidelines, but it would be nice if our logo is featured prominently on the landing page.

Optionally, it would be very nice if we can:

• Derive a new color scheme, to be used consistently for the entire project
• Have three new (vector) images on the landing which actually align with the text underneath them.

Negative weight cycle detection in Bellman-Ford

Bellman-Ford does not work in the presence of negative weight cycles. We should detect this (by doing an additional pass over the edges) and report an error if these cycles occur.

[ALGO] Edmonds-Karp Algorithm for Maximum Flow

Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is a greedy algorithm which computes the maximum flow in a flow network. See the wikipedia entry for a more detailed description.

It would be interesting to investigate if we can re-use the existing breadth_first_traverse method for the BFS part of the algorithm.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Computes the maximum flow in a flow network using the Edmonds-Karp algorithm.
 * 
 * This algorithm finds the maximum flow in a flow network from a source vertex to a sink vertex.
 * 
 * @param graph The flow network graph.
 * @param source The source vertex.
 * @param sink The sink vertex.
 * @return The maximum flow value.
 */
template <typename V, typename E, typename WEIGHT_T = decltype(get_weight(std::declval<E>()))>
[[nodiscard]] WEIGHT_T edmonds_karp_max_flow(
    const graph<V, E, graph_type::DIRECTED>& graph,
    vertex_id_t source, vertex_id_t sink);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/maximum_flow.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/maximum_flow_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[DOCS] Document BFS Based Shortest Path

Documentation BFS Based Shortest Path

The goal of this issue if the improve the documentation of an existing algorithm. This documentation should go into the algorithms section of our docusaurus docs.

More detail on how to build the documentation locally can be found on the wiki.

An existing documentation page exists, which should be extended. The page can be found under docs/docs/algorithms/shortest-path/bfs-based-shortest-path.md.

The corresponding algorithm is called bfs_shortest_path and can be found under include/graaflib/algorithm/shortest_path.h.

Documentation Contents

The documentation entry should adhere to the following template:

# [ALGORITHM_NAME]
- A short description of the algorithm, what does it do and in which use cases is it used.
- What are the limitations of the algorithm, does it work on both directed and undirected graphs? Does it consider edge weights, and if yes, does it support negative weights?
- Link to the wikipedia entry on the algorithm.

## Syntax
- A code block with the syntax of the algorithm. This should now include any javadoc comments.
- An explanation of the parameters (including template parameters) and the return type.

## (Optional) See also
- If there are similar algorithms, or we have a slightly different version of the same algorithm, you can link it here.
- If we have an example (found on the example page of the docs) which uses this algorithm, you can link it here.

[ALGO] Prim's Minimum Spanning Tree

Prim's Minimum Spanning Tree

Prim's algorithm is a greedy algorithm which finds a minimum spanning tree for a (weighted) undirected graph. See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * Computes the minimum spanning tree (MST) of a graph using Prim's algorithm.
 *
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @param graph The input graph.
 * @param start_vertex The starting vertex for the MST construction.
 * @return An optional containing a vector of edges forming the MST if it exists, 
 *         or an empty optional if the MST doesn't exist (e.g., graph is not connected).
 */
template <typename V, typename E>
[[nodiscard]] std::optional<std::vector<typename graph<V, E, graph_type::UNDIRECTED>::edge_t>>
prim_minimum_spanning_tree(const graph<V, E, graph_type::UNDIRECTED>& graph, vertex_id_t start_vertex);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/minimum_spanning_tree.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/minimum_spanning_tree_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[REQUEST] Collaboration with CXXGraph

Hi,

I'm the owner, coordinator and developer of a similar project CXXGraph.
The project has the same goals, why not collaborate?
I think CXXGraph library is a step foward with also a community of users.
What do you think?

Add existing example sections to documentation

There are currently two example usages under examples/. These both contain a README.md as well as a source file.

I would like to move these source files into our documentation. There is already a separate sidebar, so renaming the READMEs to the example name and moving them to docs/docs/examples/examples-basics should be enough.

The only issue is that some of the tags in the readme break docusaurus:

SyntaxError: docs/docs/examples/examples-basics/dot-serialization.md: Expected corresponding JSX closing tag for <img>. (67:0)
  65 | <p align="center">
  66 |     <img src="./graph.png">
> 67 | </p>
     | ^
  68 |     </MDXLayout>
  69 |   )
  70 | };

Therefore the markdown files will have to be adjusted slightly. More info on generating the documentation locally can be found on the wiki.

[ALGO] Graph Coloring (Greedy)

Greedy Graph Coloring

The Greedy Graph Coloring algorithm is a heuristic approach to assigning colors to the vertices of a graph in such a way that no adjacent vertices share the same color. It is a fundamental algorithm with applications in scheduling, map coloring, and various optimization problems. The goal is to implement this algorithm to add to the library's suite of graph algorithms.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Greedy Graph Coloring Algorithm
 *
 * This function performs greedy graph coloring on a given graph. It assigns
 * colors to vertices in such a way that no two adjacent vertices share the
 * same color. The algorithm is heuristic and does not guarantee an optimal
 * coloring.
 *
 * @tparam GRAPH The type of the graph
 * @param graph The graph object
 * @return An unordered_map where keys are vertex identifiers and values are their respective colors.
 */
template <typename GRAPH>
std::unordered_map<vertex_id_t, int> greedy_graph_coloring(const GRAPH& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/coloring/greedy_graph_coloring.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/coloring/greedy_graph_coloring_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category. The category should follow the file path of the new algorithm.
  • In case the category does not exist yet, please add one
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[ALGO] Borůvka's algorithm

Borůvka's algorithm

Borůvka's algorithm, also known as Sollin's algorithm, is a classic approach to find the Minimum Spanning Tree (MST) of a graph. It works well for disconnected graphs by finding a Minimum Spanning Forest. This algorithm is unique in the way it handles edge selections, and it can be highly efficient for sparse graphs.

More details can be found on the wikipedia entry.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds the Minimum Spanning Tree (MST) using Borůvka's algorithm.
 *
 * Borůvka's algorithm is efficient for sparse graphs and can also find the
 * Minimum Spanning Forest for disconnected graphs. This algorithm returns
 * a vector containing edge IDs that make up the MST.
 *
 * @tparam GRAPH The graph type.
 * @param graph The input graph.
 * 
 * @return A std::vector of edge IDs that make up the MST.
 *         Returns an empty vector if the MST cannot be formed.
 */
template <typename GRAPH>
std::vector<edge_id_t> boruvka_minimum_spanning_tree(
    const GRAPH& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/minimum_spanning_tree/boruvka.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/minimum_spanning_tree/boruvka_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[FEAT] Python Bindings

Feature Request

I would like to add Python bindings for the Graaf project. Since the Graaf library uses template metaprogramming, we should instantiate a few common graph types, such as undirected_graph<int, int> in order to create the bindings.

The proposal is to make use of pybind11. The goal of this issue is to implement a minimal viable product (MVP) to evaluate whether it is feasible to provide Python bindings for Graaf.

Why is this important?

Python bindings would allows Graaf to be used by a wider audience 😄

Describe the solution you'd like

To start, I would like to provide Python bindings using pybind11 for the following graph types:

undirected_graph<int, int>
undirected_graph<float, float>

directed_graph<int, int>
directed_graph<float, float>

[ALGO] Bron-Kerbosch Clique Detection

Bron-Kerbosch

The Bron-Kerbosch algorithm is a backtrack algorithm to find all cliques in an undirected graph. It serves as an essential tool for identifying densely connected subgraphs within a graph and has applications ranging from social network analysis to bioinformatics.

Implementing this would introduce a new category of algorithms (clique detection) to our library, enhancing its functionality.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds all cliques in an undirected graph using the Bron-Kerbosch algorithm.
 * 
 * The Bron-Kerbosch algorithm is used for finding all cliques in an undirected graph.
 * A clique is a subset of vertices such that every two distinct vertices are adjacent.
 * This function returns a list of all cliques, each represented as a vector of vertex identifiers.
 * 
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @param graph The graph in which we want to find the cliques.
 * @return A vector of cliques, each represented as a vector of vertex identifiers.
 */
template <typename V, typename E>
std::vector<std::vector<vertex_id_t>> bron_kerbosch(const graph<V, E, graph_type::UNDIRECTED>& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/clique/bron_kerbosch.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/clique/bron_kerbosch_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md