souffle::DisjointSet Class Reference

Structure that emulates a Disjoint Set, i.e. More...

#include <UnionFind.h>

Collaboration diagram for souffle::DisjointSet:

Public Member Functions
void	clear ()
	Clears the DisjointSet of all nodes Invalidates all iterators. More...
	DisjointSet ()=default
	DisjointSet (DisjointSet &&other)=delete
	DisjointSet (DisjointSet &other)=delete
parent_t	findNode (parent_t x)
	Equivalent to the find() function in union/find Find the highest ancestor of the provided node - flattening as we go. More...
std::atomic< block_t > &	get (parent_t node) const
	Yield reference to the node by its node index. More...
block_t	makeNode ()
	Create a node with its parent as itself, rank 0. More...
DisjointSet &	operator= (DisjointSet &&ds)=delete
DisjointSet &	operator= (DisjointSet &ds)=delete
bool	sameSet (parent_t x, parent_t y)
	Check whether the two indices are in the same set. More...
size_t	size ()
	Return the number of elements in this disjoint set (not the number of pairs) More...
void	unionNodes (parent_t x, parent_t y)
	Union the two specified index nodes. More...

Static Public Member Functions
static parent_t	b2p (const block_t inblock)
	Extract parent from block. More...
static rank_t	b2r (const block_t inblock)
	Extract rank from block. More...
static block_t	pr2b (const parent_t parent, const rank_t rank)
	Yield a block given parent and rank. More...

Private Member Functions
bool	updateRoot (const parent_t x, const rank_t oldrank, const parent_t y, const rank_t newrank)
	Update the root of the tree of which x is, to have y as the base instead. More...

Private Attributes
PiggyList< std::atomic< block_t > >	a_blocks

Friends
template<typename TupleType >
class	EquivalenceRelation

Detailed Description

Structure that emulates a Disjoint Set, i.e.

a data structure that supports efficient union-find operations

Definition at line 54 of file UnionFind.h.

Constructor & Destructor Documentation

DisjointSet() [1/3]

souffle::DisjointSet::DisjointSet ( )

default

DisjointSet() [2/3]

souffle::DisjointSet::DisjointSet ( DisjointSet &  other )

delete

DisjointSet() [3/3]

souffle::DisjointSet::DisjointSet ( DisjointSet &&  other )

delete

Member Function Documentation

b2p()

static parent_t souffle::DisjointSet::b2p ( const block_t  inblock )

inlinestatic

Extract parent from block.

Parameters

inblock

the block to be masked

Returns

The parent_t contained in the upper half of block_t

Definition at line 212 of file UnionFind.h.

                                                    {

References souffle::rank_mask.

Referenced by get().

b2r()

static rank_t souffle::DisjointSet::b2r ( const block_t  inblock )

inlinestatic

Extract rank from block.

Parameters

inblock

the block to be masked

Returns

the rank_t contained in the lower half of block_t

Definition at line 221 of file UnionFind.h.

                                                                         {

References souffle::split_size.

clear()

void souffle::DisjointSet::clear ( )

inline

Clears the DisjointSet of all nodes Invalidates all iterators.

Definition at line 140 of file UnionFind.h.

                                         {

References findNode().

Referenced by souffle::SparseDisjointSet< value_type >::size().

Here is the call graph for this function:

findNode()

parent_t souffle::DisjointSet::findNode ( parent_t  x )

inline

Equivalent to the find() function in union/find Find the highest ancestor of the provided node - flattening as we go.

Parameters

x	the node to find the parent of, whilst flattening its set-tree

Returns

The parent of x

Definition at line 97 of file UnionFind.h.

       :
    /**
     * Update the root of the tree of which x is, to have y as the base instead
     * @param x : old root
     * @param oldrank : old root rank

Referenced by clear(), and souffle::test::TEST().

get()

std::atomic<block_t>& souffle::DisjointSet::get ( parent_t  node ) const

inline

Yield reference to the node by its node index.

Parameters

node	node to be searched

Returns

the parent block of the specified node

Definition at line 86 of file UnionFind.h.

                                  {

References b2p().

Here is the call graph for this function:

makeNode()

block_t souffle::DisjointSet::makeNode ( )

inline

Create a node with its parent as itself, rank 0.

Returns

the newly created block

Definition at line 198 of file UnionFind.h.

                                                      {

Referenced by souffle::test::TEST().

operator=() [1/2]

DisjointSet& souffle::DisjointSet::operator= ( DisjointSet &&  ds )

delete

operator=() [2/2]

DisjointSet& souffle::DisjointSet::operator= ( DisjointSet &  ds )

delete

pr2b()

static block_t souffle::DisjointSet::pr2b ( const parent_t  parent, const rank_t  rank  )

inlinestatic

Yield a block given parent and rank.

Parameters

parent	the top half bits
rank	the lower half bits

Returns

the resultant block after merge

Definition at line 231 of file UnionFind.h.

                          {
    int operator()(const StorePair& a, const StorePair& b) {
        if (a.first < b.first) {

References b, and souffle::EqrelMapComparator< StorePair >::operator()().

Here is the call graph for this function:

sameSet()

bool souffle::DisjointSet::sameSet ( parent_t  x, parent_t  y  )

inline

Check whether the two indices are in the same set.

Parameters

x	node to be checked
y	node to be checked

Returns

where the two indices are in the same set

Definition at line 150 of file UnionFind.h.

                                            {

size()

size_t souffle::DisjointSet::size ( )

inline

Return the number of elements in this disjoint set (not the number of pairs)

Definition at line 76 of file UnionFind.h.

References a_blocks, and souffle::PiggyList< T >::get().

Referenced by souffle::test::TEST().

Here is the call graph for this function:

unionNodes()

void souffle::DisjointSet::unionNodes ( parent_t  x, parent_t  y  )

inline

Union the two specified index nodes.

Parameters

x	node to be unioned
y	node to be unioned

Definition at line 165 of file UnionFind.h.

                                                              {
                std::swap(x, y);
                std::swap(xrank, yrank);
            }
            // join the trees together
            // perhaps we can optimise the use of compare_exchange_strong here, as we're in a pessimistic loop
            if (!updateRoot(x, xrank, y, yrank)) {
                continue;
            }
            // make sure that the ranks are orderable
            if (xrank == yrank) {
                updateRoot(y, yrank, y, yrank + 1);
            }
            break;
        }
    }
 
    /**
     * Create a node with its parent as itself, rank 0
     * @return the newly created block
     */
    inline block_t makeNode() {

Referenced by souffle::test::TEST().

updateRoot()

bool souffle::DisjointSet::updateRoot ( const parent_t  x, const rank_t  oldrank, const parent_t  y, const rank_t  newrank  )

inlineprivate

Update the root of the tree of which x is, to have y as the base instead.

Parameters

x	: old root
oldrank	: old root rank
y	: new root
newrank	: new root rank

Returns

Whether the update succeeded (fails if another root update/union has been perfomed in the interim)

Definition at line 123 of file UnionFind.h.

      :
    /**
     * Clears the DisjointSet of all nodes
     * Invalidates all iterators
     */

Friends And Related Function Documentation

EquivalenceRelation

template<typename TupleType >

friend class EquivalenceRelation

friend

Definition at line 56 of file UnionFind.h.

Field Documentation

a_blocks

PiggyList<std::atomic<block_t> > souffle::DisjointSet::a_blocks

private

Definition at line 58 of file UnionFind.h.

Referenced by size().

---

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

• include/souffle/datastructure/UnionFind.h