在自定义数据结构上查找JavaScript中两个节点之间的路径

Question

嗨我有一个连接数组如下：

var connections =[

    {
      "source": "l1",
      "target": "l2"
    },
    {
      "source": "l2",
      "target": "l4"
    },
    {
      "source": "l2",
      "target": "l3"
    },
    {
      "source": "l4",
      "target": "l5"
    },   

]

它继续源和目标。现在想要使用某个函数找到两个节点之间的路径。让我们说函数findConnections("l2", "l5")将返回如下所示的数组

var answer =[

        {
          "source": "l2",
          "target": "l4"
        },
        {
          "source": "l4",
          "target": "l5"
        }, 
]

我不知道我怎么能做到这一点？我尝试过简单的JavaScript但失败了。我认为使用underscore.js或lodash.js我们可以实现这个目标吗？如果有人提供解决方案或给出提示，那将会非常有用吗？

Answer 1

使用递归并走“列表”

function find(list, from, to) {
    // find the current "source" 
    let current = list.find(v => v.source === from);

    if (!current) // no current? u got problems
        throw new Error("No from in list");

    // are we there yet?
    if (current.target === to)
        return current;

    // no we're not ... so keep searching with new "source"
    return [current].concat(find(list, current.target, to));
}

Answer 2

我参加派对有点晚了，但这是一个简单的解决方案：

1. 从给定边构建图形：
2. 使用简单的breadth-first-search来寻找路径

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

const connectNodes = (graph, source, target) => {
  graph.get(source).out.add(target);
  graph.get(target).in.add(source);
};

const buildGraphFromEdges = (edges) => edges.reduce(
  (graph, {source, target}) => {
    if (!graph.has(source)) {
      addNode(graph, source);
    }

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

    connectNodes(graph, source, target);

    return graph;
  },
  new Map()
);

const buildPath = (target, path) => {
  const result = [];

  while (path.has(target)) {
    const source = path.get(target);
    result.push({source, target});
    target = source;
  }

  return result.reverse();
};

const findPath = (source, target, graph) => {
  if (!graph.has(source)) {
    throw new Error('Unknown source.');
  }

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

  const queue = [source];
  const visited = new Set();
  const path = new Map();

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

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

    for (const 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;
};

//  A --* B
//      / | \
//     *  |  *
//    C   |   D --* E
//     \  |  /     *
//      * * *     /
//        F------/

const graph = buildGraphFromEdges([
  { source: 'A', target: 'B' },
  { source: 'B', target: 'C' },
  { source: 'B', target: 'D' },
  { source: 'B', target: 'F' },
  { source: 'C', target: 'F' },
  { source: 'D', target: 'E' },
  { source: 'D', target: 'F' },
  { source: 'F', target: 'E' },
]);

console.log('A -> A', findPath('A', 'A', graph)); // []
console.log('A -> F', findPath('A', 'F', graph)); // [{source: 'A', target: 'B'}, {source: 'B', target: 'F'}]
console.log('A -> E', findPath('A', 'E', graph)); // [{source: 'A', target: 'B'}, {source: 'B', target: 'D'}, {source: 'D', target: 'E'}]
console.log('E -> A', findPath('E', 'A', graph)); // null

请注意，我理解您的输入形成directed graph。相反，如果它是一个无向图，解决方案可以简化一点。

Answer 3

以下将返回JSON对象，如问题中指定的那样。它还将检查两个参数以及它们之间的连接是否存在于JSON中。我将把它留给作者来测试其他边缘情况。

var findConnections = function(json,from,to) {

  // JSON is an unordered structure, so let's compile two arrays for ease of searching
  var sources = [], targets = [];
  for ( node of json ) {
    sources.push(node.source);
    targets.push(node.target);
  }

  // Select each 'from' element from the 'sources' array, get its target...
  for(var i=0;i<sources.length;i++) {
    if( (fromIndex = sources.indexOf(from,i)) < 0 ) { throw new Error('Connection could not be established.'); }
    var fromTarget = targets[fromIndex];

    // ...then look for the connected 'to' in the 'targets' array
    for(var j=0;j<sources.length;j++) {
      if( (toIndex = sources.indexOf(fromTarget,j)) < 0 ) { continue; }

      // If we have a match, compile and return a JSON object. If not, we'll keep looping and if we loop out, an error will be thrown below
      if( targets[toIndex] == to ) {
        return [
                {
                  'source':sources[fromIndex],
                  'target':targets[fromIndex]
                },
                {
                  'source':sources[toIndex],
                  'target':targets[toIndex]                
                }
                ];
      }          
    }
  }

  throw new Error('Connection could not be established.');
}

测试如下：

var answer = findConnections(connections,'l2','l5');
console.log(answer);

Answer 4

我花了太多时间在这上面，我很确定有一个更优雅的解决方案，但我会看看我是否可以添加评论并解释自己。

// Add some more connections. Make some of them out
// of order just for fun
let connections = [{
    source: 'l1',
    target: 'l2'
  },
  {
    source: 'l1',
    target: 'l3'
  },
  {
    source: 'l2',
    target: 'l4'
  },
  {
    source: 'l2',
    target: 'l3'
  },
  {
    source: 'l4',
    target: 'l5'
  },
  {
    source: 'l3',
    target: 'l6'
  },
  {
    source: 'l3',
    target: 'l5'
  },
  {
    source: 'l4',
    target: 'l6'
  }
];

// I just realized that I didn't call this
// function what you wanted it called but
// it should be fine

let answers = findPaths(connections, 'l1', 'l5');
console.log(JSON.stringify(answers, null, 2));

function findPaths(connections, start, end) {
  // first, build a tree, for loads of connections,
  // this is probably slow as hell
  let tree = buildTree(
    connections,
    findConnection(connections, start),
    null
  );
  
  // make the tree into all the different paths
  // also probably slow as hell. Could prune the
  // tree if I could figure out how to implement
  // a backtracking algoritm in javascript but 
  // I couldn't figure it out from the wikipedia
  // article so I skipped it
  let allPaths = buildPaths(tree, []);
  
  // pare down the paths to ones that fit the start
  // and end points
  let goodPaths = verifyPaths(allPaths, start, end);
  
  // reformat that thing to match what you wanted
  return format(goodPaths);
}

// so this thing just runs through the connections
// array and returns an array of elements where the
// source property matches the source argument
function findConnection(connections, source) {
  return connections.filter(conn => conn.source === source);
}

// So this returns an array that contains a tree
// Probably a better way to do this, but...
function buildTree(connections, nodes, parent) {
  // for each node...
  return nodes.map(node => {
    // had to cheat here, just add the node's parent
    // to the node. That way, we don't have to think
    // about it later
    node.parent = parent;
    
    // find any other connections whose source property
    // matches our target property.
    node.path = findConnection(connections, node.target);
    
    // if some were found, then...
    if (node.path && node.path.length > 0) {
      // build that sub-tree. Here, I cheated big-time
      // and made the third param (parent) an object
      // that had the properties I wanted later.
      // It's just easier.
      buildTree(connections, node.path, {
        source: node.source,
        target: node.target,
        parent: node.parent
      });
    }
    // done slapping this around, return it
    return node;
  });
}

// so this is a part could be better. Probably could be
// replaced by Array.reduce, but I'm too lazy. This
// turns the "tree" into an array of all of the paths
// from beginning to end. Many of the paths will be 
// filtered out later so it could be made more efficient
function buildPaths(tree, prev) {
  tree.forEach(step => {
    if (step.path.length > 0) {
      buildPaths(step.path, prev);
    } else {
      prev.push(step);
    }
  });
  return prev;
}

// filter out the paths that don't match the specified
// start and end. We should have good paths now...in
// the wrong format, but we'll fix that up later...
function verifyPaths(paths, start, end) {
  return paths.filter(path => path.target === end).filter(path => {
    while (path.parent) {
      path = path.parent;
    }
    return path.source == start;
  });
}

// alright, go ahead and flatten out the good paths
// into the requested format
function format(arr) {
  return arr.map(el => {
    let temp = [];
    temp.unshift({
      source: el.source,
      target: el.target
    });
    while (el.parent) {
      el = el.parent;
      temp.unshift({
        source: el.source,
        target: el.target
      });
    }
    return temp;
  });
}