[#TxGraph]
= TxGraph
:mrdocs:

Data structure to encapsulate fees, sizes, and dependencies for a set of transactions&period;

== Synopsis

Declared in `&lt;txgraph&period;h&gt;`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
class TxGraph;
----

== Description

Each TxGraph represents one or two such graphs (&quot;main&quot;, and optionally &quot;staging&quot;), to allow for working with batches of changes that may still be discarded&period;

The connected components within each transaction graph are called clusters&colon; whenever one transaction is reachable from another, through any sequence of is&hyphen;parent&hyphen;of or is&hyphen;child&hyphen;of relations, they belong to the same cluster (so clusters include parents, children, but also grandparents, siblings, cousins twice removed, &period;&period;&period;)&period;

For each graph, TxGraph implicitly defines an associated total ordering on its transactions (its linearization) that respects topology (parents go before their children), aiming for it to be close to the optimal order those transactions should be mined in if the goal is fee maximization, though this is a best effort only, not a strong guarantee&period;

For more explanation, see https&colon;&sol;&sol;delvingbitcoin&period;org&sol;t&sol;introduction&hyphen;to&hyphen;cluster&hyphen;linearization&sol;1032

This linearization is partitioned into chunks&colon; groups of transactions that according to this order would be mined together&period; Each chunk consists of the highest&hyphen;feerate prefix of what remains of the linearization after removing previous chunks&period; TxGraph guarantees that the maintained linearization always results in chunks consisting of transactions that are connected&period; A chunk&apos;s transactions always belong to the same cluster&period;

The interface is designed to accommodate an implementation that only stores the transitive closure of dependencies, so if B spends C, it does not distinguish between &quot;A spending B&quot; and &quot;A spending both B and C&quot;&period;

== Types

[cols="1,4"]
|===
| Name| Description
| xref:TxGraph/BlockBuilder.adoc[`BlockBuilder`] 
| Interface returned by GetBlockBuilder&period;
| xref:TxGraph/Ref.adoc[`Ref`] 
| Data type used to reference transactions within a TxGraph&period;
|===


== Type Aliases

[cols="1,4"]
|===
| Name| Description
| xref:TxGraph/GraphIndex.adoc[`GraphIndex`] 
| Internal identifier for a transaction within a TxGraph&period;
|===


== Enums

[cols="1,4"]
|===
| Name| Description
| xref:TxGraph/Level.adoc[`Level`] 
| Selects which of the graphs (main or staging) an operation applies to&period;
|===


== Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:TxGraph/2destructor.adoc[`&#126;TxGraph`] [.small]#[destructor]# [.small]#[virtual]#
| Virtual destructor, so inheriting is safe&period;
| xref:TxGraph/AbortStaging.adoc[`AbortStaging`]  [.small]#[virtual]#
| Discard the existing active staging graph (which must exist)&period;
| xref:TxGraph/AddDependency.adoc[`AddDependency`]  [.small]#[virtual]#
| Add a dependency between two specified transactions&period; If a staging graph exists, the dependency is only added there&period; Parent may not be a descendant of child already (but may be an ancestor of it already, in which case this is a no&hyphen;op)&period; If either transaction is already removed, this is a no&hyphen;op&period;
| xref:TxGraph/AddTransaction.adoc[`AddTransaction`]  [.small]#[virtual]#
| Initialize arg (which must be an empty Ref) to refer to a new transaction in this graph with the specified feerate&period;
| xref:TxGraph/CommitStaging.adoc[`CommitStaging`]  [.small]#[virtual]#
| Replace the main graph with the staging graph (which must exist)&period;
| xref:TxGraph/CompareMainOrder.adoc[`CompareMainOrder`]  [.small]#[virtual]#
| Compare two transactions according to their order in the main graph&period; Both transactions must be in the main graph&period; The main graph must not be oversized&period;
| xref:TxGraph/CountDistinctClusters.adoc[`CountDistinctClusters`]  [.small]#[virtual]#
| Count the number of distinct clusters that the specified transactions belong to&period; Refs that do not exist in the queried graph are ignored&period; Refs can not be null&period; The queried graph must not be oversized&period;
| xref:TxGraph/DoWork.adoc[`DoWork`]  [.small]#[virtual]#
| TxGraph is internally lazy, and will not compute many things until they are needed&period; Calling DoWork will perform some work now (controlled by max&lowbar;cost) so that future operations are fast, if there is any&period; Returns whether all currently&hyphen;available work is done&period; This can be invoked while oversized, but oversized graphs will be skipped by this call&period;
| xref:TxGraph/Exists.adoc[`Exists`]  [.small]#[virtual]#
| Determine whether arg exists in the graph (i&period;e&period;, was not removed)&period; This is available even for oversized graphs&period;
| xref:TxGraph/GetAncestors.adoc[`GetAncestors`]  [.small]#[virtual]#
| Get pointers to all ancestors of the specified transaction (including the transaction itself), in unspecified order&period; The queried graph must not be oversized&period; Returns &lcub;&rcub; if arg does not exist in the graph&period;
| xref:TxGraph/GetAncestorsUnion.adoc[`GetAncestorsUnion`]  [.small]#[virtual]#
| Like GetAncestors, but return the Refs for all transactions in the union of the provided arguments&apos; ancestors (each transaction is only reported once)&period; Refs that do not exist in the queried graph are ignored&period; Null refs are not allowed&period;
| xref:TxGraph/GetBlockBuilder.adoc[`GetBlockBuilder`]  [.small]#[virtual]#
| Construct a block builder, drawing chunks in order, from the main graph, which cannot be oversized&period; While the returned object exists, no mutators on the main graph are allowed&period; The BlockBuilder object must not outlive the TxGraph it was created with&period;
| xref:TxGraph/GetCluster.adoc[`GetCluster`]  [.small]#[virtual]#
| Get pointers to all transactions in the cluster which arg is in&period; The transactions are returned in graph order&period; The queried graph must not be oversized&period; Returns &lcub;&rcub; if arg does not exist in the queried graph&period;
| xref:TxGraph/GetDescendants.adoc[`GetDescendants`]  [.small]#[virtual]#
| Get pointers to all descendants of the specified transaction (including the transaction itself), in unspecified order&period; The queried graph must not be oversized&period; Returns &lcub;&rcub; if arg does not exist in the graph&period;
| xref:TxGraph/GetDescendantsUnion.adoc[`GetDescendantsUnion`]  [.small]#[virtual]#
| Like GetDescendants, but return the Refs for all transactions in the union of the provided arguments&apos; descendants (each transaction is only reported once)&period; Refs that do not exist in the queried graph are ignored&period; Null refs are not allowed&period;
| xref:TxGraph/GetIndividualFeerate.adoc[`GetIndividualFeerate`]  [.small]#[virtual]#
| Get the individual transaction feerate of transaction arg&period; Returns the empty FeePerWeight if arg does not exist in either main or staging&period; This is available even for oversized graphs&period;
| xref:TxGraph/GetMainChunkFeerate.adoc[`GetMainChunkFeerate`]  [.small]#[virtual]#
| Get the feerate of the chunk which transaction arg is in, in the main graph&period; Returns the empty FeePerWeight if arg does not exist in the main graph&period; The main graph must not be oversized&period;
| xref:TxGraph/GetMainMemoryUsage.adoc[`GetMainMemoryUsage`]  [.small]#[virtual]#
| Get the approximate memory usage for this object, just counting the main graph&period; If a staging graph is present, return a number corresponding to memory usage after AbortStaging() would be called&period; BlockBuilders&apos; memory usage, memory usage of internally queued operations, and memory due to temporary caches, is not included here&period; Can always be called&period;
| xref:TxGraph/GetMainStagingDiagrams.adoc[`GetMainStagingDiagrams`]  [.small]#[virtual]#
| For both main and staging (which must both exist and not be oversized), return the combined respective feerate diagrams, including chunks from all clusters, but excluding clusters that appear identically in both&period; Use FeeFrac rather than FeePerWeight so CompareChunks is usable without type&hyphen;conversion&period;
| xref:TxGraph/GetTransactionCount.adoc[`GetTransactionCount`]  [.small]#[virtual]#
| Get the total number of transactions in the graph&period; This is available even for oversized graphs&period;
| xref:TxGraph/GetWorstMainChunk.adoc[`GetWorstMainChunk`]  [.small]#[virtual]#
| Get the last chunk in the main graph, i&period;e&period;, the last chunk that would be returned by a BlockBuilder created now, together with its feerate&period; The chunk is returned in reverse&hyphen;topological order, so every element is preceded by all its descendants&period; The main graph must not be oversized&period; If the graph is empty, &lcub;&lcub;&rcub;, FeePerWeight&lcub;&rcub;&rcub; is returned&period;
| xref:TxGraph/HaveStaging.adoc[`HaveStaging`]  [.small]#[virtual]#
| Check whether a staging graph exists&period;
| xref:TxGraph/IsOversized.adoc[`IsOversized`]  [.small]#[virtual]#
| Determine whether the graph is oversized (contains a connected component of more than the configured maximum cluster count)&period; Some of the functions below are not available for oversized graphs&period; The mutators above are always available&period; Removing a transaction by destroying its Ref while staging exists will not clear main&apos;s oversizedness until staging is aborted or committed&period;
| xref:TxGraph/RemoveTransaction.adoc[`RemoveTransaction`]  [.small]#[virtual]#
| Remove the specified transaction&period; If a staging graph exists, the removal only happens there&period; This is a no&hyphen;op if the transaction was already removed&period;
| xref:TxGraph/SanityCheck.adoc[`SanityCheck`]  [.small]#[virtual]#
| Perform an internal consistency check on this object&period;
| xref:TxGraph/SetTransactionFee.adoc[`SetTransactionFee`]  [.small]#[virtual]#
| Modify the fee of the specified transaction, in both the main graph and the staging graph if it exists&period; Wherever the transaction does not exist (or was removed), this has no effect&period;
| xref:TxGraph/StartStaging.adoc[`StartStaging`]  [.small]#[virtual]#
| Create a staging graph (which cannot exist already)&period; This acts as if a full copy of the transaction graph is made, upon which further modifications are made&period; This copy can be inspected, and then either discarded, or the main graph can be replaced by it by committing it&period;
| xref:TxGraph/Trim.adoc[`Trim`]  [.small]#[virtual]#
| Remove transactions (including their own descendants) according to a fast but best&hyphen;effort strategy such that the TxGraph&apos;s cluster and size limits are respected&period; Applies to staging if it exists, and to main otherwise&period; Returns the list of all removed transactions in unspecified order&period; This has no effect unless the relevant graph is oversized&period;
|===


== Protected Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:TxGraph/UnlinkRef.adoc[`UnlinkRef`]  [.small]#[virtual]#
| Inform the TxGraph implementation that a TxGraph&colon;&colon;Ref was destroyed&period;
| xref:TxGraph/UpdateRef.adoc[`UpdateRef`]  [.small]#[virtual]#
| Inform the TxGraph implementation that a TxGraph&colon;&colon;Ref has moved&period;
|===


== Protected Static Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:TxGraph/GetRefGraph-0af.adoc[`GetRefGraph`] 
| `GetRefGraph` overloads
| xref:TxGraph/GetRefIndex-06.adoc[`GetRefIndex`] 
| `GetRefIndex` overloads
|===


== Friends

[cols="1,4"]
|===
| Name| Description
| `xref:TxGraph/Ref.adoc[TxGraph::Ref]`
| Data type used to reference transactions within a TxGraph&period;
|===

== Non-Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:MakeTxGraph.adoc[`MakeTxGraph`]
| Construct a new TxGraph with the specified limit on the number of transactions within a cluster, and on the sum of transaction sizes within a cluster&period;
|===


[.small]#Created with https://www.mrdocs.com[MrDocs]#
