MinCliqueCoverSolverViaGreedy Class Reference

Detailed Description

Approximately solves the min clique cover problem via a greedy heuristic.

At each step, the largest clique found by the provided max clique solver is added to the clique cover. These vertices are then removed from graph and max clique is solved again. This loop continues until a clique is found which is smaller than the min clique size.

Note

if min clique size > 1, then this class will not strictly compute a clique cover since not all vertices will be covered.

#include <drake/planning/graph_algorithms/min_clique_cover_solver_via_greedy.h>

Public Member Functions
	MinCliqueCoverSolverViaGreedy (std::shared_ptr< MaxCliqueSolverBase > max_clique_solver, int min_clique_size=1)
	Constructs using the given max clique solver. More...
	MinCliqueCoverSolverViaGreedy (const MaxCliqueSolverBase &max_clique_solver, int min_clique_size=1)
	(Deprecated.) More...
void	set_min_clique_size (const int min_clique_size)
	Set the minimum clique size. More...
int	get_min_clique_size () const
Does not allow copy, move, or assignment
	MinCliqueCoverSolverViaGreedy (const MinCliqueCoverSolverViaGreedy &)=delete
MinCliqueCoverSolverViaGreedy &	operator= (const MinCliqueCoverSolverViaGreedy &)=delete
	MinCliqueCoverSolverViaGreedy (MinCliqueCoverSolverViaGreedy &&)=delete
MinCliqueCoverSolverViaGreedy &	operator= (MinCliqueCoverSolverViaGreedy &&)=delete
Public Member Functions inherited from MinCliqueCoverSolverBase
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. More...

Additional Inherited Members
Protected Member Functions inherited from MinCliqueCoverSolverBase
	MinCliqueCoverSolverBase ()=default
	MinCliqueCoverSolverBase (const MinCliqueCoverSolverBase &)=default
MinCliqueCoverSolverBase &	operator= (const MinCliqueCoverSolverBase &)=default
	MinCliqueCoverSolverBase (MinCliqueCoverSolverBase &&)=default
MinCliqueCoverSolverBase &	operator= (MinCliqueCoverSolverBase &&)=default

Constructor & Destructor Documentation

MinCliqueCoverSolverViaGreedy() [1/4]

MinCliqueCoverSolverViaGreedy ( const MinCliqueCoverSolverViaGreedy &  )

delete

MinCliqueCoverSolverViaGreedy() [2/4]

MinCliqueCoverSolverViaGreedy ( MinCliqueCoverSolverViaGreedy &&  )

delete

MinCliqueCoverSolverViaGreedy() [3/4]

MinCliqueCoverSolverViaGreedy ( std::shared_ptr< MaxCliqueSolverBase >  max_clique_solver, int  min_clique_size = 1  )

explicit

Constructs using the given max clique solver.

MinCliqueCoverSolverViaGreedy() [4/4]

MinCliqueCoverSolverViaGreedy ( const MaxCliqueSolverBase &  max_clique_solver, int  min_clique_size = 1  )

explicit

(Deprecated.)

Deprecated:

Pass the solver by shared_ptr not const-ref
This will be removed from Drake on or after 2025-05-01.

Member Function Documentation

get_min_clique_size()

int get_min_clique_size

(

)

const

operator=() [1/2]

MinCliqueCoverSolverViaGreedy& operator= ( MinCliqueCoverSolverViaGreedy &&  )

delete

operator=() [2/2]

MinCliqueCoverSolverViaGreedy& operator= ( const MinCliqueCoverSolverViaGreedy &  )

delete

set_min_clique_size()

void set_min_clique_size

(

const int

min_clique_size

)

Set the minimum clique size.

Throws if this is less than 1.

Parameters

min_clique_size

---

The documentation for this class was generated from the following file:

• drake/planning/graph_algorithms/min_clique_cover_solver_via_greedy.h