0

I have a problem about graphs.

In my API , I need to check if a list which contains relations between objects IDs has a circle before it is saved in the database.

The information that is gives to me is something like this below:

[
{10, 2},
{20, 32},
{45, 90}
]

As a result , I need to check either the form of the relationship and cycle or not.

Example:

If I have
[{1, 6}, {3, 1}, {3, 4}, {4, 3}, {5, 2}, {5, 3}, {5, 4}, {6, 4}, {6, 5}]
there will be 2 circles:

  • The first will be 3 → 4 → 3 and
  • the second will be 6 → 4 → 3 → 1 → 6

Notes:
The language I need to use is C#. The program must be the fastest as possible and I don't have access to the database to create any functions there. Also, I don't need to get all the possible circles.I need just one and it will be enough in order to return either TRUE or FALSE.

Could anyone give me some advice?

Community
  • 1
  • 1
Bruno Locha
  • 1
  • 1
    I think the only way is to build the graph and start to follow all the possible routes (they should be finite). If one route loops back into any "already visited" node, you return false. – Andrei Tătar Feb 01 '21 at 08:31
  • Simplest solution: assume each edge has weight of `-1` (negative one) and run https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm#Finding_negative_cycles. It will yield the output in O(|V| * |E|) which is pretty reasonable. – Zazaeil Feb 01 '21 at 08:40
  • the `asp.net-core` tag seems unrelated at all. btw your have pairs of point but the example circles pointed out are expressed in just single numbers, well it's an inconsistence in concepts. You should make it clearer. I can see how the first circle formed easily but not for the second one. – King King Feb 01 '21 at 10:11

1 Answers1

0

The problem you are mentioning here is simply finding a cycle in a directed graph. You can follow this stack-overflow post on best algorithm for detecting cycles in a directed graph. I think @KurtPeek already gave a very good answer with detailed explanation and sample python code. Consider reading that post and implement it in C#.

biqarboy
  • 852
  • 6
  • 15