seams-core v2.14.0
libyodaLib, the C++ engine of d-SEAMS
Loading...
Searching...
No Matches
chordless Namespace Reference

Functions

std::size_t cycles (const std::vector< int > &offsets, const std::vector< int > &cols, int size, std::vector< int > *rings, int *per_atom)
 Chordless cycles of one size on a CSR graph.

Variables

constexpr int kMaxSize = 12

Function Documentation

◆ cycles()

std::size_t chordless::cycles ( const std::vector< int > & offsets,
const std::vector< int > & cols,
int size,
std::vector< int > * rings,
int * per_atom )

Chordless cycles of one size on a CSR graph.

A cycle is chordless when no edge joins two of its vertices that are not neighbours on the cycle. Each cycle is listed once, starting at its lowest vertex, in the direction whose second vertex is the smaller of that vertex's two cycle neighbours. The list is sorted lexicographically, so it does not depend on the thread count.

Parameters
offsetsn + 1 row offsets.
colsColumn indices. Self entries must not appear.
sizeCycle length, from 3 through kMaxSize.
ringsWhen not null, receives count * size vertex indices.
per_atomWhen not null, n counts of cycles through each vertex.
Returns
The number of cycles.

Variable Documentation

◆ kMaxSize

int chordless::kMaxSize = 12
constexpr

Largest cycle the meet-in-the-middle search takes. A half is at most six steps.

Definition at line 11 of file chordless.hpp.