Найдите все промежуточные соединения от узла к другому в jsPlumb - PullRequest
Новая
       29

Найдите все промежуточные соединения от узла к другому в jsPlumb

1 голос
/ 28 мая 2020

В jsPlumb я пытаюсь получить полный путь между двумя узлами в виде массива с помощью одного запроса, даже если между источником и местом назначения есть несколько узлов. В настоящее время я делаю это с помощью алгоритма BFS, потому что я не нашел ничего подобного в документации, код: 

getPath: function (sourceId, targetId) {
var me = this;

var addNode = function addNode(graph, node) {
  graph.set(node, {
    in: new Set(),
    out: new Set()
  });
};

var connectNodes = function connectNodes(graph, sourceId, targetId) {
  graph.get(sourceId).out.add(targetId);
  graph.get(targetId).in.add(sourceId);
};

var buildGraphFromEdges = function buildGraphFromEdges(edges) {
  return edges.reduce(function (graph, {
    sourceId,
    targetId
  }) {
    if (!graph.has(sourceId)) {
      addNode(graph, sourceId);
    }

    if (!graph.has(targetId)) {
      addNode(graph, targetId);
    }

    connectNodes(graph, sourceId, targetId);
    return graph;
  }, new Map());
};

var buildPath = function buildPath(targetId, path) {
  var result = [];

  while (path.has(targetId)) {
    var sourceId = path.get(targetId);
    result.push({
      sourceId,
      targetId
    });
    targetId = sourceId;
  }

  return result.reverse();
};

var findPath = function findPath(sourceId, targetId, graph) {
  if (!graph.has(sourceId)) {
    throw new Error('Unknown sourceId.');
  }

  if (!graph.has(targetId)) {
    throw new Error('Unknown targetId.');
  }

  var queue = [sourceId];
  var visited = new Set();
  var path = new Map();

  while (queue.length > 0) {
    var start = queue.shift();

    if (start === targetId) {
      return buildPath(start, path);
    }

    for (var next of graph.get(start).out) {
      if (visited.has(next)) {
        continue;
      }

      if (!queue.includes(next)) {
        path.set(next, start);
        queue.push(next);
      }
    }

    visited.add(start);
  }

  return null;
};

var graph = buildGraphFromEdges(me.jsPlumbContainer.getAllConnections());
var resultPath = findPath(sourceId, targetId, graph);

return resultPath;}

Есть ли лучший способ реализовать это?

пример массив для моей конфигурации: 

var connections =[

{
  "sourceId": "l1",
  "targetId": "l2"
},
{
  "sourceId": "l2",
  "targetId": "l4"
},
{
  "sourceId": "l2",
  "targetId": "l3"
},
{
  "sourceId": "l4",
  "targetId": "l5"
},  ]
...