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

[legend]

Public Types
typedef LowMemGraph< _LMNode, _LMEdge >	THIS

typedef _LMNode	LMNode

typedef _LMEdge	LMEdge

Public Types inherited from utility::pointer::ReferenceCount
typedef platform::Size	Size

typedef platform::Size	size_type

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

LMEdge *	find_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...

LMNode *	get_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>
LMEdge *	add_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...

LMEdge *	add_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 ()

virtual	~LowMemGraphBase ()

Public Member Functions inherited from utility::pointer::ReferenceCount
	ReferenceCount ()
	Default constructor. More...

virtual	~ReferenceCount ()

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

LMEdge *	internal_get_edge (platform::Size offset) override

Private Attributes
utility::vector1< LMNode >	nodes_

utility::vector1< LMEdge >	edges_

utility::vector1< uint32_t >	deleted_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 DRRAFTER::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

memory accounting scheme

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

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

template<class _Node , class _Edge >

virtual platform::Size utility::graph::LowMemGraph< _Node, _Edge >::count_static_memory ( ) const

inlinevirtual

memory accounting scheme

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

template<class _Node , class _Edge >

void utility::graph::LowMemGraph< _Node, _Edge >::delete_edge ( LowMemEdge * edge )

inline

remove an edge from the graph

References debug_assert, utility::graph::LowMemGraph< _Node, _Edge >::deleted_edges_offsets_, utility::graph::LowMemGraph< _Node, _Edge >::get_edge_exists(), utility::graph::LowMemEdge::get_first_node_ind(), utility::graph::LowMemEdge::get_second_node_ind(), utility::graph::LowMemEdge::internal_delete_self(), utility::graph::LowMemGraph< _Node, _Edge >::nodes_, and basic::options::OptionKeys::rna::denovo::offset.

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

template<class _Node , class _Edge >

void utility::graph::LowMemGraph< _Node, _Edge >::delete_everything ( )

inline

deallocate all nodes and edges from the graph

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

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

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

delete all the edges for a single vertex in the graph

This function will not free memory associated with the deleted edges

Implements utility::graph::LowMemGraphBase.

References debug_assert, utility::graph::LowMemGraph< _Node, _Edge >::delete_edge(), utility::graph::LowMemGraph< _Node, _Edge >::edges_, ObjexxFCL::index(), utility::graph::LowMemGraph< _Node, _Edge >::nodes_, and basic::options::OptionKeys::rna::denovo::offset.

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

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

Get a const pointer to a node.

Implements utility::graph::LowMemGraphBase.

References debug_assert, ObjexxFCL::index(), and utility::graph::LowMemGraph< _Node, _Edge >::nodes_.

template<class _Node , class _Edge >

LMNode* utility::graph::LowMemGraph< _Node, _Edge >::get_node ( uint32_t index )

inlineoverridevirtual

Get a non-const pointer to a node.

Implements utility::graph::LowMemGraphBase.

References debug_assert, ObjexxFCL::index(), and utility::graph::LowMemGraph< _Node, _Edge >::nodes_.

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>