Rosetta 3.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Member Functions | Private Attributes | List of all members
core::graph::DisjointSets Class Reference

#include <DisjointSets.hh>

Collaboration diagram for core::graph::DisjointSets:
Collaboration graph
[legend]

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

core::graph::DisjointSets::DisjointSets ( )

default constructor, for when number of nodes is not known

DisjointSets::DisjointSets()

core::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.

DisjointSets::DisjointSets()

References n_nodes(), and nodes_.

Member Function Documentation

utility::vector1< platform::Size > core::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)

DisjointSets::disjoint_set_sizes()

References ds_find(), n_nodes(), and nodes_.

Referenced by core::pack::interaction_graph::HPatchInteractionGraph< V, E, G >::calculate_alt_state_hpatch_score(), and core::scoring::SecondaryStructurePotential::sheets_from_dimers().

platform::Size core::graph::DisjointSets::ds_find ( platform::Size  node_id) const
void core::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

DisjointSets::ds_make_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 core::graph::DisjointSets::ds_union ( platform::Size  node1,
platform::Size  node2 
)
platform::Size core::graph::DisjointSets::n_disjoint_sets ( ) const

count the number of disjoint sets. O(N)

DisjointSets::n_disjoint_sets()

References n_nodes(), and nodes_.

Referenced by protocols::forge::methods::replace().

platform::Size core::graph::DisjointSets::n_nodes ( ) const
DS_Node const& core::graph::DisjointSets::node ( platform::Size  node_id) const
inline
utility::vector1< platform::Size > core::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.

DisjointSets::nodes_in_set()

References ds_find(), and n_nodes().

Referenced by core::scoring::SecondaryStructurePotential::sheets_from_dimers().

std::map< platform::Size, utility::vector1< platform::Size > > core::graph::DisjointSets::sets ( ) const

Member Data Documentation

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

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