disjoint_set Class Reference

Public Member Functions
	disjoint_set (size_t size)
int	find (int aVal)
bool	unite (int aVal1, int aVal2)

Private Attributes
std::vector< int >	m_data
std::vector< int >	m_depth

Detailed Description

Definition at line 47 of file ratsnest_data.cpp.

Constructor & Destructor Documentation

disjoint_set()

disjoint_set::disjoint_set ( size_t  size )

inline

Definition at line 51 of file ratsnest_data.cpp.

 {
 m_data.resize( size );
 m_depth.resize( size, 0 );

 for( size_t i = 0; i < size; i++ )
 m_data[i] = i;
 }

Member Function Documentation

find()

int disjoint_set::find ( int  aVal )

inline

Definition at line 60 of file ratsnest_data.cpp.

 {
 int root = aVal;

 while( m_data[root] != root )
 root = m_data[root];

 // Compress the path
 while( m_data[aVal] != aVal )
 {
 auto& tmp = m_data[aVal];
 aVal = tmp;
 tmp = root;
 }

 return root;
 }

unite()

bool disjoint_set::unite ( int  aVal1, int  aVal2  )

inline

Definition at line 79 of file ratsnest_data.cpp.

 {
 aVal1 = find( aVal1 );
 aVal2 = find( aVal2 );

 if( aVal1 != aVal2 )
 {
 if( m_depth[aVal1] < m_depth[aVal2] )
 {
 m_data[aVal1] = aVal2;
 }
 else
 {
 m_data[aVal2] = aVal1;

 if( m_depth[aVal1] == m_depth[aVal2] )
 m_depth[aVal1]++;
 }

 return true;
 }

 return false;
 }

References find.

Member Data Documentation

m_data

std::vector<int> disjoint_set::m_data

private

Definition at line 105 of file ratsnest_data.cpp.

m_depth

std::vector<int> disjoint_set::m_depth

private

Definition at line 106 of file ratsnest_data.cpp.

---

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

• ratsnest_data.cpp