bobluppes / bobluppes/graaf

[FEAT] Bipartite graph specialization

Open
#254 1 comment 0 reactions 0 assignees View on GitHub
enhancement help wanted stale
Dominant language
C++
Stars
413
Forks
67
Avg merge
7h 24m
Merged PRs (30d)
53

Description

## Bipartite Graph
The goal of this issue is to add a graph specialization for bipartite graphs. For an initial version, I would propose to add a `bipartite_graph` class which can be implemented on top of a `graph` using composition. During construction and modification of the vertices/edges we can then check the invariants of the bipartite graph.

In a follow-up, we can consider a more efficient implementation compared to based it on a "normal" `graph`. In particular, we could omit storing the edge/neighbor information, as we know that any vertex in a partition has all vertices in the other partition as its neighbors. However, I am not sure how we would then still efficiently store edge values.
Another follow-up could be to generalize the class and implement a `multipartite_graph`, but this is out of scope for the current issue.

### Syntax
An initial idea on what the (public) interface of the class could look like:
_(note that this is not set in stone, and merely an initial idea)_

```c++
// include/graaflib/bipartite_graph.h

template
class bipartite_graph {
public:
// Using declarations, similar to graph.h
using partition_id_t = std::size_t;

// note: bipartite-ness of a graph is a separate property compared to directed-ness.
[[nodiscard]] constexpr bool is_directed() const;
[[nodiscard]] constexpr bool is_undirected() const;

[[nodiscard]] std::size_t vertex_count() const noexcept;
[[nodiscard]] std::size_t edge_count() const noexcept;

[[nodiscard]] const vertex_id_to_vertex_t& get_vertices() const noexcept;
[[nodiscard]] const vertex_id_to_vertex_t& get_vertices(partition_id_t partition_id) const noexcept;
[[nodiscard]] const edge_id_to_edge_t& get_edges() const noexcept;

[[nodiscard]] bool has_vertex(vertex_id_t vertex_id) const noexcept;
[[nodiscard]] bool has_vertex(vertex_id_t vertex_id, partition_id_t partition_id) const noexcept;
[[nodiscard]] bool has_edge(vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) const noexcept;

[[nodiscard]] vertex_t& get_vertex(vertex_id_t vertex_id);
[[nodiscard]] const vertex_t& get_vertex(vertex_id_t vertex_id) const;

[[nodiscard]] edge_t& get_edge(vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs);
[[nodiscard]] const edge_t& get_edge(vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) const;
[[nodiscard]] edge_t& get_edge(const edge_id_t& edge_id);
[[nodiscard]] const edge_t& get_edge(const edge_id_t& edge_id) const;

// note: if we were to go for an implementation other than composing this class on a graph,
// we could simply return all vertices in the other partition here
[[nodiscard]] vertices_t get_neighbors(vertex_id_t vertex_id) const;

[[nodiscard]] vertex_id_t add_vertex(auto&& vertex, partition_id_t partition_id);
vertex_id_t add_vertex(auto&& vertex, vertex_id_t id, partition_id_t partition_id);
void remove_vertex(vertex_id_t vertex_id);
void add_edge(vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs, auto&& edge);
void remove_edge(vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs);
};
```

## Definition of Done
This issue is done when:

- [ ] The bipartite graph is implemented
- [ ] The new class has a javadoc-style comment for the entire class and for the public methods
- [ ] Appropriate tests are added under test/graaflib/bipartite_graph_test.cpp
- [ ] A test coverage of at least 95% is reached

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.