基于P站(Poloniex)的广度优先搜索算法来获得任意两种币的兑换价格

币圈的P站是Poloniex，前几年被孙宇晨收购了，它是一个交易所。我很久之前用过Poloniex，当时对其印象并不是很好。

不过，现在我对其好感增加，因为币安买下的coinmarketcap免费的接口就很多限制。

官方文档），这个接口的频率限制是一秒200次，很慷慨了。

https://api.poloniex.com/markets/price

能返回所有交易配对，比如这样的：

[
    {
        "symbol": "BTS_BTC",
        "price": "0.0000000186",
        "time": 1731852313035,
        "dailyChange": "-0.0462",
        "ts": 1731852313054
    },
    {
        "symbol": "DASH_BTC",
        "price": "0.000317",
        "time": 1731848096481,
        "dailyChange": "0.0063",
        "ts": 1731848096489
    },
    ... ...
]

这个JSON返回的结构是一个数组，每个元素是个结构体，也就是一个币价的具体配对信息，我们可以看成是一条边Edge两个顶点Vertice，这样就是一个图结构（带权图 Weighted Graph，权值就是兑换价格），虽然给的是单边，但其实是个双向的，比如USD_BTC得值可以反过来推得BTC到USD的价格。我们可以设计一个算法，从币价A到币价B，可以通过BFS广度优先搜索算法来获取价格。比如有配对A_B、B_C、C_D我们就可以获得A_D的值。

深度优先搜索算法DFS也可以，不过这个算法会返回找到的第一条路径，并不能保证是最短的，最短的确实是最准确的，因为链也长，转换精度就会下降。

当然，可能存在多条路径，最理想的状态是把这些路径都求出来，取个平均啥的，不过这样就得暴力搜索所有的路径了，算法时间复杂度就会比较高。

以下是BFS广度优先算法的代码，Javascript的，可以用于网页前端或者NodeJs后端，甚至是CloudFlare Serverless Worker或者是其它无服务框架：Azure Function、AWS Lambda等。

const fetch = require('node-fetch');

async function getTicker(a, b) {
  try {
    const response = await fetch('https://api.poloniex.com/markets/price');
    const data = await response.json();

    // 创建一个哈希表来存储代币对及其价格
    const pairMap = new Map();

    // 使用直接对及其反向对填充哈希表
    for (const { symbol, price } of data) {
      const [base, quote] = symbol.split('_').map(token => token.toLowerCase());
      if (!pairMap.has(base)) pairMap.set(base, new Map());
      if (!pairMap.has(quote)) pairMap.set(quote, new Map());
      
      pairMap.get(base).set(quote, parseFloat(price));
      pairMap.get(quote).set(base, 1 / parseFloat(price)); // 添加反向边
    }

    // 将 token 转换为小写
    a = a.toLowerCase();
    b = b.toLowerCase();

    // BFS 查找从 a 到 b 的转换率
    const queue = [[a, 1]]; // 从初始代币和兑换率 1 开始
    const visited = new Set([a]);

    while (queue.length > 0) {
      const [currentToken, currentRate] = queue.shift();

      if (currentToken === b) return currentRate;

      // Check connected tokens
      for (const [nextToken, rate] of (pairMap.get(currentToken) || new Map())) {
        if (!visited.has(nextToken)) {
          visited.add(nextToken);
          queue.push([nextToken, currentRate * rate]);
        }
      }
    }

    // 如果未找到路径，则返回 null
    return null;
  } catch (error) {
    console.error("获取或处理数据时出错:", error);
    return null;
  }
}

// Example usage:
(async () => {
  const rate = await getTicker('btc', 'trx');
  console.log('BTC 到 TRX 的兑换率:', rate);
})();

代码的一些简单说明：

• API 数据提取：从 P站 API 提取数据并将响应解析为 JSON。
• 映射对：以每个代币作为键创建一个映射，其中值是它可以直接转换为的另一个代币映射，以及兑换率。
• 双向映射：通过反转反向转换的价格来存储直接对和反向对。
• 广度优先搜索：使用队列遍历从 a 到 b 的路径。对于每个代币，都会检查其邻居（可转换代币）。如果找到 b，该函数将返回累积率；如果没有，则继续，直到所有选项都用尽。
• 处理无路径：如果未找到转换路径，则函数返回 null。

如果有多组兑换，我们可以改成传入一个数组，这样就不用多次调用P站的API了。

const fetch = require('node-fetch');

async function getToken(pairs) {
  try {
    const response = await fetch('https://api.poloniex.com/markets/price');
    const data = await response.json();

    // 创建一个哈希表来存储代币对及其价格
    const pairMap = new Map();

    // 使用直接对及其反向对填充哈希表
    for (const { symbol, price } of data) {
      const [base, quote] = symbol.split('_').map(token => token.toLowerCase());
      if (!pairMap.has(base)) pairMap.set(base, new Map());
      if (!pairMap.has(quote)) pairMap.set(quote, new Map());
      
      pairMap.get(base).set(quote, parseFloat(price));
      pairMap.get(quote).set(base, 1 / parseFloat(price)); // 添加一条反向边
    }

    // 使用 BFS 查找单个对的转换率的辅助函数
    const findConversionRate = (a, b) => {
      a = a.toLowerCase();
      b = b.toLowerCase();
      
      if (a === b) return 1; // 直接转换

      const queue = [[a, 1]];
      const visited = new Set([a]);

      while (queue.length > 0) {
        const [currentToken, currentRate] = queue.shift(); // 出队列

        if (currentToken === b) return currentRate;

        for (const [nextToken, rate] of (pairMap.get(currentToken) || new Map())) {
          if (!visited.has(nextToken)) {
            visited.add(nextToken);
            queue.push([nextToken, currentRate * rate]);
          }
        }
      }

      return null; // 路径没找到
    };

    // 迭代列表并查找转换率
    const results = pairs.map(([a, b]) => findConversionRate(a, b));
    return results;
  } catch (error) {
    console.error("Error fetching or processing data:", error);
    return pairs.map(() => null); // 如果有错误，则返回每对的 null
  }
}

// Example usage:
(async () => {
  const conversionRates = await getToken([['btc', 'trx'], ['usd', 'steem']]);
  console.log('兑换结果：', conversionRates);
})();

简单的代码说明：

• 参数更新：getToken 现在接受成对的元组数组，其中每个元组代表一对 [a, b]。
• 辅助函数：findConversionRate 处理每对的转换，实现与以前相同的 BFS 方法。
• 映射每对：函数迭代数组里的每个配对币，应用 findConversionRate 计算转换率，并将结果存储在数组中。
• 错误处理：如果出现 API 或处理错误，则返回一个空值数组，与输入数组的长度匹配。

这个修改后的函数现在可以接受一个数组，并在一次Poloniex API调用中返回数组里每个配对的兑换率。

英文：Crypto Token Exchange Rate Computation Based on Breadth First Search Algorithm on Poloniex API

区块链技术

• 编程: NodeJs/Javascript 函数检查Tron/波场区块链上的交易是否已确认(TronGrid API)
• 波场TRX和火币HTX可能是下一个百倍币
• 诈骗者正在利用多重签名钱包(Tron/波场): 保持警惕!
• 简介: 区块链DeFi交易中的无常损失/Impermanent Loss
• 基于P站(Poloniex)的广度优先搜索算法来获得任意两种币的兑换价格
• 加密货币只是区块链的冰山一角
• 警惕区块链上的小额诈骗转帐
• 区块链: 硬分叉与软分叉
• 区块链中Layer 1和Layer 2协议的简介
• 孙老板/师卖在区块链上卖沙子 (营销/沙币/孙哥/ICO)
• 和媳妇聊聊 区块链 (Web3.0, 还有共识算法 PoW, PoS, DPoS)
• 我玩区块链虚拟货币的原则
• SteemIt 就可以把图片也存在区块链上了
• Steem转波场U的信任问题(Steem/SBD to USDT TRC-20)

Crypto虚拟货币交易所

• 你试过转帐金额和身份证信息填反么？我试过, 不过HTX交易所还我钱了
• 交易所退币: 为啥要原路退回, 不能直接充到交易所帐号上么?
• 浅谈虚拟货币交易所三角套利的算法
• 通过程序来减少到交易所转帐出错的可能
• 帐号被Wirex解封的经历
• Steem转波场U的信任问题(Steem/SBD to USDT TRC-20)
• 通过在Wirex X 账户上质押代币(USDT 等)赚取被动收入
• 订单簿简介(Order Book)+最简单的高频交易策略HFT(低买高卖)
• Coinbase 支持 比特币现金 BCH的交易了!
• 基于P站(Poloniex)的广度优先搜索算法来获得任意两种币的兑换价格

交易所跑路啦

• 交易所Ionomy跑路, 又丢了好多币, 哎
• Bittrex Global交易所即将关门大吉-请把币都转走-把价值不到7美元的BTC提现全过程
• 币放在 BitAsset 交易所里拿不出来