dsac::graph::Partition< T > Class Template Reference

#include <partition.h>

Collaboration diagram for dsac::graph::Partition< T >:

Data Structures
class	Position

Public Member Functions
Position	make_cluster (T elem)
	Adds the given element to the universe and returns its Position token.
Position	find (Position p)
void	combine (Position p, Position q)
	Combines the clusters containing elements indicated by p and q (if not already the same cluster)

Detailed Description

template<typename T>
class dsac::graph::Partition< T >

A representation of a universe of elements organized into disjoint sets

This implementation uses a tree-based representation of sets with path compression during the find operation and performing union with union-by-size heuristic

Member Function Documentation

combine()

template<typename T >

void dsac::graph::Partition< T >::combine ( Position  p, Position  q  )

inline

Combines the clusters containing elements indicated by p and q (if not already the same cluster)

Here is the call graph for this function:

find()

template<typename T >

Position dsac::graph::Partition< T >::find ( Position  p )

inline

Finds the cluster currently containing the element indicated by Position p and returns the Position for the cluster's leader

Here is the call graph for this function:

make_cluster()

template<typename T >

Position dsac::graph::Partition< T >::make_cluster ( T  elem )

inline

Adds the given element to the universe and returns its Position token.

---

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

• dsac/graph/partition.h