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 (const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > mapping, DepGraphIndex pos_range) noexcept
	Construct a DepGraph object given another DepGraph and a mapping from old to new. More...

const SetType &	Positions () const noexcept
	Get the set of transactions positions in use. More...

DepGraphIndex	PositionRange () const noexcept
	Get the range of positions in this DepGraph. More...

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

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

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

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

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

DepGraphIndex	AddTransaction (const FeeFrac &feefrac) noexcept
	Add a new unconnected transaction to this transaction graph (in the first available position), and return its DepGraphIndex. More...

void	RemoveTransactions (const SetType &del) noexcept
	Remove the specified positions from this DepGraph. More...

void	AddDependencies (const SetType &parents, DepGraphIndex child) noexcept
	Modify this transaction graph, adding multiple parents to a specified child. More...

SetType	GetReducedParents (DepGraphIndex i) const noexcept
	Compute the (reduced) set of parents of node i in this graph. More...

SetType	GetReducedChildren (DepGraphIndex i) const noexcept
	Compute the (reduced) set of children of node i in this graph. More...

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

SetType	GetConnectedComponent (const SetType &todo, DepGraphIndex tx) const noexcept
	Get the connected component within the subset "todo" that contains tx (which must be in todo). 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< DepGraphIndex > &list, const SetType &select) const noexcept
	Append the entries of select to list in a topologically valid order. More...

bool	IsAcyclic () const noexcept
	Check if this graph is acyclic. More...

Private Attributes
std::vector< Entry >	entries
	Data for each transaction. More...

SetType	m_used
	Which positions are used. More...

Friends
bool	operator== (const DepGraph &a, const DepGraph &b) noexcept
	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 28 of file cluster_linearize.h.

Constructor & Destructor Documentation

◆ DepGraph() [1/4]

template<typename SetType >

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

defaultnoexcept

◆ DepGraph() [2/4]

template<typename SetType >

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

defaultnoexcept

◆ DepGraph() [3/4]

template<typename SetType >

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

defaultnoexcept

◆ DepGraph() [4/4]

template<typename SetType >

cluster_linearize::DepGraph< SetType >::DepGraph	(	const DepGraph< SetType > &	depgraph,
		std::span< const DepGraphIndex >	mapping,
		DepGraphIndex	pos_range
	)

inlinenoexcept

Construct a DepGraph object given another DepGraph and a mapping from old to new.

Parameters

depgraph	The original DepGraph that is being remapped.
mapping	A span such that mapping[i] gives the position in the new DepGraph for position i in the old depgraph. Its size must be equal to depgraph.PositionRange(). The value of mapping[i] is ignored if position i is a hole in depgraph (i.e., if !depgraph.Positions()[i]).
pos_range	The PositionRange() for the new DepGraph. It must equal the largest value in mapping for any used position in depgraph plus 1, or 0 if depgraph.TxCount() == 0.

Complexity: O(N^2) where N=depgraph.TxCount().

Definition at line 89 of file cluster_linearize.h.

Here is the call graph for this function:

Member Function Documentation

◆ AddDependencies()

template<typename SetType >

void cluster_linearize::DepGraph< SetType >::AddDependencies	(	const SetType &	parents,
		DepGraphIndex	child
	)

inlinenoexcept

Modify this transaction graph, adding multiple parents to a specified child.

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

Definition at line 177 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 >

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

inlinenoexcept

Add a new unconnected transaction to this transaction graph (in the first available position), and return its DepGraphIndex.

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

Definition at line 133 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ Ancestors()

template<typename SetType >

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

inlinenoexcept

Get the ancestors 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:

◆ AppendTopo()

template<typename SetType >

void cluster_linearize::DepGraph< SetType >::AppendTopo	(	std::vector< DepGraphIndex > &	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 313 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ Descendants()

template<typename SetType >

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

inlinenoexcept

Get the descendants of a given transaction i.

Complexity: O(1).

Definition at line 126 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ FeeRate() [1/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 246 of file cluster_linearize.h.

◆ FeeRate() [2/3]

template<typename SetType >

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

inlinenoexcept

Get the feerate of a given transaction i.

Complexity: O(1).

Definition at line 120 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ FeeRate() [3/3]

template<typename SetType >

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

inlinenoexcept

Get the mutable feerate of a given transaction i.

Complexity: O(1).

Definition at line 122 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).

Complexity: O(ret.Count()).

Definition at line 288 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GetConnectedComponent()

template<typename SetType >

SetType cluster_linearize::DepGraph< SetType >::GetConnectedComponent	(	const SetType &	todo,
		DepGraphIndex	tx
	)		const

inlinenoexcept

Get the connected component within the subset "todo" that contains tx (which must be in todo).

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 263 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GetReducedChildren()

template<typename SetType >

SetType cluster_linearize::DepGraph< SetType >::GetReducedChildren ( DepGraphIndex i ) const

inlinenoexcept

Compute the (reduced) set of children of node i in this graph.

This returns the minimal subset of the children of i whose descendants together equal all of i's descendants (unless i is part of a cycle of dependencies). Note that DepGraph does not store the set of children; this information is inferred from the descendant sets.

Complexity: O(N) where N=Descendants(i).Count() (which is bounded by TxCount()).

Definition at line 229 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GetReducedParents()

template<typename SetType >

SetType cluster_linearize::DepGraph< SetType >::GetReducedParents ( DepGraphIndex i ) const

inlinenoexcept

Compute the (reduced) set of parents of node i in this graph.

This returns the minimal subset of the parents of i whose ancestors together equal all of i's ancestors (unless i is part of a cycle of dependencies). Note that DepGraph does not store the set of parents; this information is inferred from the ancestor sets.

Complexity: O(N) where N=Ancestors(i).Count() (which is bounded by TxCount()).

Definition at line 208 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ IsAcyclic()

template<typename SetType >

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

inlinenoexcept

Check if this graph is acyclic.

Definition at line 326 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

inlinenoexcept

Determine if this entire graph is connected.

Complexity: O(TxCount()).

Definition at line 307 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 SetType & subset ) const

inlinenoexcept

Determine if a subset is connected.

Complexity: O(subset.Count()).

Definition at line 298 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

◆ PositionRange()

template<typename SetType >

DepGraphIndex cluster_linearize::DepGraph< SetType >::PositionRange ( ) const

inlinenoexcept

Get the range of positions in this DepGraph.

All entries in Positions() are in [0, PositionRange() - 1].

Definition at line 116 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ Positions()

template<typename SetType >

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

inlinenoexcept

Get the set of transactions positions in use.

Complexity: O(1).

Definition at line 114 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ RemoveTransactions()

template<typename SetType >

void cluster_linearize::DepGraph< SetType >::RemoveTransactions ( const SetType & del )

inlinenoexcept

Remove the specified positions from this DepGraph.

The specified positions will no longer be part of Positions(), and dependencies with them are removed. Note that due to DepGraph only tracking ancestors/descendants (and not direct dependencies), if a parent is removed while a grandparent remains, the grandparent will remain an ancestor.

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

Definition at line 157 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ 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 118 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 > &	a,
		const DepGraph< SetType > &	b
	)

friend

Equality operator (primarily for testing purposes).

Definition at line 57 of file cluster_linearize.h.

Member Data Documentation

◆ entries

template<typename SetType >

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

private

Data for each transaction.

Definition at line 50 of file cluster_linearize.h.

◆ m_used

template<typename SetType >

SetType cluster_linearize::DepGraph< SetType >::m_used

private

Which positions are used.

Definition at line 53 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

Constructor & Destructor Documentation

◆ DepGraph() [1/4]

◆ DepGraph() [2/4]

◆ DepGraph() [3/4]

◆ DepGraph() [4/4]

Member Function Documentation

◆ AddDependencies()

◆ AddTransaction()

◆ Ancestors()

◆ AppendTopo()

◆ Descendants()

◆ FeeRate() [1/3]

◆ FeeRate() [2/3]

◆ FeeRate() [3/3]

◆ FindConnectedComponent()

◆ GetConnectedComponent()

◆ GetReducedChildren()

◆ GetReducedParents()

◆ IsAcyclic()

◆ IsConnected() [1/2]

◆ IsConnected() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ PositionRange()

◆ Positions()

◆ RemoveTransactions()

◆ TxCount()

Friends And Related Function Documentation

◆ operator==

Member Data Documentation

◆ entries

◆ m_used