Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors, descendants). More...

#include <cluster_linearize.h>

Classes
struct	Entry
	Information about a single transaction. More...

Public Member Functions
	DepGraph () noexcept=default

	DepGraph (const DepGraph &) noexcept=default

	DepGraph (DepGraph &&) noexcept=default

DepGraph &	operator= (const DepGraph &) noexcept=default

DepGraph &	operator= (DepGraph &&) noexcept=default

	DepGraph (ClusterIndex ntx) noexcept
	Construct a DepGraph object for ntx transactions, with no dependencies. More...

	DepGraph (const Cluster< SetType > &cluster) noexcept
	Construct a DepGraph object given a cluster. More...

auto	TxCount () const noexcept
	Get the number of transactions in the graph. More...

const FeeFrac &	FeeRate (ClusterIndex i) const noexcept
	Get the feerate of a given transaction i. More...

FeeFrac &	FeeRate (ClusterIndex i) noexcept
	Get the mutable feerate of a given transaction i. More...

const SetType &	Ancestors (ClusterIndex i) const noexcept
	Get the ancestors of a given transaction i. More...

const SetType &	Descendants (ClusterIndex i) const noexcept
	Get the descendants of a given transaction i. More...

ClusterIndex	AddTransaction (const FeeFrac &feefrac) noexcept
	Add a new unconnected transaction to this transaction graph (at the end), and return its ClusterIndex. More...

void	AddDependency (ClusterIndex parent, ClusterIndex child) noexcept
	Modify this transaction graph, adding a dependency between a specified parent and child. More...

FeeFrac	FeeRate (const SetType &elems) const noexcept
	Compute the aggregate feerate of a set of nodes in this graph. More...

SetType	FindConnectedComponent (const SetType &todo) const noexcept
	Find some connected component within the subset "todo" of this graph. More...

bool	IsConnected (const SetType &subset) const noexcept
	Determine if a subset is connected. More...

bool	IsConnected () const noexcept
	Determine if this entire graph is connected. More...

void	AppendTopo (std::vector< ClusterIndex > &list, const SetType &select) const noexcept
	Append the entries of select to list in a topologically valid order. More...

Private Attributes
std::vector< Entry >	entries
	Data for each transaction, in the same order as the Cluster it was constructed from. More...

Friends
bool	operator== (const DepGraph &, const DepGraph &) noexcept=default
	Equality operator (primarily for testing purposes). More...

Detailed Description

template<typename SetType>
class cluster_linearize::DepGraph< SetType >

Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors, descendants).

Definition at line 36 of file cluster_linearize.h.

Constructor & Destructor Documentation

◆ DepGraph() [1/5]

template<typename SetType>

cluster_linearize::DepGraph< SetType >::DepGraph ( )

defaultnoexcept

◆ DepGraph() [2/5]

template<typename SetType>

cluster_linearize::DepGraph< SetType >::DepGraph ( const DepGraph< SetType > & )

defaultnoexcept

◆ DepGraph() [3/5]

template<typename SetType>

cluster_linearize::DepGraph< SetType >::DepGraph ( DepGraph< SetType > && )

defaultnoexcept

◆ DepGraph() [4/5]

template<typename SetType>

cluster_linearize::DepGraph< SetType >::DepGraph ( ClusterIndex ntx )

inlineexplicitnoexcept

Construct a DepGraph object for ntx transactions, with no dependencies.

Complexity: O(N) where N=ntx.

Definition at line 75 of file cluster_linearize.h.

◆ DepGraph() [5/5]

template<typename SetType>

cluster_linearize::DepGraph< SetType >::DepGraph ( const Cluster< SetType > & cluster )

inlineexplicitnoexcept

Construct a DepGraph object given a cluster.

Complexity: O(N^2) where N=cluster.size().

Definition at line 89 of file cluster_linearize.h.

Member Function Documentation

◆ AddDependency()

template<typename SetType>

void cluster_linearize::DepGraph< SetType >::AddDependency	(	ClusterIndex	parent,
		ClusterIndex	child
	)

inlinenoexcept

Modify this transaction graph, adding a dependency between a specified parent and child.

Complexity: O(N) where N=TxCount().

Definition at line 149 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AddTransaction()

template<typename SetType>

ClusterIndex cluster_linearize::DepGraph< SetType >::AddTransaction ( const FeeFrac & feefrac )

inlinenoexcept

Add a new unconnected transaction to this transaction graph (at the end), and return its ClusterIndex.

Complexity: O(1) (amortized, due to resizing of backing vector).

Definition at line 137 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Ancestors()

template<typename SetType>

const SetType& cluster_linearize::DepGraph< SetType >::Ancestors ( ClusterIndex i ) const

inlinenoexcept

Get the ancestors of a given transaction i.

Complexity: O(1).

Definition at line 128 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ AppendTopo()

template<typename SetType>

void cluster_linearize::DepGraph< SetType >::AppendTopo	(	std::vector< ClusterIndex > &	list,
		const SetType &	select
	)		const

inlinenoexcept

Append the entries of select to list in a topologically valid order.

Complexity: O(select.Count() * log(select.Count())).

Definition at line 224 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ Descendants()

template<typename SetType>

const SetType& cluster_linearize::DepGraph< SetType >::Descendants ( ClusterIndex i ) const

inlinenoexcept

Get the descendants of a given transaction i.

Complexity: O(1).

Definition at line 130 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ FeeRate() [1/3]

template<typename SetType>

const FeeFrac& cluster_linearize::DepGraph< SetType >::FeeRate ( ClusterIndex i ) const

inlinenoexcept

Get the feerate of a given transaction i.

Complexity: O(1).

Definition at line 124 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ FeeRate() [2/3]

template<typename SetType>

FeeFrac& cluster_linearize::DepGraph< SetType >::FeeRate ( ClusterIndex i )

inlinenoexcept

Get the mutable feerate of a given transaction i.

Complexity: O(1).

Definition at line 126 of file cluster_linearize.h.

◆ FeeRate() [3/3]

template<typename SetType>

FeeFrac cluster_linearize::DepGraph< SetType >::FeeRate ( const SetType & elems ) const

inlinenoexcept

Compute the aggregate feerate of a set of nodes in this graph.

Complexity: O(N) where N=elems.Count().

Definition at line 169 of file cluster_linearize.h.

◆ FindConnectedComponent()

template<typename SetType>

SetType cluster_linearize::DepGraph< SetType >::FindConnectedComponent ( const SetType & todo ) const

inlinenoexcept

Find some connected component within the subset "todo" of this graph.

Specifically, this finds the connected component which contains the first transaction of todo (if any).

Two transactions are considered connected if they are both in todo, and one is an ancestor of the other in the entire graph (so not just within todo), or transitively there is a path of transactions connecting them. This does mean that if todo contains a transaction and a grandparent, but misses the parent, they will still be part of the same component.

Complexity: O(ret.Count()).

Definition at line 188 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ IsConnected() [1/2]

template<typename SetType>

bool cluster_linearize::DepGraph< SetType >::IsConnected ( const SetType & subset ) const

inlinenoexcept

Determine if a subset is connected.

Complexity: O(subset.Count()).

Definition at line 209 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ IsConnected() [2/2]

template<typename SetType>

bool cluster_linearize::DepGraph< SetType >::IsConnected ( ) const

inlinenoexcept

Determine if this entire graph is connected.

Complexity: O(TxCount()).

Definition at line 218 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator=() [1/2]

template<typename SetType>

DepGraph& cluster_linearize::DepGraph< SetType >::operator= ( const DepGraph< SetType > & )

defaultnoexcept

◆ operator=() [2/2]

template<typename SetType>

DepGraph& cluster_linearize::DepGraph< SetType >::operator= ( DepGraph< SetType > && )

defaultnoexcept

◆ TxCount()

template<typename SetType>

auto cluster_linearize::DepGraph< SetType >::TxCount ( ) const

inlinenoexcept

Get the number of transactions in the graph.

Complexity: O(1).

Definition at line 122 of file cluster_linearize.h.

Here is the caller graph for this function:

Friends And Related Function Documentation

◆ operator==

template<typename SetType>

bool operator==	(	const DepGraph< SetType > &	,
		const DepGraph< SetType > &
	)

friend

Equality operator (primarily for testing purposes).

Member Data Documentation

◆ entries

template<typename SetType>

std::vector<Entry> cluster_linearize::DepGraph< SetType >::entries

private

Data for each transaction, in the same order as the Cluster it was constructed from.

Definition at line 58 of file cluster_linearize.h.

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

src/cluster_linearize.h

Classes

Public Member Functions

Private Attributes

Friends

Detailed Description

template<typename SetType> class cluster_linearize::DepGraph< SetType >

Constructor & Destructor Documentation

◆ DepGraph() [1/5]

◆ DepGraph() [2/5]

◆ DepGraph() [3/5]

◆ DepGraph() [4/5]

◆ DepGraph() [5/5]

Member Function Documentation

◆ AddDependency()

◆ AddTransaction()

◆ Ancestors()

◆ AppendTopo()

◆ Descendants()

◆ FeeRate() [1/3]

◆ FeeRate() [2/3]

◆ FeeRate() [3/3]

◆ FindConnectedComponent()

◆ IsConnected() [1/2]

◆ IsConnected() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ TxCount()

Friends And Related Function Documentation

◆ operator==

Member Data Documentation

◆ entries

template<typename SetType>
class cluster_linearize::DepGraph< SetType >