Rosetta  2020.37
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Member Functions | Private Attributes | List of all members
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::Sizedisjoint_set_sizes () const
 count the size of each disjoint set. O(N) More...
 
utility::vector1< platform::Sizenodes_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_Nodenodes_
 

Constructor & Destructor Documentation

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

default constructor, for when number of nodes is not known

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 test.T200_Scoring::ii, n_nodes(), and nodes_.

Member Function Documentation

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(), test.T200_Scoring::ii, n_nodes(), and nodes_.

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().

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_.

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.

platform::Size utility::graph::DisjointSets::n_disjoint_sets ( ) const

count the number of disjoint sets. O(N)

References test.T200_Scoring::ii, n_nodes(), and 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().

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

DS_Node read access.

References nodes_.

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(), and n_nodes().

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(), and n_nodes().

Member Data Documentation

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

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