KiCad PCB EDA Suite
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.

52  {
53  m_data.resize( size );
54  m_depth.resize( size, 0 );
55 
56  for( size_t i = 0; i < size; i++ )
57  m_data[i] = i;
58  }
std::vector< int > m_depth
std::vector< int > m_data

Member Function Documentation

◆ find()

int disjoint_set::find ( int  aVal)
inline

Definition at line 60 of file ratsnest_data.cpp.

61  {
62  int root = aVal;
63 
64  while( m_data[root] != root )
65  root = m_data[root];
66 
67  // Compress the path
68  while( m_data[aVal] != aVal )
69  {
70  auto& tmp = m_data[aVal];
71  aVal = tmp;
72  tmp = root;
73  }
74 
75  return root;
76  }
std::vector< int > m_data

◆ unite()

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

Definition at line 79 of file ratsnest_data.cpp.

80  {
81  aVal1 = find( aVal1 );
82  aVal2 = find( aVal2 );
83 
84  if( aVal1 != aVal2 )
85  {
86  if( m_depth[aVal1] < m_depth[aVal2] )
87  {
88  m_data[aVal1] = aVal2;
89  }
90  else
91  {
92  m_data[aVal2] = aVal1;
93 
94  if( m_depth[aVal1] == m_depth[aVal2] )
95  m_depth[aVal1]++;
96  }
97 
98  return true;
99  }
100 
101  return false;
102  }
std::vector< int > m_depth
int find(int aVal)
std::vector< int > m_data

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: