1
$\begingroup$

Given a set of uniquely numbered items that each has three attributes id, from and two in the following format,

{id, from, to}

we would like to find all cycles that a particular item participates in.

For example, given the following items

{id:1,  from:h, to:l},
{id:2,  from:b, to:e},
{id:3,  from:p, to:q},
{id:4,  from:e, to:h},
{id:5,  from:e, to:g},
{id:6,  from:l, to:m},
{id:7,  from:m, to:k},
{id:8,  from:k, to:i},
{id:9,  from:g, to:i},
{id:10, from:i, to:b},

we can construct a directed graph

enter image description here

Each item is connected or related to another by the from and to attributes and there can be items that are not related to any others (for example the item with id = 3 in the example above).

The input is the id of an arbitrary item within the array and the output of the algorithm is the list of cycles that each item participates in. For example, based on the image above, examples of the expected output are:

  1. Given the id = 7, the expected result is:

    An array containing this single array (or its equivalent circular linked list). That is, the items connected by the blue line. If the items in the inner array are rotated by N, it's ok.

    output = [
        [
            {id:7,  from:m, to:k},
            {id:8,  from:k, to:i},
            {id:10, from:i, to:b},
            {id:2,  from:b, to:e},
            {id:4,  from:e, to:h},
            {id:1,  from:h, to:l},
            {id:6,  from:l, to:m}
        ]
    ]
    
  2. Given the id = 2, the expected result is:

    An array containing two arrays (or their equivalent circular linked list). That is, the two collections of items connected by the red and the blue line. If the items in the inner arrays are rotated by N, it's ok.

    output = [
        [
            {id:2,  from:b, to:e},
            {id:5,  from:e, to:g},          
            {id:9,  from:g, to:i},
            {id:10, from:i, to:b}
        ],
        [           
            {id:2,  from:b, to:e},
            {id:4,  from:e, to:h},
            {id:1,  from:h, to:l},
            {id:6,  from:l, to:m},
            {id:7,  from:m, to:k},
            {id:8,  from:k, to:i},
            {id:10, from:i, to:b}
        ]
    ]
    

So, the questions is what could be the possible algorithm and data structure to resolve this problem? It's ok to have whatever time/space complexity. Optimizations can be performed later.

$\endgroup$
  • $\begingroup$ Why 10 has two edges to 2? $\endgroup$ – orezvani Jul 7 '16 at 8:19
  • $\begingroup$ The lines between 10´ and 2 are not edges, they indicate cycles within the graph. $\endgroup$ – Jorge E. Hernández Jul 12 '16 at 4:24