Rosetta
Public Types | Public Member Functions | Protected Member Functions | Private Attributes | List of all members
utility::graph::LowMemGraph< _LMNode, _LMEdge > Class Template Reference

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

#include <LowMemGraph.hh>

Inheritance diagram for utility::graph::LowMemGraph< _LMNode, _LMEdge >:
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. @detail 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. @detail 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. @detail 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 _LMNode, class _LMEdge>
class utility::graph::LowMemGraph< _LMNode, _LMEdge >

A graph with low memory use and constant time edge insertion. Extensible. @detail 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

◆ LMEdge

template<class _LMNode , class _LMEdge >
typedef _LMEdge utility::graph::LowMemGraph< _LMNode, _LMEdge >::LMEdge

◆ LMNode

template<class _LMNode , class _LMEdge >
typedef _LMNode utility::graph::LowMemGraph< _LMNode, _LMEdge >::LMNode

◆ THIS

template<class _LMNode , class _LMEdge >
typedef LowMemGraph<_LMNode, _LMEdge> utility::graph::LowMemGraph< _LMNode, _LMEdge >::THIS

Constructor & Destructor Documentation

◆ LowMemGraph() [1/2]

template<class _LMNode , class _LMEdge >
utility::graph::LowMemGraph< _LMNode, _LMEdge >::LowMemGraph ( )
inline

ctor

◆ LowMemGraph() [2/2]

template<class _LMNode , class _LMEdge >
utility::graph::LowMemGraph< _LMNode, _LMEdge >::LowMemGraph ( platform::Size  num_nodes)
inline

Member Function Documentation

◆ add_edge() [1/2]

template<class _LMNode , class _LMEdge >
LMEdge* utility::graph::LowMemGraph< _LMNode, _LMEdge >::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. @detail WARNING!!! After adding an edge, other edge pointers are not guarenteed to be valid!!

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

◆ add_edge() [2/2]

template<class _LMNode , class _LMEdge >
template<typename... Args>
LMEdge* utility::graph::LowMemGraph< _LMNode, _LMEdge >::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. @detail WARNING!!! After adding an edge, other edge pointers are not guarenteed to be valid!!

References find_lowest_scoring_relaxed_struct::args, debug_assert, utility::graph::LowMemGraph< _LMNode, _LMEdge >::get_edge_exists(), utility::graph::LowMemGraph< _LMNode, _LMEdge >::internal_create_new_edge(), utility::graph::LowMemGraph< _LMNode, _LMEdge >::internal_get_edge(), utility::graph::LowMemGraph< _LMNode, _LMEdge >::nodes_, and erraser_analysis::temp.

Referenced by utility::graph::LowMemGraph< _LMNode, _LMEdge >::add_edge().

◆ const_edge_list_begin()

template<class _LMNode , class _LMEdge >
LowMemEdgeListConstIter utility::graph::LowMemGraph< _LMNode, _LMEdge >::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< _LMNode, _LMEdge >::getTotalMemoryUsage().

◆ const_edge_list_end()

template<class _LMNode , class _LMEdge >
LowMemEdgeListConstIter utility::graph::LowMemGraph< _LMNode, _LMEdge >::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< _LMNode, _LMEdge >::internal_edge_list_size(), and utility::graph::LowMemGraphBase::LowMemEdgeListConstIter.

Referenced by utility::graph::LowMemGraph< _LMNode, _LMEdge >::getTotalMemoryUsage().

◆ count_dynamic_memory()

template<class _LMNode , class _LMEdge >
virtual platform::Size utility::graph::LowMemGraph< _LMNode, _LMEdge >::count_dynamic_memory ( ) const
inlinevirtual

◆ count_static_memory()

template<class _LMNode , class _LMEdge >
virtual platform::Size utility::graph::LowMemGraph< _LMNode, _LMEdge >::count_static_memory ( ) const
inlinevirtual

◆ delete_edge()

template<class _LMNode , class _LMEdge >
void utility::graph::LowMemGraph< _LMNode, _LMEdge >::delete_edge ( LowMemEdge edge)
inline

◆ delete_everything()

template<class _LMNode , class _LMEdge >
void utility::graph::LowMemGraph< _LMNode, _LMEdge >::delete_everything ( )
inline

◆ drop_all_edges()

template<class _LMNode , class _LMEdge >
void utility::graph::LowMemGraph< _LMNode, _LMEdge >::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< _LMNode, _LMEdge >::drop_all_edges_for_node(), utility::graph::LowMemGraph< _LMNode, _LMEdge >::edges_, and utility::graph::LowMemGraph< _LMNode, _LMEdge >::nodes_.

◆ drop_all_edges_for_node()

template<class _LMNode , class _LMEdge >
void utility::graph::LowMemGraph< _LMNode, _LMEdge >::drop_all_edges_for_node ( uint32_t  index)
inlineoverridevirtual

◆ edge_list_begin()

template<class _LMNode , class _LMEdge >
LowMemEdgeListIter utility::graph::LowMemGraph< _LMNode, _LMEdge >::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.

◆ edge_list_end()

template<class _LMNode , class _LMEdge >
LowMemEdgeListIter utility::graph::LowMemGraph< _LMNode, _LMEdge >::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< _LMNode, _LMEdge >::internal_edge_list_size(), and utility::graph::LowMemGraphBase::LowMemEdgeListIter.

◆ find_edge() [1/2]

template<class _LMNode , class _LMEdge >
LMEdge* utility::graph::LowMemGraph< _LMNode, _LMEdge >::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< _LMNode, _LMEdge >::nodes_.

Referenced by utility::graph::LowMemGraph< _LMNode, _LMEdge >::get_edge_exists().

◆ find_edge() [2/2]

template<class _LMNode , class _LMEdge >
LMEdge const* utility::graph::LowMemGraph< _LMNode, _LMEdge >::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< _LMNode, _LMEdge >::nodes_.

◆ get_edge_exists()

template<class _LMNode , class _LMEdge >
bool utility::graph::LowMemGraph< _LMNode, _LMEdge >::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< _LMNode, _LMEdge >::find_edge().

Referenced by utility::graph::LowMemGraph< _LMNode, _LMEdge >::add_edge(), and utility::graph::LowMemGraph< _LMNode, _LMEdge >::delete_edge().

◆ get_node() [1/2]

template<class _LMNode , class _LMEdge >
LMNode const* utility::graph::LowMemGraph< _LMNode, _LMEdge >::get_node ( uint32_t  index) const
inlineoverridevirtual

◆ get_node() [2/2]

template<class _LMNode , class _LMEdge >
LMNode* utility::graph::LowMemGraph< _LMNode, _LMEdge >::get_node ( uint32_t  index)
inlineoverridevirtual

Get a non-const pointer to a node.

Implements utility::graph::LowMemGraphBase.

References debug_assert, and utility::graph::LowMemGraph< _LMNode, _LMEdge >::nodes_.

◆ getTotalMemoryUsage()

template<class _LMNode , class _LMEdge >
platform::Size utility::graph::LowMemGraph< _LMNode, _LMEdge >::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. @detail 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< _LMNode, _LMEdge >::const_edge_list_begin(), utility::graph::LowMemGraph< _LMNode, _LMEdge >::const_edge_list_end(), utility::graph::LowMemGraph< _LMNode, _LMEdge >::count_dynamic_memory(), utility::graph::LowMemGraph< _LMNode, _LMEdge >::count_static_memory(), create_a3b_hbs::ii, utility::graph::LowMemGraph< _LMNode, _LMEdge >::nodes_, and utility::graph::LowMemGraph< _LMNode, _LMEdge >::num_nodes().

◆ internal_create_new_edge()

template<class _LMNode , class _LMEdge >
template<typename... Args>
platform::Size utility::graph::LowMemGraph< _LMNode, _LMEdge >::internal_create_new_edge ( uint32_t  index1,
uint32_t  index2,
Args &&...  args 
)
inlineprotected

◆ internal_create_new_node()

template<class _LMNode , class _LMEdge >
uint32_t utility::graph::LowMemGraph< _LMNode, _LMEdge >::internal_create_new_node ( uint32_t  node_ind)
inlineprotected

◆ internal_edge_list_size()

template<class _LMNode , class _LMEdge >
platform::Size utility::graph::LowMemGraph< _LMNode, _LMEdge >::internal_edge_list_size ( ) const
inlineoverridevirtual

◆ internal_get_edge() [1/2]

template<class _LMNode , class _LMEdge >
LMEdge const* utility::graph::LowMemGraph< _LMNode, _LMEdge >::internal_get_edge ( platform::Size  offset) const
inlineoverrideprotectedvirtual

◆ internal_get_edge() [2/2]

template<class _LMNode , class _LMEdge >
LMEdge* utility::graph::LowMemGraph< _LMNode, _LMEdge >::internal_get_edge ( platform::Size  offset)
inlineoverrideprotectedvirtual

◆ num_edges()

template<class _LMNode , class _LMEdge >
platform::Size utility::graph::LowMemGraph< _LMNode, _LMEdge >::num_edges ( ) const
inline

◆ num_nodes()

template<class _LMNode , class _LMEdge >
platform::Size utility::graph::LowMemGraph< _LMNode, _LMEdge >::num_nodes ( ) const
inline

◆ print_vertices()

template<class _LMNode , class _LMEdge >
void utility::graph::LowMemGraph< _LMNode, _LMEdge >::print_vertices ( ) const
inline

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

Will call "overriden" print in derived nodes

References create_a3b_hbs::ii, and utility::graph::LowMemGraph< _LMNode, _LMEdge >::nodes_.

◆ set_num_nodes()

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

Member Data Documentation

◆ deleted_edges_offsets_

template<class _LMNode , class _LMEdge >
utility::vector1< uint32_t > utility::graph::LowMemGraph< _LMNode, _LMEdge >::deleted_edges_offsets_
private

◆ edges_

template<class _LMNode , class _LMEdge >
utility::vector1< LMEdge > utility::graph::LowMemGraph< _LMNode, _LMEdge >::edges_
private

◆ nodes_

template<class _LMNode , class _LMEdge >
utility::vector1< LMNode > utility::graph::LowMemGraph< _LMNode, _LMEdge >::nodes_
private

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