[FEAT] Bipartite graph specialization

[bobluppes]

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)

// include/graaflib/bipartite_graph.h

template <typename VERTEX_T, typename EDGE_T, graph_type GRAPH_TYPE_V>
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

[github-actions]

Marking this issue as stale. It will not be automatically closed.

Even though the maintainers of Graaf may not always have time to take a look in a timely fashion, your contributions are much appreciated.
Please allow some time for @bobluppes to take a closer look.