Rosetta  2020.37
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Types | Public Member Functions | Protected Member Functions | Private Attributes | List of all members
utility::graph::LowMemGraph< _Node, _Edge > Class Template Reference

A graph with low memory use and constant time edge insertion. Extensible. For general use, use utility::graph::DefaultLowMemGraph. More...

#include <LowMemGraph.hh>

Inheritance diagram for utility::graph::LowMemGraph< _Node, _Edge >:
Inheritance graph
[legend]

Public Types

typedef LowMemGraph< _LMNode,
_LMEdge > 
THIS
 
typedef _LMNode LMNode
 
typedef _LMEdge LMEdge
 

Public Member Functions

 LowMemGraph ()
 ctor More...
 
 LowMemGraph (platform::Size num_nodes)
 num nodes ctor More...
 
platform::Size num_nodes () const
 the number of nodes in the graph More...
 
LMEdgefind_edge (platform::Size node1, platform::Size node2)
 returns a pointer to the edge connecting nodes node1 and node2, if that edge exists in the graph, o.w. returns 0. Does not focus the graph on this edge More...
 
LMEdge const * find_edge (platform::Size node1, platform::Size node2) const
 returns a const pointer to the edge connecting nodes node1 and node2, if that edge exists in the graph, o.w. returns 0. Does not focus the graph on this edge More...
 
void delete_everything ()
 deallocate all nodes and edges from the graph More...
 
LMNode const * get_node (uint32_t index) const override
 Get a const pointer to a node. More...
 
LMNodeget_node (uint32_t index) override
 Get a non-const pointer to a node. More...
 
void print_vertices () const
 calls print() on each of the nodes in the graph More...
 
platform::Size num_edges () const
 How many edges are there in the graph? More...
 
platform::Size internal_edge_list_size () const override
 How many slots are there internally. Used for unit testing. More...
 
void set_num_nodes (uint32_t num_nodes)
 set the number of nodes in the graph – deletes any existing edges and nodes in the graph More...
 
template<typename... Args>
LMEdgeadd_edge (uint32_t node1, uint32_t node2, Args &&...args)
 add an edge between two vertices. Returns a pointer to the edge after its been added, allowing the calling function to immediately set data for this edge. WARNING!!! After adding an edge, other edge pointers are not guarenteed to be valid!! More...
 
LMEdgeadd_edge (LowMemEdge const *example_edge)
 add an edge between two vertices. Returns a pointer to the edge after its been added, allowing the calling function to immediately set data for this edge. WARNING!!! After adding an edge, other edge pointers are not guarenteed to be valid!! More...
 
bool get_edge_exists (uint32_t node1, uint32_t node2) const
 is an edge already present in the graph? O(V) worst case. O(1) iff all vertices have O(1) edges More...
 
LowMemEdgeListIter edge_list_begin ()
 returns a non-const iterator to the beginning of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex More...
 
LowMemEdgeListConstIter const_edge_list_begin () const
 returns a const iterator to the beginning of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex More...
 
LowMemEdgeListIter edge_list_end ()
 returns a non-const iterator to the end of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex More...
 
LowMemEdgeListConstIter const_edge_list_end () const
 returns a const iterator to the end of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex More...
 
void delete_edge (LowMemEdge *edge)
 remove an edge from the graph More...
 
void drop_all_edges_for_node (uint32_t index) override
 delete all the edges for a single vertex in the graph More...
 
void drop_all_edges ()
 delete all the edges present in the graph More...
 
virtual platform::Size count_static_memory () const
 memory accounting scheme More...
 
virtual platform::Size count_dynamic_memory () const
 memory accounting scheme More...
 
platform::Size getTotalMemoryUsage ()
 returns a count of all the memory used by every vertex and edge in a graph by invoking the "polymorphic" count_static_memory and count_dynamic_memory of each (possibly derived) node and edge object as well as for the (possibly derived) graph class. As long as the derived LMEdge and LMNode classes implement count_dynamic_memory() and count_static_memory(), they will be called even though they aren't technically overriden More...
 
- Public Member Functions inherited from utility::graph::LowMemGraphBase
 LowMemGraphBase ()
 
 ~LowMemGraphBase () override
 
- Public Member Functions inherited from utility::VirtualBase
 VirtualBase ()=default
 Default constructor. More...
 
virtual ~VirtualBase ()=default
 The virtual destructor is one of the main reasons for the VirtualBase class. More...
 
 VirtualBase (VirtualBase const &)=default
 
 VirtualBase (VirtualBase &&)=default
 
VirtualBaseoperator= (VirtualBase const &)=default
 
VirtualBaseoperator= (VirtualBase &&)=default
 

Protected Member Functions

uint32_t internal_create_new_node (uint32_t node_ind)
 
template<typename... Args>
platform::Size internal_create_new_edge (uint32_t index1, uint32_t index2, Args &&...args)
 
LMEdge const * internal_get_edge (platform::Size offset) const override
 
LMEdgeinternal_get_edge (platform::Size offset) override
 

Private Attributes

utility::vector1< LMNodenodes_
 
utility::vector1< LMEdgeedges_
 
utility::vector1< uint32_tdeleted_edges_offsets_
 

Detailed Description

template<class _Node, class _Edge>
class utility::graph::LowMemGraph< _Node, _Edge >

A graph with low memory use and constant time edge insertion. Extensible. For general use, use utility::graph::DefaultLowMemGraph.

Edges are 8 bytes and nodes are 32 bytes + 8 bytes for each connected edge.

Due to an implementation detail, adding an edge invalidates all edge pointers. Be sure not to hold any Edge* when adding new edges.

Deleting edges does not decrease memory use. Memory may only be recaptured by calling set_num_edges() or delete_everything()

If one wishes to inherit LowMemGraph, the correct way to inherit is:
    class MyClass : public LowMemGraph<MyNode,MyEdge> {
        typedef LowMemGraph<MyNode,MyEdge> PARENT;
Then only count_static_memory and count_dynamic_memory need to be overwritten.

See core/scoring/hbonds/graph/HBondGraph.hh for example on how to inherit.
Remarks
This class saves an extra 8 bytes per edge by not storing a list of pointers to a pool, but instead using templates. Templates cause all sorts of problems and therefore their use here was limited. Unless absolutely necessary, use the base classes instead of the template types. Under almost all circumstances, it is possible to fully extend this class without introducing any more templates. Look at LowMemGraphBase for instance. This class allows LowMemEdge and LowMemNode to interact with LowMemGraph without themselves needing to be templated.

Additionally, the entire implementation of LowMemGraph is left in the .hh file. Templates are weird and putting it in the .cc file is likely to cause weird linking errors.

Member Typedef Documentation

template<class _Node , class _Edge >
typedef _LMEdge utility::graph::LowMemGraph< _Node, _Edge >::LMEdge
template<class _Node , class _Edge >
typedef _LMNode utility::graph::LowMemGraph< _Node, _Edge >::LMNode
template<class _Node , class _Edge >
typedef LowMemGraph<_LMNode, _LMEdge> utility::graph::LowMemGraph< _Node, _Edge >::THIS

Constructor & Destructor Documentation

template<class _Node , class _Edge >
utility::graph::LowMemGraph< _Node, _Edge >::LowMemGraph ( )
inline

ctor

template<class _Node , class _Edge >
utility::graph::LowMemGraph< _Node, _Edge >::LowMemGraph ( platform::Size  num_nodes)
inline

num nodes ctor

This does not suffer from the same limitations as utility::graph::Graph

References utility::graph::LowMemGraph< _Node, _Edge >::set_num_nodes().

Member Function Documentation

template<class _Node , class _Edge >
template<typename... Args>
LMEdge* utility::graph::LowMemGraph< _Node, _Edge >::add_edge ( uint32_t  node1,
uint32_t  node2,
Args &&...  args 
)
inline

add an edge between two vertices. Returns a pointer to the edge after its been added, allowing the calling function to immediately set data for this edge. WARNING!!! After adding an edge, other edge pointers are not guarenteed to be valid!!

References auto-DRRAFTER_setup::args, debug_assert, utility::graph::LowMemGraph< _Node, _Edge >::get_edge_exists(), utility::graph::LowMemGraph< _Node, _Edge >::internal_create_new_edge(), utility::graph::LowMemGraph< _Node, _Edge >::internal_get_edge(), utility::graph::LowMemGraph< _Node, _Edge >::nodes_, and erraser_analysis::temp.

Referenced by utility::graph::LowMemGraph< _Node, _Edge >::add_edge().

template<class _Node , class _Edge >
LMEdge* utility::graph::LowMemGraph< _Node, _Edge >::add_edge ( LowMemEdge const *  example_edge)
inline

add an edge between two vertices. Returns a pointer to the edge after its been added, allowing the calling function to immediately set data for this edge. WARNING!!! After adding an edge, other edge pointers are not guarenteed to be valid!!

References utility::graph::LowMemGraph< _Node, _Edge >::add_edge(), utility::graph::LowMemEdge::get_first_node_ind(), and utility::graph::LowMemEdge::get_second_node_ind().

template<class _Node , class _Edge >
LowMemEdgeListConstIter utility::graph::LowMemGraph< _Node, _Edge >::const_edge_list_begin ( ) const
inline

returns a const iterator to the beginning of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex

References utility::graph::LowMemGraphBase::LowMemEdgeListConstIter.

Referenced by utility::graph::LowMemGraph< _Node, _Edge >::getTotalMemoryUsage().

template<class _Node , class _Edge >
LowMemEdgeListConstIter utility::graph::LowMemGraph< _Node, _Edge >::const_edge_list_end ( ) const
inline

returns a const iterator to the end of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex

References utility::graph::LowMemGraph< _Node, _Edge >::internal_edge_list_size(), and utility::graph::LowMemGraphBase::LowMemEdgeListConstIter.

Referenced by utility::graph::LowMemGraph< _Node, _Edge >::getTotalMemoryUsage().

template<class _Node , class _Edge >
virtual platform::Size utility::graph::LowMemGraph< _Node, _Edge >::count_dynamic_memory ( ) const
inlinevirtual
template<class _Node , class _Edge >
virtual platform::Size utility::graph::LowMemGraph< _Node, _Edge >::count_static_memory ( ) const
inlinevirtual
template<class _Node , class _Edge >
void utility::graph::LowMemGraph< _Node, _Edge >::delete_edge ( LowMemEdge edge)
inline
template<class _Node , class _Edge >
void utility::graph::LowMemGraph< _Node, _Edge >::delete_everything ( )
inline
template<class _Node , class _Edge >
void utility::graph::LowMemGraph< _Node, _Edge >::drop_all_edges ( )
inline

delete all the edges present in the graph

This function will also free memory associated with the delete edges

References utility::graph::LowMemGraph< _Node, _Edge >::drop_all_edges_for_node(), utility::graph::LowMemGraph< _Node, _Edge >::edges_, and utility::graph::LowMemGraph< _Node, _Edge >::nodes_.

template<class _Node , class _Edge >
void utility::graph::LowMemGraph< _Node, _Edge >::drop_all_edges_for_node ( uint32_t  index)
inlineoverridevirtual
template<class _Node , class _Edge >
LowMemEdgeListIter utility::graph::LowMemGraph< _Node, _Edge >::edge_list_begin ( )
inline

returns a non-const iterator to the beginning of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex

References utility::graph::LowMemGraphBase::LowMemEdgeListIter.

template<class _Node , class _Edge >
LowMemEdgeListIter utility::graph::LowMemGraph< _Node, _Edge >::edge_list_end ( )
inline

returns a non-const iterator to the end of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex

References utility::graph::LowMemGraph< _Node, _Edge >::internal_edge_list_size(), and utility::graph::LowMemGraphBase::LowMemEdgeListIter.

template<class _Node , class _Edge >
LMEdge* utility::graph::LowMemGraph< _Node, _Edge >::find_edge ( platform::Size  node1,
platform::Size  node2 
)
inline

returns a pointer to the edge connecting nodes node1 and node2, if that edge exists in the graph, o.w. returns 0. Does not focus the graph on this edge

References utility::graph::LowMemGraph< _Node, _Edge >::nodes_.

Referenced by utility::graph::LowMemGraph< _Node, _Edge >::get_edge_exists().

template<class _Node , class _Edge >
LMEdge const* utility::graph::LowMemGraph< _Node, _Edge >::find_edge ( platform::Size  node1,
platform::Size  node2 
) const
inline

returns a const pointer to the edge connecting nodes node1 and node2, if that edge exists in the graph, o.w. returns 0. Does not focus the graph on this edge

References utility::graph::LowMemGraph< _Node, _Edge >::nodes_.

template<class _Node , class _Edge >
bool utility::graph::LowMemGraph< _Node, _Edge >::get_edge_exists ( uint32_t  node1,
uint32_t  node2 
) const
inline

is an edge already present in the graph? O(V) worst case. O(1) iff all vertices have O(1) edges

References utility::graph::LowMemGraph< _Node, _Edge >::find_edge().

Referenced by utility::graph::LowMemGraph< _Node, _Edge >::add_edge(), and utility::graph::LowMemGraph< _Node, _Edge >::delete_edge().

template<class _Node , class _Edge >
LMNode const* utility::graph::LowMemGraph< _Node, _Edge >::get_node ( uint32_t  index) const
inlineoverridevirtual
template<class _Node , class _Edge >
LMNode* utility::graph::LowMemGraph< _Node, _Edge >::get_node ( uint32_t  index)
inlineoverridevirtual
template<class _Node , class _Edge >
platform::Size utility::graph::LowMemGraph< _Node, _Edge >::getTotalMemoryUsage ( )
inline

returns a count of all the memory used by every vertex and edge in a graph by invoking the "polymorphic" count_static_memory and count_dynamic_memory of each (possibly derived) node and edge object as well as for the (possibly derived) graph class. As long as the derived LMEdge and LMNode classes implement count_dynamic_memory() and count_static_memory(), they will be called even though they aren't technically overriden

References utility::graph::LowMemGraph< _Node, _Edge >::const_edge_list_begin(), utility::graph::LowMemGraph< _Node, _Edge >::const_edge_list_end(), utility::graph::LowMemGraph< _Node, _Edge >::count_dynamic_memory(), utility::graph::LowMemGraph< _Node, _Edge >::count_static_memory(), test.T200_Scoring::ii, utility::graph::LowMemGraph< _Node, _Edge >::nodes_, and utility::graph::LowMemGraph< _Node, _Edge >::num_nodes().

template<class _Node , class _Edge >
template<typename... Args>
platform::Size utility::graph::LowMemGraph< _Node, _Edge >::internal_create_new_edge ( uint32_t  index1,
uint32_t  index2,
Args &&...  args 
)
inlineprotected
template<class _Node , class _Edge >
uint32_t utility::graph::LowMemGraph< _Node, _Edge >::internal_create_new_node ( uint32_t  node_ind)
inlineprotected
template<class _Node , class _Edge >
platform::Size utility::graph::LowMemGraph< _Node, _Edge >::internal_edge_list_size ( ) const
inlineoverridevirtual
template<class _Node , class _Edge >
LMEdge const* utility::graph::LowMemGraph< _Node, _Edge >::internal_get_edge ( platform::Size  offset) const
inlineoverrideprotectedvirtual
template<class _Node , class _Edge >
LMEdge* utility::graph::LowMemGraph< _Node, _Edge >::internal_get_edge ( platform::Size  offset)
inlineoverrideprotectedvirtual
template<class _Node , class _Edge >
platform::Size utility::graph::LowMemGraph< _Node, _Edge >::num_edges ( ) const
inline
template<class _Node , class _Edge >
platform::Size utility::graph::LowMemGraph< _Node, _Edge >::num_nodes ( ) const
inline
template<class _Node , class _Edge >
void utility::graph::LowMemGraph< _Node, _Edge >::print_vertices ( ) const
inline

calls print() on each of the nodes in the graph

Will call "overriden" print in derived nodes

References test.T200_Scoring::ii, and utility::graph::LowMemGraph< _Node, _Edge >::nodes_.

template<class _Node , class _Edge >
void utility::graph::LowMemGraph< _Node, _Edge >::set_num_nodes ( uint32_t  num_nodes)
inline

Member Data Documentation

template<class _Node , class _Edge >
utility::vector1< uint32_t > utility::graph::LowMemGraph< _Node, _Edge >::deleted_edges_offsets_
private
template<class _Node , class _Edge >
utility::vector1< LMEdge > utility::graph::LowMemGraph< _Node, _Edge >::edges_
private
template<class _Node , class _Edge >
utility::vector1< LMNode > utility::graph::LowMemGraph< _Node, _Edge >::nodes_
private

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