MaxCliqueSolverBase Class Reference

Detailed Description

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.

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

Public Member Functions
virtual	~MaxCliqueSolverBase ()
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. More...
std::unique_ptr< MaxCliqueSolverBase >	Clone () const
	(Deprecated.) More...

Protected Member Functions
	MaxCliqueSolverBase ()=default
Implements CopyConstructible, CopyAssignable, MoveConstructible, MoveAssignable
	MaxCliqueSolverBase (const MaxCliqueSolverBase &)=default
MaxCliqueSolverBase &	operator= (const MaxCliqueSolverBase &)=default
	MaxCliqueSolverBase (MaxCliqueSolverBase &&)=default
MaxCliqueSolverBase &	operator= (MaxCliqueSolverBase &&)=default

Constructor & Destructor Documentation

~MaxCliqueSolverBase()

virtual ~MaxCliqueSolverBase ( )

virtual

MaxCliqueSolverBase() [1/3]

MaxCliqueSolverBase ( const MaxCliqueSolverBase &  )

protecteddefault

MaxCliqueSolverBase() [2/3]

MaxCliqueSolverBase ( MaxCliqueSolverBase &&  )

protecteddefault

MaxCliqueSolverBase() [3/3]

MaxCliqueSolverBase ( )

protecteddefault

Member Function Documentation

Clone()

std::unique_ptr<MaxCliqueSolverBase> Clone

(

)

const

(Deprecated.)

Deprecated:

Clone is not useful and so is being removed
This will be removed from Drake on or after 2025-05-01.

operator=() [1/2]

MaxCliqueSolverBase& operator= ( MaxCliqueSolverBase &&  )

protecteddefault

operator=() [2/2]

MaxCliqueSolverBase& operator= ( const MaxCliqueSolverBase &  )

protecteddefault

SolveMaxClique()

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 implementation 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.

---

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

• drake/planning/graph_algorithms/max_clique_solver_base.h