• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Tim Cooke
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Frank Carver
  • Henry Wong
  • Ron McLeod
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Himai Minh

Cycle detection in directed graph

 
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
am working on some project where i have to rename an entity. This implies saving a new object containing the old and the new name of the entity. This is how the soft works.

Now, what i have to do is check if a circular dependency is attempted when someone tries to rename an object. For example:



When someone tries to rename C into A, this should be signaled.

I am not sure how to approach this problem. My thought was to create a directed graph having the edges[A, B], [B, C], [C, A] and the apply some cycle detecting algorithms to find the circular dependencies (Tarjan or something).

Would that be efficient considering that the graph will not be connected? It is possible to have the aforementioned example and then:



I have come up with the following dfs approach:


and calling it like this:


And it successfully finds the connected components, but does not recognize any cycle, only if i remove the G[root][i] condition, that would be the first cycle from 0 to 0. What am i missing?
 
Marshal
Posts: 27364
88
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sure, creating a directed graph and checking for cycles sounds like a good idea to me.

Efficiency? I can't comment on that because I don't know how fast you need this operation to run, I don't know how long it will take to run in your environment, and I don't know what alternatives exist.

As for your code: You seem to be concerned about finding the connected components of that directed graph, but I don't see what that has to do with finding cycles in the graph. So your code which looks for connected components (if that's what it is) looks irrelevant to me. If I were doing that I would just get somebody else's working code for finding cycles rather than trying to write it myself.
 
A Misa
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I already have a piece of working code, but it uses an adjacecny matrix and the algorithm is a bit different. Graphs are not my strongest skill, but am i right to think it would be space comsuming to mantain a huge adjacency matrix(i might have thousands of nodes according to my model)?
 
Screaming fools! It's nothing more than a tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic