The problem of finding the maximum clique in a graph is known to be NP-complete.
This base class provides a unified interface for various implementations of a solver for this problem which may be solved rigorously or via heuristics.
| VectorX<bool> SolveMaxClique |
( |
const Eigen::SparseMatrix< bool > & |
adjacency_matrix | ) |
const |
Given the adjacency matrix of an undirected graph, find the maximum clique within the graph.
A clique is a collection of vertices in a graph such that each pair of vertices is connected by an edge (i.e. a fully connected subgraph). This problem is known to be NP-complete, and so the concrete implementation of the solver determines whether the return of this function is the true maximum clique in the graph (which may take very long to compute), or only an approximate solution found via heuristics.
This method throws if the adjacency matrix is not symmetric and may throw depending on the concrete implmementation of the solver.
- Parameters
-
| adjacency_matrix | a symmetric binary matrix encoding the edge relationship. |
- Returns
- A binary vector with the same indexing as the adjacency matrix, with true indicating membership in the clique.
