trees
- components
- nodes
- branches (binary trees have 2, others have n)
graphs
- components
- nodes
- edges (branches)
difference between traversing graphs vs trees
- because bi-directional (undirected) graphs can go backwards, we can have cycles
- to avoid cycles, we need to keep track of where we've been
- one way to do this is tracking visitation (where we've been)
- with an object/hashmap/set we get constant-time look-up w/ object or set datatype/structure
- one way to do this is tracking visitation (where we've been)
- adjacency (neighbors) list
// object/hashmap-like representation
{
0 => [1, 4],
1 => [0, 4, 3, 2],
2 => [1, 3],
3 => [4, 1, 2],
4 => [0, 1, 3],
}
// can also be an array (if nodes are integers)
// the indices are the same as the keys in the object above. right?
[
[1, 4], // index 0 is same as key 0
[0, 4, 3, 2],
[1, 3],
[4, 1, 2],
[0, 1, 3],
]- edge list (neighbors represented by pairs)
- if we see (, 1) and (1, 0) this means we have an "undirected" (bi-directional) graph because we can go backwards
[
(0, 1),
(0, 4),
(4, 0),
(1, 2),
(2, 1),
(1, 3),
(3, 4),
(2, 3),
...
]- adjacency matrix (represent edges that exist in a graph)
- 1D matrix/3D matrix
- an array of arrays
- benefit of using adj matrix is we can represent edges with WEIGHTS
0 1 2 3 4
----------------
0 | 1
|
1 | 1
|
2 |
|
3 |
|
4 |
- weights can represent other metrics used to compute some score
- how scenic
- how much time
- how well-paved
- edges
San Francisco (root/starting point)
/ | \
/ | \
101 280 1
RENO
Ethereum has a concept of a "token". Tokens are "smart contracts" on Ethereum (similar to instances of classes) that implement a particular interface called ERC20.
Uniswap allows users to swap any such tokens with a smart contract called a "pair". There are many pairs on Uniswap, each consisting of two tokens.
A user can trade one token for another directly with a pair, but sometimes a direct pairing does not exist or the best price is achieved by trading across multiple pairs. In these cases, users can trade across multiple pairs. For example, a user may wish to sell Ether for DAI. The best price may exist by selling Ether for USDC, and then USDC for DAI (i.e. Ether -> USDC -> DAI).
The list of pairs through which you swap is called a Route.
Compute the best route given the amount to sell amountIn, the token to buy tokenOut, and a list of available pairs pairs.
[execution time limit] 4 seconds (js)
interface TokenAmount {
// the token of the amount, e.g. 'ETH' or 'BTC' or 'USD'
toke: string;
// the amount, e.g. 1.5 ETH
amount: number;
}
interface Pair {
// the tokens of the pair, e.g. 'ETH' or 'BTC' or 'USD'
tokenA: string;
tokenB: string;
// Returns the amount of a token received for a given input amount
// If the pair does not accept the token as input, it throws an error
quote(amountIn: TokenAmount): TokenAmount;
}
interface Route {
path: Pair[]; // [(Pair { a: TokenAmount { token: btc, amount: 3100 }, b: eth }, Pair{ a: eth, b: sol }]
}
// return the shortest path
function bestRoute(amountIn, tokenOut, pairs) {
// pairs (edge list)
// 1. converting edge list -> adjacency list
// 2. using DFS or BFS -> generate all possible routes
// 3. of those routes, select the shortest one (return shortest array [in length])
}
Let's say we want to go from BTC -> SOL
We are given an edge list (pairs) and they represent that we can perform direct swaps between two tokens:
[
(BTC, ETH),
(BTC, USDC),
(ETH, BTC),
(ETH, USDC),
(ETH, SOL),
(SOL, ETH),
(SOL, ETH),
]
It's challenging to construct routes from this representation, so we want to convert it to an adjacency list:
{
ETH : [BTC, USD, SOL]
BTC : [USD, ETH],
SOL : [ETH],
USD : [BTC]
}
We want to produce routes in an array (which is ordered). Let's say we want to go from BTC to SOL:
[BTC, ETH, SOL]
To find the shortest path or (minimum number of swaps), we just have to try all possibilities by producing every route possible...
// best route represents the MINIMUM number of swaps needed to go from one token to another
function bestRoute(amountIn, tokenOut, pairs) {
// 1. turn pairs (edge list) into adjacency list for traversal
const tokenGraph = buildAdjacencyList(pairs)
// 2. use DFS to construct routes and return shortest one
function dfs(token, route) {
if (token in visited) return // exit (stop traversal)
// terminate traversal if we've arrived at our destination (target token)
if (token === tokenOut) {
// add this token to the route
route.append(token)
// replace current `shortestRoute` with this if shorter (better)
if (route.length < shortestRoute.length) {
shortestRoute = route
}
// exit (stop traversal)
return
}
// visit each neighbor and it's neighbors
tokenGraph[token].forEach((neighborToken) => dfs(neighborToken, route))
// NOTE:remove the last token/node added to our route/path when we "backtrack"
// - this is very important otherwise we end up just appending every token/node to our route/path
// - think about computing shortest paths, if we decide that we made a wrong turn, we don't want to count that segment, so we exclude it (backtrack), by removing it
route.pop()
}
// 3. produce best route (shortest path)
const shortestRoute = Infinity;
const visited = set()
// - if we're just given source (starting) token and amount of it we have, we start there
// - the second argument is an empty array representing our "route" or path
// - all the work is done by our DFS (NOTE: BFS would work, too)
dfs(amountIn[token], [])
return shortestRoute
}
function buildAdjacencyList(edgeList) {
const adjList = {}
pairs.forEach((pair) => {
if (pair.TokenA in adjList) { // if key exists, just add
adjList[pair.tokenA].push(pair.tokenB)
} else { // if key doesn't exist, create an array with tokenB
adjList[pair.tokenA] = [pair.tokenB]
}
})
return adjList
}