[ALGO] Graph Isomorphism

[bobluppes]

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

[sracha4355]

Please assign it to me!

[github-actions[bot]]

Stale issue message

[github-actions[bot]]

Stale issue message