#include <drake/planning/graph_algorithms/min_clique_cover_solver_base.h>
|
| virtual | ~MinCliqueCoverSolverBase () |
| std::vector< std::set< int > > | SolveMinCliqueCover (const Eigen::SparseMatrix< bool > &adjacency_matrix, bool partition=false) |
| | Given the adjacency matrix of an undirected graph, finds a (potentially approximate) minimum clique cover of the graph.
|
◆ ~MinCliqueCoverSolverBase()
◆ MinCliqueCoverSolverBase() [1/3]
◆ MinCliqueCoverSolverBase() [2/3]
◆ MinCliqueCoverSolverBase() [3/3]
◆ operator=() [1/2]
◆ operator=() [2/2]
◆ SolveMinCliqueCover()
| std::vector< std::set< int > > SolveMinCliqueCover |
( |
const Eigen::SparseMatrix< bool > & | adjacency_matrix, |
|
|
bool | partition = false ) |
|
nodiscard |
Given the adjacency matrix of an undirected graph, finds a (potentially approximate) minimum clique cover of 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). A clique cover is a collection of cliques where each vertex in the graph is in at least one of the cliques. 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 minimum clique cover of 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 implementation of the solver.
- Parameters
-
| adjacency_matrix | a symmetric binary matrix encoding the edge relationship. |
| partition | If true, then every vertex is allowed to be covered exactly once. Otherwise, the same vertex may be covered multiple times. |
- Returns
- A binary vector with the same indexing as the adjacency matrix, with true indicating membership in the clique.
-
The ith entry of the returned vector is a vector containing the indices of the ith clique.
Note that this method is intentionally not-const because some solvers may use randomized algorithms.
The documentation for this class was generated from the following file:
