-2

This is what I am trying to solve. I have a series of numbers like 

    1 -> 2
    2 -> 3
    3 -> 4
    4 -> 2
    2 -> 1

I need to write a program to prove if these numbers are points on a graph they form some kind of loop. In the above example 1 -> 2 -> 3 -> 4 -> 2 form a loop.

In the following example there is no loop.

    1 -> 2
    2 -> 3
    3 -> 4
    3 -> 5

Don't understand how this is a duplicate. Sorry if my question is not clear. I am trying my level best to describe it. I have set of points/numbers/nodes. They are in pair and also they have direction. For example pair of numbers are 1 -> 2 2 -> 3 1 -> 2 3 -> 4 4 -> 2 2 -> 1 3 -> 4

When these individual nodes are connected from top to bottom I will get linked lists as below 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 4 -> 2 -> 1 -> 3 -> 4

I am not looking for a repeated pattern in this set of numbers. trying to find closed loops like 1 -> 2 -> 3 -> 1 is a loop. 2 -> 3 -> 1 -> 2 is a loop. 3 -> 1 -> 2 -> 3, 2 -> 3 -> 4 -> 2, 3 -> 4 -> 2 -> 1 -> 3 etc. in this wiki link there is one loop that is 1 _. 6 -> 3 -> 1 http://upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Functional_graph.svg/240px-Functional_graph.svg.png

Hope this makes the question clear!

Charasala
  • 141
  • 11
  • 1
    Ask questions not programs. – sujeesh Feb 20 '13 at 04:32
  • 2
    Floyd's Cycle-Finding Algorithm is the most efficient. – JP Alioto Feb 20 '13 at 04:45
  • I don't think your question is correctly stated. Do you have a sequence of numbers or number pairs? Are you trying to detect a return to a previously-defined node? In your examples, are you showing indexes in the list and their values, or a set of state-change mappings? – Corey Feb 20 '13 at 05:49
  • I have tried various solutions but they don't make sense to me and I know they fail. So I don't think it is worth sharing any of that code with you. – Charasala Feb 20 '13 at 11:53
  • Thank you @JP Alioto I think I see a light at the end of the tunnel. Will comment here after trying Floyd's Algorithm. – Charasala Feb 20 '13 at 12:01

1 Answers1

2

A very simple way could be adding the two numbers as a key,value pair in a Hashtable:

Once you are in a situation where the key already exists error is thrown or ContainsValue condition is true , you have found a cycle.

Igoy
  • 2,942
  • 22
  • 23
  • This won't work. if I have pairs 1 -> 2, 3 -> 4 and 1 -> 5 key 1 is repeated and will throw exception but this is not forming a loop/cycle. – Charasala Feb 20 '13 at 20:23