utility::graph::DisjointSets Class Reference

#include <DisjointSets.hh>

Public Member Functions
	DisjointSets ()
	default constructor, for when number of nodes is not known More...
	DisjointSets (platform::Size n_nodes)
	ctor for class if the number of nodes is known upfront. Fastest. More...
platform::Size	n_nodes () const
	returns the total number of nodes More...
void	ds_make_set ()
	add a new node – as implemented, O(N) operation use the DS(platform::Size) constructor for better speed. More...
platform::Size	ds_find (platform::Size node_id) const
	return the representative for a node More...
void	ds_union (platform::Size node1, platform::Size node2)
	make it so that two nodes end up in the same set More...
DS_Node const &	node (platform::Size node_id) const
	DS_Node read access. More...
platform::Size	n_disjoint_sets () const
	count the number of disjoint sets. O(N) More...
utility::vector1< platform::Size >	disjoint_set_sizes () const
	count the size of each disjoint set. O(N) More...
utility::vector1< platform::Size >	nodes_in_set (platform::Size node_id) const
	return the nodes in the set containing the specified node. More...
std::map< platform::Size, utility::vector1< platform::Size > >	sets () const
	return a map from the representative node of each set to the list of nodes in their sets More...

Private Attributes
utility::vector1< DS_Node >	nodes_

Constructor & Destructor Documentation

DisjointSets() [1/2]

utility::graph::DisjointSets::DisjointSets ( )

default

default constructor, for when number of nodes is not known

DisjointSets() [2/2]

utility::graph::DisjointSets::DisjointSets

(

platform::Size

n_nodes

)

ctor for class if the number of nodes is known upfront. Fastest.

constructor for when number of nodes is known up front. fastest.

References create_a3b_hbs::ii, n_nodes(), and nodes_.

Member Function Documentation

disjoint_set_sizes()

utility::vector1< platform::Size > utility::graph::DisjointSets::disjoint_set_sizes

(

)

const

count the size of each disjoint set. O(N)

returns a vector1 containing the size of each disjoint set. O(N)

References ds_find(), create_a3b_hbs::ii, n_nodes(), and nodes_.

ds_find()

platform::Size utility::graph::DisjointSets::ds_find

(

platform::Size

node_id

)

const

return the representative for a node

given a node_id, return the representative for that node

References nodes_.

Referenced by disjoint_set_sizes(), ds_union(), nodes_in_set(), and sets().

ds_make_set()

void utility::graph::DisjointSets::ds_make_set

(

)

add a new node – as implemented, O(N) operation use the DS(platform::Size) constructor for better speed.

creates a new set

This implementation uses indices to objects in arrays instead of pointers and so it relies on vector push-back methods (O(N)) instead of list push-back methods (O(1)). If enough people clamour, I'll go back and make this faster...(apl)

References n_nodes(), and nodes_.

ds_union()

void utility::graph::DisjointSets::ds_union	(	platform::Size	node1,
		platform::Size	node2
	)

make it so that two nodes end up in the same set

combine two sets; make it so that two nodes end up in the same set

References ds_find(), nodes_, and basic::options::OptionKeys::legacy_sewing::rank.

n_disjoint_sets()

platform::Size utility::graph::DisjointSets::n_disjoint_sets

(

)

const

count the number of disjoint sets. O(N)

References create_a3b_hbs::ii, n_nodes(), and nodes_.

n_nodes()

platform::Size utility::graph::DisjointSets::n_nodes

(

)

const

returns the total number of nodes

References nodes_.

Referenced by disjoint_set_sizes(), DisjointSets(), ds_make_set(), n_disjoint_sets(), nodes_in_set(), and sets().

node()

DS_Node const& utility::graph::DisjointSets::node ( platform::Size  node_id ) const

inline

DS_Node read access.

References nodes_.

nodes_in_set()

utility::vector1< platform::Size > utility::graph::DisjointSets::nodes_in_set

(

platform::Size

node_id

)

const

return the nodes in the set containing the specified node.

returns a vector1 of the nodes in the set containing the specified node.

References ds_find(), create_a3b_hbs::i, and n_nodes().

sets()

std::map< platform::Size, utility::vector1< platform::Size > > utility::graph::DisjointSets::sets

(

)

const

return a map from the representative node of each set to the list of nodes in their sets

References ds_find(), create_a3b_hbs::i, and n_nodes().

Member Data Documentation

nodes_

utility::vector1< DS_Node > utility::graph::DisjointSets::nodes_

mutableprivate

Referenced by disjoint_set_sizes(), DisjointSets(), ds_find(), ds_make_set(), ds_union(), n_disjoint_sets(), n_nodes(), and node().

---

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

• src/utility/graph/DisjointSets.hh
• src/utility/graph/DisjointSets.cc