Documentation
¶
Overview ¶
Package simplepath provides an implementation of paths. Finder that performs a breadth first search for paths against a stellar-core's database.
The core algorithm works as follows:
- `search` object contains a queue of currently extended paths. Queue is initialized with a single-asset path containing destination asset. Paths are linked lists, head of the path is a newly extended source asset, tail of the path is always the destination asset.
- Every iteration of search does the following: - pops a path from the queue, - checks if the path starts with a source asset, if it does, it appends the path to results, - finds all assets connected to the head of the current path and prepends the path, calculating the current cost.
Algorithm ends when there is no more paths to extend (len(queue) = 0) or `maxResults` has been reached.
The actual calculation of the cost is happening in `pathNode.Cost()` method. There are a couple of important things to note: 1. We are given `DestinationAmount` and the destination asset is the tail of the list. So we need to start from the end of the path and continue to the front. 2. Because we are going from the tail to the head of the path, given the path A -> B -> C. we are interested in finding:
- amount of B needed to buy `DestinationAmount` of C,
- amount of A needed to by above amount of B.
3. Finally, the actual path payment will sell A, buy B, sell B, buy C. So we need to check the following orderbooks:
- sell C, buy B (the user will sell B, buy C),
- sell B, buy A (the user will sell A, buy B).
The algorithm works as follows:
- Because the head of the path is source account, we build a stack of assets to reverse that order.
- We start with the last asset (pop the stack), calculate it's cost (if not cached) and continue towards the source asset (bottom of the stack).
- We return the final cost.
Index ¶
Constants ¶
const (
// MaxInMemoryPathLength is the maximum path length which can be queried by the InMemoryFinder
MaxInMemoryPathLength = 5
)
const MaxPathLength uint = 7
MaxPathLength is a maximum path length as defined in XDR file (includes source and destination assets).
Variables ¶
var ( // ErrEmptyInMemoryOrderBook indicates that the in memory order book is not yet populated ErrEmptyInMemoryOrderBook = errors.New("Empty orderbook") )
var ErrNotEnough = errors.New("not enough depth")
ErrNotEnough represents an error that occurs when pricing a trade on an orderbook. This error occurs when the orderbook cannot fulfill the requested amount.
Functions ¶
This section is empty.
Types ¶
type Finder ¶
Finder implements the paths.Finder interface and searchs for payment paths using a simple breadth first search of the offers table of a stellar-core.
This implementation is not meant to be fast or to provide the lowest costs paths, but rather is meant to be a simple implementation that gives usable paths.
type InMemoryFinder ¶
type InMemoryFinder struct {
// contains filtered or unexported fields
}
InMemoryFinder is an implementation of the path finding interface using the in memory orderbook
func NewInMemoryFinder ¶
func NewInMemoryFinder(graph *orderbook.OrderBookGraph) InMemoryFinder
NewInMemoryFinder constructs a new InMemoryFinder instance
func (InMemoryFinder) FindFixedPaths ¶
func (finder InMemoryFinder) FindFixedPaths( sourceAsset xdr.Asset, amountToSpend xdr.Int64, destinationAssets []xdr.Asset, maxLength uint, ) ([]paths.Path, uint32, error)
FindFixedPaths returns a list of payment paths where the source and destination assets are fixed. All returned payment paths will start by spending `amountToSpend` of `sourceAsset` and will end with some positive balance of `destinationAsset`. `sourceAccountID` is optional. if `sourceAccountID` is provided then no offers created by `sourceAccountID` will be considered when evaluating payment paths
Source Files