operations_research::WeightedBronKerboschBitsetAlgorithm Class Reference

#include <cliques.h>

Public Member Functions
void	Initialize (int num_nodes)
void	SetWeight (int i, double weight)
void	AddEdge (int a, int b)
	Add an edge in the graph.
void	SetWorkLimit (int64_t limit)
	We count the number of basic operations, and stop when we reach this limit.
void	SetMinimumWeight (double min_weight)
	Set the minimum weight of the maximal cliques we are looking for.
void	TakeTransitiveClosureOfImplicationGraph ()
std::vector< std::vector< int > >	Run ()
std::vector< std::pair< int, double > > &	GetMutableIndexAndWeight ()
int64_t	WorkDone () const
bool	HasEdge (int i, int j) const

Detailed Description

More specialized version used to separate clique-cuts in MIP solver. This finds all maximal clique with a weight greater than a given threshold. It also has computation limit.

This implementation assumes small graph since we use a dense bitmask representation to encode the graph adjacency. So it shouldn't really be used with more than a few thousands nodes.

Definition at line 370 of file cliques.h.

Member Function Documentation

AddEdge()

void operations_research::WeightedBronKerboschBitsetAlgorithm::AddEdge ( int a, int b )

inline

Add an edge in the graph.

Definition at line 381 of file cliques.h.

GetMutableIndexAndWeight()

std::vector< std::pair< int, double > > & operations_research::WeightedBronKerboschBitsetAlgorithm::GetMutableIndexAndWeight ( )

inline

Specific API where the index refer in the last result of Run(). This allows to select cliques when they are many.

Definition at line 408 of file cliques.h.

HasEdge()

bool operations_research::WeightedBronKerboschBitsetAlgorithm::HasEdge ( int i, int j ) const

inline

Definition at line 414 of file cliques.h.

Initialize()

void operations_research::WeightedBronKerboschBitsetAlgorithm::Initialize

(

int

num_nodes

)

Resets the class to an empty graph will all weights of zero. This also reset the work done.

We need +1 in case the graph is complete and form a clique.

Initialize to empty graph.

Definition at line 267 of file cliques.cc.

Run()

std::vector< std::vector< int > > operations_research::WeightedBronKerboschBitsetAlgorithm::Run

(

)

Runs the algo and returns all maximal clique with a weight above the configured thrheshold via SetMinimumWeight(). It is possible we reach the work limit before that.

We run an iterative DFS where we push all possible next node to queue_. We just abort brutally if we hit the work limit.

We add this node to the clique.

Note

it might seems we don't need to keep both set since we only process nodes in order, but because of the pivot optim, while both set are sorted, they can be "interleaved".

Choose a pivot. We use the vertex with highest weight according to: Samuel Souza Britoa, Haroldo Gambini Santosa, "Preprocessing and Cutting Planes with Conflict Graphs", https://arxiv.org/pdf/1909.07780 but maybe random is more robust?

Heuristic: We can abort early if there is no way to reach the threshold here.

This clique is maximal.

We finished exploring node. backtrack.

Definition at line 298 of file cliques.cc.

SetMinimumWeight()

void operations_research::WeightedBronKerboschBitsetAlgorithm::SetMinimumWeight ( double min_weight )

inline

Set the minimum weight of the maximal cliques we are looking for.

Definition at line 390 of file cliques.h.

SetWeight()

void operations_research::WeightedBronKerboschBitsetAlgorithm::SetWeight ( int i, double weight )

inline

Set the weight of a given node, must be in [0, num_nodes). Weights are assumed to be non-negative.

Definition at line 378 of file cliques.h.

SetWorkLimit()

void operations_research::WeightedBronKerboschBitsetAlgorithm::SetWorkLimit ( int64_t limit )

inline

We count the number of basic operations, and stop when we reach this limit.

Definition at line 387 of file cliques.h.

TakeTransitiveClosureOfImplicationGraph()

void operations_research::WeightedBronKerboschBitsetAlgorithm::TakeTransitiveClosureOfImplicationGraph

(

)

This function is quite specific. It interprets node i as the negated literal of node i ^ 1. And all j in graph[i] as literal that are in at most two relation. So i implies all not(j) for all j in graph[i].

The transitive close runs in O(num_nodes ^ 3) in the worst case, but since we process 64 bits at the time, it is okay to run it for graph up to 1k nodes.

We use Floyd-Warshall algorithm.

Loop over all the i => k, we can do that by looking at the not(k) => not(i).

Now i also implies all the literals implied by k.

Definition at line 284 of file cliques.cc.

WorkDone()

int64_t operations_research::WeightedBronKerboschBitsetAlgorithm::WorkDone ( ) const

inline

Definition at line 412 of file cliques.h.

---

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

• ortools/graph/cliques.h
• ortools/graph/cliques.cc