ngraph.path icon indicating copy to clipboard operation
ngraph.path copied to clipboard

Possible to get the total path distance from a pathFinder lookup?

Open Sjoerd82 opened this issue 5 years ago • 1 comments

I just started using ngraph, it's pretty good. When I try the "Weighted Graph" example from the Readme, I get the correct paths. But to get the total distance I still need to traverse my dataset to lookup the weight of every path? Or is ngraph able to deliver this as part of the result as well (and if so, how???)

I use it in vue.js (webpack), so the code looks slightly different:

        let graphRoads = createGraph();
        graphRoads.addLink('Hobitton', 'Bywater', {weight: 465});
        graphRoads.addLink('Hobitton', 'Overhill', {weight: 500});
        graphRoads.addLink('Bywater', 'Frogmorton', {weight: 450});
        graphRoads.addLink('Bywater', 'Whitfurrows', {weight: 482});
        let pathFinder = path.aStar(graphRoads, {
            // We tell our pathfinder what should it use as a distance function:
            distance(fromNode, toNode, link) {
                // We don't really care about from/to nodes in this case,
                // as link.data has all needed information:
                return link.data.weight;
            }
        });
        let pathThing = pathFinder.find('Hobitton', 'Frogmorton');
        console.log('pathThing',pathThing)

Returns an array of the three nodes, it takes to get from Hobitton to Frogmorton. There is a "data" key, but it's "undefined":


[
   Node {id: "Frogmorton", links: Array(1), data: undefined
   Node {id: "Bywater", links: Array(3), data: undefined
   Node {id: "Hobitton", links: Array(2), data: undefined
]

Sjoerd82 avatar Oct 12 '20 10:10 Sjoerd82

function findShortestPath(graph, start, end) {
    const pathFinder = npath.aGreedy(graph, {
        distance(fromNode, toNode, link) {
            return link.data.weight;
        }
    });

    const pathResult = pathFinder.find(start, end);
    const shortestPath = pathResult.map(node => node.id.split(',').map(Number));

    let totalLength = 0;
    for (let i = 0; i < pathResult.length - 1; i++) {
        const fromNode = pathResult[i];
        const toNode = pathResult[i + 1];
        const link = graph.getLink(fromNode.id, toNode.id);
        totalLength += link.data.weight;
    }

    return { routelatlon: shortestPath, distance: totalLength };
}

bigsu avatar Aug 09 '23 07:08 bigsu