How can I retrieve the number of links pointing to a specific property within a JavaScript object

Question

How can I retrieve the number of links pointing to a specific property within a JavaScript object

I am faced with the following dataset:

const main = 'test1';
const data = [
  {
    from: 'test1',
    to: 'test2'
  },
  {
    from: 'test2',
    to: 'test3'
  },
  {
    from: 'test3',
    to: 'test4'
  },
  {
    from: 'test4',
    to: 'test2'
  },
  {
    from: 'test1',
    to: 'test4'
  }
];

My goal is to determine the number of connections to the main node (in this case test1). For instance, if we consider node test3, it requires 2 links to reach test1:

test3 → test2 → test1

The same applies to node test2, where only 1 link is needed to arrive at test1.

What would be the most efficient approach to calculate this? Ultimately, I aim to find the longest chain of connections leading to test1. In this particular example, it amounts to 3:

test3 → test2 → test4 → test1

javascript arrays json graph-algorithm

Answer 1

Answer №1

To cover all possible paths, one must explore each one individually. However, if a loop is encountered and the desired destination can still be reached, then the longest distance becomes infinite because one can circle through the loop indefinitely.

An efficient way to explore all paths is by using a recursive function like this:

function find(data, sourceName, targetName) {
    // Create a data structure mapping nodes by their names
    const map = new Map(data.map(({from}) => [from, []]));
    data.forEach(({from,to}) => map.get(from).push(map.get(to)));
    
    // If traversing both directions is allowed (undirected links), uncomment the following line:
    // data.forEach(({from,to}) => map.get(to).push(map.get(from)));

    const target = map.get(targetName);
    
    // Recursive function definition
    function recur(node) {
        if (node === target) return 0; // Found target
        if (node.visited) { // Detect and handle cycles during backtracking 
            node.onCycle = true;
            return -Infinity;
        }

        node.visited = true;
        let dist = 1 + Math.max(...node.map(recur)); // Maximize path length
        node.visited = false;

        // Exclude if longest path should not include cycles
        if (node.onCycle && dist > 0) return Infinity; // Solution path may contain cycles

        return dist;
    }
    
    const dist = recur(map.get(sourceName)); // Begin search!
    
    return dist < 0 ? null : dist; // Return null when target cannot be reached
}

const data = [{from: 'test1', to: 'test2'},{from: 'test2', to: 'test3'},{from: 'test3',to: 'test4'},{from: 'test4',to: 'test2'},{from: 'test1',to:'test4'}];
const longestDist = find(data, 'test1', 'test3');
console.log(longestDist);

Note that this code does not continue searching beyond the target node while trying to reach it again from there (via a cycle). It assumes a path can only have the target as its last node once, not multiple times.

If you prefer to exclude paths with cycles, delete the line returning Infinity for distance.

This implementation assumes directed links. If links are bi-directional (undirected), where specifying one direction implies the opposite direction without explicitly defining it, uncomment the second forEach line in the provided code snippet.

Answer 2

To cover all possible paths, one must explore each one individually. However, if a loop is encountered and the desired destination can still be reached, then the longest distance becomes infinite because one can circle through the loop indefinitely.

An efficient way to explore all paths is by using a recursive function like this:

function find(data, sourceName, targetName) {
    // Create a data structure mapping nodes by their names
    const map = new Map(data.map(({from}) => [from, []]));
    data.forEach(({from,to}) => map.get(from).push(map.get(to)));
    
    // If traversing both directions is allowed (undirected links), uncomment the following line:
    // data.forEach(({from,to}) => map.get(to).push(map.get(from)));

    const target = map.get(targetName);
    
    // Recursive function definition
    function recur(node) {
        if (node === target) return 0; // Found target
        if (node.visited) { // Detect and handle cycles during backtracking 
            node.onCycle = true;
            return -Infinity;
        }

        node.visited = true;
        let dist = 1 + Math.max(...node.map(recur)); // Maximize path length
        node.visited = false;

        // Exclude if longest path should not include cycles
        if (node.onCycle && dist > 0) return Infinity; // Solution path may contain cycles

        return dist;
    }
    
    const dist = recur(map.get(sourceName)); // Begin search!
    
    return dist < 0 ? null : dist; // Return null when target cannot be reached
}

const data = [{from: 'test1', to: 'test2'},{from: 'test2', to: 'test3'},{from: 'test3',to: 'test4'},{from: 'test4',to: 'test2'},{from: 'test1',to:'test4'}];
const longestDist = find(data, 'test1', 'test3');
console.log(longestDist);

Note that this code does not continue searching beyond the target node while trying to reach it again from there (via a cycle). It assumes a path can only have the target as its last node once, not multiple times.

If you prefer to exclude paths with cycles, delete the line returning Infinity for distance.

This implementation assumes directed links. If links are bi-directional (undirected), where specifying one direction implies the opposite direction without explicitly defining it, uncomment the second forEach line in the provided code snippet.

Answer 3

Answer №2

In the realm of graph theory, your query can be reframed as follows: Each "test1", "test2",... represents a vertex, while the data array stores edges connecting these vertices (in pairs of "from-to"). Thus, we have a graph - and determining the longest path within this graph poses a challenge known as an NP-hard problem (link to wiki). To pinpoint the longest path, one must explore all potential routes meticulously.

Answer 4

In the realm of graph theory, your query can be reframed as follows: Each "test1", "test2",... represents a vertex, while the data array stores edges connecting these vertices (in pairs of "from-to"). Thus, we have a graph - and determining the longest path within this graph poses a challenge known as an NP-hard problem (link to wiki). To pinpoint the longest path, one must explore all potential routes meticulously.

How can I retrieve the number of links pointing to a specific property within a JavaScript object

Answer №1

Answer №2

Similar questions

Unable to delete data in Laravel 8

What steps can be taken to ensure that any new elements generated by JavaScript do not disappear upon refreshing the page

A step-by-step guide on disabling Google Analytics in a Next.js document.js file

Struggling to showcase array data in a visually appealing table format?

What is the process for utilizing jQuery's advanced ticker feature to extract content from a text file?

Discovering escape characters while iterating through a string in javascript

Tips on deleting information from an object by utilizing Chrome storage mechanisms

Attempting to send JSX as a prop value

Unusual behavior involving the selection of $stateParams

Employing live labels on a Morris Bar Chart

Combine the values in the array with the input

Unlocking the Chrome performance tool summary using SeleniumDiscovering the Chrome performance tool

Guide to placing an image in a designated position

Tips for maintaining the functionality of IFrame?

Tips to prevent browser from freezing while creating a large number of HTML elements

Determine the available time slots for reserving a resource

The search results fail to show the required information

Sending JavaScript array to PHP server-side script

import a function from jQuery that has been defined in an external JavaScript file

NodeJS guide: Enabling cross-domain access for web services